Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Introduction

Nonconvex stochastic optimization is crucial in machine learning and have attracted tremendous attentions and unprecedented popularity. Lots of modern tasks that include low-rank matrix factorization/completion and principal component analysis (Candès & Recht,, 2009; Jolliffe,, 2011), dictionary learning (Sun et al.,, 2017), Gaussian mixture models (Reynolds et al.,, 2000), as well as notably deep neural networks (Hinton & Salakhutdinov,, 2006) are formulated as nonconvex stochastic optimization problems. In this paper, we concentrate on finding an approximate solution to the following minimization problem:

Here, $F(\mathbf{x};\bm{\zeta})$ denotes a family of stochastic functions indexed by some random variable $\bm{\zeta}$ that obeys some prescribed distribution $\mathcal{D}$, and we consider the general case where $f(\mathbf{x})$ and $F(\mathbf{x};\bm{\zeta})$ have Lipschitz-continuous gradients and Hessians and might be nonconvex. In empirical risk minimization tasks, $\bm{\zeta}$ is an uniformly discrete distribution over the set of training sample indices, and the stochastic function $F(\mathbf{x};\bm{\zeta})$ corresponds to the nonconvex loss associated with such a sample.

where $\bm{\zeta}^{t}$ is randomly sampled at iteration $t$. SGD admits perhaps the simplest update rule among stochastic first-order methods. See Algorithm 1 for a formal illustration of the meta algorithm. It has gained tremendous popularity due to its exceptional practical performance. Taking the example of training deep neural networks, the dominating algorithm at present time is SGD (Abadi et al.,, 2016), where the stochastic gradient is computed via one backpropagation step. Superior characteristics of SGD have been observed in many empirical studies, including but not limited to fast convergence, desirable solutions of low training loss, as well as its generalization ability.

Turning to the theoretical side, relatively mature and concrete analysis in existing literatures Rakhlin et al., (2012); Agarwal et al., (2009) show that SGD achieves an optimal rate of convergence for convex objective function under some standard regime. Specifically, the convergence rate of $\mathcal{O}(1/T)$ in term of the function optimality gap match the algorithmic lower bound for an appropriate class of strongly convex functions (Agarwal et al.,, 2009).

Despite the optimal convex optimization rates that SGD achieves, the provable nonconvex SGD convergence rate result has long stayed upon on finding an $\epsilon$-approximate first-order stationary point $\mathbf{x}$: with high probability SGD finds an $\mathbf{x}$ such that $\|\nabla f(\mathbf{x})\|\leq\epsilon$ in $\mathcal{O}(\epsilon^{-4})$ stochastic gradient computational cost under the gradient Lipschitz condition of $f(\mathbf{x})$ (Nesterov,, 2004). In contrast, our goal in this paper is to find an $(\epsilon,\sqrt{\rho\epsilon})$-approximate second-order stationary point $\mathbf{x}$ such that $\|\nabla f(\mathbf{x})\|\leq\epsilon$ and the least eigenvalue of the Hessian matrix $\nabla^{2}f(\mathbf{x})$ is $\geq-\sqrt{\rho\epsilon}$, where $\rho>0$ denotes the so-called Hessian-Lipschitz parameter to be specified later (Nesterov & Polyak,, 2006; Tripuraneni et al.,, 2018; Carmon et al.,, 2018; Agarwal et al.,, 2017). Putting it differently, we need to escape from all first-order stationary points that admit a strong negative Hessian eigenvalue (a.k.a. saddle points) (Dauphin et al.,, 2014) and lands at a point that quantitatively resembles a local minimizer in terms of the gradient norm and least Hessian eigenvalue.

Is it possible to sharpen the analysis of SGD algorithm and obtain a reduced stochastic gradient computational cost for finding an $(\epsilon,\mathcal{O}(\epsilon^{0.5}))$-approximate second-order stationary point?

Is artificial noise injection absolutely necessary for SGD to find an approximate second-order stationary point with an almost dimension-free stochastic gradient computational cost?

We propose the dispersive noise assumption and prove that under such an assumption, SGD ensures to escape all saddles that has a strongly negative Hessian eigenvalue. Such type of noise generalizes the existing artificial ball-shaped noise and is widely applicable to many tasks.

Our novel analytic tools for proving saddle escaping and fast convergence of SGD is of independent interests, and they shed lights on developing and analyzing new stochastic optimization algorithms.

The rest of the paper is organized as follows. §2 provides the SGD algorithm and the main convergence rate theorem for finding an $(\epsilon,\sqrt{\rho\epsilon})$-approximate second-order stationary point. Related Works are discussed in §3. We conclude our paper in §4 with proposed future directions. In Appendix A, we sketch the proof of our convergence rate theorem by providing and discussing three core propositions. And all the missing proofs are detailed in the Appendix rest sections.

Notation

Algorithm and Main Result

In this section, we formally state SGD and the corresponding convergence rate theorem. In §2.1, we propose the key assumptions for the objective functions and noise distributions. In §2.2, we detail SGD in Algorithm 2 and present the main convergence rate theorem.

With Hessian-Lipschitz parameter $\rho$ prescribed in (2.2), we formally define the $(\epsilon,\sqrt{\rho\epsilon})$-approximate second-order stationary point. To best of our knowledge, such concept firstly appeared in Nesterov & Polyak, (2006):

Turning to the assumptions on noise, we first assume the following:

Assumptions 1, 2 and 3 are standard in nonconvex optimization literatures (Ge et al.,, 2015; Xu et al.,, 2018; Allen-Zhu & Li,, 2018; Fang et al.,, 2018). We treat the parameters $L$, $\rho$, $\Delta$, and $\sigma$ as global constants, and focus on the dependency for stochastic gradient complexity on $\epsilon$ and $d$.

For the purpose of fast saddles escaping, we need an extra noise shape assumption. Let $q^{*}$ be a positive real, and let $\mathbf{v}$ be a unit vector. We define a set property as follows:

Assumption 4 is motivated from the key lemma for escaping from saddle points in Jin et al., (2017), which obtains a sharp rate for gradient descent escaping from saddle points. Such an assumption enables SGD to move out of a stuck region with probability $\geq 3/4$ in its first step and enables escaping from saddle points (by repeating logarithmic rounds). We would like to emphasize that the $\mathbf{v}$-dispersive noises contain many canonical examples; see the following

Here we exemplify a few noise distributions that satisfy the $\mathbf{v}$-dispersive property, that is, for an arbitrary set $\mathcal{A}$ with $(q^{*},\mathbf{v})$-narrow property, where $q^{*}=\sigma/(4\sqrt{d})$. We have the following proposition:

For the following noise distributions, (2.5) in Definition 3 is satisfied:

The proof of Proposition 1 is shown in Appendix F.

2 SGD and Main Theorem

