Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

Introduction

The interplay between the structure of saddle points and the performance of gradient descent dynamics is a critical and not well understood aspect of non-convex optimization. Despite our incomplete theoretical understanding, in practice, the intuitive nature of the gradient descent method (and more generally gradient-like algorithmsA gradient-like system is a system where for each non-equilibrium initial condition the dynamic will move towards a new state whose cost is strictly less than that of the initial state.) make it a basic tool for attacking non-convex optimization problems for which we have very little understanding of the geometry of their saddle points. In fact, these techniques become particularly useful as the equilibrium structure becomes increasingly complicated, e.g., such as in the cases of nonnegative matrix factorization or congestion/potential games , where symmetries in the nature of non-convex optimization problems give rise to continuums of saddle points with complex geometry. In these cases, especially, the simplistic, greedy attitude of the gradient descent method, which is by design agnostic towards the global geometry of the cost function minimized, comes rather handy. As we move forward in time, the cost keeps decreasing and convergence is guaranteed.

This simplicity, however, comes at least seemingly at a significant cost. For example, it is well known that there exist instances where bad initialization of gradient descent converges to saddle points . Despite the existence of such worst case instances in theory, practitioners have been rather successful at applying these techniques across a wide variety of problems . Recently, Lee et. al. have given a rather insightful interpretation of the effectiveness of gradient descent methods in terms of circumventing the saddle equilibrium problem using tools from topology of dynamical systems. At a glance, the paper argues the following intuitively clear message: The instability of (locally unstable) saddle points translates to a global phenomenon and the probability of converging to such a saddle point given a randomly chosen (random not over a local neighborhood but over the whole state space) initial condition is zero.

This message is clear, concise, and satisfying in the sense that it transcribes the practical success of the gradient descent method to a concrete theoretical guarantee. As is usually the case, such high level statements come with an asterisk of necessary technical conditions on the cost function $f$ minimized.

Critically, for this result to apply, $f$ is required to have isolated saddle points, $\nabla f$ is assumed to be globally $L$-LipschitzThat is, $f$ satisfies $\left\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\right\|_{2}\leq L\left\|\mathbf{x}-\mathbf{y}\right\|_{2}$. and the step-size $\alpha$ is taken to be less than $1/L$. These regularity conditions soften somewhat the impact of the statement both theoretically as well as in practice. First, although the assumption of isolated fixed points is indeed generic for abstract classes of cost functions, in several special cases of practical interest where the cost function has some degree of symmetry (e.g., due to scaling invariance) this assumption is not satisfied. For this reason, the important question of whether the assumption of isolated equilibria is indeed necessary was explicitly raised in . Moreover, the assumption of global Lipschitz continuity for $\nabla f$ is not satisfied even by low degree polynomials (e.g., cubic). Finally, a natural question is how tight is the assumption on the step-size?

In this work we provide answers to all the above questions. We show that the assumption of isolated saddle points is indeed not necessary to argue generic convergence to local minima. To argue this, we need to combine tools from dynamical systems, topology, analysis and optimization theory. Moreover, we show that the globally Lipschitz assumption can be circumvented as long as the domain is convex and forward invariant with respect to gradient descent. This proposition makes our results easily applicable to many standard settings. Finally, using linear algebra and eigenvalue analysis we provide an upper bound on the allowable step-size (for these results to hold). Our work shows that the high level message of is effectively practically always binding. Saddle points are indeed of little concern for the gradient descent method in practice, but it takes quite a bit of theory to argue so.

First-order descent methods can indeed escape strict saddle points when assisted by near isotropic noise. establishes convergence of the Robbins-Monro stochastic approximation to local minimizers for strict saddle functions, whereas establishes convergence to local minima for perturbed versions of multiplicative weights algorithm in generic potential games. Recently, quantified the convergence rate of perturbed stochastic gradient descent to local minima. The addition of isotropic noise can significantly slow down the convergence rate. In contrast, our setting is deterministic and corresponds to the simplest possible discrete-time implementation of gradient descent.

Numerous curvature-based optimization techniques have been developed in order to circumvent saddle points (e.g. trust-region methods , modified Newton’s method with curvilinear line search , cubic regularized Newton’s method , and saddle-free Newton methods ). Unlike gradient descent, these methods have superlinear per-iteration implementation costs, making them impractical for high dimensional settings.

