Escaping Saddle Points with Adaptive Gradient Methods

Introduction

Adagrad uses the square root of the sum of the outer product of the past gradients to achieve adaptivity. In particular, at time step $t$, Adagrad updates the parameters in the following manner:

where $g_{t}$ is a noisy stochastic gradient at $x_{t}$ and $G_{t}=\sum_{i=1}^{t}g_{i}g_{i}^{T}$. More often, a diagonal version of Adagrad is used due to practical considerations, which effectively yields a per parameter learning rate. In the convex setting, Adagrad achieves provably good performance, especially when the gradients are sparse. Although Adagrad works well in sparse convex settings, its performance appears to deteriorate in (dense) nonconvex settings. This performance degradation is often attributed to the rapid decay of the learning rate in Adagrad over time, which is a consequence of rapid increase in eigenvalues of the matrix $G_{t}$.

To tackle this issue, variants of Adagrad such as Adam and RMSProp have been proposed, which replace the sum of the outer products with an exponential moving average i.e., $G_{t}=(1-\beta)\sum_{i=1}^{t}\beta^{t-i}g_{i}g_{i}^{T}$ for some constant $\beta\in(0,1)$. This connection with Adagrad is often used to justify the design of Adam and RMSProp (e.g. [Goodfellow et al., 2016]). Although this connection is simple and appealing, it is clearly superficial. For instance, while learning rates in Adagrad decrease monotonically, it is not necessarily the case with Adam or RMSProp as shown recently in Reddi et al. [2018b], leading to their non-convergence in even simple convex settings. Thus, a principled understanding of these adaptive methods is largely missing.

In this paper, we introduce a much simpler way of thinking about adaptive methods such as Adam and RMSProp. Roughly, adaptive methods try to precondition SGD by some matrix $A$, e.g. when $A$ is diagonal, $A_{ii}$ corresponds to the effective stepsize for coordinate $i$. For some choices of $A$ the algorithms do not have oracle access to $A$, but instead form an estimate $\hat{A}\approx A$. We separate out these two steps, by 1) giving convergence guarantees for an idealized setting where we have access to $A$, then 2) proving bounds on the quality of the estimate $\hat{A}$. Our approach makes it possible to effectively intuit about the algorithms, prove convergence guarantees (including second-order convergence), and give insights about how to choose algorithm parameters. It also leads to a number of surprising results, including an understanding of why the Reddi et al. [2018b] counterexample is hard for adaptive methods, why adaptive methods tend to escape saddle points faster than SGD (observed in [Reddi et al., 2018a]), insights into how to tune Adam’s parameters, and (to our knowledge) the first second-order convergence proof for any adaptive method.

In addition to the aforementioned novel viewpoint, we also make the following key contributions:

We develop a new approach for analyzing convergence of adaptive methods leveraging the preconditioner viewpoint and by way of disentangling estimation from the behavior of the idealized preconditioner.

We provide second-order convergence results for adaptive methods, and as a byproduct, first-order convergence results. To the best of our knowledge, ours is the first work to show second order convergence for any adaptive method.

We provide theoretical insights on how adaptive methods escape saddle points quickly. In particular, we show that the preconditioner used in adaptive methods leads to isotropic noise near stationary points, which helps escape saddle points faster.

Our analysis also provides practical suggestions for tuning the exponential moving average parameter $\beta$.

1 Related work

There is an immense amount of work studying nonconvex optimization for machine learning, which is too much to discuss here in detail. Thus, we only briefly discuss two lines of work that are most relevant to our paper here. First, the recent work e.g. [Chen et al., 2018; Reddi et al., 2018b; Zou et al., 2018] to understand and give theoretical guarantees for adaptive methods such as Adam and RMSProp. Second, the technical developments in using first-order algorithms to achieve nonconvex second-order convergence (see Definition 2.1) e.g. [Ge et al., 2015; Allen-Zhu and Li, 2018; Jin et al., 2017; Lee et al., 2016].

