# Average case or beyond worse case analysis for non-convex optimization procedures?

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!

Citations:

(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.