Gradient descent with carefully chosen initial conditions can bypass the problem of local minima altogether and converge to the global minimum for many practical non-convex optimization settings (e.g. dictionary learning , latent-variable models , matrix completion , and phase retrieval ). In contrast, we focus on the performance of gradient descent under generic initial conditions. Finally, some recent work has been focusing on the connections between stability and efficiency of fixed points in non-convex optimization (e.g., Gaussian random fields ).

Gradient-like dynamics, where the dynamic moves towards states of decreased cost but without necessarily moving in the direction of steepest decrease, is a generalization of gradient dynamics that arise in a number of applications including game theory and mathematical biology. Similar arguments about convergence to local minima for almost all initial conditions have been argued for (variants of) replicator dynamics and multiplicative weights update algorithms when applied to games where the incentives of all agents are closely aligned.Such games are known as potential/congestion games and correspond to games where all agents act as if they share a common cost/potential function that they are trying to minimize. From the perspective of biology and specifically evolution, (variants of) replicator/MWUA capture standard models of the evolution of the frequencies of different genotypes within a species (preferential survival of the fittest). By analyzing the properties of local minimum energy states we can derive completely different conclusions about the long term system behavior (in terms e.g., of the resulting genetic diversity) from the ones that follow from analyzing all saddle points . In fact, understanding the properties of local minima raises interesting computational complexity questions . Finally, examining the stability properties of equilibria can help us capture quantitatively the long term behavior of biologically inspired gradient-like systems even under time-evolving fitness landscapes . Given the emergent overlapping interests between these areas and (non convex) optimization theory, it seems that novel opportunities for cross-fertilization between these research communities arise.

2 Organization

In Section 2, we introduce the notation and definitions used throughout the paper and state formally our main theorems. In Section 3, we prove our results establishing the negligible probability of converging to saddle points, addressing the possibility of continuums of equilibria, forward-invariant subspaces, and establishing an upper bound on the step-size. In Section 4, we produce several examples showcasing the effectiveness of our methods. Finally, we conclude in Section 5 by suggesting directions for future work.

Preliminaries

It is easy to see that the fixed points of the dynamical system $\mathbf{x}_{k+1}=g(\mathbf{x}_{k})$ are exactly the points $\mathbf{x}$ so that $\nabla f(\mathbf{x})=\mathbf{0}$, called critical points or equilibria. The set of local minima of $f$ is a subset of the set of critical points of $f$. These two sets do not coincide and this poses a serious obstacle for proving strong theoretical guarantees for gradient descent, since the dynamics may converge to a critical point which is not a local minimum, called a saddle point.

Lee et al. argue, under technical conditions which include the assumption of isolated critical points, that the set of initial conditions that converge to strict saddle points is a zero measure set (for definition of strict saddle, see Definition 1). The paper leaves as an open question whether the condition of isolated equilibria is necessary. We prove that the set of initial conditions that converge to a strict saddle point is a zero measure set even in the case of non-isolated critical pointsOur arguments hence allow for cost functions $f$’s with uncountably many critical points.. Furthermore, one of the conditions for $f$ is that $\nabla f$ is globally Lipschitz, which implies that the second derivative of $f$ is bounded, i.e., there exists a $\beta>0$ such that for all $\mathbf{x}$ we have $\left\|\nabla^{2}f(\mathbf{x})\right\|_{2}\leq\beta$. However, even third degree polynomial functions are not globally Lipschitz. We provide a theorem which can circumvent this assumption as long as the domain $\mathcal{S}$ is forward or positively invariant with respect to $g$, i.e., $g(\mathcal{S})\subseteq\mathcal{S}$. Finally, we provide an easy upper bound on the step-size $\alpha$, via eigenvalue analysis of the Jacobian of $g$, i.e., $I-\alpha\nabla^{2}f(\mathbf{x})$.

Below we give some necessary definitions as appeared in Lee et al. .