Many recent works have investigated convergence properties of adaptive methods. However, to our knowledge, all these results either require convexity or show only first-order convergence to stationary points. Reddi et al. [2018b] showed non-convergence of Adam and RMSProp in simple convex settings and provided a variant of Adam, called AMSGrad, with guaranteed convergence in the convex setting; Zhou et al. generalized this to a nonconvex first-order convergence result. Zaheer et al. showed first-order convergence of Adam when the batch size grows over time. Chen et al. bound the nonconvex convergence rate for a large family of Adam-like algorithms, but they essentially need to assume the effective stepsize is well-behaved (as in AMSGrad). Agarwal et al. give a convex convergence result for a full-matrix version of RMSProp, which they extend to the nonconvex case via iteratively optimizing convex functions. Their algorithm uses a fixed sliding window instead of an exponential moving average. Mukkamala and Hein prove improved convergence bounds for Adagrad in the online strongly convex case; they prove similar results for RMSProp, but only in a regime where it is essentially the same as Adagrad. Ward et al. give a nonconvex convergence result for a variant of Adagrad which employs an adaptively decreasing single learning rate (not per-parameter). Zou et al. give sufficient conditions for first-order convergence of Adam.

Starting with Ge et al. there has been a resurgence in interest in giving first-order algorithms that find second order stationary points of nonconvex objectives, where the gradient is small and the Hessian is nearly positive semidefinite. Most other results in this space operate in the deterministic setting where we have exact gradients, with carefully injected isotropic noise to escape saddle points. Levy show improved results for normalized gradient descent. Some algorithms rely on Hessian-vector products instead of pure gradient information e.g. [Agarwal et al., 2017; Carmon et al., 2018]; it is possible to reduce Hessian-vector based algorithms to gradient algorithms [Xu et al., 2018; Allen-Zhu and Li, 2018]. Jin et al. improve the dependence on dimension to polylogarithmic. Mokhtari et al. work towards adapting these techniques for constrained optimization. Most relevant to our work is that of Daneshmand et al. , who prove convergence of SGD with better rates than Ge et al. . Our work differs in that we provide second-order results for preconditioned SGD.

Notation and definitions

As is standard (e.g. Nesterov and Polyak ), we will discuss only $(\tau,\sqrt{\rho\tau})$-stationary points, where $\rho$ is the Lipschitz constant of the Hessian.

The RMSProp Preconditioner

Before developing our formal results, we will build intuition about the behavior of adaptive methods by studying an idealized adaptive method (IAM) with perfect access to $G_{t}$. In the rest of this section, we make use of idealized RMSProp to answer some simple questions about adaptive methods that we feel have not yet been addressed satisfactorily.

Our IAM abstraction makes it easy to explain precisely how rescaling the gradient noise helps. Specifically, we manipulate the update rule for idealized RMSProp:

2 [Reddi et al., 2018b] counterexample resolution

The counterexample is an optimization problem of the form

which is a constant independent of $x$. Hence the preconditioner is constant, and, up to the choice of stepsize, idealized RMSProp on this problem is the same as SGD, which of course will converge.

Main Results: Gluing Estimation and Optimization

The key enabling insight of this paper is to separately study the preconditioner and its estimation via EMA, then combine these to give proofs for practical adaptive methods. We will prove a formal guarantee that the EMA estimate $\hat{G}_{t}$ is close to the true $G_{t}$. By combining our estimation results with the underlying behavior of the preconditioner, we will be able to give convergence proofs for practical adaptive methods that are constructed in a novel, modular way.

The above discussion about IAM is helpful for intuition, and as a base algorithm for analyzing convergence. But it remains to understand how well the estimation procedure works, both for intuition’s sake and for later use in a convergence proof. In this section we introduce an abstraction we name “estimation from moving sequences.” This abstraction will allow us to guarantee high quality estimates of the preconditioner, or, for that matter, any similarly constructed preconditioner. Our results will moreover make apparent how to choose the $\beta$ parameter in the exponential moving average: $\beta$ should increase with the stepsize $\eta$. Increasing $\beta$ over time has been supported both empirically [Shazeer and Stern, 2018] as well as theoretically [Mukkamala and Hein, 2017; Zou et al., 2018; Reddi et al., 2018b], though to our knowledge, the precise pinning of $\beta$ to the stepsize $\eta$ is new.

We consider estimators of the form $\sum_{t=1}^{T}w_{t}Y_{t}$. For example. setting $w_{T}=1$ and all others to zero would yield an unbiased (but high variance) estimate of $G(x_{T})$. We could assign more mass to older samples $Y_{t}$, but this will introduce bias into the estimate. By optimizing this bias-variance tradeoff, we can get a good estimator. In particular, taking $w$ to be an exponential moving average (EMA) of $\{Y_{t}\}_{t=1}^{T}$ will prioritize more recent and relevant estimates, while placing enough weight on old estimates to reduce the variance. The tradeoff is controlled by the EMA parameter $\beta$; e.g. if the sequence $x_{t}$ moves slowly (the stepsize is small), we will want large $\beta$ because older iterates are still very relevant.

