Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Introduction

Nonconvex optimization problems are ubiquitous in modern machine learning. While it is NP-hard to find global minima of a nonconvex function in the worst case, in the setting of machine learning it has proved useful to consider a less stringent notion of success, namely that of convergence to a first-order stationary point (where $\nabla f(\mathbf{x})=0$). Gradient descent (GD), a simple and fundamental optimization algorithm that has proved its value in large-scale machine learning, is known to find an $\epsilon$-first-order stationary point (where $\left\|{\nabla f(\mathbf{x})}\right\|\leq\epsilon$) in $O(1/\epsilon^{2})$ iterations (Nesterov, 1998), and this rate is sharp (Cartis et al., 2010). Such results, however, do not seem to address the practical success of gradient descent; first-order stationarity includes local minima, saddle points or even local maxima, and a mere guarantee of convergence to such points seems unsatisfying. Indeed, architectures such as deep neural networks induce optimization surfaces that can be teeming with such highly suboptimal saddle points (Dauphin et al., 2014). It is important to study to what extent gradient descent avoids such points, particular in the high-dimensional setting in which the directions of escape from saddle points may be few.

This paper focuses on convergence to a second-order stationary point (where $\nabla f(\mathbf{x})=0$ and $\nabla^{2}f(\mathbf{x})\succeq 0$). Second-order stationarity rules out many common types of saddle points (strict saddle points where $\lambda_{\min}(\nabla^{2}f(\mathbf{x}))<0$), allowing only local minima and higher-order saddle points. A significant body of recent work, some theoretical and some empirical, shows that for a large class of well-studied machine learning problems, neither higher-order saddle points nor spurious local minima exist. That is, all second-order stationary points are (approximate) global minima for these problems. Choromanska et al. (2014); Kawaguchi (2016) present such a result for learning multi-layer neural networks, Bandeira et al. (2016); Mei et al. (2017) for synchronization and MaxCut, Boumal et al. (2016) for smooth semidefinite programs, Bhojanapalli et al. (2016) for matrix sensing, Ge et al. (2016) for matrix completion, and Ge et al. (2017) for robust PCA. These results strongly motivate the quest for efficient algorithms to find second-order stationary points.

On the other hand, GD is known to be suboptimal in the convex case. In a celebrated paper, Nesterov (1983) showed that an accelerated version of gradient descent (AGD) finds an $\epsilon$-suboptimal point (see Section 2.2) in $O(1/\sqrt{\epsilon})$ steps, while gradient descent takes $O(1/\epsilon)$ steps. The basic idea of acceleration has been used to design faster algorithms for a range of other convex optimization problems (Beck and Teboulle, 2009; Nesterov, 2012; Lee and Sidford, 2013; Shalev-Shwartz and Zhang, 2014). We will refer to this general family as “momentum-based methods.”

Such results have focused on the convex setting. It is open as to whether momentum-based methods yield faster rates in the nonconvex setting, specifically when we consider the convergence criterion of second-order stationarity. We are thus led to ask the following question: Do momentum-based methods yield faster convergence than GD in the presence of saddle points?

Perturbation (Lines 3-4): when the gradient is small, we add a small perturbation sampled uniformly from a $d$-dimensional ball with radius $r$. The homogeneous nature of this perturbation mitigates our lack of knowledge of the curvature tensor at or near saddle points.

Negative Curvature Exploitation (NCE, Lines 8-9; pseudocode in Algorithm 3): when the function becomes “too nonconvex” along $\mathbf{y}_{t}$ to $\mathbf{x}_{t}$, we reset the momentum and decide whether to exploit negative curvature depending on the magnitude of the current momentum $\mathbf{v}_{t}$.

In this section, we review related work from the perspective of both nonconvex optimization and momentum/acceleration. For clarity of presentation, when discussing rates, we focus on the dependence on the accuracy $\epsilon$ and the dimension $d$ while assuming all other problem parameters are constant. Table 1 presents a comparison of the current work with previous work.

Convergence to first-order stationary points: Traditional analyses in this case assume only Lipschitz gradients (see Definition 1). Nesterov (1998) shows that GD finds an $\epsilon$-first-order stationary point in $O(1/\epsilon^{2})$ steps. Ghadimi and Lan (2016) guarantee that AGD also converges in $\widetilde{O}\left({1/\epsilon^{2}}\right)$ steps. Under the additional assumption of Lipschitz Hessians (see Definition 4), Carmon et al. (2017) develop a new algorithm that converges in $O(1/\epsilon^{7/4})$ steps. Their algorithm is a nested-loop algorithm, where the outer loop adds a proximal term to reduce the nonconvex problem to a convex subproblem. A key novelty in their algorithm is the idea of “negative curvature exploitation,” which inspired a similar step in our algorithm. In addition to the qualitative and quantitative differences between Carmon et al. (2017) and the current work, as summarized in Table 1, we note that while Carmon et al. (2017) analyze AGD applied to convex subproblems, we analyze AGD applied directly to nonconvex functions through a novel Hamiltonian framework.

Convergence to second-order stationary points: All results in this setting assume Lipschitz conditions for both the gradient and Hessian. Classical approaches, such as cubic regularization (Nesterov and Polyak, 2006) and trust region algorithms (Curtis et al., 2014), require access to Hessians, and are known to find $\epsilon$-second-order stationary points in $O(1/\epsilon^{1.5})$ steps. However, the requirement of these algorithms to form the Hessian makes them infeasible for high-dimensional problems. A second set of algorithms utilize only Hessian-vector products instead of the explicit Hessian; in many applications such products can be computed efficiently. Rates of $\widetilde{O}(1/\epsilon^{7/4})$ have been established for such algorithms (Carmon et al., 2016; Agarwal et al., 2017; Royer and Wright, 2017). Finally, in the realm of purely gradient-based algorithms, Ge et al. (2015) present the first polynomial guarantees for a perturbed version of GD, and Jin et al. (2017) sharpen it to $\widetilde{O}(1/\epsilon^{2})$. For the special case of quadratic functions, O’Neill and Wright (2017) analyze the behavior of AGD around critical points and show that it escapes saddle points faster than GD. We note that the current work is the first achieving a rate of $\widetilde{O}(1/\epsilon^{7/4})$ for general nonconvex functions.

Acceleration: There is also a rich literature that aims to understand momentum methods; e.g., Allen-Zhu and Orecchia (2014) view AGD as a linear coupling of GD and mirror descent, Su et al. (2016) and Wibisono et al. (2016) view AGD as a second-order differential equation, and Bubeck et al. (2015) view AGD from a geometric perspective. Most of this work is tailored to the convex setting, and it is unclear and nontrivial to generalize the results to a nonconvex setting. There are also several papers that study AGD with relaxed versions of convexity—see Necoara et al. (2015); Li and Lin (2017) and references therein for overviews of these results.

2 Main Techniques

Our results rely on the following three key ideas. To the best of our knowledge, the first two are novel, while the third one was delineated in Jin et al. (2017).

Hamiltonian: A major challenge in analyzing momentum-based algorithms is that the objective function does not decrease monotonically as is the case for GD. To overcome this in the convex setting, several Lyapunov functions have been proposed (Wilson et al., 2016). However these Lyapunov functions involve the global minimum $\mathbf{x}^{\star}$, which cannot be computed by the algorithm, and is thus of limited value in the nonconvex setting. A key technical contribution of this paper is the design of a function which is both computable and tracks the progress of AGD. The function takes the form of a Hamiltonian:

i.e., a sum of potential energy and kinetic energy terms. It is monotonically decreasing in the continuous-time setting. This is not the case in general in the discrete-time setting, a fact which requires us to incorporate the NCE step.

Improve or localize: Another key technical contribution of this paper is in formalizing a simple but powerful framework for analyzing nonconvex optimization algorithms. This framework requires us to show that for a given algorithm, either the algorithm makes significant progress or the iterates do not move much. We call this the improve-or-localize phenomenon. For instance, when progress is measured by function value, it is easy to show that for GD, with proper choice of learning rate, we have:

For AGD, a similar lemma can be shown by replacing the objective function with the Hamiltonian (see Lemma 4). Once this phenomenon is established, we can conclude that if an algorithm does not make much progress, it is localized to a small ball, and we can then approximate the objective function by either a linear or a quadratic function (depending on smoothness assumptions) in this small local region. Moreover, an upper bound on $\sum_{\tau=0}^{t-1}\left\|{\mathbf{x}_{\tau+1}-\mathbf{x}_{\tau}}\right\|^{2}$ lets us conclude that iterates do not oscillate much in this local region (oscillation is a unique phenomenon of momentum algorithms as can be seen even in the convex setting). This gives us better control of approximation error.

Preliminaries

In this section, we will review some well-known results on GD and AGD in the strongly convex setting, and existing results on convergence of GD to second-order stationary points.

2 Convex Setting

To minimize a function $f(\cdot)$, GD performs the following sequence of steps:

The suboptimality of GD and the improvement achieved by AGD can be clearly illustrated for the case of smooth and strongly convex functions.

The gradient Lipschitz property asserts that the gradient can not change too rapidly in a small local region.

A twice-differentiable function $f(\cdot)$ is $\alpha$-strongly convex if $\lambda_{\min}(\nabla^{2}f(\mathbf{x}))\geq\alpha,\;\forall\;\mathbf{x}$.

Let $f^{*}\mathrel{\mathop{:}}=\min_{\mathbf{y}}f(\mathbf{y})$. A point $\mathbf{x}$ is said to be $\epsilon$-suboptimal if $f(\mathbf{x})\leq f^{*}+\epsilon$. The following theorem gives the convergence rate of GD and AGD for smooth and strongly convex functions.

3 Nonconvex Setting

For nonconvex functions finding global minima is NP-hard in the worst case. The best one can hope for in this setting is convergence to stationary points. There are various levels of stationarity.

$\mathbf{x}$ is an $\epsilon$-first-order stationary point of function $f(\cdot)$ if $\left\|{\nabla f(\mathbf{x})}\right\|\leq\epsilon$.

As mentioned in Section 1, for most nonconvex problems encountered in practice, a majority of first-order stationary points turn out to be saddle points. Second-order stationary points require not only zero gradient, but also positive semidefinite Hessian, ruling out most saddle points. Second-order stationary points are meaningful, however, only when the Hessian is continuous.

A twice-differentiable function $f(\cdot)$ is $\rho$-Hessian Lipschitz if:

For a $\rho$-Hessian Lipschitz function $f(\cdot)$, $\mathbf{x}$ is an $\epsilon$-second-order stationary point if:

The following theorem gives the convergence rate of a perturbed version of GD to second-order stationary points. See Jin et al. (2017) for a detailed description of the algorithm.

Note that this rate is essentially the same as that of GD for convergence to first-order stationary points. In particular, it only has polylogarithmic dependence on the dimension.

Main Result

In this section, we present our algorithm and main result. As mentioned in Section 1, the algorithm we propose is essentially AGD with two key differences (see Algorithm 2): perturbation and negative curvature exploitation (NCE). A perturbation is added when the gradient is small (to escape saddle points), and no more frequently than once in $\mathscr{T}$ steps. The perturbation $\xi_{t}$ is sampled uniformly from a $d$-dimensional ball with radius $r$. The specific choices of gap and uniform distribution are for technical convenience (they are sufficient for our theoretical result but not necessary).

NCE (Algorithm 3) is explicitly designed to guarantee decrease of the Hamiltonian (1). When it is triggered, i.e., when

the function has a large negative curvature between the current iterates $\mathbf{x}_{t}$ and $\mathbf{y}_{t}$. In this case, if the momentum $\mathbf{v}_{t}$ is small, then $\mathbf{y}_{t}$ and $\mathbf{x}_{t}$ are close, so the large negative curvature also carries over to the Hessian at $\mathbf{x}_{t}$ due to the Lipschitz property. Assaying two points along $\pm(\mathbf{y}_{t}-\mathbf{x}_{t})$ around $\mathbf{x}_{t}$ gives one point that is negatively aligned with $\nabla f(\mathbf{x}_{t})$ and yields a decreasing function value and Hamiltonian. If the momentum $\mathbf{v}_{t}$ is large, negative curvature can no longer be exploited, but fortunately resetting the momentum to zero kills the second term in (1), significantly decreasing the Hamiltonian.

The following theorem is the main result of this paper.

Overview of Analysis

In this section, we will present an overview of the proof of Theorem 3. Section 4.1 presents the Hamiltonian for AGD and its key property of monotonic decrease. This leads to Section 4.2 where the improve-or-localize lemma is stated, as well as the main intuition behind acceleration. Section 4.3 demonstrates how to apply these tools to prove Theorem 3. Complete details can be found in the appendix.

While GD guarantees decrease of function value in every step (even for nonconvex problems), the biggest stumbling block to analyzing AGD is that it is less clear how to keep track of “progress.” Known Lyapunov functions for AGD (Wilson et al., 2016) are restricted to the convex setting and furthermore are not computable by the algorithm (as they depend on $\mathbf{x}^{\star}$).

Denote the discrete Hamiltonian as $E_{t}\mathrel{\mathop{:}}=f(\mathbf{x}_{t})+\frac{1}{2\eta}\left\|{\mathbf{v}_{t}}\right\|^{2}$, and note that in AGD, $\mathbf{v}_{t}=\mathbf{x}_{t}-\mathbf{x}_{t-1}$. Lemma 4 tolerates nonconvexity with curvature at most $\gamma=\Theta(\theta/\eta)$. Unfortunately, when the function becomes too nonconvex in certain regions (so that (2) holds), the analogy between the continuous and discretized versions breaks and (6) no longer holds. In fact, standard AGD can even increase the Hamiltonian in this regime (see Appendix A.1 for more details). This motivates us to modify the algorithm by adding the NCE step, which addresses this issue. We have the following result:

Lemmas 4 and 5 jointly assert that the Hamiltonian decreases monotonically in all situations, and are the main tools in the proof of Theorem 3. They not only give us a way of tracking progress, but also quantitatively measure the amount of progress.

2 Improve or Localize

One significant challenge in the analysis of gradient-based algorithms for nonconvex optimation is that many phenomena—for instance the accumulation of momentum and the escape from saddle points via perturbation—are multiple-step behaviors; they do not happen in each step. We address this issue by developing a general technique for analyzing the long-term behavior of such algorithms.

In our case, to track the long-term behavior of AGD, one key observation from Lemma 4 is that the amount of progress actually relates to movement of the iterates, which leads to the following improve-or-localize lemma:

Under the same setting as in Lemma 4, if (2) does not hold for all steps in $[t,t+T]$, we have:

Corollary 6 says that the algorithm either makes progress in terms of the Hamiltonian, or the iterates do not move much. In the second case, Corollary 6 allows us to approximate the dynamics of $\{\mathbf{x}_{\tau}\}_{\tau=t}^{t+T}$ with a quadratic approximation of $f(\cdot)$.

The acceleration phenomenon is rooted in and can be seen clearly for a quadratic, where the function can be decomposed into eigen-directions. Consider an eigen-direction with eigenvalue $\lambda$, and linear term $g$ (i.e., in this direction $f(x)=\frac{\lambda}{2}x^{2}+gx$). The GD update becomes $x_{\tau+1}=(1-\eta\lambda)x_{\tau}-\eta g$, with $\mu_{\text{GD}}(\lambda)\mathrel{\mathop{:}}=1-\eta\lambda$ determining the rate of GD. The update of AGD is $(x_{\tau+1},x_{\tau})=(x_{\tau},x_{\tau-1})\mathbf{A}^{\top}-(\eta g,0)$ with matrix $\mathbf{A}$ defined as follows:

The rate of AGD is determined by largest eigenvalue of matrix $\mathbf{A}$, which is denoted by $\mu_{\text{AGD}}(\lambda)$. Recall the choice of parameter (3), and divide the eigen-directions into the following three categories.

Flat directions $\lambda\in[-\sqrt{\rho\epsilon},\sqrt{\rho\epsilon}]$: the representative case is $\lambda=0$ where AGD update becomes $x_{\tau+1}-x_{\tau}=(1-\theta)(x_{\tau}-x_{\tau-1})-\eta g$. For $\tau\leq 1/\theta$, we have $|x_{t+\tau}-x_{t}|=\Theta(\tau)$ for GD while $|x_{t+\tau}-x_{t}|=\Theta(\tau^{2})$ for AGD, which results in AGD moving along negative gradient directions faster than GD.