A point $\mathbf{x}^{*}$ is a critical point of $f$ if $\nabla f(\mathbf{x}^{*})=\mathbf{0}$. We denote by $C=\{\mathbf{x}:\nabla f(\mathbf{x})=\mathbf{0}\}$ the set of critical points (can be uncountably many).

A critical point $\mathbf{x}^{*}$ is isolated if there is a neighborhood $U$ around $\mathbf{x}^{*}$ and $\mathbf{x}^{*}$ is the only critical point in $U$.If the critical points are isolated then they are countably many or finite. Otherwise is called non-isolated.

A critical point $\mathbf{x}^{*}$ of $f$ is a saddle point if for all neighborhoods $U$ around $\mathbf{x}^{*}$ there are $\mathbf{y},\mathbf{z}\in U$ such that $f(\mathbf{z})\leq f(\mathbf{x}^{*})\leq f(\mathbf{y})$.

A critical point $\mathbf{x}^{*}$ of $f$ is a strict saddle if $\lambda_{\min}(\nabla^{2}f(\mathbf{x}^{*}))<0$ (minimum eigenvalue of matrix $\nabla^{2}f(\mathbf{x}^{*})$ is negative).

In , the steps of the proof of their result are the following: Under the regularity assumption that $\nabla f$ is globally Lipschitz with some Lipschitz constant $L$, Lee et al. are able to show that $g(\mathbf{x})=\mathbf{x}-\alpha\nabla f(\mathbf{x})$ is a diffeomorphism for $\alpha<1/L$. Afterwards, using the center-stable manifold theorem (see theorem 9), they show that the set of initial conditions so that $g$ converges to saddle points has measure zero under the assumption that the critical points are isolated. We generalize their result for non-isolated critical points, answering one of their open questions (see also the example in Section 4.1, where there is a line of critical points).

We can prove a stronger version of the theorem above, circumventing the globally Lipschitz condition for domains which are forward invariant (see also the example in Section 4.2).

Finally, via eigenvalue analysis of $I-\alpha\nabla^{2}f(\mathbf{x})$, we can find upper bounds on the step-size of gradient descent. A straightforward theorem is the following:

Proving the theorems

In this section, we prove Theorem 3. We start by showing that the assumptions of Theorem 3 imply that $\nabla f(\mathbf{x})$ is Lipschitz in $\mathcal{S}$.

The assumption that $\sup_{\mathbf{x}\in\mathcal{S}}\left\|\nabla^{2}f(\mathbf{x})\right\|_{2}\leq L<\infty$ implies that $\nabla f(x)$ is Lipschitz with constant $L$ in the convex set $\mathcal{S}$, as stated by Lemma 5. We show that the converse holds as well, i.e., the Lipschitz condition for $\nabla f(\mathbf{x})$ with constant $L$ in the main theorem in Lee et al. implies $\left\|\nabla^{2}f(\mathbf{x})\right\|_{2}\leq L$ for all $\mathbf{x}\in\mathcal{S}$ and hence the assumption in our Theorems 2, 3 that $\sup_{\mathbf{x}\in\mathcal{S}}\left\|\nabla^{2}f(\mathbf{x})\right\|_{2}\leq L$ is satisfied.

Fix an $\epsilon>0$. By Taylor’s theorem since $f$ is twice differentiable with respect to some point $\mathbf{x}$ it holds that

for $\mathbf{y}$ sufficiently close to $\mathbf{x}$ (depends on $\epsilon$). Therefore under the Lipschitz assumption we get that there exists a closed neighborhood $U(\epsilon)$ of $\mathbf{x}$ so that for all $\mathbf{y}\in U$ we get

Lemmas 5 and 7 show that the smoothness assumptions in Lee et al. paper are equivalent to ours. We use the condition on the spectral norm of the matrix $\nabla^{2}f(\mathbf{x})$ so that we can work with the eigenvalues in our theorems (e.g., in Remark 6 the spectral norm coincides with spectral radius for $\nabla^{2}f(\mathbf{x})$). Below we prove that the update rule of gradient descent, i.e., function $g$ is a diffeomorphism under the assumptions of Theorem 3 (similar approach appeared in ).

Under the assumptions of Theorem 3, function $g$ is a diffeomorphism in $\mathcal{S}$.