A $(W,T,\eta,\Delta,\delta)$-estimable matrix sequence is a sequence of matrices $\{A(x_{t})\}_{t=1}^{W+T}$ generated from $\{x_{t}\}_{t}$ with $\lVert x_{t}-x_{t-1}\rVert\leq\eta$ so that with probability $1-\delta$, after a burn-in of time $W$, we can achieve an estimate sequence $\{\hat{A}_{t}\}$ so that $\lVert\hat{A}_{t}-A_{t}\rVert\leq\Delta$ simultaneously for all times $t=W+1,\dots,W+T$.

Applying Theorem 4.1 and union bounding over all time $t=W+1,\dots,W+T$, we may state a concise result in terms of Definition 4.1:

We are hence guaranteed a good estimate of $G$. What we actually want, though, is a good estimate of the preconditioner $A=(G+\varepsilon I)^{-1/2}$. In Appendix G we show how to bound the quality of an estimate of $A$. One simple result is:

2 Convergence Results

We saw in the last two sections that it is simple to reason about adaptive methods via IAM, and that it is possible to compute a good estimate of the preconditioner. But we still need to glue the two together in order to get a convergence proof for practical adaptive methods.

In this section we will give non-convex convergence results, first for IAM and then for practical realizations thereof. We start with first-order convergence as a warm-up, and then move on to second-order convergence. In each case we give a bound for IAM, study it, and then give the corresponding bound for practical adaptive methods.

In Appendix C we provide bounds on these constants for several variants of the second moment preconditioner. Below we highlight the two most relevant cases, corresponding to SGD and RMSProp:

The preconditioner $A=(G+\varepsilon I)^{-1/2}$ is a $(\Lambda_{1},\Lambda_{2},\Gamma,\nu,\lambda_{-})$-preconditioner, with

2.2 First-order convergence

Proofs are given in Appendix E. For all first-order results, we assume that $A$ is a $(\cdot,\cdot,\Gamma,\cdot,\lambda_{-})$-preconditioner. The proof technique is essentially standard, with minor changes in order to accomodate general preconditioners. First, suppose we have exact oracle access to the preconditioner:

Run preconditioned SGD with preconditioner $A$ and stepsize $\eta=\tau^{2}\lambda_{-}/(L\Gamma)$. For small enough $\tau$, after $T=2(f(x_{0})-f^{*})L\Gamma/(\tau^{4}\lambda_{-}^{2})$ iterations,

Now we consider an alternate version where instead of the preconditioner $A_{t}$, we precondition by an noisy version $\hat{A}_{t}$ that is close to $A_{t}$, i.e. $\lVert\hat{A}_{t}-A_{t}\rVert\leq\Delta$.

Suppose we have access to an inexact preconditioner $\hat{A}$, which satisfies $\lVert\hat{A}-A\lVert\leq\Delta$ for $\Delta<\lambda_{-}/2$. Run preconditioned SGD with preconditioner $\hat{A}$ and stepsize $\eta=\tau^{2}\lambda_{-}/(4\sqrt{2}L\Gamma)$. For small enough $\tau$, after $T=32(f(x_{0})-f^{*})L\Gamma/(\tau^{4}\lambda_{-}^{2})$ iterations, we will have

The results are the same up to constants. In other words, as long as we can achieve less than $\lambda_{-}/2$ error, we will converge at essentially the same rate as if we had the exact preconditioner. In light of this, for the second-order convergence results, we treat only the noisy version.

Theorem 4.3 gives a convergence bound assuming a good estimate of the preconditioner, and our estimation results guarantee a good estimate. By gluing together Theorem 4.3 with our estimation results for the RMSProp preconditioner, i.e. Proposition 4.2, we can give a convergence result for bona fide RMSProp:

Consider RMSProp with burn-in, as in Algorithm 3, where we estimate $A=(G+\varepsilon I)^{-1/2}$. Retain the same choice of $\eta=O(\tau^{2})$ and $T=O(\tau^{-4})$ as in Theorem 4.3. For small enough $\tau$, such a choice of $\eta$ will yield $\Delta<\lambda_{-}/2$. Choose all other parameters e.g. $\beta$ in accordance with Proposition 4.2. In particular, choose $W=\Theta(\eta^{-2/3})=\Theta(\tau^{-4/3})=O(T)$ for the burn-in parameter. Then with probability $1-\delta$, in overall time $O(W+T)=O(\tau^{-4})$, we achieve

2.3 Second-order convergence