3 Main Framework

It can be verified by the choice of parameters (3) and Lemma 4 that whenever (2) holds so that NCE is triggered, the Hamiltonian decreases by at least $\mathscr{E}$ in one step. So, if NCE step is performed even once in each round of $\mathscr{T}$ steps, we achieve enough average decrease. The troublesome case is when in some time interval of $\mathscr{T}$ steps starting with $\mathbf{x}_{t}$, only AGD steps are performed without NCE. If $\mathbf{x}_{t}$ is not an $\epsilon$-second order stationary point, either the gradient is large or the Hessian has a large negative direction. We prove the average decrease claim by considering these two cases.

Consider the setting of Theorem 3. If $\left\|{\nabla f(\mathbf{x}_{\tau})}\right\|\geq\epsilon$ for all $\tau\in[t,t+\mathscr{T}]$, then by running Algorithm 2 we have $E_{t+\mathscr{T}}-E_{t}\leq-\mathscr{E}$.

Consider the setting of Theorem 3. If $\left\|{\nabla f(\mathbf{x}_{t})}\right\|\leq\epsilon$, $\lambda_{\min}(\nabla^{2}f(\mathbf{x}_{t}))<-\sqrt{\rho\epsilon}$, and perturbation has not been added in iterations $\tau\in[t-\mathscr{T},t)$, then by running Algorithm 2, we have $E_{t+\mathscr{T}}-E_{t}\leq-\mathscr{E}$ with high probability.

For AGD, gradient and momentum interact, and both play important roles in the dynamics. Fortunately, according to Lemma 4, the Hamiltonian decreases sufficiently whenever the momentum $\mathbf{v}_{t}$ is large; so it is sufficient to discuss the case where the momentum is small.

(informal) If $\mathbf{v}_{t}$ is small, $\left\|{\nabla f(\mathbf{x}_{t})}\right\|$ not too large and $E_{t+\mathscr{T}/2}-E_{t}\geq-\mathscr{E}$, then for all $\tau\in[t+\mathscr{T}/4,t+\mathscr{T}/2]$ we have $\left\|{\mathcal{P}_{\mathcal{S}}\nabla f(\mathbf{x}_{\tau})}\right\|\leq\epsilon/2$.

(informal) If $\mathbf{v}_{t}$ is small and $\left\|{\mathcal{P}_{\mathcal{S}^{c}}\nabla f(\mathbf{x}_{t})}\right\|\geq\epsilon/2$, then we have $E_{t+\mathscr{T}/4}-E_{t}\leq-\mathscr{E}.$

See the formal versions, Lemma 16 and Lemma 17, for more details. We see that if the Hamiltonian does not decrease much (and so is localized in a small ball), the gradient in the strongly convex subspace $\left\|{\mathcal{P}_{\mathcal{S}}\nabla f(\mathbf{x}_{\tau})}\right\|$ vanishes in $\mathscr{T}/4$ steps by Lemma 9. Since the hypothesis of Lemma 7 guarantees a large gradient for all of the $\mathscr{T}$ steps, this means that $\left\|{\mathcal{P}_{\mathcal{S}^{c}}\nabla f(\mathbf{x}_{t})}\right\|$ is large after $\mathscr{T}/4$ steps, thereby decreasing the Hamiltonian in the next $\mathscr{T}/4$ steps (by Lemma 10).

3.2 Negative Curvature Scenario

See the formal version in Lemma 18. We note $\delta$ in above Lemma is a small number characterize the failure probability of the algorithm (as defined in Theorem 3), and $\mathscr{T}$ has logarithmic dependence on $\delta$ according to (3). Lemma 11 says that around any strict saddle, for any two points that are separated along the smallest eigen-direction by at least $\delta r/\sqrt{d}$, PAGD, starting from at least one of those points, decreases the Hamiltonian, and hence escapes the strict saddle. This implies that the width of the region starting from where AGD is stuck has width at most $\delta r/\sqrt{d}$, and thus has small volume.

Conclusions

In this paper, we show that a variant of AGD can escape saddle points faster than GD, demonstrating that momentum techniques can indeed accelerate convergence even for nonconvex optimization. Our algorithm finds an $\epsilon$-second order stationary point in $\widetilde{O}\left({1/\epsilon^{7/4}}\right)$ iterations, faster than the $\widetilde{O}\left({1/\epsilon^{2}}\right)$ iterations taken by GD. This is the first algorithm that is both Hessian-free and single-loop that achieves this rate. Our analysis relies on novel techniques that lead to a better understanding of momentum techniques as well as nonconvex optimization.

The results here also give rise to several questions. The first concerns lower bounds; is the rate of $\widetilde{O}\left({1/\epsilon^{7/4}}\right)$ that we have established here optimal for gradient-based methods under the setting of gradient and Hessian-Lipschitz? We believe this upper bound is very likely sharp up to log factors, and developing a tight algorithm-independent lower bound will be necessary to settle this question. The second is whether the negative-curvature-exploitation component of our algorithm is actually necessary for the fast rate. To attempt to answer this question, we may either explore other ways to track the progress of standard AGD (other than the particular Hamiltonian that we have presented here), or consider other discretizations of the ODE (4) so that the property (5) is preserved even for the most nonconvex region. A final direction for future research is the extension of our results to the finite-sum setting and the stochastic setting.

References

Appendix A Proof of Hamiltonian Lemmas

In this section, we prove Lemma 4, Lemma 5 and Corollary 6, which are presented in Section 4.1 and Section 4.2. In section A.1 we also give an example where standard AGD with negative curvature exploitation can increase the Hamiltonian.

Recall that we define the Hamiltonian as $E_{t}\mathrel{\mathop{:}}=f(\mathbf{x}_{t})+\frac{1}{2\eta}\left\|{\mathbf{v}_{t}}\right\|^{2}$, where, for AGD, we define $\mathbf{v}_{t}=\mathbf{x}_{t}-\mathbf{x}_{t-1}$. The first lemma shows that this Hamiltonian decreases in every step of AGD for mildly nonconvex functions.

Recall that the update equation of accelerated gradient descent has following form:

assuming that the precondition (2) does not hold:

The last inequality uses the fact that $\theta\in[2\eta\gamma,\frac{1}{2}]$ so that $\theta^{2}\leq\frac{\theta}{2}$ and $\eta\gamma\leq\frac{\theta}{2}$. We substitute in the definition of $\mathbf{v}_{t}$ and $E_{t}$ to finish the proof. ∎

We see from this proof that (8) relies on approximate convexity of $f(\cdot)$, which explains why in all existing proofs, the convexity between $\mathbf{x}_{t}$ and $\mathbf{y}_{t}$ is so important. A perhaps surprising fact to note is that the above proof can in fact go through even with mild nonconvexity (captured in line $8$ of Algorithm 2). Thus, high nonconvexity is the problematic situation. To overcome this, we need to slightly modify AGD so that the Hamiltonian is decreasing. This is formalized in the following lemma.

When we perform an NCE step, we know that (2) holds. In the first case ($\left\|{\mathbf{v}_{t}}\right\|\geq s$), we set $\mathbf{x}_{t+1}=\mathbf{x}_{t}$ and set the momentum $\mathbf{v}_{t+1}$ to zero, which gives:

In the second case ($\left\|{\mathbf{v}_{t}}\right\|\leq s$), expanding in a Taylor series with Lagrange remainder, we have:

where $\zeta_{t}=\phi\mathbf{x}_{t}+(1-\phi)\mathbf{y}_{t}$ and $\phi\in$. Due to the certificate (2) we have

On the other hand, clearly $\min\{\langle\nabla f(\mathbf{x}_{t}),\delta\rangle,\langle\nabla f(\mathbf{x}_{t}),-\delta\rangle\}\leq 0$. WLOG, suppose $\langle\nabla f(\mathbf{x}_{t}),\delta\rangle\leq 0$, then, by definition of $\mathbf{x}_{t+1}$, we have:

where $\zeta^{\prime}_{t}=\mathbf{x}_{t}+\phi^{\prime}\delta$ and $\phi^{\prime}\in$. Since $\left\|{\zeta_{t}-\zeta^{\prime}_{t}}\right\|\leq 2s$, $\delta$ also lines up with $\mathbf{y}_{t}-\mathbf{x}_{t}$:

The Hamiltonian decrease has an important consequence: if the Hamiltonian does not decrease much, then all the iterates are localized in a small ball around the starting point. Moreover, the iterates do not oscillate much in this ball. We called this the improve-or-localize phenomenon.

Under the same setting as in Lemma 4, if (2) does not hold for all steps in $[t,t+T]$, we have:

The proof follows immediately from telescoping the argument of Lemma 4. ∎

In the previous section, we proved Lemma 4 which requires $\theta\geq 2\eta\gamma$, that is, $\gamma\leq\theta/(2\eta)$. In this section, we show Lemma 4 is almost tight in the sense that when $\gamma\geq 4\theta/\eta$ in (2), we have:

Monotonic decrease of the Hamiltonian may no longer hold, indeed, AGD can increase the Hamiltonian for those steps.

Consider a simple one-dimensional example, $f(x)=-\frac{1}{2}\gamma x^{2}$, where (2) always holds. Define the initial condition $x_{0}=-1,v_{0}=1/(1-\theta)$. By update equation in Algorithm 1, the next iterate will be $x_{1}=y_{0}=0$, and $v_{1}=x_{1}-x_{0}=1$. By the definition of Hamiltonian, we have：

since $\theta\leq 1/4$. It is not hard to verify that whenever $\gamma\geq 4\theta/\eta$, we will have $E_{1}\geq E_{0}$; that is, the Hamiltonian increases in this step.

This fact implies that when we pick a large learning rate $\eta$ and small momentum parameter $\theta$ (both are essential for acceleration), standard AGD does not decrease the Hamiltonian in a very nonconvex region. We need another mechanism such as NCE to fix the monotonically decreasing property.

Appendix B Proof of Main Result

In this section, we set up the machinery needed to prove our main result, Theorem 3. We first present the generic setup, then, as in Section 4.3, we split the proof into two cases, one where gradient is large and the other where the Hessian has negative curvature. In the end, we put everything together and prove Theorem 3.

To simplify the proof, we introduce some notation for this section, and state a convention regarding absolute constants. Recall the choice of parameters in Eq.(3):

which represent the special units for time, the Hamiltonian, the parameter space and the momentum. All the lemmas in this section hold when the constant $c$ is picked to be sufficiently large. To avoid ambiguity, throughout this section $O(\cdot),\Omega(\cdot),\Theta(\cdot)$ notation only hides an absolute constant which is independent of the choice of sufficiently large constant $c$, which is defined in the precondition of Theorem 3. That is, we will always make $c$ dependence explicit in $O(\cdot),\Omega(\cdot),\Theta(\cdot)$ notation. Therefore, for a quantity like $O(c^{-1})$, we can always pick $c$ large enough so that it cancels out the absolute constant in the $O(\cdot)$ notation, and make $O(c^{-1})$ smaller than any fixed required constant.

Our general strategy in the proof is to show that if none of the iterates $\mathbf{x}_{t}$ is a SOSP, then in all $\mathscr{T}$ steps, the Hamiltonian always decreases by at least $\mathscr{E}$. This gives an average decrease of $\mathscr{E}/\mathscr{T}$. In this section, we establish some facts which will be used throughout the entire proof, including the decrease of the Hamiltonian in NCE step, the update of AGD in matrix form, and upper bounds on approximation error for a local quadratic approximation.

The first lemma shows if negative curvature exploitation is used, then in a single step, the Hamiltonian will decrease by $\mathscr{E}$.

Under the same setting as Theorem 3, for every iteration $t$ of Algorithm 2 where (2) holds (thus running NCE), we have:

It is also easy to check that the precondition of Lemma 5 holds, and by the particular choice of parameters in Theorem 3, we have:

where the last inequality is by picking $c$ in Theorem 3 large enough, which finishes the proof. ∎

Therefore, whenever NCE is called, the decrease of the Hamiltonian is already sufficient. We thus only need to focus on AGD steps. The next lemma derives a general expression for $\mathbf{x}_{t}$ after an AGD update, which is very useful in multiple-step analysis. The general form is expressed with respect to a reference point $\mathbf{0}$, which can be any arbitrary point (in many cases we choose it to be $\mathbf{x}_{0}$).

Let $\mathbf{0}$ be an origin (which can be fixed at an arbitrary point). Let $\mathcal{H}=\nabla^{2}f(\mathbf{0})$. Then an AGD (Algorithm 1) update can be written as:

where $\delta_{\tau}=\nabla f(\mathbf{y}_{\tau})-\nabla f(\mathbf{0})-\mathcal{H}\mathbf{y}_{\tau}$, and

Substituting for $(\mathbf{y}_{t},\mathbf{v}_{t})$ in Algorithm 1, we have a recursive equation for $\mathbf{x}_{t}$:

By definition of $\delta_{\tau}$, we also have:

Clearly $\mathbf{A}$ in Lemma 13 is a $2d\times 2d$ matrix, and if we expand $\mathbf{A}$ according to the eigenvector directions of $\begin{pmatrix}\mathcal{H}&0\\ 0&\mathcal{H}\end{pmatrix}$, $\mathbf{A}$ can be reorganized as a block-diagonal matrix consisting of $d$ $2\times 2$ matrices. Let the $j$th eigenvalue of $\mathcal{H}$ be denoted $\lambda_{j}$, and denote $\mathbf{A}_{j}$ as the $j$th $2\times 2$ matrix with corresponding eigendirections:

We note that the choice of reference point $\mathbf{0}$ is mainly to simplify mathmatical expressions involving $\mathbf{x}_{t}-\mathbf{0}$.

Lemma 13 can be viewed as update from a quadratic expansion around origin $\mathbf{0}$, and $\delta_{\tau}$ is the approximation error which marks the difference between true function and its quadratic approximation. The next lemma shows that when sequence $\mathbf{x}_{0},\cdots,\mathbf{x}_{t}$ are all close to $\mathbf{0}$, then the approximation error is under control:

Using the notation of Lemma 13, if for any $\tau\leq t$, we have $\left\|{\mathbf{x}_{\tau}}\right\|\leq R$, then for any $\tau\leq t$, we also have

$\left\|{\delta_{\tau}}\right\|\leq O(\rho R^{2})$;

$\left\|{\delta_{\tau}-\delta_{\tau-1}}\right\|\leq O(\rho R)(\left\|{\mathbf{x}_{t}-\mathbf{x}_{\tau-1}}\right\|+\left\|{\mathbf{x}_{\tau-1}-\mathbf{x}_{\tau-2}}\right\|)$;

$\sum_{\tau=1}^{t}\left\|{\delta_{\tau}-\delta_{\tau-1}}\right\|^{2}\leq O(\rho^{2}R^{2})\sum_{\tau=1}^{t}\left\|{\mathbf{x}_{\tau}-\mathbf{x}_{\tau-1}}\right\|^{2}$.

Finally, since $(\left\|{\mathbf{x}_{\tau}-\mathbf{x}_{\tau-1}}\right\|+\left\|{\mathbf{x}_{\tau-1}-\mathbf{x}_{\tau-2}}\right\|)^{2}\leq 2(\left\|{\mathbf{x}_{\tau}-\mathbf{x}_{\tau-1}}\right\|^{2}+\left\|{\mathbf{x}_{\tau-1}-\mathbf{x}_{\tau-2}}\right\|^{2})$, the third inequality is immediately implied by the second inequality. ∎

B.2 Proof for large-gradient scenario

The first lemma shows that if momentum or gradient is very large, then the Hamiltonian already has sufficient decrease on average.

Again the last step is by picking $c$ to be a large enough constant, which finishes the proof. ∎

Next, we show that if the initial momentum is small, but the initial gradient on the nonconvex subspace $\mathcal{S}^{c}$ is large enough, then within $O(\mathscr{T})$ steps, the Hamiltonian will decrease by at least $\mathscr{E}$.