First we prove that $g$ is a injective. We follow the same argument as in . Suppose $g(\mathbf{y})=g(\mathbf{x})$, thus $\mathbf{y}-\mathbf{x}=\alpha(\nabla f(\mathbf{y})-\nabla f(\mathbf{x}))$. We assume that $\mathbf{x}\neq\mathbf{y}$ and we will reach contradiction. From Lemma 5 we get $\left\|\nabla f(\mathbf{y})-\nabla f(\mathbf{x})\right\|_{2}\leq L\left\|\mathbf{y}-\mathbf{x}\right\|_{2}$ and hence $\left\|\mathbf{x}-\mathbf{y}\right\|_{2}\leq\alpha L\left\|\mathbf{y}-\mathbf{x}\right\|_{2}<\left\|\mathbf{y}-\mathbf{x}\right\|_{2}$ since $\alpha L<1$ (contradiction).

We continue by showing that $g$ is a local diffeomorphism. Observe that the Jacobian of $g$ is $I-\alpha\nabla^{2}f(\mathbf{x})$. It suffices to show that $\alpha\nabla^{2}f(\mathbf{x})$ has no eigenvalue which is 1, because this implies matrix $I-\alpha\nabla^{2}f(\mathbf{x})$ is invertible. As long as $I-\alpha\nabla^{2}f(\mathbf{x})$ is invertible, from Inverse Function Theorem (see ) follows that $g$ is a local diffeomorphism. Finally, since $g$ is injective, the inverse $g^{-1}$ is well defined and since $g$ is a local diffeomorphism in $\mathcal{S}$, it follows that $g^{-1}$ is smooth in $\mathcal{S}$. Therefore $g$ is a diffeomorphism.

We will use the center-stable manifold theorem since $g(\mathbf{x})=\mathbf{x}-\alpha\nabla f(\mathbf{x})$ is a diffeomorphism, where $\sup_{\mathbf{x}\in\mathcal{S}}\left\|\nabla^{2}f(\mathbf{x})\right\|_{2}\leq L$ and $\alpha<1/L$. A modification of this proof for replicator dynamics (not gradient descent) appeared in and .

From this point on our approach deviates significantly from that of and new, orthogonal ideas and tools need to be introduced.

Let $\mathbf{r}$ be a critical point of function $f(\mathbf{x})$ and $B_{\mathbf{r}}$ be the (open) ball that is derived from Theorem 9. We consider the union of these balls

For every open cover there is a countable subcover.

Therefore due to Lindelőf’s lemma, we can find a countable subcover for $A$, i.e., there exists fixed-points $\mathbf{r}_{1},\mathbf{r}_{2},\dots$ such that $A=\cup_{m=1}^{\infty}B_{\mathbf{r}_{m}}$. If gradient descent converges to a strict saddle point, starting from a point $\mathbf{v}\in\mathcal{S}$, there must exist a $t_{0}$ and $m$ so that $g^{t}(\mathbf{v})\in B_{\mathbf{r}_{m}}$ for all $t\geq t_{0}$. From Theorem 9 we get that $g^{t}(\mathbf{v})\in W_{loc}^{sc}(\mathbf{r}_{m})\cap\mathcal{S}$ where we used the fact that $g(\mathcal{S})\subseteq\mathcal{S}$ (from assumption forward invariant), namely the trajectory remains in $\mathcal{S}$ for all times $W_{loc}^{sc}(\mathbf{r}_{m})$ denotes the center stable manifold of fixed point $\mathbf{r}_{m}$. By setting $D_{1}(\mathbf{r}_{m})=g^{-1}(W_{loc}^{sc}(\mathbf{r}_{m})\cap\mathcal{S})$ and $D_{i+1}(\mathbf{r}_{m})=g^{-1}(D_{i}(\mathbf{r}_{m})\cap\mathcal{S})$ we get that $\mathbf{v}\in D_{t}(\mathbf{r}_{m})$ for all $t\geq t_{0}$. Hence the set of initial points in $\mathcal{S}$ so that gradient descent converges to a strict saddle point is a subset of

The following lemma is standard, but we provide a proof for completeness.