Now we leverage the power of our high level approach to prove nonconvex second-order convergence for adaptive methods. Like the first-order results, we start by proving convergence bounds for a generic, possibly inexact preconditioner $A$. Our proof is based on that of Daneshmand et al. , though our study of the preconditioner is wholly new. Accordingly, we study the convergence of Algorithm 4, which is the same as Algorithm 1 (generic preconditioned SGD) except that once in a while we take a large stepsize so we may escape saddlepoints. The proof is given completely in Appendix D. At a high level, we show the algorithm makes progress when the gradient is large and when we are at a saddle point, and does not escape from local minima. Our analysis uses all the constants specified in Definition 4.2, e.g. the speed of escape from saddle points depends on $\nu$, the lower bound on stochastic gradient noise.

Then, as before, we simply fuse our convergence guarantees with our estimation guarantees. The end result is, to our knowledge, the first nonconvex second-order convergence result for any adaptive method.

Consider Algorithm 4 with inexact preconditioner $\hat{A}_{t}$ and exact preconditioner $A_{t}$ satisfying the preceding requirements. Suppose that for all $t$, we have $\lVert\hat{A}_{t}-A_{t}\rVert=O(\tau^{1/2})$. Then for small $\tau$, with probability $1-\delta$, we reach an $(\tau,\sqrt{\rho\tau})$-stationary point in time

The big-O suppresses other constants given in the proof.

Consider the RMSProp version of Algorithm 4 that is described in Appendix B. Retain the same choice of $\eta=O(\tau^{5/2})$, $r=O(\tau)$, and $T=O(\tau^{-5})$ as in Theorem 4.4. For small enough $\tau$, such a choice of $\eta$ will yield $\Delta<\lambda_{-}/2$. Choose $W=\Theta(\eta^{-2/3})=\Theta(\tau^{-5/3})=O(T)$ for the burn-in parameter Choose $S=O(\tau^{-3/2})$, so that as far as the estimation scheme is concerned, the stepsize is bounded by $\max\{\eta,r/S\}=O(\tau^{5/2})=O(\eta)$. Then as before, with probability $1-\delta$, we can reach an $(\tau,\sqrt{\rho\tau})$-stationary point in total time

where $\Lambda_{1},\Lambda_{2},\Gamma,\nu,\lambda_{-}$ are the constants describing $A=(G+\varepsilon I)^{-1/2}$.

Discussion

Separating the estimation step from the preconditioning enables evaluation of different choices for the preconditioner.

In the adaptive methods literature, it is still a mystery how to properly set the regularization parameter $\varepsilon$ that ensures invertibility of $G+\varepsilon I$. When the optimality tolerance $\tau$ is small enough, estimating the preconditioner is not the bottleneck. Thus, focusing only on the idealized case, one could just choose $\varepsilon$ to minimize the bound. Our first-order results depend on $\varepsilon$ only through the following term:

where we have used the preconditioner bounds from Proposition 4.4. This is minimized by taking $\varepsilon\to\infty$, which suggests using identity preconditioner, or SGD. In contrast, for second-order convergence, the bound is

which is instead minimized with $\varepsilon=0$. So for the best second-order convergence rate, it is desireable to set $\varepsilon$ as small as possible. Note that since our bounds hold only for small enough convergence tolerance $\tau$, it is possible that the optimal $\varepsilon$ should depend in some way on $\tau$.

2 Comparison to SGD

Another important question we make progress towards is: when are adaptive methods better than SGD? Our second-order result depends on the preconditioner only through $\Lambda_{1}^{4}\Lambda_{2}^{4}\Gamma^{4}/(\lambda_{-}^{10}\nu^{4})$. Plugging in Proposition 4.3 for SGD, we may bound

3 Alternative preconditioners

4 Tuning the EMA parameter β𝛽\beta

Another mystery of adaptive methods is how to set the exponential moving average (EMA) parameter $\beta$. In practice $\beta$ is typically set to a constant, e.g. 0.99, while other parameters such as the stepsize $\eta$ are tuned more carefully and may vary over time. While our estimation guarantee Theorem 4.1, suggests setting $\beta=1-O(\eta^{2/3})$, the specific formula depends on constants that may be unknown, e.g. Lipschitz constants and gradient norms. Instead, one could set $\beta=1-C\eta^{2/3}$, and search for a good choice of the hyperparameter $C$. For example, the common initial choice of $\eta=0.001$ and $\beta=0.99$ corresponds to $C=1$.

Experiments

We experimentally test our claims about adaptive methods escaping saddle points, and our suggestion for setting $\beta$.

