8
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ This paper: arxiv.org/pdf/1602.04915.pdf might be of use. In particular: "if [the function] is twice continuously differentiable and satisfies the strict saddle property, then gradient descent with a random initialization and sufficiently small constant step size converges to a local minimizer or negative infinity almost surely" $\endgroup$ – David Kozak Feb 11 '18 at 2:11
  • $\begingroup$ Thanks! I wonder if there is a sense in which the paper you cited is weaker than this more recent result, arxiv.org/abs/1709.01434 Any ideas? $\endgroup$ – gradstudent Feb 12 '18 at 16:24
  • $\begingroup$ Conveniently that paper is already on my list to tackle this week, I will get back to you with a proper answer once I have digested. $\endgroup$ – David Kozak Feb 12 '18 at 16:26
  • $\begingroup$ Thanks! Looking forward to a discussion! :D Do let me know if you know of any "small" prototypes of such proofs of showing convergence in non-convex gradient descent! $\endgroup$ – gradstudent Feb 12 '18 at 16:36
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is a QCQP and what does it mean to see strong duality? $\endgroup$ – MachineEpsilon Feb 7 '18 at 5:03
  • $\begingroup$ @Sid What has this got to do with convergence of gradient descent that I am asking about? $\endgroup$ – gradstudent Feb 7 '18 at 5:16
  • $\begingroup$ I have edited my answer. My apologies for the terse respone $\endgroup$ – Sid Feb 7 '18 at 5:34
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks for the reply! Two comments (a) I think Reddi et. al. is a better result than Lee et. al. because its a convergence with a rate bound and not just an asymptotic result. (b) There is this paper which seems to claim (and looks like so) to be better than all these papers, opt-ml.org/papers/OPT2017_paper_16.pdf $\endgroup$ – gradstudent Feb 14 '18 at 16:42
  • $\begingroup$ Agreed, and it is much simpler mathematically. But the Lee result is interesting for its unique approach -- I think there will be more progress from that direction as we begin looking for more ways to understand high dimensional nonconvex surfaces. I'll check out the paper you referenced, thanks for that! $\endgroup$ – David Kozak Feb 14 '18 at 16:50
  • $\begingroup$ Let add one more question : Given this Reddi et. al. paper is there still any relevance of the the same group's more famous paper, arxiv.org/abs/1603.06160 $\endgroup$ – gradstudent Feb 15 '18 at 2:01
  • $\begingroup$ There definitely is relevance as the gradient descent variant that they use in their more recent paper is SVRG. We might close this question out and begin afresh though so that the community gets the benefit of participating. I still haven't yet read the paper you recommended beyond the abstract but it is on the list and may inspire further questions. $\endgroup$ – David Kozak Feb 15 '18 at 2:11
1
$\begingroup$

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)|| $$ 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".

$\endgroup$
  • $\begingroup$ Thanks! Let me look this up! Can you kindly add some intuitions about this condition? $\endgroup$ – gradstudent Sep 7 at 17:40
  • $\begingroup$ I updated my answer with some intuition. Hope it helps. $\endgroup$ – xel Sep 11 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.