Our SGD algorithm for analysis purposes is detailed in Algorithm 2. Our SGD algorithm only differs from classical SGD algorithms on stopping criteria. Distinct from the classical ones that simply terminate in a certain number of steps and output the final iterate or a randomly drawn iterate, the SGD we consider here introduces a ball-controlled mechanism as the stopping criteria: if $\mathbf{x}^{k}$ exits a small neighborhood in $K_{0}$ iterations (Line 2 to 6), one starts over and do the next round of SGD; if exiting does not occur in $K_{0}$ iterations, then the algorithm simply outputs an arithmetic average of $\mathbf{x}^{k}$ of the last $K_{0}$ iterates within the neighborhood, which in turns is an $(\epsilon,\sqrt{\rho\epsilon})$-approximate second-order stationary point with high probability. In contrast with the stopping criteria in the deterministic setting that checks the descent in function values (Jin et al.,, 2017), the function value in stochastic setting is reasonably costly to approximate (costs $O(\epsilon^{-2})$ stochastic gradient computations), and the error plateaus might be hard to observe theoretically.

For brevity of analysis, we assume $B\leq\min(1,\frac{\sigma}{L},\frac{1}{L})\asymp\mathcal{O}(1)$, and $\delta\leq 1$. In other words, we assume the accuracy $\epsilon\leq\mathcal{O}(1)$.

Now we are ready to present our main result of SGD theorem.

Let Assumptions 1, 2, 3, and 4 hold. Let the parameters $K_{0}$, $\eta$ and $B$ be set in (2.2) with $p\in(0,1)$ being the error probability, and set $T_{1}=\left\lceil\frac{7\Delta\eta K_{0}}{B^{2}}\right\rceil+1\asymp\epsilon^{-1.5}$, then running Algorithm 2 in $T_{0}=T_{1}\cdot K_{0}\asymp\frac{\Delta\rho^{1/2}}{\max(\sigma^{2},1)\epsilon^{3.5}}\asymp\epsilon^{-3.5}$, with probability at least $1-(T_{1}+1)\cdot p$, SGD outputs an $\bar{\mathbf{x}}_{output}$ satisfying

For the function class that admits the strict-saddle property (Carmon et al.,, 2018; Ge et al.,, 2015; Jin et al.,, 2017), an approximate second-order stationary point is guaranteed to be an approximate local minimizer. For example for optimizing a $\sigma_{*}$-strict-saddle function, one can first find an $(\epsilon_{*},\sqrt{\rho\epsilon_{*}})$-approximate second-order stationary point with $\epsilon_{*}\leq\sigma_{*}^{2}/(2\rho)$ which is guaranteed to be an approximate local minimizer due to the strict-saddle property. Our SGD convergence rate $\mathcal{O}(\epsilon_{*}^{-3.5})=\mathcal{O}(\sigma_{*}^{-7})$ is independent of the target accuracy $\epsilon$, and one can run a standard convex optimization theory to obtain an $\mathcal{O}(1/t)$ convergence rate in terms of the optimality gap. Limited by space we omit the details.

Discussions on Related Works

Due to the recent heat of deep learning, many researchers have studied the nonconvex SGD method from various perspectives in the machine learning community. We compare our results with concurrent theoretical works on nonconvex SGD in the following discussions. For clarity, we also compare the convergence rates of some works most related to ours in Table 1.

In the recent two years, sharper convergence rates for nonconvex stochastic optimization can be achieved using variance reduced gradient techniques (Schmidt et al.,, 2017; Johnson & Zhang,, 2013; Xiao & Zhang,, 2014; Defazio et al.,, 2014). The SVRG/SCSG (Lei et al.,, 2017) adopts the technique from Johnson & Zhang, (2013) and novelly introduces a random stopping criteria for its inner loops and achieve a stochastic gradient costs of $\mathcal{O}(\epsilon^{-3.333})$. Very recently, two independent works, namely SPIDER (Fang et al.,, 2018) and SVRC (Zhou et al., 2018b, ), design sharper variance reduced gradient methods and obtain a stochastic gradient computational costs of $\mathcal{O}(n^{1/2}\epsilon^{-2}\land\epsilon^{-3})$, which is state-of-the-art and near-optimal in the sense that they achieve the algorithmic lower bound in the finite-sum setting.

Escaping Saddles in Single-Function Case

Recently, many theoretical works care about convergence to an approximate second-order stationary point or escaping from saddles for the case of one single function (Carmon & Duchi,, 2016; Jin et al.,, 2017; Carmon et al.,, 2018, 2017; Agarwal et al.,, 2017; Jin et al., 2018b, ; Lee et al.,, 2017; Du et al.,, 2017). Among them, the work Jin et al., (2017) proposed a ball-shaped-noise-perturbed variant of gradient descent which can efficiently escape saddle points and achieves a sharp stochastic gradient computational cost of $\epsilon^{-2}$, which is also achieved by Neon+GD (Xu et al.,, 2018; Allen-Zhu & Li,, 2018). Another line of works apply momentum acceleration techniques (Agarwal et al.,, 2017; Carmon et al.,, 2017; Jin et al., 2018b, ) and achieve a rate of $\epsilon^{-1.75}$ for a general optimization problem.

Escaping Saddles in Finite-Sum Case

Miscellaneous

It is well-known that for general nonconvex optimization problem in the form of (1.1), finding an approximate global minimizer is in worst-case NP-hard (Hillar & Lim,, 2013). Seeing this, many works turn to study the convergence properties based on specific models. Faster convergence rate to local or even global minimizers can be guaranteed for many statistical learning tasks such as principal component analysis (Li et al., 2018a, ; Jain & Kar,, 2017), matrix completion (Jain et al.,, 2013; Ge et al.,, 2016; Sun & Luo,, 2016), dictionary learning (Sun et al.,, 2015, 2017) as well as linear and nonlinear neural networks (Zhong et al.,, 2017; Li & Yuan,, 2017; Li et al., 2018b, ).

In retrospect, our focus in this paper is on escaping from saddles, and we refer the readers to recent inspiring works studying how to escape from local minimizers Zhang et al., (2017); Jin et al., 2018a .

Conclusions and Future Direction

We have not considered several important extensions in this work, such as the convergence rate of SGD in solving constrained optimization problems, and how one extends the analysis in this paper to the proximal case.

It will be also interesting to study the stochastic version of Nesterov’s accelerated gradient descent (AGD) (Jin et al., 2018b, ).

Zhouchen Lin is supported by 973 Program of China (grant no. 2015CB352502), NSF of China (grant nos. 61625301 and 61731018), Qualcomm, and Microsoft Research Asia.

References

Appendix A Proof Sketches for Theorem 1

Once $\mathbf{x}^{k}$ does not move out of $\mathcal{B}(\mathbf{x}^{0},B)$ until $K_{0}$ iteration, with high probability, we find a desired approximate second-order stationary point (Refer to Appendix E).