We initialize SGD and (diagonal) RMSProp (with $\beta=1-\eta^{2/3}$) at the saddle point and test several stepsizes $\eta$ for each. Results for the first $10^{4}$ iterations are shown in Figure 1. In order to escape the saddle point as fast as RMSProp, SGD requires a substantially larger stepsize, e.g. SGD needs $\eta=0.01$ to escape as fast as RMSProp does with $\eta=0.001$. But with such a large stepsize, SGD cannot converge to a small neighborhood of the local minimum, and instead bounces around due to gradient noise. Since RMSProp can escape with a small stepsize, it can converge to a much smaller neighborhood of the local minimum. Overall, for any fixed final convergence criterion, RMSProp escapes faster and converges faster overall.

Next, we test our recommendations regarding setting the EMA parameter $\beta$. We consider logistic regression on MNIST. We use (diagonal) RMSProp with batch size 100, decreasing stepsize $\eta_{t}=0.001/\sqrt{t}$ and $\varepsilon=10^{-8}$, and compare different schedules for $\beta$. Specifically we test $\beta\in\{0.7,0.9,0.97,0.99\}$ (so that $1-\beta$ is spaced roughly logarithmically) as well as our recommendation of $\beta_{t}=1-C\eta_{t}^{2/3}$ for $C\in\{0.1,0.3,1\}$. As shown in Figure 2, all options for $\beta$ have similar performance initially, but as $\eta_{t}$ decreases, large $\beta$ yields substantially better performance. In particular, our decreasing $\beta$ schedule achieved the best performance, and moreover was insensitive to how $C$ was set.

Acknowledgements

This work was supported in part by the DARPA Lagrange grant, and an Amazon Research Award. We thank Nicolas Le Roux for helpful conversations.

References

Appendix A More Insights from Idealized Adaptive Methods (IAM)

Both of the above issues with the natural gradient interpretation are also pointed out in Balles and Hennig , who argue that the primary function of adaptive methods is to equalize the stochastic gradient noise in each direction. But it is still not clear precisely why or how equalized noise should help optimization.

Taking $\varepsilon\to 0$, the idealized RMSProp update approaches

First, the actual descent direction is not changed, and curvature is totally absent. Second, the resulting algorithm is unstable unless $\eta$ decreases rapidly: as $x_{t}$ approaches a stationary point, the magnitude of the step $\nabla_{t}/\lVert\nabla_{t}\rVert^{2}$ grows arbitrarily large, making it impossible to converge without rapidly decreasing the stepsize.

By contrast, using the standard $-1/2$ exponent and taking $\varepsilon\to 0$ in the noiseless case yields normalized gradient descent:

In neither case do adaptive methods actually change the direction of descent (e.g. via curvature information); only the stepsize is changed.

Appendix B Algorithm Details

Per our estimation results in Section 4.1, we must alter RMSProp to ensure it achieves an accurate estimate of the preconditioner. Namely, before updating the parameter $x_{t}$, we need to burn-in the estimate for several iterations so the initial estimate $\hat{G}_{0}$ is accurate. This subroutine is given in Algorithm 5.

Later, when we prove second-order convergence, we need to modify RMSProp to occassionally take a large step. However, this complicates estimation: per Theorem 4.1, estimation quality deteriorates as the step size increases. Naively applying Theorem 4.1 to the large stepsize yields an estimate of $G$ that is not accurate enough. To get around this, every time RMSProp takes a large step, we will hallucinate a number of smaller steps to feed into the estimation procedure. This is formalized in Algorithm 6. Overall, the variant of RMSProp we study is formalized in Algorithm 7.

Appendix C Curvature and noise constants for different preconditioners

In the simplest case, $A=I$ and we merely run SGD. We reproduce Proposition 4.3:

The overall second-order complexity depends on

Clearly, $\Lambda_{1}=\Lambda_{2}=\lambda_{-}=1$. Then,

C.2 Constants for full matrix IAM

The preconditioner $A=(G+\varepsilon I)^{-1/2}$ is a $(\Lambda_{1},\Lambda_{2},\Gamma,\nu,\lambda_{-})$-preconditioner, with

Overall, the complexity depends on $\Lambda_{1}\Lambda_{2}\Gamma/\nu$:

Note that when $\varepsilon=0$ and we do not regularize the preconditioner, the complexity bound is

We can bound both $\Lambda_{1}$ and $\Lambda_{2}$ by

It follows that we can bound the trace of $A^{2}G$ by

