What situations do we know of where gradient descent can be shown to converge (either to a critical point or to a local/global minima) for non-convex functions?
For SGD on non-convex functions, one kind of proof has been reviewed here, http://www.cs.cornell.edu/courses/cs6787/2017fa/Lecture7.pdf
In this answer I will explore two interesting and relevant papers that were brought up in the comments. Before doing so, I will attempt to formalize the problem and to shed some light on some of the assumptions and definitions. I begin with a 2016 paper by Lee et al.
We seek to minimize a non-convex function $f: \mathbb{R}^d \to \mathbb{R}$ that is bounded below. We require it to be twice differentiable. We use a gradient descent algorithm of the form:
$\pmb{x}_{t+1} = \pmb{x}_t - \alpha\nabla f(\pmb{x}_t)$.
Additionally, we have the following requirement:
$\| \nabla f(\pmb{x}_1)-\nabla f(\pmb{x}_2) \| \leq \ell \| \pmb{x}_1 - \pmb{x}_2 \|, \quad \text{for all } \pmb{x}_1, \pmb{x}_2$.
That is, we require our function to be $\ell$-Lipschitz in its first derivative. In english this translates to the idea that our gradient can not change too rapidly anywhere in the domain. This assumption ensures that we can choose a step-size such that we never end up with steps that diverge.
Recall that a point $\pmb{x}$ is said to be a strict saddle if $\nabla f(\pmb{x}) = 0$ and $\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right) < 0$ and $\lambda_{\max}\left(\nabla^2 f(\pmb{x})\right) > 0$. If all of the eigenvalues of the Hessian have the same sign then the point is a minimum (if they're positive) or a maximum (if they're negative). If there are any 0 eigenvalues then it is said to be degenerate, and it is not a strict saddle.
The paper shows that with the above assumptions, along with the assumption that all saddle points of the function are strict-saddle, gradient descent is guaranteed to converge to a minimum.
The proof is quite technical, but the intuition is this: define a set $W^s(\pmb{x}^s) = \{\pmb{x} : \lim_k g^k(\pmb{x}) = \pmb{x}^s \}$, where $\pmb{x}^s$ is a saddle point. I don't like this notation at all. What they are trying to get at is that $W$ is the set of starting values for which the gradient map $g : \mathbb{R}^d \to \mathbb{R}^d$ sends $\pmb{x}_k$ to $\pmb{x}^s$. Put more plainly, it is the set of random initializations that will ultimately converge to a saddle.
Their argument relies on the Stable Manifold Theorem. With the above assumptions and a bunch of esoteric math they conclude that the set $W^s$ must be measure zero, that is, there is zero probability of randomly initializing on a point that will converge to a saddle point. As we know that gradient descent on functions of the type outlined in the assumptions with suitably small step sizes will eventually reach a critical point, and we now know (almost surely) that it will never land on a saddle, we know that it converges to a minimizer.
The second, more recent paper by Reddi et al. I will discuss in less detail. There are several differences. First, they are no longer working in a deterministic framework, instead opting for the more practically relevant stochastic approximation framework on a finite sum (think Stochastic Gradient Descent). The primary differences there are that the step-size requires some additional care, and the gradient becomes a random variable. Additionally, they relax the assumption that all saddles are strict, and look for a second-order stationary point. That is, a point such that, $ \|\nabla(f) \| \leq \epsilon, \quad \text{and}, \quad \lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\geq -\sqrt{\rho\epsilon}$
Where $\rho$ is the Lipschitz constant for the Hessian. (That is, in addition to the requirement that our gradient not vary too rapidly, we now have a similar requirement on our Hessian. Essentially, the authors are looking for a point which looks like a minimum in both the first and second derivative.
The method by which they accomplish this is to use a variant (pick your favorite) of stochastic gradient descent most of the time. But wherever they encounter a point where $\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\leq 0$, they use a suitably chosen second order method to escape the saddle. They show that by incorporating this second order information as-needed they will converge to a second-order stationary point.
Technically this is a second order gradient method, which may or may not fall under the umbrella of algorithms you were interested in.
This is a very active area of research and I've left out many important contributions (ex Ge et al.). I'm also new to the topic so this question has provided me an opportunity to look. I'm happy to continue the discussion if there is interest.
*** Suitably chosen means one one that is shown to converge to a second-order stationary point. They use the Cubic regularized Newton method of Nesterov and Polyak.
See appendix B1 in https://web.stanford.edu/~boyd/cvxbook/.
The function and the constraint can be non-convex in a Quadratically Constrained Quadratic Program, and you can still see strong duality (it is guaranteed if a technical condition known as Slater's constraint qualifier holds)
Strong duality in weak terms means that we can solve the optimization problem. From the original problem which is called the primal, you can formulate an alternative problem called the dual problem. The solution of the dual problem provides a solution which in some sense is the "best lower bound" for your original problems
In a lot of the optimization problems which are non-convex, there will be a gap between the primal and dual solutions i.e., the lower bound can be far below the true optimal value (even negative infinity). In some special cases, the bound is tight. These special cases are those in which we have strong duality.
The algorithm is a TECHNIQUE used to arrive at the optimal point. The optimal solution and our ability to find it depends on the GEOMETRY of the problem (which is what duality tries to arrive at). Loosely put, the analysis says that if the optimization properly set up will converge to a minimum.
In general, the gradient descent will converge to a stationary point. This point can be a local minimum/global minimum/saddle minimum. In only few non-convex cases we can guarantee what it converges to
I will try and answer the "when does Gradient Descent convergence to a critical point" part of the question.
The paper "Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods"
by Attouch, Bolte and Svaiter,
shows that if the objective function satisfies the Kurdyka-Lojasiewicz (KL) inequality, then GD and other descent methods do in fact converge to a minimizer. Note that the KL condition is extremely general but hard to grasp. Functions which satisfy KL are for example given by semi-algebraic functions (again, very general but not a simple notion).
In order to give some intuitions about these notions I'll try to be less vague but also not too technical, so bare with me. A function $f$ satisfies the KL condition at a critical point $\bar{x}$ if there exists a function $\phi$ (note that I'm leaving out some conditions) such that $$ || \nabla (\phi \circ f)(x)|| \ge 1 $$ for all $x$ such that $f(\bar{x}) < f(x) < r$ for some $r$. The intuition is that there exists a function $\phi$ which reparametrizes our function of interest $f$ in such a way that it is sharp around the critical point (the derivative is bounded away from zero). In some sense this means, that the function can't be too flat around $\bar{x}$.
Semialgebricity on the other hand is a bit more difficult. The field studying it is also known as tame geometry. I think the name tame captures the essence very well. Functions belonging to this class can't be arbitrarily "wild".