Let ${\bm{\mathcal{F}}}^{k}=\sigma\{\mathbf{x}^{0},\bm{\zeta}^{1},\cdots,\bm{\zeta}^{k}\}$ be the filtration involving the full information of all the previous $k$ times iterations, where $\sigma\{\cdot\}$ denotes the sigma field. And let $\mathscr{K}_{0}$ be the first time (mathematically, a stopping time) that $\mathbf{x}^{k}$ exits the $B$-neighborhood of $\mathbf{x}^{0}$, i.e.

Both $\mathbf{x}^{k}$ and $\mathcal{I}_{\mathscr{K}_{0}>k}$ is measurable on ${\bm{\mathcal{F}}}^{k}$, where $\mathcal{I}$ denotes the indicator function.

Our goal is to prove the following proposition:

Assume $\lambda_{\min}\left(\nabla^{2}f(\mathbf{x}^{0})\right)\leq-\delta_{2}$, and recall the parameter set in (2.2). Initialized at $\mathbf{x}^{0}$ and running Line 2 to Line 8, with probability at least $1-\frac{p}{3}$ we have

where $K_{o}=2\log\left(\frac{24\sqrt{d}}{\eta}\right)\eta^{-1}\delta_{2}^{-1}$.

Obviously, we have $\mathbf{x}^{k}=\mathbf{w}^{k}(\mathbf{x}^{0})$. Let $\mathcal{K}_{exit}(\mathbf{u})$ be the first step number $k$ (a stopping time) such that $\mathbf{w}^{k}(\mathbf{u})$ exits the $B$-neighborhood of $\mathbf{x}^{0}$. Formally,

It is easy to see from (A.1) that $\mathscr{K}_{0}=\mathcal{K}_{exit}(\mathbf{x}^{0})$. Inspired from Jin et al., (2017), we cope with the stochasticity of gradients and define the so-called bad initialization region as the point $\mathbf{u}$ initialized from which iteration $\mathbf{w}^{k}(\mathbf{u})$ exits the $B$-neighborhood of $\mathbf{x}^{0}$ with probability $\leq 0.4$:

We will show that the bad initialization region $\mathcal{S}_{K_{o}}^{B}(\mathbf{x}^{0})$ enjoys the $(q_{0},\mathbf{e}_{1})$-narrow property, where $q_{0}=\frac{\sigma}{4\sqrt{d}}$. Since the first step will provide a continuous noise as supposed by Assumption 3, with the properly selected $q_{0}$, it will move the iteration out of the bad initialization region in its first step with probability $\geq 3/4$. Repeating such an argument in a logarithmic number of rounds enables escaping to occur with high probability.

The idea is to prove the following lemma:

Let the assumptions of Proposition 2 hold, and assume WLOG $\mathbf{e}_{1}$ be an arbitrary eigenvector of $\nabla^{2}f(\mathbf{x}^{0})$ corresponding to its smallest eigenvalue $-\delta_{m}$, which satisfies $\delta_{m}\geq\delta_{2}>0$. Then we have for any fixed $q\geq q_{0}$ and pair of points $\mathbf{u},\mathbf{u}+q\mathbf{e}_{1}\in\mathcal{B}(\mathbf{x}^{0},B)$ that

Lemma 1 is inspired from Lemma 15 in Jin et al., (2017). Nevertheless due to the noise brought in at each update step, the analysis of stochastic gradient differs from that of the gradient descent in many aspects. For example, instead of showing the decrease of function value, we need to show that with a positive probability, at least one of the two iterations, $\mathbf{w}^{k}(\mathbf{u}+q\mathbf{e}_{1})$ or $\mathbf{w}^{k}(\mathbf{u})$, exits the $B$-neighborhood of $\mathbf{x}^{0}$. Our proof is also more intuitive compared with Lemma 15 in Jin et al., (2017). The core idea is to focus on analyzing the difference trajectory for $\mathbf{w}^{k}(\mathbf{u}+q\mathbf{e}_{1})$ and $\mathbf{w}^{k}(\mathbf{u})$, and to show that the rotation speed for the difference trajectory is the same as the expansion speed. Detailed proof is provided in §C.1.

A.2 Part II: Faster Descent

The goal of Part II is to prove the following proposition:

For Algorithm 2 with parameter set in (2.2). With probability at least $1-\frac{2}{3}p$, if $\mathbf{x}^{k}$ moves out of $\mathcal{B}(\mathbf{x}^{0},B)$ in $K_{0}$ iteration, we have

We start with reviewing the more traditional approach for proving sufficient descent of SGD, and then we will discuss how to improve it as done in this work. The previous approaches are all based on the idea of (Nesterov,, 2004), which mainly takes advantage of the gradient-smoothness condition of the objective. The proof can be briefly described below:

From the above derivation, in order to guarantee the monotone descent of function value in expectation, the step size $\eta$ needs to be

where the last equality uses $\left\|\nabla f(\mathbf{x}^{k})\right\|\geq\epsilon$. Plugging (A.9) into (A.8), and using $\|\nabla f(\mathbf{x}^{k})\|\geq\epsilon$, we have that the function value per-iteration would descent with a magnitude of at least $\mathcal{O}(\epsilon^{4})$. Such result indicates that, in the worse case, SGD takes $\mathcal{O}(\epsilon^{-4})$ stochastic oracles to find an $\epsilon$-approximate first-order stationary point. This simple argument is the reason why previous works conjectured that the complexity of SGD is $\mathcal{O}(\epsilon^{-4})$.

However, in this paper, we show that the above analysis can be further improved by using the Hessian-smoothness condition of the objective, and by considering the decomposition of objective function $f(\mathbf{x})=f_{+}(\mathbf{x})+f_{-}(\mathbf{x})$, and treating component $f_{+}(\mathbf{x})$ and component $f_{-}(\mathbf{x})$ separately as follows:

(Case 1) The component $f_{+}(\mathbf{x})$ is near convex locally, in the sense that $\lambda_{\min}\left(\nabla^{2}f(\mathbf{x})\right)\geq-\Omega(\epsilon^{0.5})$ for all $\mathbf{x}\in\mathcal{B}(\mathbf{x}^{0},B)$. In this case, by using techniques for near convex problems, it is possible for us to take a larger stepsize $\eta=\mathcal{O}(\epsilon^{1.5})$ and prove a faster convergence rate.

(Case 2) The component $f_{-}(x)$ is near concave locally, in the sense that $\lambda_{\max}\left(\nabla^{2}f(\mathbf{x})\right)\leq\mathcal{O}(\epsilon^{0.5})$ for all $\mathbf{x}\in\mathcal{B}(\mathbf{x}^{0},B)$ . In this case, It can be shown that the last term on the right hand side of (A.8) can be reduced to $\mathcal{O}(\eta^{2}\epsilon^{0.5}\sigma^{2})$. Therefore the step size can be chosen as $\eta=\mathcal{O}(\epsilon^{1.5})$, leading to a fast function value reduction.