Next, $\nu$ is a bound on the least eigenvalue of

Since $t\mapsto t/(t+\varepsilon)$ is increasing, it is minimized when $t$ is small. Therefore

C.3 Constants for diagonal IAM

so the overall second-order dependence is

If we set $\varepsilon=0$ and do not regularize the preconditioner, the complexity bound is

As before, we can bound both $\Lambda_{1}$ and $\Lambda_{2}$ by

For $\Gamma$, using the same manipulations as before, we want to bound

Again, bounding $\nu$ is difficult, as we would need to bound the least eigenvalue of

The first two terms are $\nu$ if we had not added $\varepsilon$ to $A$. The remaining terms can be bounded as before by

Appendix D Main Proof

Here we will study the convergence of Algorithm 4. This is the same as Algorithm 1 except that once in a while we take a large stepsize so we may escape saddlepoints.

The vector $u$ is not necessarily an eigenvector of $A^{1/2}HA^{1/2}$, but the above expression guarantees that $A^{1/2}HA^{1/2}$ has a negative eigenvalue with magnitude at least

Throughout, we will assume that $A$ is a $(\Lambda_{1},\Lambda_{2},\Gamma,\nu,\lambda_{-})$-preconditioner, that $\hat{A}$ also satisfies the $\Lambda_{1}$ inequality, and that $\lVert\hat{A}-A\rVert\leq\Delta$.

Differing from Daneshmand et al. , we will assume a uniform bound on $\lVert Ag\rVert\leq M$. In general this bound need not depend on either the spectrum of $A$ or any uniform bound on $g$. For example, if $g$ were Gaussian, $Ag$ would be a Gaussian with zero mean and identity covariance, so we would expect $\lVert Ag\rVert=O(\sqrt{d})$ with high probability. In general $M$ should have the same scale as $\sqrt{\Gamma}$, and the statement of Theorem 4.4 reflects this.

D.2 High level picture

For shorthand we write $A_{t}:=A(x_{t})$. Since we want to converge to a second order stationary point, our overall goal is to study the event