Under the setting of Theorem 3, if $\left\|{\mathcal{P}_{\mathcal{S}^{c}}\nabla f(\mathbf{x}_{0})}\right\|\geq\frac{\epsilon}{2}$, $\left\|{\mathbf{v}_{0}}\right\|\leq\mathscr{M}$, $\mathbf{v}_{0}^{\top}[\mathcal{P}_{\mathcal{S}}^{\top}\nabla^{2}f(\mathbf{x}_{0})\mathcal{P}_{\mathcal{S}}]\mathbf{v}_{0}\leq 2\sqrt{\rho\epsilon}\mathscr{M}^{2}$, and for $t\in[0,\mathscr{T}/4]$ only AGD steps are used without NCE or perturbation, then:

The high-level plan is a proof by contradiction. We first assume that the energy doesn’t decrease very much; that is, $E_{\mathscr{T}/4}-E_{0}\geq-\mathscr{E}$ for a small enough constant $\mu$. By Corollary 6 and the Cauchy-Swartz inequality, this immediately implies that for all $t\leq\mathscr{T}$, we have $\left\|{\mathbf{x}_{t}-\mathbf{x}_{0}}\right\|\leq\sqrt{2\eta\mathscr{T}\mathscr{E}/(4\theta)}=\mathscr{S}/2$. In the rest of the proof we will show that this leads to a contradiction.

Given initial $\mathbf{x}_{0}$ and $\mathbf{v}_{0}$, we define $\mathbf{x}_{-1}=\mathbf{x}_{0}-\mathbf{v}_{0}$. Without loss of generality, set $\mathbf{x}_{0}$ as the origin $\mathbf{0}$. Using the notation and results of Lemma 13, we have the following update equation:

Consider the $j$-th eigen-direction of $\mathcal{H}=\nabla^{2}f(\mathbf{0})$, recall the definition of the $2\times 2$ block matrix $\mathbf{A}_{j}$ as in (12), and denote

Then we have for the $j$-th eigen-direction:

Clearly $\sum_{\tau=0}^{t-1}p^{(j)}_{\tau}=1$. For $j\in\mathcal{S}^{c}$, by Lemma 25, we know $\sum_{\tau=0}^{t-1}a_{\tau}^{(j)}\geq\Omega(\frac{1}{\theta^{2}})$. We can thus further write the above equation as:

By the Cauchy-Swartz inequality, this gives:

Recall that for $t\leq\mathscr{T}$, we have $\left\|{\mathbf{x}_{t}}\right\|\leq\mathscr{S}/2$. By Proposition 14, we know: $\left\|{\delta_{0}}\right\|\leq O(\rho\mathscr{S}^{2})$, and by Corollary 6 and Proposition 14:

Recall that we have assumed by way of contradiction that $E_{\mathscr{T}/4}-E_{0}\leq-\mathscr{E}$. By the precondition that NCE is not used at $t=0$, due to the certificate (2), we have:

where $\zeta_{0}=\phi\mathbf{x}_{0}+(1-\phi)\mathbf{y}_{0}$ and $\phi\in$. Noting that we fix $\mathbf{x}_{0}$ as the origin $\mathbf{0}$, by the Hessian Lipschitz property, it is easy to show that $\left\|{\nabla^{2}f(\zeta_{0})-\mathcal{H}}\right\|\leq\rho\left\|{\mathbf{y}_{0}}\right\|\leq\rho\left\|{\mathbf{v}_{0}}\right\|\leq\rho\mathscr{M}\leq\sqrt{\rho\epsilon}$. This gives:

Again letting $\lambda_{j}$ denote the eigenvalues of $\mathcal{H}$, rearranging the above sum give:

The second inequality uses the fact that $\theta^{2}/\eta(2-\theta)^{2}\leq O(\sqrt{\rho\epsilon})$. Substituting into (13) gives:

Finally, putting all pieces together, we have:

which contradicts the fact $\left\|{\mathbf{x}_{t}}\right\|$ that remains inside the ball around $\mathbf{0}$ with radius $\mathscr{S}/2$. ∎

The next lemma shows that if the initial momentum and gradient are reasonably small, and the Hamitonian does not have sufficient decrease over the next $\mathscr{T}$ iterations, then both the gradient and momentum of the strongly convex component $\mathcal{S}$ will vanish in $\mathscr{T}/4$ iterations.

Since $E_{\mathscr{T}}-E_{0}\geq-\mathscr{E}$, by Corollary 6 and the Cauchy-Swartz inequality, we see that for all $t\leq\mathscr{T}$ we have $\left\|{\mathbf{x}_{t}-\mathbf{x}_{0}}\right\|\leq\sqrt{2\eta\mathscr{T}\mathscr{E}/\theta}=\mathscr{S}$.

Given initial $\mathbf{x}_{0}$ and $\mathbf{v}_{0}$, we define $\mathbf{x}_{-1}=\mathbf{x}_{0}-\mathbf{v}_{0}$. Without loss of generality, setting $\mathbf{x}_{0}$ as the origin $\mathbf{0}$, by the notation and results of Lemma 13, we have the update equation:

We will upper bound four terms $\bm{g}_{1},\bm{g}_{2},\bm{g}_{3},\bm{g}_{4}$ separately. Clearly, for the last term $\bm{g}_{4}$, we have:

Next, we show that the first two terms $\bm{g}_{1},\bm{g}_{2}$ become very small for $t\in[\mathscr{T}/4,\mathscr{T}]$. Consider coordinate $j\in\mathcal{S}$ and the $2\times 2$ block matrix $\mathbf{A}_{j}$. By Lemma 20 we have:

This immediately gives when $t\geq\mathscr{T}/4=\Omega(\frac{c}{\theta}\log\frac{1}{\theta})$ for $c$ sufficiently large:

Finally, for $\bm{g}_{3}$, by Lemma 29, for all $j\in\mathcal{S}$, we have

In sum, this gives for any fixed $t\in[\mathscr{T}/4,\mathscr{T}]$:

We now provide a similar argument to prove the upper bound for the momentum. That is, $\forall\;t\in[\mathscr{T}/4,\mathscr{T}]$, we show $\mathbf{v}_{t}^{\top}[\mathcal{P}_{\mathcal{S}}^{\top}\nabla^{2}f(\mathbf{x}_{0})\mathcal{P}_{\mathcal{S}}]\mathbf{v}_{t}\leq\sqrt{\rho\epsilon}\mathscr{M}^{2}$. According to (14), we have:

Consider the $j$-th eigendirection, so that $j\in\mathcal{S}$, and recall the $2\times 2$ block matrix $\mathbf{A}_{j}$. Denoting

by Lemma 19 and 27, we have for $t\geq\mathscr{T}/4=\Omega(\frac{c}{\theta}\log\frac{1}{\theta})$ with $c$ sufficiently large:

This gives, for $t\geq\mathscr{T}/4=\Omega(\frac{c}{\theta}\log\frac{1}{\theta})$, and for $c$ sufficiently large:

Finally, for any $j\in\mathcal{S}$, by Lemma 29, we have:

Finally, we are ready to prove the main lemma of this subsection (Lemma 7), which claims that if gradients in $\mathscr{T}$ iterations are always large, then the Hamiltonian will decrease sufficiently within a small number of steps.

Consider the setting of Theorem 3. If $\left\|{\nabla f(\mathbf{x}_{\tau})}\right\|\geq\epsilon$ for all $\tau\in[0,\mathscr{T}]$, then by running Algorithm 2 we have $E_{\mathscr{T}}-E_{0}\leq-\mathscr{E}$.

Since $\left\|{\nabla f(\mathbf{x}_{\tau})}\right\|\geq\epsilon$ for all $\tau\in[0,\mathscr{T}]$, according to Algorithm 2, the precondition to add perturbation never holds, so Algorithm will not add any perturbation in these $\mathscr{T}$ iterations.

Next, suppose there is at least one iteration where NCE is used. Then by Lemma 12, we know that that step alone gives $\mathscr{E}$ decrease in the Hamiltonian. According to Lemma 4 and Lemma 12 we know that without perturbation, the Hamiltonian decreases monotonically in the remaining steps. This means whenever at least one NCE step is performed, Lemma 7 immediately holds.

For the remainder of the proof, we can restrict the discussion to the case where NCE is never performed in steps $\tau\in[0,\mathscr{T}]$. Letting