To formalize the above observations into a rigorous proof, in this paper we introduce the quadratic approximation of $f(\mathbf{x})$ at point $\mathbf{x}^{0}$, defined as

The analysis for $g_{\mathcal{S}\bot}(\cdot)$ can be obtained via the standard analysis informally described above in Case 2 (Refer to Lemma 7).

Our proof technique for dealing with $g_{\mathcal{S}}(\cdot)$ is to introduce an auxiliary trajectory with the following deterministic updates for $k=0,1,2,\dots,$ as:

and $\mathbf{y}^{0}=\mathbf{0}$. We then track and analyze the difference trajectory between $\bm{\mathcal{P}}_{\mathcal{S}}\left(\mathbf{x}^{\mathscr{K}_{0}}-\mathbf{x}^{0}\right)$ and $\mathbf{y}^{\mathscr{K}_{0}}$ (Refer to Lemma 6). In the sense that $\mathbf{y}^{k}$ simply performs Gradient Descent, we can arrive our final results for $g_{\mathcal{S}}(\cdot)$ (Refer to Lemma 5), which leads to a rigorous statement of Case 1.

Finally, via the fact that $\mathbf{x}^{k}$ moves out of the ball in $K_{0}$ iteration throughout the execution of Algorithm 2, we prove that with high probability the sum for the norm of gradients can be lower bounded as:

which ensures sufficient descent of the function value. By putting the above arguments together, we can obtain Proposition 3.

A.3 Part III: Finding SSP

Part III proves the following proposition:

With probability of at least $1-p$, if $\mathbf{x}^{k}$ has not moved out of the ball in $K_{0}$ iterations, then let $\bar{\mathbf{x}}=\sum_{k=0}^{K_{0}-1}\mathbf{x}^{k}$, we have

Proposition 4 can be obtained via the same idea of Part II. We first study the quadratic approximation function $g(\bar{\mathbf{x}})$ and then bound the difference between $g(\bar{\mathbf{x}})$ and $f(\bar{\mathbf{x}})$.

Finally, integrating Proposition 2, 3, and 4, and using the boundedness of the function value in Assumption 2, we know with probability at least $1-(T_{1}+1)p$, Algorithm 2 shall stop before $T_{0}$ steps, and output an approximate second-order stationary point satisfying (2.7), which immediately leads to Theorem 1.

Appendix B Concentration Inequalities

In our proofs, concentration inequalities are fundamental to obtain the high-probability result. Before we prove our results, we introduce the following two (advanced) inequalities which will be used in our proofs.

where $\lambda$ is an arbitrary real positive number.

Theorem 2 is not a straightforward derivation of one-dimensional Azuma’s inequality. Because the bound on the right hand of (B.1) is dimension-free. Such result might be first found by Pinelis, (1994). See also Kallenberg & Sztencel, (1991), Lemma 4.4 in Zhang, (2005) or Theorem 2.1 in Zhang, (2005) and the references therein.

B.2 Data-Dependent Concentration Inequality

Theorem 3 extends the standard Freedman’s Inequality (Freedman,, 1975) by allowing $\sigma_{k}$ being the conditional variance. Similar results can be found in Bartlett et al., (2008) and Lemma $2$ in Zhang, (2005) and the references therein.

Note that Theorem 2 and 3 only list the results for the bounded martingale difference. Similar results can also be established when the martingale difference follows from a sub-gaussian distribution. In the rest of our proofs, we also only present the results for the bounded noise case, i.e. (2.3) in Assumption 3. Analogous analysis can be applied for sub-gaussian noise, i.e. (2.4) in Assumption 3.

Appendix C Deferred Proofs of Part I: Escaping Saddles

where $q_{0}=\frac{\sigma\eta}{4\sqrt{d}}$. We prove Proposition 2 that bound the iteration number to escape $\mathcal{B}(\mathbf{x}^{0},B)$.

We prove in this item that $\mathcal{S}_{K_{o}}^{B}(\mathbf{x}^{0})$ satisfies the $(q_{0},\mathbf{e}_{1})$-narrow property, i.e. there cannot be two points $\mathbf{u},\mathbf{u}+q\mathbf{e}_{1}\in\mathcal{S}_{K_{o}}^{B}(\mathbf{x}^{0})$ such that $q\geq q_{0}$. Indeed if such two points do exist, from (A.5) we have

and hence by inclusion-exclusion principle

where we applied (A.3) and that $\mathbf{w}^{0}(\mathbf{u})=\mathbf{u}$. Thus

This subsection denotes to the proof of Lemma 1 in the following steps:

Denote for simplicity $\mathbf{w}^{k}\equiv\mathbf{w}^{k}(\mathbf{u})$, and $\bar{\mathbf{w}}^{k}\equiv\mathbf{w}^{k}(\mathbf{u}+q\mathbf{e}_{1})$. Recall from the SGD update rule we have $\mathbf{w}^{0}=\mathbf{u}$, and for all $k=1,2,\dots$ for a random index $\bm{\zeta}^{k}$ drawn from distribution $\mathcal{D}$,

Recall the definition of $\mathcal{K}_{exit}(\mathbf{u})$ in (A.4), we let

For our analysis, we define a coupled ${\bm{\mathcal{F}}}^{k}$-measurable iteration $\mathbf{z}^{k}$, as follows:

Letting $\mathbf{H}=\nabla^{2}f(\mathbf{x}^{0})$, and we first conclude the following lemma to express $\mathbf{z}^{k}$ defined in (C.4):

$\{\bm{\xi}_{d}^{k}\}$ forms a martingale difference sequence satisfying

By setting $\mathbf{D}^{k-1}=\mathbf{0}^{d\times d}$ and $\bm{\xi}_{d}^{k}=\mathbf{0}$, on event $(k\geq\mathcal{K}_{1})$ we can easily see from (C.4) that all (C.6), (C.7) and (C.8) hold, since their left hands are zero. For its complement $(k<\mathcal{K}_{1})$, we have

where we set the following terms (C.9) and (C.10):

and the noise term $\bm{\xi}_{d}^{k}$ generated at each iteration

It leaves us to prove (C.7) and (C.8). From (C.9), we have

which is bounded by $\rho B$ since $\max\left(\|\bar{\mathbf{w}}^{k-1}-\mathbf{x}^{0}\|,\|\mathbf{w}^{k-1}-\mathbf{x}^{0}\|\right)\leq B$, proving (C.7).

This completes the proof of (C.8), and hence the lemma.

We observe from (C.6) that if $\nabla^{2}f(\mathbf{z})$ does not rotate in the sense that each pair of Hessian matrices $\nabla^{2}f(\mathbf{w}_{1})$ and $\nabla^{2}f(\mathbf{w}_{2})$ can be spectrally decomposed via the same orthogonal matrix, one can analyze the iteration coordinate-wisely. Here, the rotation effect of Hessian matrix cannot be ignored. Hence, we analyze the difference iteration $\mathbf{z}^{k}$ in two aspects: (i) $\mathbf{z}^{k}$ has a rotation effect after standardization, and (ii) its norm $\|\mathbf{z}^{k}\|$ has an expansion effect.