(where $t$ is obvious from context, we will omit it. In words, $\mathcal{E}_{t}$ is the event that we are not at a second order stationary point. The main theorem results from bounding the progress we make when $\mathcal{E}_{t}$ does not yet hold, while also ensuring we do not leave once we hit a second order stationary point:

Let $P_{t}$ be the probability that $\mathcal{E}_{t}$ occurs. Then,

Summing over all $T$ iterations, we have:

Write $\gamma=\lambda_{-}\sqrt{\rho}\tau^{1/2}$. Let $K$ be a universal constant. The parameter $\omega$ will be set later and depends only logarithmically on the other parameters. Set

In the above setting, with probability $1-\delta$, we reach an $(\tau,\sqrt{\rho}\tau^{1/2})$-stationary point in time

D.3 Amortized increase due to large stepsize iterations

Hence it suffices to bound the function increase conditioned on $\lVert\nabla f(x_{t})\rVert\leq\tau$. By Corollary D.2 we have

Cancelling like terms, we find that the inequality is equivalent to $\omega\geq 9/4$, which we can easily enforce later. Therefore we may indeed write that

In words, we split $\mathcal{E}_{t}$ into two cases: either the gradient is large, or we are near a saddlepoint but there is an escape direction.

If the norm of the gradient is large enough, i.e.

D.5.2 Sharp negative curvature regime

We start at a point $x_{0}$ around which we base our Hessian approximation:

For every twice differentiable $\rho$-Hessian Lipschitz function $f$ we have

With the above definitions in hand, we will form a stale Taylor expansion of $f$, and express it in terms of the above terms:

To proceed, we must bound all these terms.

We assume $A(x)$ is $\alpha$ Lipschitz, so that $\lVert A_{i}-A\rVert\leq\alpha\lVert x_{i}-x_{0}\rVert$. Then,

where for the last identity we have applied Lemma D.11. By Lemma D.12, we may further bound this by

Applying Lemma D.14 with $\beta=\eta\gamma$ yields:

where again, the last inequality comes from Lemma D.11. Applying Lemma D.14 with $\beta=\eta\gamma$ yields:

For small enough $\eta$, we have $\lVert\eta AH\rVert\leq 1$ and hence:

Under the above conditions, we get an exponentially growing lower bound on the expected squared norm of $u_{t}$:

We wish to choose a unit vector $v$ so that this is as large as possible. If $AH$ were symmetric, we could choose $v$ to be an eigenvector, but the product of symmetric matrices is not in general symmetric. However, because $A$ and $H$ are both symmetric, and $A$ is positive definite, it follows that $A^{1/2}$ exists and that $A^{1/2}HA^{1/2}$ is symmetric. Hence for orthonormal $U$ and diagonal $\Lambda$, we have

The diagonal matrix $\Lambda$ contains the eigenvalues of $A^{1/2}HA^{1/2}$. Without loss of generality, $\Lambda_{11}$ corresponds to a negative eigenvalue with absolute value $\gamma$. Therefore

Since we can choose $v$ to be any unit vector we want, we will set it equal to $C(U^{T}A^{1/2})^{-1}e_{1}$ so that $U^{T}A^{1/2}v=Ce_{1}$. Here $e_{1}$ is the first standard basis vector and $C$ is a scalar constant chosen to make $v$ a unit vector. Taking transposes, we have $v^{T}A^{1/2}U=Ce_{1}^{T}$. Now,

Substituting in the definition of $v$, this is equal to:

This equality holds for any $v$ of the form specified above; in particular, choose $C$ so that $v$ is unit. Then, we may finally bound

where the last two lines follow by the fact that $\lVert v\rVert=1$ and by definition of $\nu$. ∎

Under the above conditions we have a deterministic bound on $\lVert u_{t}\rVert$:

Putting all these results together, we can give a lower bound on the distance between iterates:

As long as the sum in the parentheses is positive, this term will grow exponentially and grant us the contradiction we seek. We want to bound each of the seven terms in brackets by $r\nu/8$, so that the overall bound is $r^{2}\kappa^{2t}\nu/8$. For simplicity, we will write $K=1/8$ as a universal constant. Then, we want to choose parameters so the following inequalities all hold.

We start with the last term (from $\iota_{t}$) because it is the most simple. Since $\gamma=\Theta(\tau^{1/2})$, we require that

Since we will eventually set $r=O(\tau)$, this constraint is simply $\Delta\leq O(\tau^{1/2})$.

Next we move onto the first three terms, which correspond to $\delta_{t}$:

The first constraint is satisfied for small enough $\tau$ because we chose $r=O(\tau)\leq O(\tau^{1/2})$. The second term is equivalent to

which trivially always holds since the two expressions are equal.

Finally, we address the three terms corresponding to $\chi_{t}$. For small enough $\tau$, it will turn out that none of the resulting constraints are tight, i.e. they are all weaker than some other constraint we already require. First,

Hence, for small enough $\tau$, for the above parameter settings, we have

We now have a lower bound and an upper bound that when combined yield $(1+\eta\gamma)^{2t}\leq C$, where

Remember, we are making the simplifying assumption that $\Lambda_{1}$ serves as a bound in the same way for $\hat{A}$ as it does for $A$. This is trivially true if $\Delta=0$. Applying the definition of $\Lambda_{1}$ yields:

By rearranging, we can get a bound on the gradient norms:

Before we proceed, note that we already have

Hence we can further bound equation (181) by

Now we will work toward bounding the norm of the difference $x_{t}-x_{0}$. We will first bound the difference $x_{t}-x_{1}$, then the difference $x_{1}-x_{0}$.

where $\xi_{i}=\hat{A}_{i}(\nabla f(x_{i})-g_{i})$ is the zero mean effective noise that arises from rescaling the stochastic gradient noise. We may write

where we have used Lemma D.15. We can then bound

Plugging this into Equation (185) yields:

D.6 Auxiliary lemmas

If $B^{2}\geq 4AC$, then $C/A-B^{2}/(2A)^{2}\leq 0$. Otherwise, $-2\sqrt{C/A}+B/A\leq 0$. Hence,

Let $0<x<1$. For $t\geq 2\log C/x$, we have $(1+x)^{t}\geq C$.

For $x<1$ we have $\log(1+x)\leq x-x^{2}/2\leq x/2$. Hence,

and the lemma follows by exponentiating both sides. ∎

For $0<\beta<1$ the following inequalities hold:

D.7 Descent lemmas

First we need a quick lemma relating the constants of the true preconditioner to those of an approximate preconditioner:

where the penultimate line follows by $\Delta<\lambda_{-}/2$ and $\Delta I\preceq\frac{1}{2}A_{t}$. ∎

Note that in the noiseless case $\Delta=0$, all the below results still apply, and we only lose a constant factor compared to the typical descent lemma.

Assume $f$ has $L$-Lipschitz gradient. Suppose we perform the updates $x_{t+1}\leftarrow x_{t}-\eta\hat{A}_{t}g_{t}$, where $g_{t}$ is a stochastic gradient, $A_{t}$ is a $(\Lambda_{1},\Lambda_{2},\Gamma,\nu,\lambda_{-})$-preconditioner, and $\lVert\hat{A}_{t}-A_{t}\rVert\leq\Delta<\frac{\lambda_{-}}{2}$. Then,

where the third line follows by Lemma D.15. ∎

Suppose $\eta\leq 4\lambda_{-}\lVert\nabla f(x_{0})\rVert^{2}/(9L\Gamma)$. Then,

Suppose $\lVert\nabla f(x_{0})\rVert^{2}\geq\tau^{2}$. Then if $\eta\leq 4\lambda_{-}\tau^{2}/(9L\Gamma)$

Appendix E Convergence to First-Order Stationary Points

Let $g$ be the stochastic gradient at time $t$. We will precondition by $A_{t}=A(x_{t})$. We write

Now rearrange, and bound $f(x_{T})$ by $f^{*}$ to get:

Optimally choosing $\eta=\sqrt{2(f(x_{0})-f^{*})/(TL\Gamma)}$ yields the overall bound

Rephrasing, in order to be guaranteed that the left hand term is bounded by $\tau^{2}$, it suffices to choose $T$ so that

E.2 Generic Preconditioners with Errors: Proof of Theorem 4.3

Let $g$ be the stochastic gradient at time $t$. We will precondition by $\hat{A}_{t}$ which satisfies $\lVert\hat{A}_{t}-A_{t}\rVert\leq\Delta<\lambda_{-}/2$. We write

where the penultimate line follows by $\Delta<\lambda_{-}/2$ and $\Delta I\preceq\frac{1}{2}A_{t}$. Summing and telescoping, and further bounding $9/8<2$, we have

Now rearrange, and bound $f(x_{T})$ by $f^{*}$ to get:

Optimally choosing $\eta=\sqrt{(f(x_{0})-f^{*})/(2TL\Gamma)}$ yields the overall bound

Rephrasing, in order to be guaranteed that the left hand term is bounded by $\tau^{2}$, it suffices to choose $T$ so that

Appendix F Online Matrix Estimation

We first reproduce the Matrix Freedman inequality as presented by Tropp :

In other words, we can deterministically bound $\lVert W_{n}\rVert\leq\sigma^{2}_{\text{max}}\lVert w\rVert_{2}^{2}$. Combining this bound with Theorem F.1, it follows that for any $k\geq 0$,

By assumption, $k\leq 3\lVert w\rVert_{2}^{2}\sigma^{2}_{\text{max}}/R$, so $Rk/3\leq\sigma^{2}_{\text{max}}\lVert w\rVert_{2}^{2}$, and we may further bound

Now we can apply the above matrix concentration results to prove Theorem 4.1:

Applying Corollary F.1 to the martingale difference sequence $Z_{t}=Y_{t}-G(x_{t})$, we have that

Setting the right hand side of the high probability bound to $\delta$, we have concentration w.p. $1-\delta$ for $k$ satisfying

Combining this with the triangle inequality,

with probability $1-\delta$. Since $1/\sqrt{1-\beta^{T}}\leq 1/(1-\beta^{T})$, this can further be bounded by

Write $\alpha=1-\beta$. The inner part of the bound is optimized when

If $T$ is sufficiently large, the $1/(1-\beta^{T})$ term will be less than 2. In particular,

Since $\log(1+\alpha)>\alpha/2$ for $\alpha<1$, it suffices to have $T>4/\alpha$. ∎

Appendix G Converting Noise Estimates into Preconditioner Estimates

Suppose $\lVert G-\hat{G}\rVert\leq\varepsilon$, i.e. $\hat{G}$ is a good estimate of $G$ in operator norm. Assume $\varepsilon$ is so small that $\varepsilon\lVert G^{-1}\rVert<1/2$. Then,

Grouping $\delta$ terms together, we find

By assumption $\varepsilon$ is small enough so that $\varepsilon\lVert G^{-1}\rVert<1/2$, so overall we have

By monotonicity of the matrix square root,

At this point we can bound each side by applying Lemma G.3 to $G$ and to $G-\varepsilon I$. The result is the bound

The lower bound is looser, so the operator norm of the difference is bounded by

Suppose $\lVert G-\hat{G}\rVert\leq\varepsilon$, for small enough $\varepsilon$. Then,

Simply apply Lemma G.1 and Lemma G.2 to $G+\delta I$. ∎