I'm not sure if this is a well-formed question or not, but I thought I would ask to see if anyone is aware of related literature.

It is known that global optimization of non-convex functions is NP-hard in general (1). However, it seems for some large classes of structured non-convex optimization problems e.g.,, matrix factorization (2), there are no spurious local minima (all minima are global, and Fermat's optimality condition is sufficient for global minimality). I believe there are many more examples of this that have recently been proved.

Here are my questions:

  1. What are the known regularity conditions under which we know that indeed non-convex global optimization (or even escaping saddle points to obtain global minima) is possible? References are appreciated.
  2. Are there beyond worse case/smoothed analysis or even average-case results in non-convex optimization that show an algorithm (say for example, the gradient method, or a stochastic/accelerated/noise-perturbed version of it) usually optimizes non-convex functions to epsilon-approximate local/global optimality? Essentially just like the simplex method "usually" takes polynomial time (3), is there an equivalent result available for non-convex optimzation? (Informally, this would show that the hardness is 'concentrated' in 'pathological' functions)
  3. Are there results that show, for example, that 'easy to optimize' non-convex functions are dense in some larger space of non-convex functions? A result like this would show that non-convex functions are 'close' (in some metric put on the space) to easy-to-optimize functions. I'm not sure if this is a well posed question or not, also unsure if it is interesting. The reason this seems like a fruitful question is we have recently seen papers on functions that are 'locally-strongly convex' or 'strongly non-convex' with second derivative matrices (hessians) that are 'approximately' PSD. It seems that this type of result could be extended to a more quantitative description of how many functions are not 'approximately locally convex'/easy-to-optimize.

With all questions listed above, any pointers to key papers/reviews would be extremely appreciated!


(1) Avrim L Blum and Ronald L Rivest. Training a 3-node neural network is NP-complete. Neural Networks, 5(1):117–127, 1992.

(2) Rong Ge, Jason Lee, and Tengyu Ma. Matrix Completion has No Spurious Local Minimum.

(3) Spielman, D. A., & Teng, S.-H. (2004). Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51, 385–463.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.