To decouple these two effect, we define a rescaled iteration as follows. Let $\delta_{m}$ denote the negated least eigenvalue $\lambda_{\min}(\nabla^{2}f(\mathbf{x}^{0}))$ of Hessian so $\delta_{m}\geq\delta_{2}$. Let for each $k=0,1,\dots$

We state the following lemma for the update rule of $\bm{\psi}^{k}$.

Let $\hat{\mathbf{D}}^{k}\equiv(1+\eta\delta_{m})^{-1}\mathbf{D}^{k},$ and $\bm{\zeta}_{d}^{k}\equiv q^{-1}(1+\eta\delta_{m})^{-k}\bm{\xi}_{d}^{k}.$ We have $\bm{\psi}^{0}=\mathbf{e}_{1}$ and

and the rescaled noise iteration $\bm{\zeta}_{d}^{k}$ has

and for the projection of $\bm{\psi}^{k}$ onto the first coordinate,

We have from the definition of $\bm{\zeta}_{d}^{k}$

To handle the term involving the $\bm{\zeta}_{d}^{k}$ terms on the right hands of (C.16) and (C.15), we first set

Since $\eta L\leq 1$ we simply have $\left[\mathbf{I}-\eta\mathbf{H}\right]$ is symmetric and has all eigenvalues in $[0,1+\eta\delta_{m}]$, so $\|\mathbf{I}-\eta\mathbf{H}\|\leq 1+\eta\delta_{m}$. This implies $\|\hat{\bm{\psi}}^{k-1}\|\leq\|\bm{\psi}^{k-1}\|$.

On the other hand, for all $k\geq 1$, we have

where $\mathcal{I}$ denotes the indicator function, $\overset{a}{=}$ uses $\bm{\psi}^{k-1}$ and $\hat{\bm{\psi}}^{k-1}$ are measurable on ${\bm{\mathcal{F}}}^{k-1}$. By the standard Azuma’s inequality, with probability $1-0.1/(2K_{0})$, for any $l$ from $1$ to $K_{0}$,

happens with probability at least $1-0.1/(2K_{0})$.

So by union bound, there exists a high-probability event $\bm{\mathcal{H}}_{o}$ happening with probability at least $0.9$ such that the following inequalities hold for each $l=1,2,\dots,K_{0}$,

On the other hand, we have from (C.12) and (C.17) that for all $k\geq 1$,

Under the event $\bm{\mathcal{H}}_{0}$ happens, by induction, when $k=0$, $\|\bm{\psi}^{0}\|=\|\mathbf{e}_{1}\|\leq 2$, suppose $\|\bm{\psi}^{l}\|\leq 2$ holds for all $l=0$ to $k-1$, we have for the step $k$,

where $\overset{a}{\leq}$ uses $\eta\leq\frac{\rho B}{8L^{2}}$ (because (2.2) and $B\leq\frac{1}{L}$). This conclude the proof of (C.15). For $\mathbf{e}_{1}^{\top}\bm{\psi}^{k}$, we have

concluding (C.16), and hence the lemma. ∎

Now, we have all the ingredients necessary to prove our final lemma.

Recall that the deterministic time $K_{o}$ was defined in (C.1), we have on the event $(\mathcal{K}_{1}>K_{o})$ that $\mathbf{z}^{K_{o}}=\bar{\mathbf{w}}^{K_{o}}-\mathbf{w}^{K_{o}}$ and hence $\|\mathbf{z}^{K_{o}}\|\leq\|\bar{\mathbf{w}}^{K_{o}}\|+\|\mathbf{w}^{K_{o}}\|\leq 2B$, which concludes

In the mean time, from (C.4) we know that on the event $(\mathcal{K}_{1}>K_{o})$, $\mathbf{z}^{k}=\bar{\mathbf{w}}^{k}-\mathbf{w}^{k}$ for all $k\leq K_{o}$, from (C.16)

So on the event $(\mathcal{K}_{1}>K_{o})\cap\bm{\mathcal{H}}_{0}$

Combining (C.24), (C.25) and the fact that $B>0$ gives

and hence $(\mathcal{K}_{1}>K_{o})\subseteq\bm{\mathcal{H}}_{0}^{c}$ which leads to

proving (C.5). Hence (A.6) and Lemma 1 hold.

Appendix D Deferred Proofs of Part II: Faster Descent

In Part II, we still use $\mathbf{H}$ to denote $\nabla^{2}f(\mathbf{x}^{0})$ and let

Recall the definition of $\mathcal{S}$, $\bm{\mathcal{P}}_{\mathcal{S}}$, $\mathcal{S}\bot$, and $\bm{\mathcal{P}}_{\mathcal{S}\bot}$ in Appendix A.2. Let $\mathbf{u}^{k}=\bm{\mathcal{P}}_{\mathcal{S}}\left(\mathbf{x}^{k}-\mathbf{x}^{0}\right)$, and $\mathbf{v}^{k}=\bm{\mathcal{P}}_{\mathcal{S}\bot}\left(\mathbf{x}^{k}-\mathbf{x}^{0}\right)$. We can decompose the update equation of SGD as:

with $k\geq 0$. And $\mathbf{u}^{0}=\mathbf{0}$, $\mathbf{v}^{0}=\mathbf{0}$. From the definition of $g(\mathbf{x})$ in Appendix A.2, we have

where in the last equality we use $\bm{\mathcal{P}}^{2}_{\mathcal{S}}=\bm{\mathcal{P}}_{\mathcal{S}}$ and $\bm{\mathcal{P}}^{2}_{\mathcal{S}\bot}=\bm{\mathcal{P}}_{\mathcal{S}\bot}$, because $\bm{\mathcal{P}}_{\mathcal{S}}$ and $\bm{\mathcal{P}}_{\mathcal{S}\bot}$ are projection matrices. Thus if $\mathbf{u}=\bm{\mathcal{P}}_{\mathcal{S}}(\mathbf{x}-\mathbf{x}^{0})$ and $\mathbf{v}=\bm{\mathcal{P}}_{\mathcal{S}\bot}(\mathbf{x}-\mathbf{x}^{0})$, we have

For clarify, we denote $\nabla_{\mathbf{u}}f(\mathbf{x}^{k})=\bm{\mathcal{P}}_{\mathcal{S}}\nabla f(\mathbf{x}^{k})$, and $\nabla_{\mathbf{v}}f(\mathbf{x}^{k})=\bm{\mathcal{P}}_{\mathcal{S}\bot}\nabla f(\mathbf{x}^{k})$, respectively. Similarly, let $\bm{\xi}_{\mathbf{u}}^{k}=\bm{\mathcal{P}}_{\mathcal{S}}\bm{\xi}^{k}$, and $\bm{\xi}_{\mathbf{v}}^{k}=\bm{\mathcal{P}}_{\mathcal{S}\bot}\bm{\xi}^{k}$. In the following, we denote $\mathscr{K}=\mathscr{K}_{0}\wedge K_{0}$ which is also a stopping time. The Lemma below is basic to obtain our result.

