What makes the problem of non convex optimization hard?

What makes the problem of non convex optimization hard?

Non-Convex Problems •Anything that’s not convex What makes non-convex optimization hard? •Potentially many local minima •Saddle points •Very flat regions •Widely varying curvature Source: https://commons.wikimedia.org/wiki/File:Saddle_point.svg But is it actually that hard? •Yes, non-convex optimization is at least NP-hard

How does nonconvex optimization meet low rank factorization?

Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview. Abstract: Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due

When is non convex optimization lecture 7 Fall 2017?

Non-Convex Optimization CS6787 Lecture 7—Fall 2017 First some words about grading •I sent out a bunch of grades on the course management system •Everyone should have all their grades in •Not including paper review #6 •If you submitted something and it’s not on CMS, send me an email Also some reminders about the reviews

Are there any nonconvex algorithms for matrix factorization?

While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently.

Which is an example of a non convex problem?

Examples of non-convex problems •Matrix completion, principle component analysis •Low-rank models and tensor decomposition •Maximum likelihood estimation with hidden variables •Usually non-convex •The big one: deep neural networks Why are neural networks non-convex? •They’re often made of convex parts! •This by itself would be convex.

What should I do in a non convex optimization lecture?

•Also, be sure to do at least: 1. Summarize the paper 2. Discuss the paper’s strengths andweaknesses 3. Discuss the paper’s impact. Non-Convex Optimization CS6787 Lecture 7—Fall 2017 Review —We’ve covered many methods •Stochastic gradient descent •Mini-batching •Momentum •Variance reduction •Nice convergence proofs that give us a rate

Why do neural nets need to be non-convex?

Why do neural nets need to be non-convex? •Neural networks are universal function approximators •With enough neurons, they can learn to approximate any function arbitrarily well •To do this, they need to be able to approximate non-convex functions •Convex functions can’t approximate non-convex ones well.

Is the update rule the same for non convex functions?

•Local convergence to the global minimum •Global convergence to the global minimum Non-convex Stochastic Gradient Descent Stochastic Gradient Descent •The update rule is the same for non-convex functions •Same intuition of moving in a direction that lowers objective

Can a nonconvex problem have a local minima?

Nonconvex problems can have local minima, i.e., there can exist a feasible xsuch that f(y) \(x) for all feasible ysuch that kx yk 2\ but xis still not globally optimal.

Which is a strong guarantee of assuming convexity?

Assuming convexity provides a couple of strong guarantees: the minimum we find is a global minimum, so we don’t have to say rerun the algorithm with multiple initializations in general strong duality applies, so there is a zero duality gap (I think)