Since $\epsilon$ was arbitrary, it follows that $\mu(h(E_{i}))=0$. To finish the proof, observe that $h(E)=\cup_{i=1}^{\infty}h(E_{i})$ therefore $\mu(h(E))\leq\sum_{i=1}^{\infty}\mu(h(E_{i}))=0$. ∎

A straightforward application of Theorem 3 is the following:

Assume that the conditions of Theorem 3 are satisfied and all saddle points of $f$ are strict. Additionally, let $\nu$ be a prior measure with support $\mathcal{S}$ which is absolutely continuous with respect to Lebesgue measure, and assume $\lim_{k\to\infty}g^{k}(x)$ exists$g^{k}$ denotes the composition of $g$ with itself $k$ times. for all $\mathbf{x}$ in $\mathcal{S}$. Then

where $\mathbf{x}^{*}$ is a local minimum.

Since the set of initial conditions whose limit point is a (strict) saddle point is a measure zero set and we have assumed $\lim_{k\to\infty}g^{k}(x)$ exists for all initial conditions in $\mathcal{S}$ then the probability of converging to a local minimizer is $1$. ∎

Arguing that $\lim_{k}g^{k}(\mathbf{x})$ exists follows from standard arguments in several settings of interest (e.g for analytic functions $f$ that satisfy (Lojasiewicz Gradient Inequality)), see paper and references therein.

The importance of Theorem 3 will become clear in the examples of Section 4. Specifically, in the example of Section 4.2, the function is not globally Lipschitz (we use the example that appears in ), nevertheless Theorem 3 applies and thus we have convergence to local minimizers with probability 1. In the example of Section 4.1 we see that simple functions may have non-isolated critical points.

2 Proof of Theorem 4

Examples

2 Example for forward invariant set

We use the same function as in Lee et al. $f(x,y)=\frac{x^{2}}{2}+\frac{y^{4}}{4}-\frac{y^{2}}{2}$. As argued in previous sections, $f$ is not globally Lipschitz so the main result in cannot be applied here. We will use our Theorem 3 which talks about forward invariant domains.

The critical points of $f$ are $(0,0),(0,1),(0,-1)$. $(0,0)$ is a strict saddle point and the other two are local minima. Observe that the Hessian $\nabla^{2}f(x,y)$ is

3 Example for step-size

We use the same function as in the previous example. Observe that for $(0,0),(0,1),(0,-1)$ we have that the spectral radius of $\nabla^{2}f$ is $1,2,2$ respectively (so the minimum of all is 1). We choose $\alpha\geq 2$ and we get that $g(x,y)=(-x,3y-2y^{3})$. It is not hard to see that gradient descent does not converge (in the first coordinate function $g$ cycles between $x$ and $-x$).

Conclusion

Our work argues that saddle points are indeed of little concern for the gradient descent method in practice under rather weak assumptions for $f$ which allow for non-isolated critical points. In some sense, this is the strongest positive result possible without making explicit assumptions on the structure of the cost function $f$ nor using beneficial random noise/well chosen initial conditions. Naturally, all these directions are of key interest and are the object of recent work (see section 1.1). Keeping up with this simplest, deterministic implementation of gradient descent a natural hypothesis is that (in settings of practical interest) it converges not only to local minimizers but moreover the size of the region of attraction of each local minimizer is in a sense directly proportional to its quality.

Recently, in there has been some progress in proving such statements in non-convex gradient-like systems that arise from learning in games. In such settings, (stable) fixed points correspond to Nash equilibria, but instead of having the typical system performance being dominated by the worst case Nash equilibria (as Price of Anarchy suggests) the regions of attractions of such bad (social) states prove to be minimal and the system works near optimally on average (given uniformly random initial conditions). Extending such statements to actual gradient-dynamics as well as comparing the average case performance of different heuristics even in restricted settings is a fascinating question that could shed more light into the in-many-cases surprising efficiency of the gradient descent method.

Acknowledgements

We are grateful to Jason D. Lee, Max Simchowitz, Michael I. Jordan and Benjamin Recht for their support and helpful discussions and suggestions as well as for the elucidating blog article at http://www.offconvex.org on their elegant work, which inspired our investigation. We are also thankful to Nisheeth Vishnoi, on whose blog the article appeared, for pointing it out to us.

References