Given $\mathbf{x}^{0}$, for any $\mathbf{x}$, if $\left\|\mathbf{x}-\mathbf{x}^{0}\right\|\leq B$, then

For any symmetric matrix $\mathbf{A}$, with $0<a\leq\frac{1}{\|\mathbf{A}\|_{2}}$, for any $i=0,1,\dots$, and $j=0,1,\dots$, we have

where in $\overset{a}{\leq}$, we use (2.2) that $f(\mathbf{x})$ has $\rho$-Lipschitz continuous Hessian.

(D.6) is from Jin et al., (2017). To prove it, suppose the eigenvalue of $\{\mathbf{A}\}$ is $\{\lambda_{l}\}$, thus the eigenvalue of $(\mathbf{I}-a\mathbf{A})^{i}\mathbf{H}(\mathbf{I}-a\mathbf{A})^{j}$ is $\{\lambda_{l}(1-a\lambda_{l})^{i+j}\}$. For the function of $\lambda(1-a\lambda)^{i+j}$, we can compute out its derivative as $(1-a\lambda)^{i+j}-(i+j)a\lambda(1-a\lambda)^{i+j-1}$. Then with simple analysis, we can find that the maximal point is obtained only at $\frac{1}{(1+i+j)a}$. If $i=0$ and $j=0$, (D.6) clearly holds. Otherwise, we have

D.2 Analysis on Quadratic Approximation

We first summarize our result for $g_{\mathcal{S}}(\cdot)$ in the following lemma:

Set hyper-parameters in (2.2) for Algorithm 2. With probability at least $1-p/4$, we have

Proofs of Lemma 5 Our novel technique to analyze $g_{\mathcal{S}}(\cdot)$ is by first considering an auxiliary Gradient Descent trajectory, which performs update as:

and $\mathbf{y}^{0}=\mathbf{u}^{0}$. $\mathbf{y}^{k}$ preforms Gradient Decent on $g_{\mathcal{S}}(\cdot)$, which is deterministic given $\mathbf{x}^{0}$. We study the property of $\mathbf{y}^{\mathscr{K}}$ and obtain the following standard results:

Because $g_{\mathcal{S}}(\cdot)$ has $L$-Lipschitz continuous gradient ($\|\mathbf{H}_{\mathcal{S}}\|_{2}\leq L$), we have

By telescoping (D.11) from to $\mathscr{K}-1$, we have

To obtain Lemma 5, we bound the difference between $\mathbf{u}^{\mathscr{K}}$ and $\mathbf{y}^{\mathscr{K}}$. Define

The remaining is to conclude the properties of $\mathbf{z}^{\mathscr{K}}$, stated as follows:

With probability at least $1-p/6$, we have

With $\mathbf{z}^{k}=\mathbf{u}^{k}-\mathbf{y}^{k}$ being the difference iteration, we have

And $\mathbf{z}^{0}=\mathbf{0}$. Thus we can obtain the general solution of (D.15) as

Setting $k=\mathscr{K}$, by triangle inequality, we have

We separately bound the two terms in the right hand sides of (D.17). For the first term, for any fixed $l$ from $1$ to $K_{0}$, and any j from $1$ to $l$, we have

where $\overset{a}{=}$ uses that $\|\bm{\xi}^{j}_{\mathbf{u}}\|=\|\bm{\mathcal{P}}_{\mathcal{S}}\bm{\xi}^{j}\|$, $\overset{b}{\leq}$ further uses $\|\bm{\xi}^{j}_{\mathbf{u}}\|\leq\|\bm{\xi}^{j}\|\leq\sigma$, because $\bm{\mathcal{P}}$ is projection matrix, and the the bounded noise assumption in (2.3) and $\|(\mathbf{I}-\eta\mathbf{H}_{\mathcal{S}})^{l-j}\|_{2}\leq 1$ for all $j$ from $1$ to $l$. Thus by the Vector-Martingale Concentration Inequality in Theorem 2, we have with probability $1-p/(12K_{0})$,

By union bound, with probability at least $1-p/12$, (D.19) holds for all $l$ from $1$ to $K_{0}$. Because $1\leq\mathscr{K}\leq K_{0}$, with probability at least $1-p/12$,

For the second term in the right hand side of (D.17), we have

where in $\overset{a}{\leq}$, we use triangle inequality, and $\left\|\mathbf{I}-\eta\mathbf{H}_{\mathcal{S}}\right\|^{\mathscr{K}-1-j}_{2}\leq 1$ with $j$ from to $\mathscr{K}-1$; $\overset{b}{\leq}$ uses $\|\bm{\mathcal{P}}_{\mathcal{S}}(\nabla f(\mathbf{x})-\nabla g(\mathbf{x}))\|\leq\|\nabla f(\mathbf{x})-\nabla g(\mathbf{x})\|$ becuase $\bm{\mathcal{P}}_{\mathcal{S}}$ is projected matrix. Substituting (D.20) and (D.21) into (D.17), we obtain (D.13).

To prove (D.14), using the fact that $(\mathbf{a}+\mathbf{b})^{\top}\mathbf{A}(\mathbf{a}+\mathbf{b})\leq 2\mathbf{a}^{\top}\mathbf{A}\mathbf{a}+2\mathbf{b}^{\top}\mathbf{A}\mathbf{b}$ holds for any symmetry positive definite matrix $\mathbf{A}$, we have

For the first term in the right hand side of $\eqref{zend1}$, for any fixed $l$ from $1$ to $K_{0}$, and any j from $1$ to $l$, we have

by the Vector-Martingale Concentration Inequality in §2, we have with probability $1-p/(12K_{0})$

By union bound, with probability at least $1-p/12$, (D.24) holds for all $l$ from $1$ to $K_{0}$. Because $1\leq\mathscr{K}\leq K_{0}$, with probability at least $1-p/12$,

For the second term in the right hand side of $\eqref{zend1}$, we have

Substituting (D.25) and (D.26) into (D.2), we obtain (D.14). ∎

We can bound the first-order difference between $g_{\mathcal{S}}\left(\mathbf{u}^{\mathscr{K}}\right)$ and $g_{\mathcal{S}}\left(\mathbf{y}^{\mathscr{K}}\right)$ as:

where in $\overset{a}{=}$, we use $(\mathbf{I}-\mathbf{H}_{\mathcal{S}})\mathbf{H}_{\mathcal{S}}=\mathbf{H}_{\mathcal{S}}(\mathbf{I}-\mathbf{H}_{\mathcal{S}})$, and in $\overset{b}{=}$, we use $\mathbf{z}^{0}=\mathbf{0}$.