we know in case $\tau_{1}\geq\frac{\mathscr{T}}{4}$, that Lemma 15 ensures $E_{\mathscr{T}}-E_{0}\leq E_{\frac{\mathscr{T}}{4}}-E_{0}\leq-\mathscr{E}$. Thus, we only need to discuss the case $\tau_{1}\leq\frac{\mathscr{T}}{4}$. Again, if $E_{\tau_{1}+\mathscr{T}/2}-E_{\tau_{1}}\leq-\mathscr{E}$, Lemma 7 immediately holds. For the remaining case, $E_{\tau_{1}+\mathscr{T}/2}-E_{\tau_{1}}\leq-\mathscr{E}$, we apply Lemma 17 starting at $\tau_{1}$, and obtain

by Lemma 15 we again know we only need to discuss the case where $\tau_{2}\leq\tau_{1}+\frac{\mathscr{T}}{2}$; otherwise, we already guarantee sufficient decrease in the Hamiltonian. Then, we clearly have $\left\|{\mathcal{P}_{\mathcal{S}}\nabla f(\mathbf{x}_{\tau_{2}})}\right\|\leq\frac{\epsilon}{2}$, also by the precondition of Lemma 7, we know $\left\|{\nabla f(\mathbf{x}_{\tau_{2}})}\right\|\geq\epsilon$, thus $\left\|{\mathcal{P}_{\mathcal{S}^{c}}\nabla f(\mathbf{x}_{\tau_{2}})}\right\|\geq\frac{\epsilon}{2}$. On the other hand, since if the Hamiltonian does not decrease enough, $E_{\tau_{2}}-E_{0}\geq-\mathscr{E}$, by Lemma 6, we have $\left\|{\mathbf{x}_{\tau_{1}}-\mathbf{x}_{\tau_{2}}}\right\|\leq 2\mathscr{S}$, by the Hessian Lipschitz property, which gives:

Now $\mathbf{x}_{\tau_{2}}$ satisfies all the preconditions of Lemma 16, and by applying Lemma 16 we finish the proof. ∎

B.3 Proof for negative-curvature scenario

We prove Lemma 8 in this section. We consider two trajectories, starting at $\mathbf{x}_{0}$ and $\mathbf{x}^{\prime}_{0}$, with $\mathbf{v}_{0}=\mathbf{v}^{\prime}_{0}$, where $\mathbf{w}_{0}=\mathbf{x}_{0}-\mathbf{x}^{\prime}_{0}=r_{0}\mathbf{e}_{1}$, where $\mathbf{e}_{1}$ is the minimum eigenvector direction of $\mathcal{H}$, and where $r_{0}$ is not too small. We show that at least one of the trajectories will escape saddle points efficiently.

Assume none of the two sequences decrease the Hamiltonian fast enough; that is,

where $E_{0}$ and $E^{\prime}_{0}$ are the Hamiltonians at $(\mathbf{x}_{0},\mathbf{v}_{0})$ and $(\mathbf{x}^{\prime}_{0},\mathbf{v}^{\prime}_{0})$. Then, by Corollary 6 and the Cauchy-Swartz inequality, we have for any $t\leq\mathscr{T}$:

Taking the difference of two AGD sequences starting from $\mathbf{x}_{0},\mathbf{x}^{\prime}_{0}$, and let $\mathbf{w}_{t}=\mathbf{x}_{t}-\mathbf{x}^{\prime}_{t}$, we have:

We thus obtain the update of the $\mathbf{w}_{t}$ sequence in matrix form:

Intuitively, we want to say that the first term dominates. Technically, we will set up an induction based on the following fact:

It is easy to check the base case holds for $t=0$. Then, assume that for all time steps less than or equal to $t$, the induction assumption hold. We have:

where in the last inequality, we used Lemma 33 for monotonicity in $t$.

To prove that the induction assumption holds for $t+1$ we compute:

By the precondition we have $\lambda_{\min}(\mathcal{H})\leq-\sqrt{\rho\epsilon}$. Without loss of generality, assume that the minimum eigenvector direction of $\mathcal{H}$ is along he first coordinate $\mathbf{e}_{1}$, and denote the corresponding $2\times 2$ matrix as $\mathbf{A}_{1}$ (as in the convention of (12). Let:

We then see that (1) $\mathbf{w}_{0}$ is along the $\mathbf{e}_{1}$ direction, and (2) according to Lemma 32, the matrix $\begin{pmatrix}\mathbf{I},0\end{pmatrix}\mathbf{A}^{t-\tau}\begin{pmatrix}\mathbf{I}\\ 0\end{pmatrix}$ is a diagonal matrix, where the spectral norm is achieved along the first coordinate which corresponds to the eigenvalue $\lambda_{\min}(\mathcal{H})$. Therefore, using Equation (16), we have:

where, in the second to last step, we used Lemma 31, and in the last step we used $1/\theta\leq\mathscr{T}$. Finally, $O(\eta\rho\mathscr{S}\mathscr{T}^{2})\leq O(c^{-1})\leq 1/2$ by choosing a sufficiently large constant $c$. Therefore, we have proved the induction, which gives us:

Noting that $\lambda_{\min}(\mathcal{H})\leq-\sqrt{\rho\epsilon}$, by applying Lemma 33 we have

This means our assumption is wrong, and we can therefore conclude:

where the last step is due to our choice of $r=\eta\epsilon\cdot\chi^{-5}c^{-8}$ in (3). Combining these two facts:

We are now ready to prove the main lemma in this subsection, which states with that random perturbation, PAGD will escape saddle points efficiently with high probability.

Consider the setting of Theorem 3. If $\left\|{\nabla f(\mathbf{x}_{0})}\right\|\leq\epsilon$, $\lambda_{\min}(\nabla^{2}f(\mathbf{x}_{0}))<-\sqrt{\rho\epsilon}$, and a perturbation has not been added in iterations $\tau\in[-\mathscr{T},0)$, then, by running Algorithm 2, we have $E_{\mathscr{T}}-E_{0}\leq-\mathscr{E}$ with probability at least $1-\frac{\delta\mathscr{E}}{2\Delta_{f}}$.

Since a perturbation has not been added in iterations $\tau\in[-\mathscr{T},0)$, according to PAGD (Algorithm 2), we add perturbation at $t=0$, the Hamiltonian will increase by at most:

where the last step is due to our choice of $r=\eta\epsilon\cdot\chi^{-5}c^{-8}$ in (3) with constant $c$ sufficiently large. Again by Algorithm 2, a perturbation will never be added in the remaining iterations, and by Lemma 4 and Lemma 12 we know the Hamiltonian always decreases for the remaining steps. Therefore, if at least one NCE step is performed in iteration $\tau\in[0,\mathscr{T}]$, by Lemma 12 we will decrease $2\mathscr{E}$ in that NCE step, and at most increase by $\mathscr{E}$ due to the perturbation. This immediately gives $E_{\mathscr{T}}-E_{0}\leq-\mathscr{E}$.

Thus, with probability at least $1-\frac{\delta\mathscr{E}}{\Delta_{f}}$, the perturbation will end up outside of $\mathcal{X}_{\text{stuck}}$, which give $E_{\mathscr{T}}-E_{0}\leq-\mathscr{E}$. This finishes the proof.

B.4 Proof of Theorem 3

Our main result is now easily obtained from Lemma 7 and Lemma 8.

Suppose we never encounter any $\epsilon$-second-order stationary point. Consider the set $\mathfrak{T}=\{\tau|\tau\in[0,\mathscr{T}]\text{~{}and~{}}\left\|{\nabla f(\mathbf{x}_{\tau})}\right\|\leq\epsilon\}$, and two cases: (1) $\mathfrak{T}=\varnothing$, in which case we know all gradients are large and by Lemma 7 we have $E_{\mathscr{T}}-E_{0}\leq-\mathscr{E}$; (2) $\mathfrak{T}\neq\varnothing$. In this case, define $\tau^{\prime}=\min\mathfrak{T}$; i.e., the earliest iteration where the gradient is small. Since by assumption, $\mathbf{x}_{\tau}^{\prime}$ is not an $\epsilon$-second-order stationary point, this gives $\nabla^{2}f(\mathbf{x}_{\tau^{\prime}})\leq-\sqrt{\rho\epsilon}$, and by Lemma 8, we can conclude $E_{\tau^{\prime}+\mathscr{T}}-E_{0}\leq E_{\tau^{\prime}+\mathscr{T}}-E_{\tau^{\prime}}\leq-\mathscr{E}$. Clearly $\tau^{\prime}+\mathscr{T}\leq 2\mathscr{T}$. That is, in either case, we will decrease the Hamiltonian by $\mathscr{E}$ in at most $2\mathscr{T}$ steps.

Then, for the the first case, we can repeat this argument starting at iteration $\mathscr{T}$, and for the second case, we can repeat the argument starting at iteration $\tau^{\prime}+\mathscr{T}$. Therefore, we will continue to obtain a decrease of the Hamiltonian by an average of $\mathscr{E}/(2\mathscr{T})$ per step. Since the function $f$ is lower bounded, we know the Hamiltonian can not decrease beyond $E_{0}-E^{\star}=f(\mathbf{x}_{0})-f^{\star}$, which means that in $\frac{2(f(\mathbf{x}_{0})-f^{\star})\mathscr{T}}{\mathscr{E}}$ steps, we must encounter an $\epsilon$-second-order stationary point at least once.

Finally, in $\frac{2(f(\mathbf{x}_{0})-f^{\star})\mathscr{T}}{\mathscr{E}}$ steps, we will call Lemma 8 at most $\frac{2\Delta_{f}}{\mathscr{E}}$ times, and since Lemma 8 holds with probability $1-\frac{\delta\mathscr{E}}{2\Delta_{f}}$, by a union bound, we know that the argument above is true with probability at least:

Appendix C Auxiliary Lemma

In this section, we present some auxiliary lemmas which are used in proving Lemma 16, Lemma 17 and Lemma 18. These deal with the large-gradient scenario (nonconvex component), the large-gradient scenario (strongly convex component), and the negative curvature scenario, respectively.

The first two lemmas establish some facts about powers of the structured matrices arising in AGD.

When the eigenvalues $\mu_{1}$ and $\mu_{2}$ are distinct, the matrix $\mathbf{A}$ can be rewritten as $\begin{pmatrix}\mu_{1}+\mu_{2}&-\mu_{1}\mu_{2}\\ 1&0\end{pmatrix}$, and it is easy to check that the two eigenvectors have the form $\begin{pmatrix}\mu_{1}\\ 1\end{pmatrix}$ and $\begin{pmatrix}\mu_{2}\\ 1\end{pmatrix}$. Therefore, we can write the eigen-decomposition as:

and the $t$th power has the general form:

When there are two repeated eigenvalue $\mu_{1}$, the matrix $\begin{pmatrix}a&b\\ 1&0\end{pmatrix}$ can be rewritten as $\begin{pmatrix}2\mu_{1}&-\mu_{1}^{2}\\ 1&0\end{pmatrix}$. It is easy to check that $\mathbf{A}$ has the following Jordan normal form:

The remainder of the proof follows from simple linear algebra calculations for both cases. ∎

When $\mu_{1}$ and $\mu_{2}$ are distinct, we have:

When $\mu_{1},\mu_{2}$ are repeated, we have:

The remainder of the proof follows from Lemma 22 and linear algebra. ∎

The next lemma tells us when the eigenvalues of the AGD matrix are real and when they are complex.

Let $\theta\in(0,\frac{1}{4}]$, $\mathbf{x}\in[-\frac{1}{4},\frac{1}{4}]$ and define the $2\times 2$ matrix $\mathbf{A}$ as follows:

Then the two eigenvalues $\mu_{1}$ and $\mu_{2}$ of $\mathbf{A}$ are solutions of the following equation:

Moreover, when $x\in[-\frac{1}{4},\frac{\theta^{2}}{(2-\theta)^{2}}]$, $\mu_{1}$ and $\mu_{2}$ are real numbers, and when $x\in(\frac{\theta^{2}}{(2-\theta)^{2}},\frac{1}{4}]$, $\mu_{1}$ and $\mu_{2}$ are conjugate complex numbers.

An eigenvalue $\mu$ of the matrix $\mathbf{A}$ must satisfy the following equation:

Then $\mu_{1}$ and $\mu_{2}$ are real if and only if $\Delta\geq 0$, which finishes the proof. ∎

Finally, we need a simple lemma for geometric sums.

For any $\lambda>0$ and fixed $t$, we have:

All the lemmas in this section are concerned with the behavior of the AGD matrix for eigen-directions of the Hessian with eigenvalues being negative or small and positive, as used in proving Lemma 16. The following lemma bounds the smallest eigenvalue of the AGD matrix for those directions.

Under the same setting as Lemma 21, and for $x\in[-\frac{1}{4},\frac{\theta^{2}}{(2-\theta)^{2}}]$, where $\mu_{1}\geq\mu_{2}$, we have:

Let $f(u)=u^{2}+\theta u+2xu-x\theta u+x$. To prove $\mu_{2}(\mathbf{A})\leq 1-\frac{\sqrt{|x|}}{2}$ when $x\in[-\frac{1}{4},-\theta^{2}]$, we only need to verify $f(-\frac{\sqrt{|x|}}{2})\leq 0$:

The last inequality follows because $|x|\leq\frac{1}{4}$ by assumption.

On the other hand, when $x\in[0,\theta^{2}/(2-\theta)^{2}]$, both eigenvalues are still real, and the midpoint of the two roots is:

Combining the two cases, we have shown that when $x\in[-\theta^{2},\theta^{2}/(2-\theta)^{2}]$ we have $\mu_{2}(\mathbf{A})\leq 1-\frac{\theta}{2}$.

In the same setting as above, the following lemma bounds the largest eigenvalue.

Under the same setting as Lemma 21, and with $x\in[-\frac{1}{4},\frac{\theta^{2}}{(2-\theta)^{2}}]$, and letting $\mu_{1}\geq\mu_{2}$, we have:

By Lemma 21 and Vieta’s formula， we have:

An application of Lemma 23 finishes the proof. ∎

The following lemma establishes some properties of the powers of the AGD matrix.

Consider the same setting as Lemma 21, and let $x\in[-\frac{1}{4},\frac{\theta^{2}}{(2-\theta)^{2}}]$. Denote:

Then, for any $t\geq\frac{2}{\theta}+1$, we have:

We prove the two inequalities seperately.

The last inequality holds because in $\sum_{i=0}^{\tau}(\frac{\mu_{1}}{\mu_{2}})^{\frac{\tau}{2}-i}$ at least $\frac{\tau}{2}$ terms are greater than one. Finally, since $x\leq\theta^{2}/(2-\theta)^{2}\leq\theta^{2}\leq\theta$, we have $1-x\geq 1-\theta$, thus:

Second Inequality: Without loss of generality, assume $\mu_{1}\geq\mu_{2}$. Again by Lemma 19:

The second-to-last inequality holds because it is easy to check

for any $\tau\geq(t-1)/2$. Finally, by Lemma 24, we have

Since $\mu_{1}=\Theta(1)$, $\mu_{2}=\Theta(1)$, we have that when $|x|\leq\theta^{2}$,

Combining the two cases finishes the proof. ∎

C.2 Large-gradient scenario (strongly convex component)

All the lemmas in this section are concerned with the behavior of the AGD matrix for eigen-directions of the Hessian with eigenvalues being large and positive, as used in proving Lemma 17. The following lemma gives eigenvalues of the AGD matrix for those directions.

Under the same setting as Lemma 21, and with $x\in(\frac{\theta^{2}}{(2-\theta)^{2}},\frac{1}{4}]$, we have $\mu_{1}=re^{i\phi}$ and $\mu_{2}=re^{-i\phi}$, where:

By Lemma 21, we know that $\mu_{1}$ and $\mu_{2}$ are two solutions of

This gives $r^{2}=\mu_{1}\mu_{2}=(1-\theta)(1-x)$. On the other hand, discriminant is equal to

Under the same setting as above, the following lemma delineates some properties of powers of the AGD matrix.

Under the same setting as in Lemma 21, and with $x\in(\frac{\theta^{2}}{(2-\theta)^{2}},\frac{1}{4}]$, denote:

By Lemma 19 and Lemma 26, using $|\cdot|$ to denote the magnitude of a complex number, we have:

Reorganizing these two equations finishes the proof. ∎

The following is a technical lemma which is useful in bounding the change in the Hessian by the amount of oscillation in the iterates.

Under the same setting as Lemma 26, for any $T\geq 0$, any sequence $\{\epsilon_{t}\}$, and any $\varphi_{0}\in[0,2\pi]$:

Let $\tau=\lfloor 2\pi/\phi\rfloor$ be the approximate period, and $J=\lfloor T/\tau\rfloor$ be the number of periods that exist within time $T$. Then, we can group the summation by each period:

We prove the lemma by bounding the first term and the second term on the right-hand-side of this equation separately.

Term 2: Since $r\leq 1$, it is not hard to see:

Term 1: We first study the inner-loop factor, $\sum_{t=j\tau}^{(j+1)\tau-1}r^{t}\sin(\phi t)$. Letting $\psi=2\pi-\tau\phi$ be the offset for each approximate period, we have that for any $j<J$:

Combined with the fact that for all $y\in$ we have $e^{-3y}\leq 1-y\leq e^{-y}$, we obtain the following:

Also, for any $a,b\in$, we have $(1-ab)^{2}\leq(1-\min\{a,b\})^{2}\leq(1-a^{2})^{2}+(1-b^{2})^{2}$, and by definition of $\tau$, we immediately have $\psi\leq\phi$. This yields:

The second last inequality used the fact that $r=\Theta(1)$ (although note $r^{\tau}$ is not $\Theta(1)$). The last inequality is true since by Lemma 26, we know $(\theta+x)/\sin^{2}\phi\geq\Omega(1)$. This gives:

and therefore, we can now bound the first term:

The second-to-last inequality used Eq.(17). In conclusion, since $\tau\leq\frac{2\pi}{\phi}\leq\frac{2\pi}{\sin\phi}$, we have:

The following lemma combines the previous two lemmas to bound the approximation error in the quadratic.

Under the same setting as Lemma 21, and with $x\in(\frac{\theta^{2}}{(2-\theta)^{2}},\frac{1}{4}]$, denote:

Then, for any sequence $\{\epsilon_{\tau}\}$, any $t\geq\Omega(\frac{1}{\theta})$, we have:

We prove the two inequalities separately.

First Inequality: Since $x\in(\frac{\theta^{2}}{(2-\theta)^{2}},\frac{1}{4}]$, we further split the analysis into two cases:

Case $x\in(\frac{\theta^{2}}{(2-\theta)^{2}},\frac{2\theta^{2}}{(2-\theta)^{2}}]$: By Lemma 19, we can expand dthe left-hand-side as:

Noting that in this case $x=\Theta(\theta^{2})$, by Lemma 27 and Lemma 22, we have for $t\geq O(1/\theta)$:

Case $x\in(\frac{2\theta^{2}}{(2-\theta)^{2}},\frac{1}{4}]$: Again, we expand the left-hand-side as:

Noting in this case that $x=\Theta(\sin^{2}\phi)$ by Lemma 26, then by Lemma 28 we have:

Second Inequality: Using Lemma 19, we know:

where we note $r=\Theta(1)$ and the coefficient of the first term is upper bounded by the following:

As in the proof of the first inequality, we split the analysis into two cases:

Case $x\in(\frac{\theta^{2}}{(2-\theta)^{2}},\frac{2\theta^{2}}{(2-\theta)^{2}}]$: Again, we use

Noting $x=\Theta(\theta^{2})$, again by Lemma 22 and $|\frac{\sin\tau\phi}{\sin\phi}|\leq\tau$, we have:

Case $x\in(\frac{2\theta^{2}}{(2-\theta)^{2}},\frac{1}{4}]$: From the above derivation, we have:

According to Lemma 26, in this case $x=\Theta(\sin^{2}\phi)$, $r=\Theta(1)$ and since $\Omega(\theta^{2})\leq x\leq O(1)$, we have:

Putting all the pieces together finishes the proof. ∎

C.3 Negative-curvature scenario

In this section, we will prove the auxiliary lemmas required for proving Lemma 18.

The first lemma lower bounds the largest eigenvalue of the AGD matrix for eigen-directions whose eigenvalues are negative.

Under the same setting as Lemma 21, and with $x\in[-\frac{1}{4},0]$, and $\mu_{1}\geq\mu_{2}$, we have:

Let $f(u)=u^{2}+\theta u+2xu-x\theta u+x$. To prove $\mu_{1}(\mathbf{A})\geq 1+\frac{\sqrt{|x|}}{2}$ when $x\in[-\frac{1}{4},-\theta^{2}]$, we only need to verify $f(\frac{\sqrt{|x|}}{2})\leq 0$:

The last inequality holds because $\theta\leq\sqrt{|x|}$ in this case.

where the last inequality is due to $\theta^{2}\geq|x|$.

The next lemma is a technical lemma on large powers.

Under the same setting as Lemma 21, and with $x\in[-\frac{1}{4},0]$, denote

Let $\mu_{1}$ and $\mu_{2}$ be the two eigenvalues of the matrix $\mathbf{A}$, where $\mu_{1}\geq\mu_{2}$. Since $x\in[-\frac{1}{4},0]$, according to Lemma 21 and Lemma 23, we have $0\leq\mu_{2}\leq 1-\frac{\theta}{2}\leq 1\leq\mu_{1}$, and thus expanding both sides using Lemma 19 yields:

The following lemma gives properties of the $(1,1)$ element of large powers of the AGD matrix.

Let the $2\times 2$ matrix $\mathbf{A}(x)$ be defined as follows and let $x\in[-\frac{1}{4},0]$ and $\theta\in(0,\frac{1}{4}]$.

For any fixed $t>0$, letting $g(x)=\left|{\begin{pmatrix}1&0\end{pmatrix}[\mathbf{A}(x)]^{t}\begin{pmatrix}1\\ 0\end{pmatrix}}\right|$, then we have:

$g(x)$ is a monotonically decreasing function for $x\in[-1,\theta^{2}/(2-\theta)^{2}]$.

For any $x\in[\theta^{2}/(2-\theta)^{2},1]$, we have $g(x)\leq g(\theta^{2}/(2-\theta)^{2})$.

For $x\in[-1,\theta^{2}/(2-\theta)^{2}]$, we know that $\mathbf{A}(x)$ has two real eigenvalues $\mu_{1}(x)$ and $\mu_{2}(x)$, Without loss of generality, we can assume $\mu_{1}(x)\geq\mu_{2}(x)$. By Lemma 19, we know:

By Lemma 21 and Vieta’s formulas, we know that $[\mu_{1}(x)\mu_{2}(x)]^{\frac{t}{2}}=[(1-\theta)(1-x)]^{\frac{t}{2}}$ is monotonically decreasing in $x$. On the other hand, we have that:

is monotonically decreasing in $x$, implying that $\sum_{i=0}^{t}\left[\frac{\mu_{1}(x)}{\mu_{2}(x)}\right]^{\frac{t}{2}-i}$ is monotonically decreasing in $x$. Since both terms are positive, this implies the product is also monotonically decreasing in $x$, which finishes the proof of the first part.

For $x\in[\theta^{2}/(2-\theta)^{2},1]$, the two eigenvalues $\mu_{1}(x)$ and $\mu_{2}(x)$ are conjugate, and we have:

and this finishes the proof of the second part. ∎

The following lemma gives properties of the sum of the first row of large powers of the AGD matrix.

Under the same setting as Lemma 21, and with $x\in[-\frac{1}{4},0]$, denote

Since $x<0$, we know that $\mathbf{A}$ has two distinct real eigenvalues. Let $\mu_{1}$ and $\mu_{2}$ be the two eigenvalues of $\mathbf{A}$. For the first inequality, by Lemma 19, we only need to prove:

Taking the difference of the LHS and RHS, we have:

According to Lemma 21 and Lemma 23, $\mu_{1}\geq 1\geq\mu_{2}\geq 0$, which finishes the proof of the first claim.

For the second inequality, again by Lemma 19, since both $\mu_{1}$ and $\mu_{2}$ are positive, we have:

By Lemma 23 we have $1-\mu_{2}\geq\frac{\theta}{2}$, By Lemma 30 we know $\mu_{1}\geq 1+\frac{1}{2}\min\{\frac{|x|}{\theta},\sqrt{|x|}\}$. Combining these facts finishes the proof. ∎