We also bound the two terms in the right hand side of (D.2). For any fixed $l$ from $1$ to $K_{0}$, and any j from $1$ to $l$, we have

where $\overset{a}{\leq}$ uses $\|\bm{\xi}^{j}_{\mathbf{u}}\|\leq\|\bm{\xi}^{j}\|\leq\sigma$, $\overset{b}{\leq}$ uses $\|(\mathbf{I}-\eta\mathbf{H}_{\mathcal{S}})^{l-j+1}\|_{2}\leq 1$ for all $j$ from $1$ to $l$. So for any $l$ from $1\leq k\leq K_{0}$, by standard Azuma–Hoeffding inequality, using $\nabla g_{\mathcal{S}}\left(\mathbf{y}^{k}\right)$ is measurable on ${\bm{\mathcal{F}}}^{0}$, with probability at least $1-p/(12K_{0})$, we have

By union bound, with probability at least $1-p/12$, (D.31) holds for all $l$ from $1$ to $K_{0}$. we have with probability at least $1-p/12$

where in $\overset{a}{\leq}$, we use $\sqrt{ab}\leq\frac{a+b}{2}$ with $a\geq 0$ and $b\geq 0$.

For the second term in the right hand side of (D.2), we have

where $\overset{a}{\leq}$ uses $\left\|(\mathbf{I}-\eta\mathbf{H}_{\mathcal{S}})^{\mathscr{K}-k}\right\|_{2}\leq 1$ with $k<\mathscr{K}$, $\overset{b}{\leq}$ uses $ab\leq\frac{a^{2}+b^{2}}{2}$.

Substituting (D.2) and (D.33) into (D.2), and using (D.14), we have

We then investigate $g_{\mathcal{S}\bot}(\cdot)$ and summarize its property as follows:

With hyper-parameters set in (2.2) for Algorithm 2, we have

Lemma 7 can be obtained via the standard analysis. Specifically, from the definition of $g_{\mathcal{S}\bot}(\cdot)$, we have

We can further bound the right hand side of (D.37) as follows:

Substituting (D.38) into (D.37), and telescoping the results with $k$ from to $\mathscr{K}-1$, we have

D.3 Proofs of Proposition 3

With Lemma 5 and 7 in hand, the mainly rest to do is to prove

and bound the noise term $-\sum_{k=1}^{\mathscr{K}}\eta\left\langle\nabla g_{\mathcal{S}\bot}\left(\mathbf{v}^{k-1}\right),\bm{\xi}_{\mathbf{v}}^{k}\right\rangle$. We separately consider two cases:

$\left\|\nabla f\left(\mathbf{x}^{0}\right)\right\|>5\sigma\asymp 1$,

$\left\|\nabla f\left(\mathbf{x}^{0}\right)\right\|\leq 5\sigma\asymp 1$.

Case 1: in the sense that the gradient is large, we show that function value is guaranteed to decrease monotonously.

Because $\left\|\nabla f\left(\mathbf{x}^{0}\right)\right\|>5\sigma$, we have, for all $0\leq k\leq\mathscr{K}-1$,

where $\overset{a}{\geq}$ uses $\|\mathbf{x}^{k}-\mathbf{x}^{0}\|\leq B$ for all $k\leq\mathscr{K}_{1}$, the $L$-Lipschitz continuous of the gradient. Furthermore, we also have

where $\overset{a}{=}$ uses the update rule of SGD: $\mathbf{x}^{k+1}=\mathbf{x}^{k}-\eta\nabla f\left(\mathbf{x}^{k}\right)-\eta\bm{\xi}^{k+1}$, $\overset{b}{\leq}$ uses $\|\mathbf{a}+\mathbf{b}\|^{2}\leq 2\|\mathbf{a}\|^{2}+2\|\mathbf{b}\|^{2}$, in $\overset{c}{\leq}$, we use $L\eta\leq\frac{1}{16}$ from (2.2), $-\left\langle\nabla f\left(\mathbf{x}^{k}\right),\bm{\xi}^{k+1}\right\rangle\leq\frac{5}{32}\left\|\nabla f\left(\mathbf{x}^{k}\right)\right\|^{2}+\frac{8}{5}\left\|\bm{\xi}^{k+1}\right\|^{2}$, and $\left\|\bm{\xi}^{k+1}\right\|\leq\sigma$. By telescoping (D.42) with $k$ from to $\mathscr{K}-1$, we have

On the other hand, again by the update rule of SGD, we have

By the Vector-Martingale Concentration Inequality in Theorem 2, we have with probability $1-p/12$,

where $\overset{a}{\leq}$ uses $\mathcal{I}_{k\leq\mathscr{K}}$ is measurable on ${\bm{\mathcal{F}}}^{k-1}$ and $\|\bm{\xi}^{k}\|\leq\sigma$. So if (D.45) happens, and $\mathbf{x}^{k}$ exits $\mathcal{B}\left(\mathbf{x}^{0},B\right)$ in $K_{0}$ iterations, we have

where in $\overset{a}{\geq}$, we use the inequality that

holds for all $l\geq 1$. Plugging (D.46) into (D.43), with probability at least $1-p/12$ ((D.45) happens), we have

Case 2: To obtain the result, we first prepare the following lemmas:

We fuse Lemma 5 and 7 and obtain the lemma shown below:

With the parameters set in (2.2), and if $\|\nabla f(\mathbf{x}^{0})\|\leq 5\sigma$, with probability $1-p/4$ ((D.19), (D.24) and (D.2) happen), we have

Because $\left\|\nabla g_{\mathcal{S}\bot}\left(\mathbf{v}^{0}\right)\right\|=\left\|\nabla_{\mathbf{v}}f\left(\mathbf{x}^{0}\right)\right\|\leq\left\|\nabla f\left(\mathbf{x}^{0}\right)\right\|\leq 5\sigma$, for all $0\leq k\leq\mathscr{K}-1$, we have

where in $\overset{a}{\leq}$, we use $\left\|\mathbf{v}^{k}-\mathbf{v}^{0}\right\|=\left\|\bm{\mathcal{P}}_{\mathcal{S}\bot}(\mathbf{x}^{k}-\mathbf{x}^{0})\right\|\leq B$ and $L$-Lipschitz continuous gradient for $g_{\mathcal{S}\bot}(\cdot)$. In the same way, for all $0\leq k\leq\mathscr{K}-1$, we have

We then bound the difference between $f(\mathbf{x}^{\mathscr{K}})$ and $g(\mathbf{x}^{\mathscr{K}})$: using $\rho$-smoothness of Hessian, we have

Then by adding (D.35) and (D.2), using (D.52), and $g_{\mathcal{S}}\left(\mathbf{u}^{0}\right)+g_{\mathcal{S}\bot}\left(\mathbf{v}^{0}\right)=0$, we have, with probability at least $1-p/4$, ((D.19), (D.24) and (D.2) happen)

we obtain with probability at least $1-p/4$, ((D.19), (D.24) and (D.2) happen)

Furthermore, the following lemma ensures the function value sufficient descent:

With probability $1-\frac{p}{6}$ ((D.19) and (D.59) happen), if $\mathbf{x}^{k}$ exits $\mathcal{B}\left(\mathbf{x}^{\mathcal{K}},B\right)$ in $K_{0}$ iterations, we have

where $\overset{a}{=}$ uses $\mathbf{v}^{k}=\mathbf{v}^{k-1}-\eta\bm{\xi}^{k+1}_{\mathbf{v}}-\eta\nabla_{\mathbf{v}}f(\mathbf{x}^{k})$ and $\mathbf{y}^{k}=\mathbf{y}^{k-1}-\eta\nabla g_{\mathcal{S}}\left(\mathbf{y}^{k}\right)$, $\overset{b}{\geq}$ uses $\mathbf{z}^{\mathscr{K}}=\mathbf{u}^{\mathscr{K}}-\mathbf{y}^{\mathscr{K}}$, $\mathbf{z}^{0}=\mathbf{u}^{0}=\mathbf{y}^{0}=\mathbf{0}$, and triangle inequality, $\overset{c}{\geq}$ uses (D.5).

From (D.13), with probability at least $1-\frac{1}{12}p$, we have $\left\|\mathbf{z}^{\mathscr{K}}-\mathbf{z}^{0}\right\|\leq\frac{3B}{32}$. By the Vector-Martingale Concentration Inequality in Theorem 2, we have with probability $1-p/12$,

where $\overset{a}{\leq}$ uses $\mathcal{I}_{k\leq\mathscr{K}}$ is measurable on ${\bm{\mathcal{F}}}^{k-1}$ and $\|\bm{\xi}_{\mathbf{v}}^{k}\|\leq\sigma$. We obtain

So with probability $1-p/6$, if $\mathbf{x}^{k}$ exits $\mathcal{B}\left(\mathbf{x}^{\mathcal{K}},B\right)$ in $K_{0}$ iterations, we have

Now, we have all the ingredients necessary to prove Proposition 3:

We first bound the noise term $\sum_{k=1}^{\mathscr{K}}\left\langle\nabla g_{\mathcal{S}\bot}\left(\mathbf{v}^{k-1}\right),\bm{\xi}_{\mathbf{v}}^{k}\right\rangle$. We have for all $k$ from $1$ to $K_{0}$

From (D.49), and $\|\bm{\xi}_{\mathbf{v}}^{k}\|\leq\sigma$, we have

by Data-Dependent Berinstein inequality in Theorem 3 with $\delta=\frac{p}{3\log(K_{0})}$, we have with probability at least $1-\frac{p}{3}$,

where $\overset{a}{\leq}$ uses $\sqrt{ab}\leq\frac{a+b}{2}$ for $a\geq 0$. Substituting (D.66) and (D.67) into (iv), with probability at least $1-3/p$, we have

Fusing (D.68) with (8) in Lemma 8, using $\frac{7}{8}-\frac{1}{8}\leq\frac{25}{32}$, we have with probability at least $1-\frac{7}{12}p$ ((D.19), (D.24), (D.2), and (iv) happen),

Finally, applying Lemma 9, if $\mathbf{x}^{k}$ moves out of the ball in $K_{0}$ iteration, with probability at least $1-\frac{2}{3}p$ ((D.19), (D.24), (D.2), (D.59), and (iv) happen), we have

Combining Case 1 and Case 2, we obtain Proposition 3. ∎

Appendix E Deferred Proofs of Part III: Finding SSP

Clearly, under the random event $\bm{\mathcal{H}}_{0}$ in Part I happens, we know that if $\lambda_{\min}\nabla f(\mathbf{x}^{0})\leq-\delta_{2}$, $\mathbf{x}^{k}$ must gone out of the ball. Thus with probability at least $1-p/3$ (the random events $\bm{\mathcal{H}}_{0}$ in Part I happens), if $\mathbf{x}^{k}$ does not move out the ball in $K_{0}$ steps, we have $\lambda_{\min}\left(\nabla f(\mathbf{x}^{0})\right)\geq-\delta_{2}$. Using that $f(\mathbf{x})$ has continuous Hessian, we have

To a give upper bound on the $\|\nabla f(\bar{\mathbf{x}})\|^{2}$, we follow the idea by considering quadratic approximations in Part II. We have

where in $\overset{a}{\leq}$, we use the gradient of the quadratic function $g(\cdot)$ is a linear mapping.

By the Vector-Martingale Concentration Inequality, we have with probability $1-2p/3$,

Using $\|\bar{\mathbf{x}}-\mathbf{x}^{0}\|\leq B$, we have $\left\|\nabla f(\bar{\mathbf{x}})\right\|\leq\left\|\nabla g(\bar{\mathbf{x}})\right\|+\frac{\rho B^{2}}{2}\leq 18\rho B^{2}$.

In all, we have with probability at least $1-p$, $\lambda_{\min}\left(\nabla f(\bar{\mathbf{x}})\right)\geq-17\delta$, and $\left\|\nabla f(\bar{\mathbf{x}})\right\|\leq 18\rho B^{2}$. ∎

By union bound, with probability at least $1-T_{1}\cdot p$, if at step $T_{0}=T_{1}\cdot K_{0}$, Algorithm 2 has not stopped, $\mathbf{x}^{k}$ must have moved out of the ball at least $T_{1}$ times, then from Proposition 3, the function values shall decrease at least

Contradiction with Assumption 2. Thus with probability at least $1-T_{1}\cdot p$, Algorithm 2 shall stop before $T_{0}$ steps. Further, fusing with Proposition 4, we have with probability at least $1-(T_{1}+1)\cdot p$, Algorithm 2 outputs a second-order stationary point satisfying (2.7) in $T_{0}$ steps.

Appendix F Proof of Proposition 1

Let $\mathbf{v}$ be an arbitrary unit vector, and due to symmetry in below we assume WLOG $\mathbf{v}=\mathbf{e}_{1}$. Recall we have set $\mathcal{A}$ satisfying the $(q^{*},\mathbf{v})$-narrow property in Definition 2. Then

Therefore we have for any $\mathcal{A}$ admitting $(q^{*},\mathbf{v})$-narrow property where $q^{*}=(\sigma/4\sqrt{d})$, that for any given $\bm{\chi}_{\backslash 1}$,

where $\mathcal{A}[\bullet,\bm{\chi}_{\backslash 1}]$ is of Lebesgue measure $\leq 1.1q^{*}$. Taking expectation again gives

and we complete the proof that $\bm{\xi}=\sigma/\sqrt{d}*\bm{\chi}$ is $\mathbf{v}$-disperse for any $\mathbf{v}$.

and analogously for $\mathcal{B}^{d-1}$. We have