Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity
Authors: Daniel Yiming Cao
August Y Chen
Karthik Sridharan
Benjamin Tang
Venue: NeurIPS 2025 poster ()
Keywords: Non-convex optimization
stochastic optimization
second order stationary points
generalized smoothness
Primary area: optimization
TL;DR: We develop a new framework and establish convergence to second order stationary points under generalized smoothness

Abstract: We study the optimization of non-convex functions that are not necessarily smooth (gradient and/or Hessian are Lipschitz) using first order methods. Smoothness is a restrictive assumption in machine learning in both theory and practice, motivating significant recent work on finding first order stationary points of functions satisfying generalizations of smoothness with first order methods. We develop a novel framework that lets us systematically study the convergence of a large class of first-order optimization algorithms (which we call decrease procedures) under generalizations of smoothness. We instantiate our framework to analyze the convergence of first order optimization algorithms to first and *second* order stationary points under generalizations of smoothness. As a consequence, we establish the first convergence guarantees for first order methods to second order stationary points under generalizations of smoothness. We demonstrate that several canonical examples fall under our framework, and highlight practical implications.

Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity
Daniel Yiming Cao"
August Y. Chen' Karthik Sridharan' Department of Computer Science, Cornell University {dyc33, ayc74, ks999, bt283)0cornell..o edu
Benjamin Tang"
Abstract
We study the optimization non-convex functions that are not necessarily smooth (gradient and/or Hessian are Lipschitz) using first order methods. Smoothness is a restrictive assumption in machine learning in both theory and practice, moti- vating significant recent work on finding first order stationary points of functions satisfying generalizations of smoothness with first order methods. We develop large
novel framework that lets us systematically study the convergence class of first-order optimization algorithms (which we call decrease procedures) under generalizations of smoothness. We instantiate our framework to analyze the convergence of first order optimization algorithms to first and second order station- ary points under generalizations of smoothness. the first convergence guarantees for first order methods to second order stationary points under generalizations of smoothness. We demonstrate that several canonical examples fall under our framework, and highlight practical implications.
a consequence, we establish
Introduction
widely studied problem in machine learning (ML) and optimization is finding First Order Stationary Point (FOSP) of a generic function F with domain Rd. defined as follows:
Given tolerance 0, find such that F/ s.
(1)
The methods of choice in theory and practice for this task are Gradient Descent (GD), Stochastic Gradient Descent (SGD), and variants thereof. Under the additional assumption of (second-order smoothness on F. i.e. that the gradient VF is Lipschitz with parameter understood. In several settings such as with access to exact gradients, stochastic gradients, Hessian- Vector Products, and the exact Hessian we have matching upper and lower bounds. The literature on this problem is extensive; for subset see e.g. Ghadimi and Lan (2013); Johnson and Zhang (2013); Fang et al. (2018. 2019); Foster et (2019); Arjevani al. (2020); Carmon et al. (2020. 2021).
this task is well-
However, for many non-convex functions F, FOSPs are uninformative. A significant and difficult problem established in the literature for over decade which carries strong theoretical and practical implications in optimization for machine learning is establishing efficient rates for finding a Second Order Stationary Point (SOSP). In many non-convex optimization problems such as Phase Retrieval and Matrix Square Root (Ge et al., 2015; Jin et al., 2017; Ge et al., 2017; Sun et al., 2018), SOSPs are global minima. Finding a SOSP defined as follows:
Given tolerance > 0, find w such that |VF(w) s F, 2 -VEI,
(2)
where 2 denotes the PSD order, I the d d identity matrix, and v F(w) is the Hessian of F.?
Under the additional Hessian Lipschitz assumption, that the operator norm of the Hessian 2 in addition the gradient VF is Lipschitz, this task also well-understood. Under these regularity
Authors are listed in alphabetical order.
2 There are several definitions a SOSP; see Remark for why we use this definition here.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

assumptions, finding SOSPs is classical under exact oracle access to the full Hessian V²F. Decades ago, it was shown that cubic regularization and trust region methods succeed (Nesterov and Polyak, 2006; Conn et al., 2000), with matching lower bound in Arjevani et al. (2020). Motivated by the success of non-convex optimization in MI. via first order methods, solving this problem (2) with first order methods has seen much recent study (Ge et al., 2015; Jin et al., 2017; Fang et al., 2019; Arjevani et al., 2020; Jin et al., 2021a). We have matching upper and lower bounds in several cases, such as for SGD which is perhaps most relevant to ML (Fang et al., 2019; Arjevani et al., 2020).
However, in many optimization problems in ML, the gradient and Hessian of the loss function is not Lipschitz. This was observed empirically through extensive experiments of Zhang et al. (2019) on LSTMs and of Crawshaw et al. (2022) on transformers. We provide theoretical examples in Subsection 3.6. As such, a line of work began in Zhang et al. (2019) on studying finding FOSPs under weaker regularity assumptions, see c.g. (Zhang ct al., 2020; Jin et al., 2021b; Crawshaw et al., 2022: Reisizadeh et al., 2023; Li et al., 2023b; Wang et al., 2024; Hong and Lin, 2024; Gaash et al., 2025; Yu et al., 2025). The regularity assumption generally made is L1) -smooohhsssssss:: |[>](w)]] op s Lo + / [w)] for all w ε Rd for some Lo. L 2 O. This allows for arbitrarily polynomial growth rates of F in |//]. The guarantees in Zhang al. (2019) and follow-up works generally hold for adaptive methods, presented as theoretical justification for gradient clipping.
The authors of Li et al. (2023a), under milder regularity assumption than Zhang et al. (2019), studied finding FOSPs via fixed-step-size GD and SGD rather than adaptive methods. In particular, Li et al. (2023a) demonstrated clipping is not necessary for (Lo, L1 -smoohhhh functions. Related works extended this analysis to Nesterov's ' Accelerated Gradient Descent (Li et al., 2023b; Hong and Lin, 2024). Xie al. (2024) studied finding SOSPs under (In, L1 -smoothnness and similar assumption that for all w. in a small neighhorhood of w, the Hessian of F is Lipschitz with parameter Mo+ M1 V F((w) F(w)]: []. However, their algorithm is second-order and requires the full Hessian, analogous to classical work (Nesterov and Polyak, 2006; Conn et al., 2000). This contrasts with recent developments of finding SOSPs using first order methods when F has Lipschitz gradient and Hessian, which are more pertinent to ML where first-order algorithms are the only tractable method (Ge et al., 2015: Jin et al., 2017; Fang al., 2019; Arjevani al., 2020; Jin et al., 2021a).
1.1 Our Contributions
In this work, we develop a novel framework to study non-asymptotic guarantees finding FOSPs and SOSPs via first-order methods, for functions whose gradient and/or Hessian are not Lipschitz. Central to our work the following regularity assumption:
Assumption 1.1 (Second-Order Self-Bounding Regularity). F is twice differentiable, and there exists a non-decreasing function P1 : IR20 + Rgo such that || [[>? s (1(F(w)) for all w e Rd.
This assumption implies the relevant Hessian operator norm is upper bounded by a function of the function value. It was also made in De Sa et al. (2022) for the different task of studying global convergence of GD/SGD, where it was shown that Assumption 1.1 holds for many canonical non-convex optimization problems. Some quantitative control of the Hessian is necessary for non- asymptotic guarantees of finding FOSPs (Kornowski et al., 2024). In Example 1, we show these prior assumptions are not satisfied by a natural univariate function. We show in Proposition A.1 that Assumption 1.1 generalizes (Lo, LI)- smoothhesss and its extension from Li et al. (2023a), and that
(Lo, -mmoothtsssss (1Vv'11 op S Lo IVFI)
Assumption 1.1 with pi (x) = Lo.4L,0.
For finding SOSPs, we impose the following additional regularity assumption: Assumption 1.2 (Third-Order Order Self- Self-Bounding Regularity). F satisfies Assumption 1.1, and either:
F is three-times differentiable everywhere, and for some non-decreasing function P2 Bozo + Rgz, F("F( ll.p S p2 (2(F(w) (w)) for all w e TRd
* Or for some constant 8 > 0 and some non-decreasing function P2 R20 Rgo for all -
w, w' e Rd with ww- w' || s 8, we have (DFF(w)-VFFuel
S P2 (F w'll
Assumption 1.2 naturally extends Assumption 1.1, and generalizes the Hessian Lipschitz assumption ubiquitous in the literature on non-asymptotic rates for finding SOSPs. (We note that the works Lee et al. (2016, 2019) established asymptotic guarantees for GD finding SOSPs without the Hessian
2

---

Lipschitz assumption, and note their proof strategy uses Lipschitzness of the gradient in a crucial way.) In Subsection 3.6, we show several canonical non-convex losses with non-Lipschitz gradient and Hessian satisfy Assumption 1.2. Assumption 1.2 covers several growth rates of interest (e.g. univariate self-concordant functions satisfying Assumption 1.1). It also subsumes that of Xie et al. (2024), which to our knowledge is the only other result on finding SOSPs under generalized smoothness (but uses the full Hessian). Under the assumptions of Xie et al. (2024), an explicit, simple form for p2(-) can be found. We detail all of this in Example 2.
Furthermore, Assumption 1.2 encompasses several examples of Distributionally Robust Optimization (DRO) problems. Xie al. (2024) very interestingly demonstrates that under mild assumptions, the objective of DRO satisfies their Assumption 3, see Theorem therein. Assumption of Xie et al. (2024) is subsumed by Assumption 1.2 as per our Example 2. Thus our results apply to DRO. DRO a general optimization problem that has significant applications in fairness in machine learning and in learning under distribution shifts; Xie et al. (2024) for more discussion.
We now introduce the following standard definition, which, when combined with Assumption 1.1 and Assumption 1.2, forms the core of our argument, as we explain in Subsection 2.1.
Definition 1.1. For function F and threshold a, the a-sublevel set of F is LF {w: :()) s a}.
Now, our contributions are as follows:
1. We develop a novel, systematic framework detailed in Section 2 and Theorem 2.1 to study the convergence of first order methods to FOSPs and SOSPs under Assumption 1.1 and Assumption 1.2 respectively. The core idea is in Subsection 2.1. Our framework lets us systematically analyze existing practical, and widely used first-order optimization algorithms in the challenging generalized smooth setting,
2. Main Results, non-asymptotic convergence SOSPs: Under Assumption 1.2, we estab- lish efficient rates for first-order optimization algorithms finding SOSPs. See Theorem 3 3.4 for Perturbed GD (Jin et al., 2017) and Theorem 3.5 for Restarted SGD (Fang et al., 2019). The dependence on d matches that in the smooth setting, and in particular is polylogarith- mic in d. This is particularly pertinent for ML applications, where the ambient dimension is large that the second-orde, methods of Xie et al. (2024) are not feasible.
3. Non-asymptotic convergence to FOSPs: Under Assumption 1.I, we establish efficient rates for GD, Adaptive GD, and SGD finding FOSPs. See Theorem 3.1, Theorem 3.2, and Theorem 3.3 respectively. The dependence on E, d again matches that in the smooth setting.
4. We provide examples and practical implications in Subsection 3.6. Our examples are direct corollaries of Theorem 3.4, Theorem 3.5. They show variants of GD/SGD globally optimize non-convex 'strict-saddle' losses from ML. with non-Lipschitz gradient and Hessian.
Notation: Bpp, R) denotes the Euclidean l2 ball centered at p E Ed with radius R 2 O, with boundary, By shifting, we assume WLOG that F' attains a minimum value of 0. We follow the convention that F is smooth, specifically L-smooth, if | Fl| s L holds globally. We always let wo denote the initialization of a given algorithm (which is clear from context) unless stated otherwise.
2
Main Idea
2.1 High Level Idea
One classic analysis of GD on smooth functions to converge to FOSP goes by establishing decrease per iterate, via the so-called 'Descent Lemma' (Bubeck et al., 2015). For L-smooth functions, setting the step size 1 = 1 in GD,
F(W+1) S F(w,) 7(1 - (17--1n)1 (=F())) =F(())
1 IVF(w.))
(3)
2L
Such an analysis fails if F is not L-smooth. Following the above recipe under Assumption 1.1, as such a bound < oo need not exist, one must set 7) = and does not obtain any convergence rate.
Core Insight 1: The first simple but powerful insight in our work is that many optimization algorithms such as GD decrease the function value at each iterate (with high probability) when y is appropriately chosen function of the smoothness (Hessian operator norm) at the current iterate.
3

---

Specifically, consider iterates of GD initialized at some Wy. For step size 77 small enough in terms of [V2F(wo)) ||, the next iterate W1 of GD is sufficiently 'local' (see Corollary 1). This lets us upper bound || along the segment W by increasing function Li (FWW)) of F(wo) (see Lemma 3.2). Thus, for appropriate in terms of F(wn), obtain F F(w1) s F(Wo), and so w lies in the (sublvvelleell set F(wo))
Core Insight 2: Crucially, we can 'chain together' this decrease. By Assumption 1.1, the afore- mentioned argument goes through at any w in the -subleelll set Cy.F(w)) - in particular, at w1. Consequently, this same step size 1j small enough to ensure F(w2) < F(w,) N F(wo), and so forth through all the iterates of GD. Moreover, this argument yields a convergence rate. As each iterate ((w.)) the gradient norm is at least at each iterate, we obtain decrease of least
2L, (P(w)) per iterate analogously (3). Too many iterations contradicts that F is lower bounded by
0 (recall Notation), so we must reach an iterate w, which is a FOSP within (F,(F())) iterates.
e²
Generalizing the argument: This idea is powerful enough to readily analyze SGD and variants of GD/SGD which find SOSPs. Rather than a single iterate where decrease need not hold, we consider a sequence of consecutive fahres iterates. We show with high probability, the last iterate in this sequence decreases function value for w ε F(wo)))) To do so, recall the analyses of first-order optimization algorithms often establish decrease by considering 'local' behavior. Locally around FF Assumption 1.1 and Assumption 1.2 give enough control over the relevant derivatives to do so.
Then the above argument still goes through, with fixed step size defined in terms of F(wo). We group the iterates of the algorithm into 'blocks' of length Litress and establish F( S F (wn) and so forth (rather than establishing F(w2) s F F(w1) F F(Wo) for consecutive iterates).
2.2 The Formal Framework
Consider a set of interest S, e.g. FOSPs or SOSPs with tolerance e. We begin by presenting a simpler version of our formal framework. Consider deterministic update procedure A : R Rd where the output of A denotes the future iterate of the algorithm. For example, A(w) = w FVW) for GD. Following Subsection 2.1, we consider algorithms that decrease function value in the F(wa)- -sublevel set FF ((w)) if they have not reached S. The following definition formalizes this property:
Definition 2.1 (Special case of Decrease Procedure in Definition 2.2). Consider set of interest S, decrease threshold
O, a point us. and deterministic procedure to compute the next iteration. We say A forms (S, (.,oeette (uo), A (un). -decrease procedure if computing A(uo) takes at most Loracle (uo) oracle calls, and one of the following holds:
1) F(A(uo)) < F(uo) - A(uo), or
2) SS+ (--
Here 1) means that the subsequent iterate has smaller function value, and 2) means that the rule of output A2 outputs sequence of candidate vectors, one of which is S.
Then, Theorem 2.1 states that if A a decrease procedure for all ug in LF,F(wo)- we can bound the number of oracle calls for A to output candidate vector in S, e.g. for GD to output FOSP. We prove it arguing as in Subsection 2.1, 'chaining together' the decrease per iterate in Cy. (wo). as F is lower bounded, 1) in Definition 2.2 cannot occur too often, so 2) must occur at some point.
(wo)) Then
We now generalize this to randomized procedures which can output several candidate vectors.
Framework in full generality. Consider an update procedure A: Rdd - Rd xU (Red)" (possibly randomized). We now consider map A (A1, A: RRd + Rd U ( defined as follows:
For all e R A(u) (p1.P2) for p1 E Rd, .2 (R")", and define A A1 :=) A2)) := P2-
Intuitively, An computes a future iterate A₁ (u). A2 outputs sequence of candidate vectors in Rd among which we hope one lies in S (e.g. different candidate models in statistical learning).
However, the output of A₁ need not correspond to the 'next iterate' in the traditional sense. For SGD, Ai does not output the next iterate of SGD, but rather the iterate produced by SGD after Ko > steps. This is necessary to guarantee decrease; single step of SGD need not decrease the value of F, but with high probability and large enough Kg. a consecutive 'block' of Kg iterates will. We will lay this out concretely next in Subsection 2.3.

---

Remark 1. Often A2 will output a single vector in R which we hope lies in S, but this is not always the case. Consider guarantees for GD or SGD, which upper bound + (FW,),) E² the set of FOSPs to
or + Ei=1 | F(w,)] á e. This only ensures a single w, S, 1 i 7 where tolerance (e.g. Zhang et al. (2019), Jin et al. (2021b), Li et al. (2023b), Xie et al. (2024) and many others). Consequently [W..... WT) ) is our sequence of candidate vectors, and the guarantee obtained is that w E S for some st... We thus allow for A2 to output multiple candidate vectors.
The following definition formalizes common property of optimization algorithms we study:
Definition 2.2 (Decrease Procedure). Consider a set of interest S, a confidence parameter > 0, a decrease threshold A O, point up, and a procedure A compute the next iteration. We say A forms (S, foracte (ua) ( , A (((u)), ( -dec-ede procedure if with probability at least 1 5( over the randommess in to compute A(ua) from uo, computing A(uo) takes at most Lorale (uo) oracle calls, and one of the following holds:
1) F(A)(u))) < F((u) A(wo),
2) A2 ng ().
Here 1) means that the subsequent iterate has smaller function value, and 2) means that the rule of output A2 outputs sequence of candidate vectors, one of which is in S. A forms (S, foracee (Uo)) ((uo), 6(w)), un 40)--dcreasss procedure 1) or 2) occurs with high probability.
For analogous reasons as before, we will establish that if A is decrease procedure for all un in (FFF(w))> we can bound the number of oracle calls for A₂ to output candidate vector lying in Formally, this is Theorem 2.1.
Informal Theorem:
2.3 Examples Subsumed by Framework
We demonstrate that a host of first-order optimization algorithms are covered in our framework, and highlight the general recipe for using our framework.
GD: Starting from u, the next iterate of GD with step size v > 0 tu -7V
1. For e > O, let (w: || F w) s s), , the set of FOSPs.
2. For all uo Rdd let A(uo) = (uo- VV (Vu))) uo). Hence, A1(w)) = udo n/ F(u).
A2(un) Mo. and foructe (uo)
3. In Claim 1, we establish that if F is satisfies Assumption 1.1, then A is decrease procedure for all ug LF.F(w.)) for suitable v) depending on F(wo). Our result for GD, Theorem 3.1, subsequently follows by our general framework Theorem 2.1.
Starting from u, the next iterate of Adaptive GD is Thu P(u), where Y/u > is an adaptive step size that depends on u.
Adaptive GD:
For E O, let (w: : |VF(W) S 5s), , the set of FOSPs.
2. For all uo E R.d, let A A(uo) = (uo - Thu V F(un), uo). Hence, A AI(u)) = uo v7V F(n), A2(w)) Mgg and foracto (uo)
3. In Claim 4, we establish that if F is satisfies Assumption 1.1, then A is decrease procedure for all ug E FF.F(()))) for suitable The depending on F(w;) and [v]]]]] Our result for Adaptive GD, Theorem 3.2, then follows by Theorem 2.1.
However, for SGD and other randomized algorithms involving randomness, 1) in Definition 2.2 does hold deterministically. This is where the generality in our framework powerful. For SGD, by concentration inequalities we show that 1) is true with high probability over a long enough 'block' of subsequent iterates, long as none of the iterates the block have small gradient. We then define A so that A₁ outputs the composition of the SGD steps in the block, and A outputs all the iterates of the block. The resulting guarantee that one of the points among all the blocks lies S.
Starting from u, letting V f (u; () be stochastic gradient oracle where Ç is minibatch sample, the next iterate of SGD is 7/V (u; where 7) > 0 the step size.
SGD:
1. For 0, let S (w: | w) S 5). the set of FOSPs.
5

---

2. Consider any Kg 2 1. For all uy RR, let Po and define a sequence (pi (Pisocs<K, via where the Çi are i..d. minibatch samples. Note this sequence can be equivalently defined by repeatedly composing the function u u 1/ / (). We then define A(uo) (Px,: (P: )osis hence A (4n) = PK., A2(un) (p: usis Ko-1- Note all the P; are function of Mg and the randomness in the stochastic gradient oracle Vf()). We let foracle (Wo) (un) = Ko. which need not equal 1. This procedure is clearly SGD, with its iterates divided into blocks of length Ko-
P: = - PP-1-nyf(p---iiC)
3. Claim 5, we establish that if F is satisfies Assumption 1.1 and f(:)) satisfies Assumption 3.1, then A is a decrease procedure for all uy é Lr F((n)) for suitable algorithm parameters. Our result for SGD, Theorem 3.3, then follows by Theorem 2.1.
SOSP-finding algorithms: We now study finding SOSPs using first order methods under regularity assumptions. We analyze two algorithms to achieve this under exact and stochastic gradients, respectively Perturbed GD (Algorithm 1, Jin et al. (2017)) and Restarted SGD (Algorithm Fang et al. (2019)). We remark that our framework likely subsumes many other algorithms.
Perturbed GD: This algorithm, formally written in Algorithm 1, Section D, is as follows. At u,
If | FV)) Ithres for some appropriate Ithres the algorithm simply runs step of GD.
Else, Algorithm 1 adds uniform noise from ball with particular radius and runs GD for fitres iterations for suitably chosen furees yielding u'. We check if F(u') - F(u) S ffhres for some appropriate fures. If decrease does not occur, return if decrease occurred, go back to the If/Else with u' in place of u.
Notice now that the oracle complexity loracles probability 8, and amount of decrease A depend on the location u. Our framework readily subsumes this example as follows.
1. For E O, let S = {ww: [[)(()) < (FW)) =-EE), the set of SOSPs.
2. For all un e Rd, if F 9tness we let
A(uo) = (uo - 7/V (uo). un); hence Ai (uo) up 1/ F(un), un-
Otherwise ((w))) S Ithres: we let Po un f where & is uniform from B(O,r), and define sequence (p, osistue via p. Pi-1 FV-F(P.1). We then define
A(uo) (Ptn.. 2u)) hence A1 (uo) Penves A2(uo) un.
Thus
fahres :|VF(uu)) S Pthres
foracte (uo)
(Voo( Ithres
This identical to Algorithm 1, and highlights why loralle, 5, A need to depend on thn-
3. In Claim 2, we establish that if F satisfies Assumption 1.2, then A is a decrease procedure for all uo e Ly,F(wo) for suitable algorithm parameters. Our result for Perturbed GD. Theorem 3.4, then follows by Theorem 2.1.
Restarted SGD: This algorithm, formally written in Algorithm 2, Section E, works as follows.
Take B ( Ko = Ô(==?). Consider an anchor point u. first taken to be the initialization Wo- The algorithm runs SGD until its iterates first escape the ball B (u,, B), tracking most Ko iterations.
If an escape occurs within K, iterations, letting u' be the first iterate that escaped B u, B), the algorithm sets u' to be the anchor point and runs the same procedure.
If these Ko iterates do not escape within Ko iterations, return their average.
We cover Restarted SGD in our framework as follows.
1. For E 0, let S = {w: [V)(w) S F2 -EE], the set of SOSPs.
2. For all ug E Rdd let Po un- We define a sequence (p:)osisko via p: = Pi-1 ((V/((.rr:.)) + GA*), where v((:)) our stochastic gradient oracle, the Ç; are i.i.d. minibatch samples, the A B(O 1) are i.i.d., and is parameter governing the noise level. Note this sequence can be equivalently defined by repeatedly composing the function

---

u - - u-n((f + If it exists, let i, S i S Ko be the minimal index such that pp -P--Pol -oll B. Otherwise let i Ko. In either case, we define
- ΣE P...
A(uo)= Pi:
hence Al(ua) A2(u))
Σpe
Pt-
1=0
1=U
We let loraclo (uo) Ko. This is clearly identical Algorithm 2.
3. In Claim 7, we establish that if F satisfies Assumption 1.2 and f-:-) satisfies Assump- tion 3.1 and Assumption 3.2, then is decrease procedure for all un Cr.F(wr)) for suitable algorithm parameters. Our result for Restarted GD, Theorem 3.5, then follows by Theorem 2.1.
Theorem 2.1 (General Framework). Consider given initialization wa of A and a desired set S. Define a sequence (W:)120 recursively by Wx+1 = Ai (w.). Suppose that for all un & FFF((.)) A forms a (S, (uo), (uu)), 0(uo), (n)):)oreedssss procedure. Define A -infueCr F(w)) (u)
A(u)
Then with probability at least
F(wn) A(u)
upon making N F(Wo) A
1 sup (ECF)
8(u)- sup
sup F.
forate (u)
oracle calls, there exists We (wo)tzu such that A2(w:) n & (). Lee. for some wi As will outpul a sequence of candidate vectors, one of which is in S. Furthermore, the outpul of A2 has
length most S, then the number of candidate vectors outputted is most S.SUPucCp.Ftem)
F(ww))
A(u)
Our full proof is in Section B.* The proof formalizes the main idea from Subsection 2.1, by 'chaining together' the decrease per iterate in LF.F(wo) Then as F is lower bounded, 1) in Definition 2.2 cannot occur too many times, 2) must occur some point.
To verify A is a decrease procedure in L FF.(())): we can systematically port over analyses in the literature. As discussed in Subsection 2.1, 4gg being in L F(we)))) allows us show the algorithm is 'local', crucially giving us quantitative control over the relevant derivatives. We view this as a core strength of our work; our framework allows us systematically extend results from the smooth setting to generalizations of smoothness.
Remark 2.
Convergence Results
Here we systematically obtain our convergence results for the algorithms listed Subsection 2.3, by formally showing that they are decrease procedures. Our main results are Theorem 3.4, Theorem 3.5: that under Assumption 1.2, variants of GD/SGD can find SOSPs. We note our dependence on d for Theorem 3.1, Theorem 3.2, Theorem 3.3, and Theorem 3.5 match lower bounds for smooth functions (Carmon et al., 2020, 2021; Arjevani et al., 2020), and hence are optimal in this setting too. We present examples and implications of our results in Subsection 3.6.
our results, the step size here depends only on Pı(F wo)): ), fixed value depending only initialization. Moreover, the expressions 1j depending on pi (w))) in our results and proofs to follow are only an upper bound for working step sizes. We do need know these exact values. Therefore, all that is needed is upper bound on fixed quantities such as pı ( (F(w))) ) hence a working step size v) for our algorithms in practice and theory can be found using cross validation or binary search.
Remark 3 (Dependence on Initialization).
Letting (ww)) be an upper bound on the step size 7 needed to guarantee convergence, we note by searching over log( (w)) with binary search, we will find an r) with a constant factor of 77 (w)). This log factor will be logarithmic in e, d. and will only change the claimed iteration complexity by universal constant factor. The latter is because the amount of decrease in the definition of Decrease Procedure will in turn only change by universal constant multiple
'Defining i as above, note that we can compute A(uo) using i rather than Ko oracle calls, but this change does not affect runtime beyond constant factors.
*The extra second term in the sum defining occurs as forall: A, have uo-dependence. Dependence e in Theorem 3.3 and d in Theorem 3.5 tight up to log factors.
7

---

Remark 4 (On Adaptivity), Our results hold for non-adaptive versions of GD/SGD and their variants. That said, one can interpret cross validation binary search over 7 as adaptive algorithms their own right. As mentioned above, it is relatively straightforward to obtain analogous results to our current ones for cross validation or binary search. the learning from data setting, one can make the cross validation result formal using classic techniques.
3.1
Gradient Descent
Theorem 3.1 (GD for FOSP). Suppose F satisfies Assumption 1.1. Run GD initialized at wo, with step size 17 (wo) where L1 (wa) is defined in (4). Then letting
T 2F 2F(ww)Li(w)) within T 1 oracle calls 4 F().
GD will output candidate vectors (PI..... Pr)), one of which satisfies F[v)(p))
We prove Theorem 3.1 here to show our strategy's simplicity. The following Lemmas, proved in Subsection A.3, help show GD is 'local' for FF
Corollary 1. For F satisfying Assumption I.I, we have | [V((w] I Po Po(F(w)), where Po l820
Rso is non-decreasing function given by Pu(x) p1 p1 28(x). where 8(x) -0" pI(u) pr(odde.
Lemma 3.1. Under Assumption for x, with yy - x s (o(F(a)-T) F F(x) 1
Combining the above with Assumption 1.1 immediately gives:
Lemma 3.2. Suppose F satisfies Assumptioo 1.1. Defining po as in Corollary 1, let
Li (wo) = max po PF (wo) + (F)) + 1), (F(w)) 1)). Then for all w e LF,F(w))) F op $ L1 (wo) for all E B W. Pa F (wo) + 1)-1)
(4)
Proof of Theorem 3.1. Use Theorem 2.1 with S (w : [VF(w)] s E). defining AA as in Subsection 2.3. Upon applying Theorem 2.1, the following Claim directly proves Theorem 3.1:
e² Claim 1. For any up in (FFF((W)) A is (S, 2L,(w,) O. un) -eecress procedure.
To prove Claim 1, note for un E S, by definition of Aa that Ag(ua) ) (un) E S. Now if un & S (i.e. V F(u))) > 8), consider 4 Ai (uo) = Un 1/V F(ua). By Corollary and as F(uo) s F(Wa),
V un) $ Po (P((F(u)) s Po (((w)). so by choice of 1),
|lu1 uul 7 (u.) S npo ((ww)) Po (o(FF(o))))))) + 11
By Lemma 3.2, for all p in the line segment Lzسn. ( S L1 (wo). By Lemma A.I, which only depends on the smoothness constant in the segment between the two iterates (see Subsection A.1),
F(u1) s F (uo) F (ww))' [VF(u))] < F(uo) 2L,(wo)
as V F(u))) e and by our choice of n,. This proves Claim 1, completing the proof.
Note is critical here that un the Fublevsulleve set. Also, to satisfy Corollary 1, po(x) just needs to be non-decreasing pointwise upper bound of P1 (x) (20x))(();)
(r). For example when F is (Lo, L1) -mooth, we show Proposition A.2 that we can take po (x) 2L 1/2 1/2 + 5L Lo 1/ 3//2
3.2 Adaptive Gradient Descent
Our proof and framework readily adapt to Adaptive GD, discussed Subsection 2.3. It even easier as Adaptive GD is automatically 'local" via gradient clipping. Our proof is in Subsection C.I.
Theorem 3.2 (GD for FOSP). Suppose F' satisfies Assumption 1.1. Run Adaptive GD initialized We-
with adaptive step size The = min
[((w))' ' Po (F( where L' (wo) (W(F(w)) 1).
Let T
(F(w)
Within T 1 oracle calls to VF()), Adaptive GD will output T
(w0)
min 2- (wg)
candidate vectors (p.,.... pT) one of which satisfies | (VF(p.))

---

3.3 Stochastic Gradient Descent
We make the following assumption on the stochastic gradient oracle:
Assumption 3.1. The stochastic gradient oracle V ((s))) is unhiased (L.e. E3 [: VF()) and for non-decreasing function a : R + R² and all w, Ç, [V VF ( (F((w)))
In many problems of interest in MI., noise scales with function value (Wojtowytsch, 2023, 2024); Assumption 3.1 captures this setting. Note we do not assume a global bound on |V or F, thus noise unbounded. We show in Remark 7 that one can extend Theorem 3.3 to when V.f(w; is sub-Gaussian with parameter o (F(w)) with a longer technical argument. We also note that bounding L2 gradient error in terms of function value has been studied denoted by the expected smoothness assumption in Gower et al. (2019, 2021).
vF(w)l
Theorem 3.3 (SGD for FOSP). Suppose F satisfies Assumption 1.1 and that the stochastic gradient orucle v ((())) satisfiey Assumption 3.1. For any 8 e (0, 1). run SGD initialized at wo. for given fixed step size 7j Ō(=²) depending E, 8, and F(wo). Then with probability at least 1 8, within
T T= Ó( - polylog(L/s,,1/)) oracle calls to vf(;)),
SGD will outpul T candidate vectors w, one of which satisfies V (w)) s.
Here Ö(-) hides additional ((eoo)-deeeddnnce Our full proof is in Subsection C.2. As discussed in Subsection 2.3, the idea is similar to the proof of Theorem 3.1, except we now establish high- probability decrease over blocks of consecutive iterates using concentration inequalities.
3.4 Perturbed Gradient Descent
Theorem 3.4 (Perturbed GD for SOSP). Suppose F satisfies Assumption 1.2. For any 5e (0,1), run Perturbed GD (Algorithm I, from Jin et al. (2017)) initialized at Wa. with appropriate step size n and other parameters depending E, 5, d, and F(Wo). Then with probability at least 1 - 5, within
T T= log" ) oracle calls to VF((), E2
Perturbed GD outputs T candidates w, one of which satisfies [vF(w)] S ( -VEl.
Remark 5. Here we find w with F²F(w) -EE,, which is most sensible without Lipschitz Hessian.
For Perturbed GD here in Subsection 3.4, asymptotic notation hides universal constants and depen- dence on F(Wo). The full proof is in Section D; here we give the main ideas. Define A, loraete as in Subsection 2.3 for Perturbed GD. Consider Ithres O(E), fihres = @(5..5) defined in Algorithm 1. Let
Sthres F(u)) S Jihres |VF (Fo))) Jthres-
A(uo)
1 Pures
The central Claim is as follows, from which Theorem 3.4 follows directly via Theorem 2.1:
Claim 2. For all us Cr.F(wo) A a (S,torate(uu)) A(uo), where x O(og( (I))(=AA)) and Li (wo) is defined in (4).
dL)(wo) ex xx uo) (xx,,x))deereeaee decrease procedure, VE
Perturbed GD is decrease procedure only in L FFF((w)) where we have quantitative control on F and its derivatives using our framework crucial. To prove Claim 2, we note the analysis of Perturbed GD in Jin et al. (2017) only considers 'local' points close to the current iterate the algorithm. Thus we can apply similar analysis, using Lemma 3.1, Lemma 3.2, and the similar Lemma D.1 to give enough control over the derivatives of F between these "local" points close to ug (FFF(W))
3.5 Restarted Stochastic Gradient Descent
In addition Assumption 3.1, will make the following mild assumption on the error of the stochastic gradient oracle, a relaxation of Assumption of Fang et al. (2019).
Assumption 3.2. For every w, S. fw: () s f F(w)), where ps(:.)) : Roo x R.0 Reo is non-decreasing in both arguments.

---

Note if f(:{) satisfies the regularity assumptions of Zhang et al. (2019) or Li et al. (2023a) for every Ç, then Assumption 3.2 satisfied. However, Assumption 3.2 goes well beyond these assumptions. allowing for the operator norm of v² (+) to also diverge in (ww)."
Theorem 3.5 (Restarted SGD for SOSP). Suppose F satisfies Assumption 1.2 and V ((::) satisfies Assumption 3.1 and Assumption 3.2. For any å (0,1), run Restarted SGD (Algorithm 2, the same algorithm from Fang al. (2019)) initialized at Wo, with appropriate step size v and other parameters depending on e, ó, d, and F (Wo). Then with probability at least 1- - 5, upon making
T T= 1
oracle calls V f(()),
e3.5
Restarted SGD outpuls T candidates w, one of which satisfies [FF (3
constants, and logarithmic factors in d, d,1/e,16 1/ó. We specify the exact parameters and detail the proof in Section E. The proof follows our framework instantiated for Restarted GD in Subsection 2.3. The crux again is establishing that the algorithm is decrease procedure in the F(Wo)- -sublleel set, done in Claim 7.
Here O() only hides constant factors,
3.6 Examples
Several interesting problems in MI. and optimization, such as Phase Retrieval and Matrix PCA, can be globally optimized by finding a SOSP (but not a FOSP), and satisfy Assumption 1.2. See Section F for these verifications. Thus Theorem 3.4 and Theorem 3.5 immediately imply we can solve the following problems, with customized analysis required.
Phase Retrieval: We reconstruct a hidden vector w" E Rd with |w"|| || = using phaseless observations S = ((aj,0;)) where yj = (a,, )2 aj ~ NO, The population loss is (w) Ea-N(0.1a) (la, w)² (a, w )
Matrix PCA: Given d d symmetric positive definite (PD) matrix M. we aim to find w e R (the first principal component) minimizing (w) 1 /ww" M
3.7 Practical Implications and Simulations
Our results show under generalizations of smoothness, unlike with Lipschitz gradient/Hessian, the larger the loss is at initialization (larger F' F(wo)) and larger self-bounding functions p1 (-) shrink the 'window" for choosing working 17. Specifically, with larger loss initialization, the smaller the largest working step size is, in contrast to optimizing smooth functions. This implies in practice, for losses with non-Lipschitz gradient/Hessian,
should tane ri based suboptimality at initialization.
In Section G, we validate this finding through simulations with GD and SGD on several natural smooth and generalized smooth functions, namely F(w)= ||Aw|' for p 2, 3, 4, 5, 6. Our simulations show the above theoretical conclusions match behavior practice, validating the practical implications of our theoretical results on which step sizes successfully optimize generalized smooth functions.
4 Conclusion
We present systematic framework to amalyze the convergence of first order methods to FOSPss and SOSPs under generalizations of smoothness, extending key results in finding SOSPs via first-order methods to this setting. Our work elucidates fundamental behavior of first-order optimization al- gorithms, showing that "chaining together high-probability decrease' enables their success under generalizations of smoothness. Our framework applies for many other algorithms (e.g. Langevin Dynamics) and sets interest S (e.g. higher order stationary points, or minima with good gener- alization properties). It can also inform the design of new optimization algorithms, by designing procedures which are decrease procedures. These promising directions are left for future research.
5 Acknowledgments
We thank Dylan J. Foster and Ayush Sekhari for discussions, and Anthony Bao, Fan Chen, and Albert Gong for useful suggestions on the presentation of our manuseript.
'While the above assumes that f(:C) is twice differentiable, it can be easily phrased in terms of ()({))
10

---

References
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations. In Conference Learning Theory, pages 242-299. PMLR, 2020.
Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin, and Ambuj Tewari. High High--roobbbility Regret Bounds for Bandit Online Linear Optimization. In Proceedings of the 21 Annual Conference on Learning Theory, pages 342-342. Omnipress, 2008.
Sébastien Bubeck et Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357) 2015.
Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase Retrieval via Wirtinger Flow: Theory and Algorithms. IEEE Transactions on Information Theory, 61(4):1985-2007, 2015.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower Bounds for Finding Stationary Points I. Mathematical Programming, 184(1):71-120) 2020.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower Bounds for Finding Stationary Points II: First-Order Methods. Mathematical Programming, 185(1):315-355, 2021.
August Y Chen and Karthik Sridharan. Optimization, Isoperimetric inequalities, and Sampling via Lyapunov Potentials. Conference on Learning Theory, pages 1094-1153, 2025.
Andrew Conn, Nicholas IM Gould, and Philippe Toint. Trust Region Methods. SIAM, 2000.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to Unbounded Smoothness of Generalized SignSGD. Advances in Neural Information Processing Systems, 35:9955-99666 2022.
Christopher De Sa, Satyen Kale, Jason Lee, Ayush Sekhari, and Karthik Sridharan. From Gradient Flow Population Loss to Learning with Stochastic Gradient Descent. Advances in Neural Information Processing Systems, 35:30963-30976, 2022.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-Optimal Non-Conver Optimization via Stochastic Path- lath-Integrated Differential Estimator. Advances in Neural Information Processing Systems, 31, 2018.
Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp Analysis for Nonconvex SGD Escaping from Saddle Points. Conference on Learning Theory, pages 1192-1234, PMLR, 2019.
Gerald B Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
Dylan J Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, and Blake Wood- worth. The complexity of making the gradient small in stochastic convex optimization. In Conference on Learning Theory, pages 1319-1345. PMLR, 2019.
Ofir Gaash, Kfir Yehuda Levy, and Yair Canmon. Convergence of Clipped SGD Convex (L_0,11)- Smooth Functions. arXiv preprint wxXi:22502.16492 2025.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from Saddle Points Online Stochastic Gradient for Tensor Decomposition. In Conference Learning Theory, pages 797-842. PMLR, 2015.
Rong Ge, Chi Jin, and Yi Zheng, No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
Saeed Ghadimi and Guanghui Lan. Stochastic First-And Zeroth- Methods for Nonconvex Stochastic Programming. SIAM Journal on Optimization, 23(4):23411 2013.
Robert M Gower, Peter Richtárik, and Francis Bach. Stochastic quasi-gradient methods: variance reduction via Jacobian sketching, Mathematical Programming, 188(1):135-19) 2021.
11

---

Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General Analysis and Improved Rates. In International Conference on Machine Learning, pages 2200. PMIR, 2019.
Yusu Hong and Junhong Lin. On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions. Advances in Neural Information Processing Systems, 2024.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to Escape Saddle Points Efficiently. In International Conference on Machine Learning, pages 1734-1732.
PMLR, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points. Journal of the ACM, 68(2):1-29, 2021a.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-Convex Distributionally Robust Optimization: Non-asymptotic Analysis. Advances in Neural Information Processing Systems, 34: 2771-2782, 2021b.
Rie Johnson and Tong Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. Advances in Neural Information Processing Systems, 26, 2013.
Olav Kallenberg and Rafal Sztencel. Some dimension-free features of vector-valued martingales. Probability Theory and Related Fields, 88(2):215-244 1991.
Guy Kornowski, Swati Padmanabhan, and Ohad Shamir. On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization. OPT 2024: Optimization for Machine Learning, 2024.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient Descent Only Converges to Minimizers. In Conference on Learning Theory, pages 1246-1257. PMLR, 2016.
Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I Jordan, and Ben- jamin Recht. First-order Methods Almost Always Avoid Striet Saddle Points. Mathematical Programming, 176(1))3 2019.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and Non-convex Optimization Under Generalized Smoothness, Advances in Neural Information Processing Systems, 36, 2023a.
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of Adam Under Relaxed Assump- tions. Advances in Neural Information Processing Systems, 36:52166-52196, 2023b.
Yurii Nesterov and Boris T Polyak. Cubic regularization Newton method and its global performance. Mathemutical Programming, (08(1):177-20)) 2006.
Iosif Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probability, pages 1679-1706, 1994.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization. International Conference on Machine Learning, 2012.
Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced Clipping for Non-convex Optimization. arXiv preprint 200.::::33330088. 2023.
Ju Sun, Qing Qu, and John Wright. Geometric Analysis of Phase Retrieval. Foundations of Computational Mathematics, 18:1 131-1198, 2018
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, Tie- Liu, Zhi-Quan Luo, and Wei Chen. Provable Adaptivity of Adam under Non-uniform Smoothness. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 2960-2969, 2024.
Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis. Journal of Nonlinear Science, 33(3):45, 2023.
12

---

Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysis. Journal of Nonlinear Science, 34(1):16, 2024.
Chenghan Xie, Chenxi Li, Chuwen Zhang, Qi Deng, Dongdong Ge, and Yinyu Ye. Trust Region Methods For Nonconvex Stochastic Optimization Beyond Lipschitz Smoothness. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 16049-16057, 2024.
Chenhao Yu, Yusu Hong, and Junhong Lin. Convergence Analysis of Stochastic Accelerated Gradient Methods for Generalized Smooth Optimizations. arXiv preprint 1rXiv:2502.11125, 2025.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved Analysis of Clipping Algorithms for Non-convex Optimization. Advances in Neural Information Processing Systems, 13:15511-15521,
2020.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference on Learning Represen- tations, 2019.
Tong Zhang.
Learning Bounds for Kernel Regression using Effective Data Dimensionality. Neural Computation, 17(9):2077-2099 2099,, 2005.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatiin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] " provided a proper justification is given (c.g.. "error bars are not reported because it would be too computationally expensive" " or "we were unable to find the license for the dataset we used"). )) In general, answering "[No] " or "[NA] is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims the abstract and introduction clearly and accurately reflect the paper's contributions and scope. See the abstract and Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations and assumptions used throughout the paper. Our assumptions are clearly stated. In the rest of the paper, we state our claims clearly and reference the assumptions corresponding to each claim.
Guidelines:
14

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.mitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide full set of assumptions and complete and correct proofs in the paper. We define all assumptions, reference them throughout when used, and all proofs are provided in either the main body or appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
15

---

Answer:
[Yes]
Justification:
We provide all details necessary to reproduce the main experimental results.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide the code the supplementary material. The code has sufficient instructions to reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/ onlylicooooooooooooooooooommppee for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
16

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //n //nips.ccoo //ipps.ccppui ptpppp/g/espiiiiigdidieeesesee/e ottp://///ggiiee///oooooosoooooa sii.iiiiiiisioioiiiiooccccoc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We provide a full description of the training and details of our experiments. These provided in the Appendix along with experimental results; the Appendix is the only place our experimental results are presented.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We provide suitable error bars and detail all the settings of our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
17

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide precise compute information for our experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt////eurippp.epe httpss//eorssss.ccc/ll/////////
Answer: [Yes]
Justification: We have reviewed the NeurlPS code of ethics. The research conforms in every respect to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
The paper is theoretical study of non-convex optimization, which can help improve the training of non-convex models practice. There are many societal impacts of this, none of which we feel we need to particularly highlight here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations
18

---

(e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question:
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly credit all creators and/or owners of assets when used. When used, the license and terms of use are explicitly mentioned and are properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www/com///aao/o /amtattsssss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answ
Justification:
The paper does not introduce assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects
20

---

Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Question:
Answer: [NA]
The core method development in our research did not involve L.MSs in any original or important way.
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21

---

Additional Notation: For a matrix M, (MinnMM denotes its minimum eigenvalue, and (M) denotes its r-th largest eigenvalue. Thus X (M) X² ..... We denote the & & identity matrix by Ιs- We use (p. R) denote the full k-dimensional 12-ball centered at p R with radius R. including the boundary. When & is not specified explicitly, [p,, It) refers the (2-ball in R following Notation. All logarithms in the following are the natural logarithm. For an event S, 1s denotes the indicator function. In the following, the norm I-|l of matrices and higher-order tensors refers to the operator norm unless otherwise stated. The norm |-| of vectors refers to l2 Euclidean norm.
Contents
1
Introduction
1.1
Our Contributions.
2
Main Idea
2.1
High Level Idea
2.2
The Formal Framework
2.3
Examples Subsumed by Framework
3
Convergence Results
3.1
Gradient Descent
3.2
Adaptive Gradient Descent
3.3
Stochastic Gradient Descent
3.4
Perturbed Gradient Descent
3.5
Restarted Stochastic Gradient Descent
3,6
Examples
3.7
Practical Implications and Simulations
4
Conclusion
10
5
Acknowledgments
10
A Technical Preliminaries
23
A.1 Helpful Background Lemmas
A.2 Comparison of Assumptions with Literature
................................
A.3 Proofs of Technical Results
29
B Proof of Framework
31
C First Order Convergence Proofs
C.1 Proofs for Adaptive GD
C.2 Proofs for SGD for FOSPs
34
D Perturbed GD finding Second Order Stationary Points
42
D.1 Proof using the Framework
................................
D.2 Proving the key Lemma
................................
45
D.3 Proof of Escaping Saddles Lemmas
Restarted SGD finding Second Order Stationary Points
56
E.1
Notation and Parameters
................................
56
E,2
Result
E.3
Preliminaries
E,4
Escaping Saddles
E.5
Faster Descent...
E,6
Finding Second Order Stationary Points
84
F
Examples
86
F.1
Phase Retrieval
86
F.2
Matrix PCA
88
22

---

G Simulations
90
G.1 Synthetic Simulations with GD
91
G.2
Synthetic Simulations with SGD
95
A Technical Preliminaries
A.1 Helpful Background Lemmas
We will use the following classical inequalities from optimization to show we still have some notion of control if have local bounds the relevant derivatives.
Lemma A.1. Suppose F twice differentiable, and for all u E xy (the line segment) we have F & L. Then, we have
L
F(y) s s(x)+ (VF(t)))
x=
Proof. This follows by the proof of Lemma 3.4 in Bubeck et al. (2015). In particular, readily verify that x t(y - x) E zy for all [o, 1]. Hence for all t [0,1] and u in the line segment between æ and x tyy - z). F²F(u)
op $ L. Thus,
IF(y)-F(z) (v x)
(vF(x + ((y ((y-((y))))))) - x)d1 (VF(x)) a))
Jo (VF(x+ ((((x+tly--0 -(y-z))
F z)
S Lt x1 =1|2tt
4 ly x
This gives the desired result.
Analogously, one can show the following by considering the local second-order approxima- tion around æ.
Lemma A.2. Suppose twice differentiable, and for all E xy (again the line segment), we have
- - T xx|.
Then,
L
Fly) s F(x) (VF(x) x) ) ( vV=))(()((())())) x)
x
Proof. Similarly to the proof of Lemma A.I, show this via the proof of Lemma in Nesterov and Polyak (2006). Analogously as in the proof of Lemma A.1, one can readily verify that for any y' ry. x t(y' - æ) zy holds for all t [0, 1]. Hence for all [0, 1]. applying the condition of this Lemma,
|V² + tly' =)) V s Ltly' z|-
Thus for any y' zy. by Cauchy-Sehwartz and the above, obtain
x) Sn ( F(z - (((06-x))).0 (
(v²F(x t(y' - -x)) - -2
2
$ SC Lilly' x x1 2dd = /// x1/²
Applying the above relation for y = f(y x) which is in zy for all [0. 1]. obtain
- -
x)
=150 (1
23

---

11 -VF
t(y x). z)dt
$ So ly - x||| _ 1((1 - =) (i(yy>>1' ~ x1
This gives the desired result.
We will also use the following Lemmas.
Lemma A.3. For vectors a, the matrix operator norm |ab" llp & |||lb]].
Proof. Consider any unit vector x. By Cauchy- and associativity, have
x xaabb" x s (z, (xx b) s |>> |a]]]b|| = |||]
The conclusion follows by definition of operator norm.
Lemma A.4. Consider any non-negative, continuous function g(x) such that lim ((x) and such that g(x) on (o) Then on [1, 00), g(2) can be lower bounded by a strictly positive, infinitely differentiable, strictly increasing function ((x). where 9 has domain [1, o0).
Proof. We will explicitly construct such a ğ in terms of g. First, since lim ((x) co, for all 22 1, there exists & é [1, 00) such that g(x) 2 +i for all 2 4.. We furthermore can clearly assume 2 f < 12 < ..,, by increasing each ÊN if necessary. Also let to = 1. Thus Ussalti, 1+1) forms disjoint union of oo).
Now, let c = min( 1, ( ((x) 0; the striet inequality here holds as t1 oo and as is continuous. Define a sequence {b;) by bu c/2,b, b2 c, and b; = i for all i 2 2. Thus bo < bj <.., Furthermore, this construction of {2r implies for all 2 have g(x) 2 b for all xe é [tq, f.1).
Now construct ī(x:) as follows. For all 2 0, we let o(x) equal function ha( defined on [4, 441] such that (1,4,) = b,, h2(441)) = bit1, where we define h2 as follows. We first define h: [0, 1] + [0, 1] such that h is infinitely differentiable, h(0)) 0, h(1) 1, (0))()) (1))) (1) 0 for all n 1 where ((n) denotes the n-th derivative, and h' (x) > 0 for all x e (0, 1). To this end we use a construction from Chen and Sridharan (2025): let
h(x))
(0,1),
+ 1-27
and extend h to [0. by h(0)= 0, (1) =1 We justify these claims about shortly below. Now we let
hx(x) = (64-1-b)) 1 -
t, - t; ) b, for all i 0.
We now check h satisfies the claimed properties.
In Chen and Sridharan (2025), it is argued that maps to [0, 1]. (0)) = 0, h(1) and that h is infinitely differentiable. It is also argued in Chen and Sridharan (2025), Lemma 11.5, that h' hz)x) (which is called 5(x) there) is non-negative on [0,1].
Next, we check ((()) (0) = h (m) (1) = for all n 2 1. Via a straightforward induction
outlined in Chen and Sridharan (2025), one check that (e- )m) 0., (2- 1-22 (n))
for all n. 2 (following the standard convention analysis that 0 0a = 0, see e.g. Folland (1999)). Now let f(x) = e- + g(x) -- +
+ t E thus h = f/g. Consequently
((a) (0) 0, (()) = 0. (0) (0) 0. (1) = 0 for all 2 1. As y 0 always holds in [0, 1] as shown in Chen and Sridharan (2025) and can be easily checked, we have f gh. A straightforward induction gives (m) Σi (1))(())(( where (*) is the binomial coefficient. We thus obtain (h(")) f(n) ΣnD (k) (n-x), For any 1.
24

---

taking z 0,1 in this expression for h(x) and noting at least one of k. n - k 2 1 for 0s k 1 n implies ((0) = (1)) = O. Recalling g(x) > 0 on [0, 1] proves h (0) = (1) 0 for 2 1, as requested.
Finally, check that (x) 0 for all (0, 1). Consider any E (0. By
calculation in Lemma 11.5, Chen and Sridharan (2025), we have h' h1)x) > 0 if and only
If x [ .). directly following the proof of Lemma 11.5 in Chen and Sridharan (2025) establishes that ((x) O. (1-a2y²
if q(()) 2 +e + + 23 + 1- (1-29)²
Otherwise E (0, ) note the strict incquality 1
x which in turn implics
((x)> > O.
By the above properties of h, it follows from the Chain Rule that for all 2 h4 satisfies the following properties:
(t,) b;, 1t(41.1) 1 and (x) e b for all xr [t,, 4.11]
h; is infinitely differentiable.
. h((x) 0 for E (t,,t and for all x é [t,, (. 2 0.
(1(")) (4+-1) O, where again ((")) denotes the n-th derivative. Finally, we check that ÿ has the desired properties:
For all n 2 1, (1.) (1+)
ğ is well-defined: This follows because for all 2 1, we have h₂(t,) 11:-1 b;-
i is strictly positive: This follows because (a:):) [br, bb,, S (0, o0) for all [4e, (+1)
9 is continuous, and moreover is infinitely differentiable: Continuity of g follows because each h2 is infinitely differentiable, and hence continuous, combined with the fact that for all 2 1, we have (t,),) = h4-1 (t;) = b,. Infinite differentiability of g follows because each h; is infinitely differentiable, and because for all 2 and all i 2 0, (/(") (t:) =n("' (t++1) 0.
ğ(x) & g(x) always holds for E [1,,0), oo): Recall for all 2 O, we have g(x) 2 b for all x [Tt,, f. Since we have ğ(x) = (z()) s dis1 for all x é [t, f++1]. it follows that for all x [4, I. J. ((x) S g(x). The result follows upon recalling that UssuL4, (--1) forms a disjoint union of [1,
ğ is strictly increasing: Consider any I1 < Z2, $1,
oo). Since Tı < 22, and recalling that Uizo t(1) forms a disjoint union of [1, oo). it follows that for some j 0, (2) (tz.tz+1)
open, and therefore contains some open interval (a, b) E (L,, (++1). Let = inf 2=(2ar> m=2b N2 (x) > O, where the strict inequality
Ø. This intersection
follows as [ 244h a+2h
S (ty, tzt1), and by continuity of ht on the compact 20th a+2h
3 3
33
Since we have (((x) 0 for all x [ti, 1i-1] for all i O, we obtain
((~2) 2 0+ d' b-a + ((x1) > ((x1).
3
This proves that ğ is strictly increasing as claimed.
Thus, have constructed function ğ that satisfies the requested properties.
A.2 Comparison of Assumptions with Literature
Here, we establish that our regularity conditions are more general than those of literature.
Proposition A.1. !f [(w)) s ((VF(w))
for non-decreasing, differentiable sub-quadratic I
(where quadratic means that lim
a2 [xx) = O). then our Assumption 1.1 is satisfied for some
non-decreasing P1 (x)). this generality, P1 (xx) depends on 1(x)), and can be found explicitly from the construction from Lemma A.4.
Furthermore, suppose F is (Lo, -mmssh,thh, that || s Lo + L, [VF(W) for Lo. L, 2 O.
Then Assumption 1.1 is satisfied with p1 (z) Lo 4L7x
25

---

Proof. Essentially this follows from Lemma 3.5, Li et al. (2023a), where it is shown that these assumptions of Zhang al. (2019), Li et al. (2023a) imply an upper bound on VVF(w) ||]l in terms of an increasing function of F(w); combining with the assumptions of Zhang et al. (2019); Li et al. (2023a) implies that 2 F(w)] is upper bounded in terms of an increasing function of F(w).
Proof for general
Consider any w R... By Lemma 3.5 of Li et (2023a),
|[ 22((2) F(w)).
This implies
4| (()]l [(2) [2] s (F()).
Let 2[VF(w)] = Consider when t 2 Then the left hand side equals ((r) Note that WLOG, can add I to (()) so that ((t) for 1. Thus L² I(t) is continuous on [1, oo), and furthermore
positive on this interval. Now note lim ((z) oo by the condition (including after adding x²
WLOG), and thus by Lemma A.4, I(w) is lower bounded by some strictly increasing function g(x)
on oo). Therefore, ğ is invertible and we have
4[lVF(w)1²
(( & (2]VF(w))l) & 8FF(w) - [VF(w)ll 70 ( (8F(w))
Then by the assumptions of Li et al. (2023b), it holds that
$ 1( 2
1 ((F((()()))
| F(w)
Else when t 2, we have [VF(w) 1, and by the assumptions of Li al. (2023b), we have [[>) s (i()).
Thus the assumptions of Li et al. (2023b) imply that the following always holds:
[ s {1 ( 1(1).
We thus can take (1 = 1('5 (8x)) + (1), which is clearly non-negen negative. It remains to check that (( (1zgg(((x) ) is non-decreasing. As / is non-decreasing, as compositions of non-decreasing functions are non- rendereeesing. it remains to check that 1/ (8x) is non-decreasing. Since ğ is non-decreasing, g is non-decreasing as well, and this completes the proof.
Proof for (Lo, Li )-smoothness: First, when L1 0 the result immediate, so from here on out suppose L1 > By Lemma 3.5 from Li et al. (2023a) we have for all Rd
[|V 2((2 F(w),
where ((x)= Lo Li(x) for Lo, L1 2 0. We thus obtain:
IVF(w) 2 < 2 Lo + 2T, ((w))l FF())
Rewriting this inequality, we get
22 S.
Consider the quadratic -2 ((w) (() The coefficient on the quadratic term is positive, and the quadratic is non-negative when x = V (w) J. Thus / FVF(w)) (w))l must be no larger than the largest root of 22 4L, Fww) x FL F(w,, and we obtain
S 1 44, ((w) + - (1 SLoF(()))) 2
[FF()]
$ 21, F(w) +
(5)
26

---

F 0. the above immediately implies [V](w)]] = O. Otherwise, recall by shifting (in Notation)
that F(w) 0 always holds, so suppose F(w) Recall also from earlier that it suffices show
the result for L1 > 0. Applying the inequality va² + s a 2a²
valid for all a > 0, b 2 0 with
a = F(w) () > 0, F(w) 2 O, we obtain
La
((2 2LoF(w) s 2L1F(W) +
21
Substituting into (5) gives that for all w with F(w)= > 0, we have
Lo FVF(W)] $ 21.
+ +4L,F(w)
(6)
By the argument earlier, if F(w) = O, the above bound (6) holds too. Thus (6) holds for all w e IRd. Now inserting (6) into the definition of (Lo, L1) smoothness gives
F(w)l Lu L1
La 211
44, (L,F(w)) -o FLW)
Hence Assumption 1.1 is satisfied with the increasing function pr (2)) 3/2 Lo 41,30.
Proposition A.2. When F is (Lu, L1) L00,-L2ssmmn smooth, letting pu(x) 22,''² 2/ [VF(w)] S (o(F(w)).
1/2
5L.
2/2
3/2
we have
L
Proof. By Proposition A. we can take P (a)) / T +4T,2x in this case. As noted in Subsection 3.1, need to show that 2 //
5L? 3/2 is pointwise upper bound on 1
p (=) 20(x) where 0(x) = So 1 dr. PI(
To this end note for each x 2 0 that ((r) S x.
1
2 x, thus for each 2 0,
%oo
3Lp
pi (x)
3
Lo 4L3a0
4
s 21
1/2
x
1/2
5L3
3/2 x
2
3
L 1/2
This completes the proof.
Example 1. We now provide natural example of univariate function that satisfies our regularity assumptions but does not necessarily satisfy those of Li et al. (2023b) for non-convex optimization. Namely, consider the univariate function:
π
F(x) = 1 looo(coss +1 x
1.
2
The argument here is in radians. The first derivative is:
F' F'(x) = tan + x).
The second derivative is:
F" F"(x) = sec? + x).
Thus as tan + 1 (0), F satisfies the ODE:
F"(x) = F" (x)² 1.
(7)
Suppose that F satisfied the conditions Li et al. (2023b) for non-convex optimization on relevant domain, thus for all 0 a _ 1, we would have
F"(x) ((F
for some sub-quadratic ((-).
27

---

Then by (7) and noting F²(x) 0 on the domain, we obtain for all 0 <
-1
F' (x) ((F())))
1
F)) F())2 F(xx)2 F()x)
As / subquadratic, there exists x' oo such that 1())/a² 1 for all a x'. Noting F()) for I 2 yields a contradiction.
Consequently F does not satisfy the conditions of Li et al. (2023b) for non-convex optimization.
However, we show that satisfies Assumption 1.1. Rewriting (r) in terms of F(z), note that:
cos(1 + x) = e2-f(x),
and thus:
F"(x) sec
(1+x) (e
(F()))
cos2 +
Hence we can define the increasing, non-negative function
pi(t) 2
which satisfies:
s ((oo)(p(F(x))
Thus F satisfies Assumption 1.1 (in the relevant domain).
We now discuss Assumption 1.2.
Example 2. First, we show that Assumption 1.2 captures several univariate functions of interest. Notice also F(w) is sum of functions satisfying Assumption 1.2. Triangle Inequality implies that F(w) also satisfies Assumption 1.2.
Polynomials: Consider whenever F(x) is linear combination of monomials x! for p combined with a constant term. We claim F(x) satisfies Assumption 1.2. By linearity of derivative and Triangle Inequality, it suffices to prove this whenever F F(z) xx for p as
the constant term vanishes, and then add up all the non-decreasing, non-negative functions the right hand side to form Pl and p2. To this end note (x) p(p 1)x""2 thus
[F"()) = p(p 1)x²²2 p(p 1)(x -
Similarly, F")(x) -
1p -)) thus
- (1 -))(-)))1++)
Noting 1) t) and (p
non-decreasing and non-negative for
2 O, combined with our earlier remarks that suffices to prove this result when F(x) = x?, completes the proof.
Single-exponential functions: Consider when F(x) = a" lna for a Then F"(x) (In & F=(()) (z) (ena) and we can take pI(t) (Ina) p2())
(Ina)3t.
Doubly-exponential functions: Consider when F(x) d² inn
rlub for b 1. Thus
F' F'(x) = in Ina Inb= lnd=nnnb(F()))
It follows that
F"(x) In b( + =nb((x)etho))((na((n)))) 24lb mate This then implies F" (x)
Inb) (Ina) 222 In rmb ln
((nn))(b)) (2c 20 ma wln c 30 @xlnd( + 2r In
Notice
e Inb S Ina - -I<F(z),
28

---

therefore we have
F"(x) & ( F (*) s ((an) (3P +3(x))maa++++ F(z))
We thus can take
= p
(())
P2(t) (( 31 In
which are clearly non-negative and non-decreasing on [0, o0).
Next we highlight the natural example of any self-concordant function F: R - R. Thus
|F [F"(()) 2F (z) 3/2 2x)"
Suppose /' satisfies Assumption 1.1. Then there exists non-negative, non-decreasing P1 such that [F"()) (=(()))). Thus,
s 2
Since P1 is non-negative and non-decreasing, p2(t) 2p1(1) as well, and thus Assumption 1.2 is satisfied.
Next, show that the regularity assumptions Assumptions and 3 of Xie al. (2024), which they need for their guarantees finding SOSPs, are less general than Assumption 1.2 when F is wwice-differentiable To do show they imply Assumption 1.2, and hence subsumed by Assumption 1.2.
When F is twice-differentiable, their Assumption implies (Lo, L, smootthnsss. As shown in Proposition A.2, this means that
5L} 3/2
1/2 1/2 | [VF()) S (o(F(w)) where po(x) = 22/ 1/
L
Their Assumption 3 implics for Mo, M4 2 and some ö that for all w, w' with wl - www 56,
[ F2F("") op |w w' (Mo M/]lV(()])).
Combining this with the carlier display gives for all w, w' with ww w'l s8.
(y² !lop s w| w'''' w'M + M1
where Po(x) = / 1/2 1/2
3/2, We thus see that F satisfies Assumption 1.2 with the non- GL?
decreasing, non-negative function (2 Mo Mi /² 1/2 +
GL? 3/2 r 3/22
where the latter two
properties are evident as po(.) is nen-dccrggs and non-negative.
A.3 Proofs of Technical Results
Now, prove general results used throughout our work. We prove Corollary which gives us control over the gradient:
Proof of Corollary 1. Applying Lemma 11, De Sa et al. (2022) with +b in place of F, we obtain
[V/(w)] ((F(())
= (F(())
where 8(-) is defined in the statement of Corollary 1. To prove (o(x:) is increasing, simply note and thus v are clearly increasing, and are both non-negative, P1 is non-decreasing and non-negative nog-negative as well, thus is non-decreasing and nen-negative.
We also prove the central Lemma 3.1, which is very important to our results: it lets us con- trol the change in function value under our regularity assumptions. We first state the following Lemma from Li et al. (2023a), generalization of Gronwall's Inequality:
29

---

Lemma A.5 (Lemma A.3, Li et al. (2023a)), Let - and B [0, 00) [0, 00) be two continuous functions. Suppose (t) $ B(a(t)) almost everywhere over (a. b). Let (uu) So de Then for all all t [..
d(a(t)) s ((a(a)() -
This allows us to prove Lemma 3.1, which is an extension of Lemma A.4, Li et al. (2023a):
Proof of Lemma 3.1. The proof is essentially identical to the proof of Lemma A.4, Li al. (2023a).
Let zt) = (1 - t)x by, a(t) = F(z((). Then for all & (0, 1), we obtain
a(8) a(1)
a' lim
$ 8-t IF(z(s)) F(x(t))
1im
8-t F(z(s)) - F(z(t))
lim
3-t
F(z(t))
di
FF(
$ (o(((2(tt))ll xl,
the last step using F(w)] (o(F(w)). Let ((x) = yy - (>)) and let d(u) = S0" 3(0) de. Thus, a'(t) & ((a()) almost everywhere. Applying Lemma A.5 gives
(F(w)) (a(())) s ((a(0)) ((F(=)) 1
Let (u) = v S po(م] du, which is clearly strictly increasing. Consequently obtain from the above and assumption on that
v(F(z)) s ((F(z))) + +l 1--
(FF())) Po(F(x)+1)
[ F(z) du+
Po(u) du+ JP(e) ((()))
du
Po(1)
So F(z)+1
Po(u) du (F(x)) +1).
Since vb is strictly increasing, taking inverses implies
F(v)s((x)) +1,
as desired.
We also introduce the following Lemma, which lets us exploit Assumption 1.2 to control the Lipschitz constant of the Hessian of F.
Lemma A.6. Suppose F satisfies Assumption 1.2. Suppose x. y Rdd are such that yy - x r for
some 0. Then
[v' op s x yll sup (2
wezy
In particular, we have
1F) s <1z yl sup (2(F())).
ucR(y.r)
Proof. Consider 8 0, either from Assumption 1.2 if the second case of Assumption 1.2 holds, and otherwise set to some arbitrary positive real. Similar to the proof of Lemma 3.1, divide the line segment between v, into N |æ-yl equally spaced segments of length between points z;, where we define Zo 2,T1, IN y. Thus x yll N8.
30

---

Suppose for all u e zy we have (2 op & L. Consider any z' in the line segment zy. Applying this for tly x') for t E [0, 1]. which always lies in the line segment zy, we obtain
FF' V llop $ $1.6 (1
+ tly ( =2))),'''' x') z')atl s T. T.ly' =='1
Consequently irrespective of which case of Assumption 1.2 holds, because [x; - xi- 1l s o, we have for each s N that
$ Iz Ii-1 sup (2(()u)) uczy
Now Triangle Inequality gives
$
F1
$
Ij #;-1
sup p2p F(u))
[-1
u=zy
$ No sup P2 [ (u))
uery
x
yl sup P2 F(u))
uczy
desired.
We will also generalize the proof of Theorem 3.1 to show that GD, when initialized in the ((wo)-sublevel set (w,F(w)) with appropriate step size defined in terms of F(wo). never increases function value.
Lemma A.7. Consider any wo Rdd and consider iterates (ue of GD initialized at any uo E F(,F( the F(wo)-sublevel set. If the step size 1) of GD at most [y(w]] where (.(-) is defined as per (4), then F(u)) s F(uo) for all 0. Proof. It suffices to prove this for t 2 O. We have in u0 7/V F (uo). By Corollary and because un CF,F(wo)) [[o)) s Po( ((w))) s pa (F(w)). Thus by choice of r and definition of L1 (Wo).
simple inductive argument then establishes this for all
Iu uol F (Fwo)) po (F + 1)"
By Lemma 3.2, because uo E F(.)())) for all p in the line segment Ug we have /22 op Ta (Wo). By Lemma A.1, it follows that
F(u:) s F(u)) nl/VF(u))1 L(ww))?
2 |[oFF()))
(-1+
L, (wo)))))
$ F(wo) + +VF((u))
Li (wo))? for e [0, [,] the conclusion follows.
Noting -1)
2
B Proof of Framework
Proof of Theorem 2.1. For convenience, for all 2 0, define Pa, := 1 n- Su--Suupeerrr. p. 8(u). Also
let T suPuuL_ {
F(wo))
A(u)
Lemma B.1. For any n let En be the event that the sequence of iterates (wr)netsn-1 satisfies either:
1. The event En,i For all 0 <t n F(Ar(w:)) F(w.) A(w:).
31

---

2. The event Ex,2: There exists Wi (w; )oeten11-111 such that A2(w;) nn + {}. and for all w, with 0 8 < we have F(Ai (A=))w)) < F( -.)-aaa-)- A(w.).
That is, E, 1 E. Then over the randomness in A, we have ((E,) 2 Pr. for all 2 0. Proof.
We proceed by induction on n. The base case is vacuously evident, and the case n follows immediately by the definition of a decrease procedure from Definition 2.2 and hypotheses of Theorem 2.1.
For the inductive step, suppose Lemma B.1 is true for some 2 1; we show it is for n + 1. By the inductive hypothesis, we know that (PE))) Pn- We aim to show P(E,)) Pn=1- pr. there nothing to prove, suppose now that n is such that pv, > O.
1. Let p 2l Note En, E En+1,2 E En+1-
2. Let B = E, Eh Thus, if B occurs, then all the (w:)osten> are such that F(A1 (w;)) but En did not occur. Note En is the disjoint union Ln,, so F,)
1-p.
Under B, we know w, = -A(w,-1) is such that F(w,), & F(wo). Hence w,, F(w)()))) Therefore, conditioned on B, by the hypotheses of Theorem 2.1 we have with probability at least Pu that either ((A1 (w,,) )}+ F(,,,) (w,,) or (2,w,, n # {
Let C be the event that F.Ai (w,)) F(w,)) (ww,,, occurs. Let D be the event that (2(w,) n. # { occurs but C does not occur. Recall that w,, ((wo)) conditioned on B. Furthermore recall that A(w,. is only a function of Wn, and none of the (W=)ostnn-1 Thus the definition of decrease procedure, Definition 2.2, implies that
PCCC L DDB) 2 Po.
Now since P(B) -P 2 (1 p)p, 0, Bayes' Rule implies
P(BBnC) P(B ((5 (BBn((B)C)I(Bnn))
IP(B)
((Bn(CUD)) =P(CUD 2 Po- PPBB)
Note B in C implics that En+1,1 occurs, since under n C we have F(A1 (w:) < F F(w,) A(w, for all 0 t S n. Similarly, B D implies that En+ 1,2 occurs, since under 13 n D have F(A1(w:) < F(w.) Aw,, for 0 s $ n and A2(w,, n # ()-
Thus recalling E,,,; B disjoint,
that E,+1 contains the following disjoint union of events:
E En (B nC) (Bn
The above observations imply via Bayes' Rule that
IFEEn+1) u (BnC)u(BnD))
+ (Te
(()))( (BB))))(((B)) (1 pp)
pn(p+ (1-1))
2 Pn + po - p)) = PrPP 2 Pn+1-
Here we used that (P(EE,) 2 Pr. PoPo 2 Px+1 which follows immediately from the definition of Pas Po $ 1, and simple manipulations. The inductive step, and hence the proof, is thus complete. D
Using Lemma B.I now readily proves the following:
Claim 3. Let be the event that there exists w; with w; e (w, (Wg)STTT-II such that A2(w:) n (). and for all w. with 0 S < we have F(Ai (w.)) F(w.)= A(w.). Then P(E) 2 pT.
Proof of Claim 3. Apply Lemma B.1 with n = T. Following the notation from there, we have that the event E Ex.1 U E has probability at least pr.
32

---

Suppose that ε occurs. Note Ex, implies that é (FFF(w)) for all 0 s T. Therefore
A(w:)
inf P((w))(ww)
Auu) for all Ss
(8)
Moreover, telescoping the direct implication of E gives that
2-1
F(WT) < F(wo) - Σ A(w,).
(9)
2=0
Combining (8) and (9) and recalling that we shifted WLOG so F' has minimum value 0 (see Notation) gives
inf A(u) S
Σ
A(w)) < F(wo) F(WT) s F(wo).
weLp.F(wo)
1=
This contradicts our choice T.
Thus ετ, cannot occur, and so Er must occur, i.e. ET ET,2- Note &T,2 is exactly the event E. Thus
P(E)= =( FF())) P(ET) 2 pr:
as desired.
Conditioning on the event & from Claim 3, by Claim we immediately recover the desired guarantee on the output, probability, and number of candidate vectors stated in Theorem 2.1. The only part remaining to prove Theorem 2.1 is to establish the bound N F(w.) SuPueC F(ww)) foracle (u) on
A
the number of oracle calls.
To this end, condition on & from Claim in all of the following, and follow the notation from there, in particular the definition of w.. Directly, we obtain that the number of oracle calls is at most Ei=o loracte (w:) (the last term loracle in the sum appears since computing A(w,) and A(w:) takes at most loracte (w:) oracle calls). We now upper bound this sum.
As conditioning & and since assumed WLOG by shifting that F has minimum value O, we have
F(w..)) FFw:)= -A(w;) < for all 0sist-1
Σ A(w:) < F(wo) F(w,) F F(wo).
(10) The above also implies F(w;) F(Wa), i.e. w, (..F( for all 0 sist Therefore, loracle ( (w;) ) suPueCr F(ww)) foracte (z) for S Thus (10) gives
F(wn)
El=o A(W:)
min A(w:) A. 0sist-1
I--1 Ei=0 lorntte (w:)
foracte (w:)
turace (w:)
Dy' Σ
2 min, for a, 0, 0, that w; E FFFF(w)) for all s is 1- and the definition of A. Rearranging and recalling foruoe(Wi BuPweLF. F(wo) loraete (u) as justified above, we obtain
where the last inequality uses the elementary inequality
toracto (u) + F(Wo)
Σ toracte (w;)
sup ws Cr. F(wo)
Eoracto (u)
toracto (w:) S sup
ucCr,
A
This yields the desired conclusion oracle complexity, completing the proof.
C First Order Convergence Proofs
C.1 Proofs for Adaptive GD
Proof. As with the proof of Theorem 3.1, we use Theorem 2.1. We again have S = (w : /// ((w) E). and recall the choice of 7) from Theorem 3.2. Now we let A(uo) (uo "ua v F(un) uo). Thus (uo) uo F FVVF(uu). Ag(uo) too and toracte (uo) 1.
33

---

Claim 4. For any in
the F(woe-subleve set LF,F(wo) A
is
(,,,, (pu(F( (10()
(wo) g²
uo) (0,20) deerrase procedure.
To show this, analogously to the proof of Theorem 3.1, for any ue S in the suuleesublevel set (( we will show that the function will deterministically decrease by strictly greater than
(u(((w))+1)) [1.( at the next iterate. By definition of A2, exactly with the proof of Theorem 3.1, we conclude via Theorem 2.1 upon showing Claim 4.
min
1, (ww)
z²
To show Claim 4, by choice step size, we have M/ (V & "u(F(wo)+1)" Thus
uu -uu S
Po (FWF))) + 1) Po (o(F(un)+1]
Now combining Lemma 3.1 with Assumption 1.1, and because uo (FFF(W))) see for all uothi FV) op (i where Li (wo) is defined in the statement of Theorem 3.2. We thus obtain by Lemma A.1,
F(ui) F(u)) vllFF(()) (wo))) [VF
(1I)
2
Recall that uo $ SS so [VF(u)) >
We break into cases:
((
E (wo) no Po(F(wo)+1])
then Thup [((F(wo))T)|BF(()))) this case, substituting into
(11) gives
F(u1) s F(uu)) 100m-m11100 (/lo) (wo)) (vF(u))
(((w))
= =F(u))
| |VF 2po 1)²
Po po(F(Wo) +1
(i(w)
< <((u))
(o(FF(o)) 1)2
2. Else if (VF())) s LL (wo), then Tha [mmo In this case, substituting into (11) gives
F(u1) F(un) (oin))nnlVVeC n/VF(u))) (wonn? .|V
VVF(u)) F(uo)
E²
F((w))
21 (wv)
21, (wo)
where we used that [|V((u))] > s.
In either case, for F we have that
L (wp) 2 (F(w)) + 1)2 21, (w))
F(ui) < F(wo) min
This proves Claim 4. By our framework Theorem 2. the proof is complete.
C.2 Proofs for SGD for FOSPs
Here, we prove Theorem 3.3. We first introduce technical preliminaries, which will also be used in Section E.
Theorem C.I (Vector-Valued Valued Azuma-Hoefiding, Theorem 3.5 Pinelis (1994)). Let EK E Rd 0, ||ex
be such that for all k, E[Ex|T*-1
s oz. Then for any X > 0,
K Σ
2
I
< exp
34

---

Note the bound here is dimension free, so this result does not follow directly from standard Azuma- Hoeffding. Such result can also be found in Kallenberg and Sztencel (1991); Zhang (2005); Fang et al. (2019).
Theorem C.2 (Data-Dependent Concentration Inequality, Lemma in Rakhlin et al. (2012)). Let E e R be such that for all k. [[ 0. E [ I o. Furthermore suppose that P(ex s 113+-1) = 1. Letting Vx= = Σx-1 o for any 5 < 1/e, 2 4, we have
Σ Ek 2 max 2/ Vn, by log(110) byl,,
1ox(1/5) s (llo((K)
Such result is also presented in Zhang (2005); Bartlett et al. (2008); Fang et al. (2019).
We will first prove Theorem 3.3 in the case where V () (F is bounded by (F(()). As noted in Fang et al. (2019), these same inequalities hold when the martingale difference is not bounded almost-surely bounded but rather the norms sub-Gaussian with parameter σ Thus after the proof, we remark how to straightforwardly generalize Theorem 3.3 to the case when [V ()
v F(w)) is sub-Gaussian with parameter o (F(w)) in Remark 7.
Now, we prove Theorem 3.3.
se). Recall as per the discussion of SGD in our framework Subsection 2.3, we po uy. and define a sequence (p;) via
Proof. We use our framework Theorem 2.1 with S = {w: V (w)l
p: P:-1 1/V (p:
where the Çi are minibatch samples i.i.d. across different i. Note this sequence can be equivalently defined by repeated compositions of the function u + u 1/V ()
We now let A(us) (pKo: (p:)osssKo1),, hence A1 (t4)) PKo A2(un) = (p.)osis.o--- Thus foracle (u)) = Ko. Also note the noise & used defining A are independent across different t.
For appropriate 1 ((=²), K₂ Ô depending only e, 8, F(ws) and polylogarithmically in 1/6, which we define below, we establish the following Claim 5:
Claim 5. For any uo in the F(wo)-subleet set LF.F(wo)) A is (8, Ko, yka=" 1 .p. uo) deccease
óy
procedure, where p= [(P(Ww)+1)'
Then using Theorem 2.1, then directly conclude Theorem 3.3.
To show Claim 5, consider any un the F(wy)-sublevel set but not in S. Following the notation from above, consider "block' of Kg consecutive iterates of SGD starting at Po ug. We establish that with probability at least 1 - p. none the iterates {Po = Uo...., PK.-113 lie in S, then
F(Pk.) F(Po) A where A gkas" Then recalling the definitions of Az, we immediately conclude Claim 5.
Definitions and Parameters:
For convenience, define
Lo(wo) Po (wo) 1); L, (wo) /1 =F (F(wo) 1); σ1 (www o(F(wu) + 1),
B(wo) (www))² + 1
aor (wo) Lo(w))
Also define
Ê-- Vf(p((( VF(p.).
where Çi-1 denotes the i.i.d. minibatch samples. Note by Assumption 3.1 that [[[..]] 0, where expectation is with respect to {++1-
In particular, choose these parameters follows:
8²
n I(wp) (o
35

---

Ko C(wo) log(1/7)² log(1/))1oog(1/)) log(1/6)²
1
7= ((x())) 1)} 7
where
C(wo) (2oBB(w) 1)²
('(w)) = 81, (wo) (um
(wo) v 2T (wo) v (wo),
L(ws) (((w)))((w))) (3V22l ((322lo((((wo))
(3v2)².
Remark 6. Note that C, i,, depend only polynomially in terms of the self-bounding functions Po. Pl. G, and F F(wo).
Note assume WLOG that and the desired probability ó are at most some small enough universal constants in (0, 1); by doing so, the result does not change up to universal constant, and hence is identical under the (-)). Consequently
may assume WLOG that î and n are at most some small enough universal constant in (0, 1) and that Kg
Claim 6. For e, small enough universal constants, the above choice of parameters satisfies the following properties:
max(1, Po ((wo) +1)m
1
i min
8L1 (w)))))
40,(wo) (()
Ko log( (4Ku/p)
(12)
2og Ko
Kos² 2 128B(wo) log
(13)
For the sake of brevity, we prove Claim 6 after the our main proof. Checking this is a matter of elementary, albeit tedious, univariate inequalities.
Again, our plan is to apply Theorem 2.1 by showing decrease with high probability for block of Ko iterates starting at Po.
Notation:
Let 8 denote the filtration of all information up through pt, but not including the mini-
batch sample Ç1+1- Let K. be a stopping time denoting the first t such that Pa & B Po: Po(F(wo)+1)
ie. the escape time of the iterates beginning at po from IB Pu. po(F(wo)+1) = B un. po (o(F(w))+1)
We first detail two high probability events we will condition on for the remainder of the proof:
By Vector-Valued Azuma Hoeffding Theorem C.1, for a given t S Kg we have with probability at least
2K.
log(48Ko/p) Σ a (F((:.))) = 2m log(4Ko/p) Σ (F((p-))))
Σ &x k=1
s $2
This follows since each E[E, = the stochastic gradient oracle unbiased, and as I&x (F((tt))) by Assumption 3.1.
Thus by Union Bound, with probability at least p/2, we have for all 1 1 / S Ko that
Σ E1
s $211
log(4Ko/p) Σ (FF(p)))
(14)
Denote this event by E1. P(Ei) 1 -/22.
36

---

We define a stochastic process with the following trick to derive uniform bounds. Define the following sequence of real numbers:
Y == (i=))(()
Notice leck is 8 3i-measurable, as {t < X.) holds and only pt.....P E IB Po- po(F(un)+1))
Clearly (p.) is also 3 measuuaabl.. Thus as the stochastic gradient oracle is unbiased (i.c. E 1 =0),
B B = [[())))((F(p)))))
For / 2 K. we have Y, = For K, we have p. B B(po, (o(F(to))1))) Consequently by
Lemma 3.1 and Corollary I we have
M s Fl.
Fllv (Po(F(Wo) 1)
Moreover by Assumption 3.1 and Lemma 3.1,
| o (F())) o (((ww) 1) o (wo).
In particular, recall that fi+1 the difference between the gradient oracle and actual gradient at Pr-
By the above arguments, both of the following inequalities hold deterministically:
Yil nl (o Mi np + 1) (wo) (ww)
We now apply both of these bounds in Data- anta-Dependent Concentration Inequality, Theo- rem C.2 (whose conditions hold because we can assume 6, e are at most given universal constants, Ko 2 4, 2,2 Ko/p e). Consequently obtain with probability at least 1 that
Ke-1 Σ (VF(p:). s 2n) (wo) log
2og Ko P
1
Ko
2 log Ku log
aV (wn))
|F((:))
(15)
p
Denote this event by Eg, so P(E2) 2 p/2..
For the rest of this proof, we condition on ε E2. By the above, E n occurs with probability least 1 - p. Denote = & n Eg.
A-priori, these bounds are not particularly useful, especially in our more challenging setting under Assumption 3.2 where noise can depend on function value. However conditioned on ε, we prove that SGD sufficiently 'local', in particular that lpp woll s 1 for all t, 1 1st Ko- This will then give us control over function value via Lemma 3.1, which then allow us to make use these bounds in more standard way.
Lemma C.1. Conditioned on Eg (and hence conditioned on E), for all f, S S Ko, we have
lp. -p--pol [|p, 11ol= po(F(wo) + 1)
Proof. We go by induction on Notice after iterates,
p: Wo VF(p)) -1 Σ
For the base case f. 1, we have from Corollary that | F(wo)) Po ((ww)) s Loww) From the definition of the hiob-piobayylityy event E and properties of 77 from Claim and as 0i (7((2) (wo) (wp)), it follows that
|nTEll (F Kolog(4Ko//)
2po (F(()) 1)
37

---

Consequently by properties of 17 from Claim 6,
PP Poll [[nFF(w))) + In s
Pa Po (Fww)) + 1)
This finishes the proof of the base case.
Now suppose Lemma C.I holds for all 1 s k 1; we will show it for t. From Lemma 3.1, for all k s 1, we have
[FF(p))] s po (F(wn) + 1) Loww)
Thus for each k we have
(F((:)) so(F(o)) 1) σ. (wg)
Thus conditioned on & we obtain
1-1
Pp - PP--Pol s
11 Σ (px)
+
Ex
Eh
k=0
R-1
Kp-1
$ (nKooo(wo) 2
log(4Ko/p)
(www)
=nKoLo(wo) (n101(w0) v Ko log(4Ko//p)
$ 2po(F((wo) + +) 2po(F + 1)
Po (o(F(w)) 1)
Here used the choice of r from Claim 6 and the upper bound (14) | Ek= Ex implied by E This completes the induction.
Now that we know the iterates of SGD are 'sufficiently local' for K2 iterations via Lemma C.1, the finish straightforward. Condition on & for the rest of the proof. Consider any s s Kg 1. E implies for all p PP-iPi. writing = 0p:-1 (1 0)p; for 0 [0, 1J, that we have
|p Poll s 0 - Poll + (1 0) pp - -Poll s (1 - 0 0)
(u(F(wo)) +) (o(F(wo)) 1)
Consequently F(p) S (F 1), so the above combined with Assumption 1.1 gives
F2F(p) (wwo).
(16)
We also obtain from Lemma C.I together with Corollary I and Assumption 3.1 that for all 0 s is Ko.
[ < (F + +1) = σ (wo), FvF s (F(FFwo) + +1 (wwo)
(17)
Now by Lemma A.1 and (16),
In (v](p::(++))
F(p+1) - ((FF(()F))
F(:)) =F(p:) )
+ (wo) (IFF(()) |kE+1l 1))
The last step uses the definition of 1 and Young's Inequality. Summing and telescoping the above for 0 st Ko 1, and applying (17), gives
Kn-1
Ka-1
F(pKo) F(po) "
Σ [F
- Σ (VF(p:).
0w0
L (wo) + (wo) (wo).
(18)
Now, conditioned on E, we upper bound
Kp-1
7
v F (P:)))
t=0
38

---

using (15). Under &, by Lemma C.I and Lemma 3.1, have Ps BB (po: (o(F((mo)+)) for all
1 1st s Ko, which implies that < K. for all s t Ko. Therefore
Ko-1 (F(::) E--1) = - Σ
Kp-1
Now AM-GM gives
Ko
2 log Ko
1
1 (wo)²
[F V log
P
Ko-1
2 2og Ko
2n
Σ
V (p:))l (wo))
t-0
Combining with (15), we obtain
Ke-1
Ko-1
(VF(pt). = Σ (VF(p:).E:.1)ll
Ka-1
2 log Ko
Σ
[F((:)) 12 16nB(wo) log
2 0
p
Combining with (18) gives
F(DKo) s F(Do) 7 Ka-1
2og Ko
(p:)) )12 16n log
+ (o (wo)
+ K (w))(w()))))))))))) (wo).
(19)
Suppose that |vF(p.) > for all 0 s Ko Then the above gives
F(px.) < F(po) n/os²
16n (6n))(w))) log 2 log Ko
p
+ KoLo(wo)) (wo) Kooo (wo).
To make of this bound, by our choice of n, Claim implies that
nKoE?
nf Kowoowo) L (wo) 2 (L
8
By choice of Ko, Claim 6 implies that
2 log Ko
nKos
B( log
P
The above was all conditioned E, which occurred with probability at least 1 p. Thus by (19), obtain that with this same probability which is at least - p, if none of .......P..... have gradient norm larger than e, we have
nKos² F(uo) nKo=²
F(PK.) Fpp))
4
4
This establishes that A (S, Kn + 1, aKae² observations, conclude via Theorem 2.1.
.p, -d)-reccesse procedure. Following our initial
Now prove Claim 6.
Proof Claim 6. We first prove (13), Recall we chose
C(wo)
Ko
log( L/ñ)² log(118) ()g(1/))².
e2
Furthermore recall p= 3 3(((w))+]
6āKaz Thus, (13) holds and only if
8 log Ko (F(wn) + +1)
((w))) log(1/6) log(1/))² 128B(wo) log
39

---

As C(wo) 128B(wa) v 64(F(ww) + 1)², again using the expression for Ku, it suffices to prove
log Ku ((wo)))26jlog(41))) log (1/6)3
log(1/h)*log(1//) log (1/=)² log
As log(1/6), log((/i) are both larger than 1, suffices to prove
log( log(1/)) log (2/ log(1//)
log ((wo) + log(1/E²) + 2log log( (/i)) loglog log(1/)) + 2log (og(1/e)
log
C(wo)
Since ((wo) 2 64, satisfies log ((wo) < C(wo) 1/2 so it suffices to prove
log(1 (1/7)) log( 1/6)* ll/6)> (1/=)²
2 log(1/ñ) + log(1/6)
+ log(1 2 loggg111/) 1/e) + 2 log log(1/i)) 2 log(1/6) + -2log log(1/e))
By comparing 'degrees', we conclude recalling we can assume WLOG that E, fj are smaller than some universal constant.
Now we prove (12). We will prove that
(20)
L'(wo) Koy /oylog( 4Ko/p)
After proving (20), recalling choice of Ko 1/s² directly implies (12). To show (20), equivalently, we want to show
E²
(lg((11))² (logi))"oooo4a)) 4Ko/p)
T'(wo)C((w)) log(1/5) log (1/e)2
Recalling the definition of p, this holds and only if
16 (6(F(ww)) 1)
8²
i log(1/7))
log
SijE?
L'(wo)C(wo) log (/00)//010((/))))))))
2² Now we explicitly recall our expression for rj [(wo) log(1/e)) log( Plugging this in and recalling i(wo)= 2 ((w,))((w)) it suffices prove
L(wo) ((too)oo((//e)) log(1/e) log log(1/6)
log
L (wo) 1 1/2 (1/))(((1//))) (1/8)6
e²
16 16(F(wo) + 1) (wo) 6 (oggl//))/o/////// log(1/8)6) log
de
1 log(1/8)2 log(1 (1/))²
Thus suffices to prove:
18
[(wo) log(1/))
16(F(wo) + 1) (wo) log log (1/))
L(wo) 1/2 log
log
8
dE
s log(1/8) l
Recall i(wo) 1/8 2 3 3 (2lg((((L)))) v 3/2 and so
3/2 log
i(wp) log( 1/E) log 1/5)
L(w;) 1/4
E
40

---

3
((w)) 1/4 (log(1/2) loglog(1/E) loglog(1/0)) + log [(wo))
((w (1 log((/))) log log (og())))).
Thus suffices to show
(1 log((1/)) + log loglog(1/2) + log log (
((wo) 1/4
16(F(w)) + 1)L(wo) log log) log()
log
dz
$ log(116)) log(1//))
To this end recall L(wo) 1/8 log(16(F((w)) 1)(()))), thus
16(F(wo) (w)) log (og())))
L(wo) 1/8 log
((wo)2/8 (lgg(6(F((w)) + 1))((w))))))))))))))))())) (1)g()11)))))) log(1//) + loglog(1/)) + log log( 1/:))
$ + log((/6)) + log(1/=) + log log (1/))) log log(1/s))
Therefore it suffices show
(1 + log(1/e) log log (1/e))))))))) log log( 1/8))²
(1 + log(1/0) + log [ls)) log (1/))) ) + log log (og(1/)))
s llg((1/5) (
Evidently the above holds for small enough universal constants ó, (compare 'degrees') ) so we conclude the proof.
Remark We also discuss how to extend this result to when the [Er] has Sab-Gaussianity parameter (FF()))) The extension is straightforward. Again, we aim prove Claim 5. For the rest of this remark, follow the notation from the proof for SGD above. Besides applying Theorem C.I, Theorem C.2 when the relevant random variables sub- Sab-Gaussian, which still hold true mentioned in Fang et al. (2019), the only other time we used that ||E.ll s (F((:)) holds deterministically is to derive (18).
We apply Theorem C.1, Theorem C.2 identically to the proof earlier. This time, we have for L < IC that E++1 is sub-Gaussian with parameter an (wo), thanks to the same trick of multiplying with 1 when applying Theorem C.2.
The only change is as follows: in the definition &, add in the intersection the event &g that for all 1 1 t < Ko, Is, s oFF(p.)) log( Ka/p). where is defined the same as before. We control the probability of Eg via the following Lemma:
Lemma C.2 (Equivalent of Lemma 12, De Sa al. (2022)). With probability at least - P. we have for all 1 <ts Ko.
| o(F(p:)) log (oop)). p. Ko
Proof. By Assumption 3.1, with probability -
we have
1| o (F())) log(Ko/p))
A Union Bound finishes the proof.
Now we condition = E₁ Eg Ez. which has probability at least - 2p by combining
41

---

our earlier argument with Lemma C.2. Note this only changes the resulting guarantee by universal constant. We still have Lemma C.I, which does not require an upper bound on each [Exl its proof but simply uses concentration from event E
Thus, conditioned on &, we still have F(p:) F(wo) by Lemma C.I, Lemma 3.1, and as U4 F. Now conditioned on &, by Lemma C.2, we still have the following upper bound for all s s Ko:
|Ex11 & (F(W))) + 1) log (og(Ko/p) on (wn)² log Ko/p).
Therefore conditioned on &, we can still derive bound analogous to (18), This resulting bound changes by only log( (K//p) factor (from Lemma C.2, see the above display); moreover recall Ko. p depend polynomially in 6, 1/c. By adjusting ! smaller by polylog( Ko/p) factor, the same proof as above goes through, up changing quantities by polylogarithmic factors.
D Perturbed GD finding Second Order Stationary Points
D.1 Proof using the Framework
Here we prove Theorem 3.4. We instantiate Algorithm formally here. The parameters Algorithm will depend on L1 (Wa) (zww)), which defined in (4), (21) respectively, and depend only on PL, 12, F (wo). Given a desired success probability
for 8 > 0, a tolerance O, and F(wo), ; (wo), L2 (w)), the algorithm's 's other parameters are defined in terms of follows:
1. e Cmax is universal constant, where Gmax is universal constant defined Lemma D.2.
2. 8 L2(wo))
3. X - 4ax log(
(wo) (w))) F(wa) 04g2.68
4. 1) (wo)
5. r L
V0 x²
6. Othres
7. Jihres
+
x3
c V Lz(wo)
(wo))
8. tutres
(L2(wo)E
Proof of Theorem 3.4 given Lemma D.2. We will first prove the following Lemma, which will define L2(Wa) and explain its significance.
Lemma D.1. Define T, (wo) in (4), and define
L2(wo) =
Pz 1)).
(21)
Then we have the following:
1. Suppose such that ||u T||l pal pu(F(w))+1)) where w LF,F(w.)) the F(wo)-subleve set. Then under Assumption 1.1 (and in particular under Assumption 1.2).
|F2 op (wo))
2. Suppose that u1 U2 are such that ||u - u||| |lu2 w| not ( where FF.F()))) Then
(FF(u)-vFF(en
L2(w)) uu Uz/.
Remark 8. Note L, (Wo). (2(w)) 2 1, and T.2 (wn) 2 (wo).
Proof of Lemma D.1. Recall by Corollary 1 that [F S Po (F(w)). Now by Lemma 3.1 and as i E LP.F(w,) for any u' with Ju' - Po(F(())+1] 5 Po(F(1))TT) we have F(u') s F()) + The first part directly follows by Assumption 1.1.
42

---

Algorithm Perturbed Gradient Descent, modified from Jin et al. (2017).
E= Lo(wo)' X 4 2dL, (wo)
53 7 L, (ww))
Vce x (wo)'
c82.58 (wo)
Ithres
x² x²e,
fihres x
Here refers to a small enough universal constant c3 (wo)) upper bounded by Cmax in Lemma D.2.
La(wo)) litres
Ea
while True do if | [v:)) Ithres then
w + wt, Imoise + t
w, - w. + Er, uniform from B(O,r)
0
while 8 4hrres do
W++1 We 1/ 8-
end while
if F(w)) F(W - fthres then
Return w tnose end if
else
W++1 we NVF(W)),
end
end while
The second part now follows by noting the line segment Ug is contained in B B(W, po >o(F(wo)+1) via Triangle Inequality, recalling (F.((w)): and then applying Lemma A.6 and Lemma 3.1.
We now prove Theorem 3.4 by instantiating our framework.
Define ē= [n(wo] as we did earlier, and note (ww)) 2 1. suffices to show for é s 1, that with probability at least 1 - 8, we will return such that [V || s E, v²F(w) T O (ww) max( ((ww). of Lz(w)) max(((ww).1)x) oracle calls.?
in
Now let the set of interest
S= (w: [F 9thres v²F(w) -VLL(wo)EI)
Note Athres S E S immediately implies [VF(w) S v2F(w) -v L2(W2) 5. Also note it suffices to show the result for all غ 100L2(wo)' otherwise for larger E can just apply the result for 1
É 100))(w0)' Thus as Lg(wn (w)) 2 1, we can assume È < 1. Clearly, we also can assume WLOG that tiress
As in Subsection 2.3, we make the following definitions for Algorithm For all uo Rd (VF(u))) > Ithress we let
A(ua) (wo F(uo) up), hence A1 = -4 1/V F(o)) Az(uo) = ug-
Otherwise if [[
||
Ithress we let Po un where uniform from B(O r), and define
sequence (p. (p.) osistaes via
When then take
A(uo) (Ptans Un) hence Ai (uo) = =Praes A2(uo) = u0-
We then have
tutres
=1(FF(u)) ) S Ithres
Loracte (unncte(uo))))
VV(u)) > Ithres
We also define
A(uo) = funes
vF(u))) S Ithres
VF()))) > Ithres
The is proof artifact.
43

---

We now establish the crucial Claim 2: for all uo
LF,F(w))) La(wo))
A is a
(S, foracl uo): ((wo), (L1(w)) uo) decrease procedure. (Recall (Lz(wo)E
To do this, we use the following crucial Lemma ensuring high-probability decrease around saddle points in the F(wo) set:
Lemma D.2 (Equivalent of Lemma 13, Jin al. (2017)). There exists universal constant Cmax 1 such that the following occurs. Suppose we start with a w LF,((w))) that is in the F(wo) suubevvelle set, satisfying the following conditions:
V F (w)l
Ithres and
Amin( ( S (LD((
Now let po i + S, where Ç is sampled uniformly from B(Orr) where r is defined in Lemma D.3, and let (p:) be the iterales of gradient descent starting from pn- Then when the step size 1) [w(w)) with
probability at least (2n)) e exx, we have:
VT2((wo)8
F(P:...)) F(w) < fitress
The variables in the above defined in Algorithm As noted earlier, because work in the generalized smooth setting, the details require significant care compared to the proof of Lemma 13 in Jin et al. (2017).
With Lemma D.2, we have the ingredients to prove Theorem 3.4. First we establish Claim 2.
Proof of Claim 2. We prove this by breaking into the following cases:
Suppose V Fun))) 9thres- Then 41 AA(uu) uo 7/ F(uo).
Our condition on 7) implies that
(wo)) < (o(F(w))))o(F(())))
As un E (F.F(W.)). we have by Corollary 1,
| uoll 7/ vFo(l)) s mppo(F(uo) s tpp (F s Pu(F(wo) 1)
Consequently, by Lemma 3.1.
F()) S F(uo) F(w)) + for all un
Now by Lemma A.I and Assumption 1.1.
F(u1) F(wa) nlo/(ub)1l L ((
|VF
F(wo) |IFF(u))
F(wo)
2 F(uo) A(uo).
Else suppose [VF(u))] s Jthres Then un is perturbed, and we consider the sequence the next fshres iterates Po Ug + E.P....... Piass
Consider the event & from Lemma D.2, which occurs with probability least dLi(wo) xx Under E, for such ug we have:
(T
Either
F(Ptam)) F(un) < -fthnes
that is
F(u1) = F(Ptna)) F(ua) Jihres-
Or
AwaN (v² -VELz(wo)) hence uoo S.
44

---

In all cases, by definition of A, we conclude that A is (S, lomale (un) Auun); decrease procedure for u L (F.F()))
(Li(wo) La(
2,00)
Consider these two cases, and recall the definition of A from Theorem 2.1. Using the definition of 7), Ithess Jihres we obtain for e a small enough universal constant,
A min
2L (woox x L
x Li
Combining with Theorem 2.1, and note Lornele (uo) s lahres S mmxx(1F((wo) for ē 1. We thus obtain the desired oracle complexity O La (wo) max F(wa). obtain an iterate in S.*
O (wo) max F(wo), to
22
We finally show the desired probability of success. Through Theorem 2.1, since X 2 18 and by definition of we can verify that the probability of failure is at most
dLi (wo)
F ((wo)
X. sup F.
(2Wo)
A A(w)
d. (T.((Wo)
F(wo)
TT2(wo)
c282
(wwo) (Iz(wo)
$ x²* x-xxxX 2clL1 (wo) F(wo)
C2
$ se x/4 2F (w))
Wp)
2.5
86.
This completes the proof, assuming Lemma D.2.
D.2 Proving the key Lemma
We now prove Lemma D.2 to complete the proof. The rest of the proof is similar to that of Jin et al. (2017), but hinges crucially on the fact that the analysis in Jin al. (2017) is 'local'.
Consider any 7 > 0, and define the "units" in similar way Jin al. (2017), but now in terms of L1 (Wo). L2(w)) > defined earlier. First the new 'condition number' be x x(w)) := (w (note this is not the real condition number, but rather is the 'effective condition number' of 2 in F(w))) Now define the following positive reals:
3
log 3 dic
Fi = =-<L(wo)
L (ww))
F2 log de
2
-2 dk 8 )
9 VnL (Wo)
log
L2 (2ww)
dx
L- VnLi
log"
Tz
Our goal is to prove the following.
"Note tines generally does not decrease with F(Wo), and this is why the max(1,FFur) comes in.
45

---

Lemma D.3 (equivalent of Lemma 14 in Jin et al. (2017)), There exists universal constant Cyaxx such that the following holds. For any F satisfying the conditions of Theorem 3.4, for any ô 6 (0, di suppose we start with a point i F(,F(w)) satisfying the following conditions for some 7 where G is defined as above:
|VF(E)
Sg and Xmin (V²F(#)) -7y-
Let Po w C. where Ç is sampled from the uniform distribution over ball with radius x-logl "F and where L is defined above. Let {pi) be the iterates of gradient descent starting from po- Then, when the step size 1j S Li(wo)' with probability at least 1 1- 8. we have the following for any
C
T F2:
F(pr) - F(w)
- < FF.
Plugging in LL(ww)) 17
dL,((1))) e into the above expressions for (wn(
(www))
F2, 9, L, using S Cmax, and directly applying Lemma D.3, we immediately obtain Lemma D.2. The of Section D is thus devoted to proving Lemma D.3.
Remark Note it suffices to prove Lemma D.3 for å and y smaller than universal constants, as the result Theorem 3.4 will remain identical under the O(-). Thus
assume WLOG that log(dx/6) is larger than some universal constant, and that y S 1 Also notice by our choice of step size Spmz and the assumption 7 60 for Cmax [ww
60
obtain
12100
K2 11
This in turn implies
G s C,
Fg 2 40,
((dn) dx
L VnLi(wo)) T22(wo) llog"
min (1,
< 6600
Po (o((Fwo) + 1)' (P(((())) + +1]
where the second line uses that
(22 2 Ln (wo) max(1,, (llsPo(FFW)) (F(w)) + 1), Po (F(())))))))))) (P( (F(w)) + 1)}-
As these assumptions come with no loss of generality, we make these assumptions for the rest of the proof.
To show Lemma D.3, again as Jin et al. (2017), we prove that the width of the stuck region is not too large.
Lemma D.4 (equivalent Lemma 15 in Jin et (2017)). There exists universal constant Cmax such that the following occurs. For any 8 (0, di let F and satisfy the conditions in Lemma D.3. Without loss of generality, by rotational symmetry, let e1 be the minimum eigenvector of FW)). Consider two gradient descent sequences {u,} and (z,) with initial points un Zo satisfying (again, denote the radius C
elog( 4x)
Uo w ST, In = Uo e1, M
2
Then for any step size y L. and any T
Gaur F2. we have:
Fin[) F(wo), F(xT) F F(xo))
-2.F..
Now, prove Lemma D.3 given Lemma D.4.
Proof of Lemma D.3 given Lemma D.4. Recall as per Remark 9 that
Ipo - w| S <rS LS
(o(F(w)) + 1)
46

---

Also recall i E ((.F(w))- Thus by Lemma D.1 we obtain for all u Pow that
| $ Lı(w).
Therefore by Lemma A.I,
F(po) s F()) + ||F(W))r++ (wo)) ,² FFW) Gr
L1 Li(w)) === F()) Fi,
2
2
where we can readily verify from Remark 9 that Gr L.(w)) p2 S F1.
Now let the stuck region be the set of points Po in (B such that F(pr) F(po) 2.5Fi.
Define the unstuck points by the complement of the stuck points.
We upper bound the volume of the stuck region as done in Jin et al. (2017); this step does not use gradient and Hessian Lispchitzness. Let Stuck Region (.) be the indicator function the stuck region. Write all w E Rd as w = (w("), w(-)),, where w(1) the component of w along ei direction and (-1) is the component of w along the orthogonal complement of ej. By Lemma D.4, for any IB (w)
+ V p² wl ( - -ū-V12 - -
Stuck region (w)
Stuck region (w))
dw
5
(1w .2.
r.
2/d
Using this, we have:
Sancee.) 1stock region (w)
Volume Volume(Stuck region)
w 1 -((-)))11111
Sa ((w,r)
1suck region (oin))rggn (w)dw((1)
dw (1)
i 1o-vVe-11 ao -w 1)12
< S (()r))
dw (-1. ..
5
2vd
= Volume(B d- (0,r)) Vd
Then letting I'(-) denote the Gamma function, we have the following ratio:
Volume(Stuck region)
dr
Volume r))
Volume (BameeeB(w,)1 (B),rr))
Vd Volume rŌ)
8
+1)
nd
r 2
+ 1
d
2 S8.
md
Here we use the following property of the Gamma function: for x
[(x+1) I(
$
x
This directly implies that with probability at least 8. Po is an unstuck point. Consequently with probability least 1 6, for any T 2
cass F2, we have
F(pr) - F()) = F(PT) F(po) + F F(po) F(w) s 2.55 +F= -155 < FF..
This proves Lemma D.3.
Now we prove Lemma D.4, which we do with an analogous strategy as Jin et al. (2017) by coupling two gradient descent sequences. We have the following two Lemmas, analogous to
47

---

from Lemmas 16, 17 in Jin et al. (2017). Again, the reason why they hold in our setting under generalized smoothness because they all concern 'local' behavior around points in the sublevel set of F(wo).
Consequently Lemma 3.1 and Assumption 1.2 ensure we have the required 'local' smoothness properties.
Again define H, (z) analogously to page 20, Jin et al. (2017), follows:
= v2 F (z) Fly) + (VF(y), x y)
2
2 (a ((=-y)' H H) -)) y).
(22)
That is, Fy is a quadratic approximation of F, Taylor expanded about i. The aforementioned Lemmas follows:
Lemma D.5 (equivalent of Lemma 16 Jin et (2017)), Letting 11, there exists a univer- sal constant Cmax S 12100 such that following holds. For any ö (0, de b, consider F, F.W, r as in Lemma D.3. For any uo with ||u0o w| s 2r rloog " 3
22
define
min-iiiftt inf(t) Fan (ue) F(uo) -33Fi 8F2
T min
Then for any 1) '(wa)'
Guary we have for all & that ll: w| s 150c2.
Lemma D.6 (equivalent Lemma 17
al. (2017)). Letting é= 11, there exists universal
constant Cmax S 12100 such that the following holds. For any ö (0, d consider F, r as in Lemma D.3, and sequences {u:). {2t} satisfying the conditions Lemma D.4. Define:
T min inf {t) Pao (I+) F(xo) s - 2F2
Then, for any 17 S Can means that
if u. wl 150 all < T. we will have T < &Fz. Equivalently, this (wo))
inf (t: (z. F s 33. 2F
Lee. that we escaped the saddle point.
Proof Lemma D.4 given Lemma D.5, Lemma D.6. Choosing Gmas to be the minimum of the Cmax from Lemma D.5, Lemma D.6, ensure both Lemmas hold. Clearly this preserves that Cmax T2100
Define
T" = 2F,, inf(t: (u. F(uo) s 33Fi).
We break into cases on T versus T
T By Lemma D.5, 1rr-1- - w| 2 150Ca. Since L s Remark 9 and é= 11, this yields
1
G000 (a(F(w))=1)
1
|UT - 10 150Ce
4 po(F(wo) +)
Thus because e (..F((.)) by Lemma D.1, we have
||))((u)| s Li (wo) for all u ur Thus, recalling g < L from Remark 9, obtain
FVF(ur-1))
|| < | ((w) I. (wo) (w))))lrrr- w/
$ S 150 (wo) 1500)) (w)).
Therefore, nL1 (wo) Cmax S 1.
| w| s |ur-1 W + 7/ F(
150C L 1508 7L11 (Wo) (3006+ 1)
(23)
Recalling k, logg( dx the conditions of Lemma D.4 give
|u0
w STS L.
(24)
48

---

Combining (23), (24) and applying Triangle Inequality gives
UT uol s (3002 2)
(25)
Also by (24), we have [uo أرهه 5 (o(F(100++I) Thus as is F(,)( by Lemma D.1 we obtain
[(o)( (wo)).
(26)
Moreover, by Triangle Inequality we obtain that for any e UoUT', we have
u أ| s (3002 2) = 33022 s
Po Po(F(Ww) 1)
As (F.F(w)): Lemma D. implies for all such u1, u2 UgUT that
v F(u)) -
[n u2 L2(w)).
Now applying Lemma A.2, and by choosing 1) = I(we) for small enough universal constant C, we obtain:
F(ur)) F(uo)
VFF(u)) (wr uu) 1
(ur FF?F(F)) uo) L2(wo) | - I
(uT)) F(uu)) [=((Wo)
|UT forn-uol 2012 16 I=2(wo) lut uol
2
$ -FF + (w)))))))))))))))
- 0 (00 / (wo) 5 -2.5...
Here we used (26), (24), (25), and that L s Remark 9, In the above, O(-) only hides universal constants as ē= is a universal constant, and so these final inequalities can be made to hold by choosing Cmax a sufficiently small universal constant.
Since w (F.F((w)) and 17 L.(w,)' Lemma A.7 shows that gradient descent will not increase value (this essentially the same as several steps the proof of Theorem 3.1. combined with induction). Thus for all T 2 I" and hence for all T F2 2 eF2 2 T
along this gradient descent trajectory, we have
- ((ur)=F(ur)
s F(ur)- - F(uo) S 1..5
T > T": In this case, by Lemma D.5, we know |u, - u0| s 150CE for all t T" 2F2.
Define
T" inf { (x.) F(xo) s -3Fi..
Since |/u. - w|| s 150C for all < T* &Fz it follows that |u: w 150C for all < min(2", T" Thus by Lemma D.6, we have that min(T", ,T") } < T and so T T
Applying the same argument as in the first case the (æt), we have that for all T 2 Fz that
can
F(xr) - F(xu) -2.5..
This proves Lemma D.4.
Remark 10. Note that w é L FFFF(w))) is central to this argument, unlike the Lipschitz gradient and Hessian case from Jin al. (2017).
49

---

D.3 Proof of Escaping Saddles Lemmas
Now we prove Lemma D.5, Lemma D.6.
Proof of Lemma D.5. We follow the proof of Lemma 16, Jin et al. (2017). Again, we aim to show that if the function value does not decrease, then all the iterates must remain constrained in a small ball. This is done by analyzing the dynamics of the iterates and decomposing the d-dimensional space into two subspaces: a subspace S, which is the span of the negative enough eigenvectors the Hessian, and its orthogonal complement.
The main difference now that now we cannot directly control relevant operator norms with global Lipschitz properties of the gradient and Hessian. However, it turns out that the proof of this Lemma will follow induction on the iterate UN and consequently uy for l' < / are close enough to w. By similar argument as in Lemma D.3, since w E L ((wo)))) this lets us upper bound the gradient of these points. By the Gradient Descent update rule, this in turn implies the current iterate is also close to w, and thus we obtain bounds on the relevant derivatives in terms of L1 (wo). (2) for all points in the convex hull of the relevant iterates.
will obtain that all of the prior iterates
We begin the argument. Analogously Jin al. (2017), since 5 (0, dic ]. we always have log dx 2 1. By the gradient descent update function, we have
U++1 ue n/V F(u).
This can be expanded as:
Uc+1 Ur 10--111 -V/VF(uu)) - S (fo V²F(O((: - uo) + +uo)d0 (a)0)u un).
Recall the definition H = (.) Let A, be defined as:
A, = S/' 2 F'F((( un) uo)dd 1 H.
Substituting, we obtain:
Uc+1 = (I - (I-1 n):)(u: - un) 1/ FVV)())) uo.
Note we do not immediately have an upper bound on the operator norm of A. In particular this is because i could diverge (logarithmically) in the dimension, only being upper bounded by F2.
We now compute the projections u, 44g in different eigenspaces H. Define as the subspace spanned by all eigenvectors of H whose eigenvalues are less than Elog(";" "r Let S denote the
subspace of the remaining cigenvectors. Let and B, denote the projections of onto S and St respectively, i.e., a; Ps (u: uo), and B. = Ps- (u. uo).
We can decompose the update equations for u into:
a++1 - (1 - (u: up) -1PPsV((u))
Bi11 - (I- 5- A, (w: - uo) -I/Ps:F((un)
By the definition of T, we know for all 1. T:
-3F, Fun (u:) F(wo) F((u)) (w: -uo) (u: un) T "HH( (uu uo)
FVF( (u, -u) 7 lay |2
B HB..
2 člog
de
$
Evidently we have
u0l2 211===20 1u0=2
|ay 1 1| and thus the above rearranges to
Uu uol uol2² 2ćlog dis
3F ( (w: uo) + 7 8.8.B.) 118.1
(27)
Now we control (u.)) I. We use the fact that w Cr.F(w)) to give us the necessary control over this quantity. Similar ideas were used in the proof of Lemma D.4, and will continue to be used in the rest of the proofs of Lemma D.5, Lemma D.6. In particular, recall as per Remark 9 that
luo w|| s 2r < 2C
Po (( 1)
50

---

Thus by Lemma D.I. as ū E ((w))( we obtain
||v)[(u)| s L1 (wo) for all u uow.
Consequently,
(FF(u))-V((i)) s (w - اا|l s 2rlL1 = 29,
which implies
VVF(4)) (V 29 3g.
(28)
This gives analogous bound [VF in the proof of Lemma 16, Jin et al. (2017). Substituting this bound on |/v F(uol into (27), we obtain
de Gèlog
Fièlog
de 8
B,HB, (x))
||u - wo max
U, uol
11B.11
In this implies
Gèlog dec
Fièlog de
B H H,,clog (dr))
u, uoll 14 max
-118al1
(29)
The key induction:
Now, we induct on to prove
Iu uo s 148Cà for all t
(30)
Clearly this implies Lemma D.5, upon recalling |lu, w 2r 2C s èC by our choice è = 11.
The base case is evident.
Now for the inductive step, suppose (30) is true for all r S such that / + < <T We show is true for 1 1.
Due to the above bound (29), suffices to upper bound |8.+11 HB We note as the proof of Lemma 16 of Jin et al. (2017) that letting
6 := Ps- (Ar(u: uo) ((())),
we have by the Triangle Inequality and properties of projections that
| s | un |Vo(]))]]
(31)
Furthermore, we have by definition of the update rule for B&11 that
B 11HH) + 1/8..
(32)
Thus,
1B s - - H | n6; s |B 1) HHB 176, Now, consider any 5, S St. We upper bound | Ilop Rewrite
(33)
v²F())) A, = J. (v2 up) + +wo) - 2² F(uo))(O v2 -FF()) F2F()).
Clearly, as per Remark 9,
1u0 w||l 2r 2C (o(F(wo) + 1)
Recalling w (F,F(w)) and applying Lemma D.I gives
| - F²)) op Lz(ww) 1 up - w|
(34)
Moreover by inductive hypothesis, we know that |u,, - uoll S 148Cè. Consequently as à 11 2 and following Remark 9, for all 0 [0, 1]. we have
1
(1(,,, uo) uo) T| s 2C 1486L S Po (o(F(wo) (wo)++ 1)
51

---

Since w é LF.F(wo) it follows by Lemma D.1 that
|v²F(B(u,- uo) un) v² F(uuu))) L2 uol for all 0 [0, 1].
(35)
Hence by Triangle Inequality, from (34) and (35), we have
/ s (www) (I,, 4 + | - =1) L (2(wo) | - -wl))
(36)
Proceeding from here is now exactly the same as Jin et al. (2017). We detail the argument for completeness.
Combining (31), (36), (28) and applying the inductive hypothesis and the condition of Lemma D.3 that [40 :||l 2r, gives
| s L2(wo) (14822+ llue l uol + +IIVF(uo))
2
$ (22(w)) 1488
1482+ K log
2 39.
du
Plugging in the choice of L, and choosing small enough constant Craxx (21188(1 ) and choosing step size < (ww) gives for any 0 OSTSE.
| S 1488 1482 +
V 11 ( (wo) +3 + 3.5g.
(37)
llo
dx
We now bound | 1,, B:.1, which combining with (29) finishes the induction and thus the proof.
In order to bound [Bt+1]. combining (33) with (37) and recalling the definition of S and B gives:
BBr-1 s 1+
17y de (nd
|B, + 3.55/..
člog
Since
[Bo] = and t + 1 T, by applying the above relation recursively, we have:
|8++1| Σ 7-0
3.5
1+
1/7 drs dr))
B/9 3. 10.5Ca.
(38)
člog
T
In the above used T < CF, which also implies
1+
$ 3
elog (one can find an easy upper bound on based on definition and check using Tog (wo) T. (wo) 2 that this is the case).
Eloo 4x)
Now for bounding HB notice also write the update equation (32) for Br as:
t1 B.= (I-nHH) 8
7=0
As H is symmetric this gives:
BT. = 1
Σ Σ
8 1-11-7 (1- (1 nH) 7 78.1122
-2002=0
Thus we have:
HB s S
Σ Σ 16
(1(I- HHI -1HH -
71
Since for < T1. S we have 188 1861111 $ 3.5g as argued earlier, we have:
1 $
B Hp $3 Σ Σ 1 H(I H
12-0
52

---

Let the eigenvalues of H be {A:}. Thus for any 71, O. the eigenvalues of ( - are (>((1-1d)) We now detail calculation from Jin et al. (2017). Letting (2) == X(1 n/) and setting its derivative to zero yields
Vga(A) -1- 7))= =.
1 is the unique maximizer, and ge(A) monotonically It is easy to check that X (1+t)n increasing in (-o0, A.]
This gives:
111 - (I max ), n n s sA(1- 77)
(1+ +22)
where = min(f, Xr ) Therefore, we have:
Bl. 1 n/g
Σ
71 m=
1
To bound the sum note:
21
1
Σ Σ
Σ
min 1 + 2t 1-T)
2t + 27.
1 +
1+7
22-
Thus:
3.5² L252
B HBr. 22-3.""nT'''
(39)
de log 8
Finally, substituting the previous upper bounds (38), (39) for [| B HB into our prior display (29) for [u uoll. we obtain:
Gé
Gélog
dx 8
Ficlog (
dic 8
dx B. H.HBBiooo
u. uul 14 max
Bell s 148ca.
This finishes the induction, and hence the proof of the Lemma.
Proof Lemma D.6. Again, we aim to show that if all iterates from un are contained in small ball, then the iterates from Zo decrease function value. As with the proof of Lemma D.5, the proof combines the proof idea of Lemma 17, Jin et al. (2017) with the self- bouudoonning framework. This time it goes through even easier, because the required new bounds that we need from the relevant iterates being 'local' hold not due to induction, but rather from direct application Lemma D.5.
Define v. Et - u, By the assumptions of this Lemma we have that un +/4
C m-log( 4x)
e1 where
2 1..
Consequently
2/d r S 1ool sr.
(40)
Recall the definition
H = FF
as per (22). Also define
4= = S. F2 dv:)d0-F
Exactly in the proof of Lemma 17, Jin et al. (2017), by directly writing the update equations, have
U1+1 + Mt+1 = Ex+1 = -t F
= + U. 7/ F(u, v.)
53

---

u. + v2 -nFF(u)) - -n [o F²F fo oos
= =u, - - (VF((u) - -1( + D,)u
= =u,-
- -u
(V--NFF(u)) + (1-1/ -
Hence U++1 U. 7/ F(:): obtain
U++1 = (I-nH - -n
(41)
The difference from the proof of Lemma 17, Jin et al. (2017) now that we do not immediately have upper bound | without global Lipschitzness of the gradient and Hessian. However, similarly as in the proof of Lemma D.5, we can obtain such a bound using the self-bounding framework, since the point w in question is in the (subleeel & F(wo)))
Note by hypothesis up from Lemma D.4 and |voll S by (40),
I w 800 w|| llvol s 2r.
Applying Lemma D.5 directly to the (It) implies that
at w| 150Cè for all T.
By assumption of this Lemma, we have
u. u| 150Cè for <
Triangle Inequality thus gives
|| < 300Cè, w uoll s 300CS for all < T.
Therefore for all 0 s s
u, + Ov, B(w, 600Ce).
Note as per Remark 9,
1
600C 6600C S
Po (woo) + 1)"
As i C (FF(())). it follows from Lemma D.I that |v²F(u, (v.) v Futuull (2(w)) Ov, for all 0 [0. 1].
(42)
Similarly, by the above bound
|u أ| s 150Cès
Po Do(F(wo) + 1)
and as w é (F.F(wo) Lemma D.I proves that
sL2(wo) |u: W.
(43)
Now, rewrite
A S. (v" +vv) 42 =² -FFF))
By (42), (43), and the above bounds on ||vel. llu, w/Il we obtain for all [0, 1] that D (0)))()lo)) ||u. wll) (22 ) ((402 1).
(44)
From here, exactly the same proof as that of Lemma 17, Jin al. (2017) lets us conclude. We detail it for completeness. Similar to the proof of Lemma 17, Jin et al. (2017), let S be the subspace corresponding to eigenvectors of H with eigenvalues larger or equal in absolute value to 7, and let St be its orthogonal complement. Note e₁ S S. Denote the norm of u, projected onto S by th, and the norm of v, projected onto St by Φz.
Notice therefore from the assumptions of this Lemma that @u 0 as Uo is scalar multiple of ej Similarly, note vho |vol
2và"" r by (40).
Let
B = (L2((w)) ((50c 1).
Observe B s L, as (L2(wo) s and as S Cmax 5 T 11. Combining (41) with (44) gives that
dee 2 (1 mn) B 07 owr (1 (1+)))0 +B o3
(45)
54

---

The key induction: Now we induct on to show that for all < T,
Φe S 4Bt t/-
For the base case, recall by hypotheses of the Lemma that vo a scalar multiple ei, thus Φo and the base case holds.
Now, for the inductive step. assume that the inductive hypothesis holds true for all 7 < for some such that & 1 s T. Substituting the inequality (45) for Φt+1 and applying the inductive hypothesis de & 4Bt Ve, we obtain
Φ41 s 4Bt(1 + +m) B 1/? 07.
Also note (45) gives
1 (1+m))
4B(++ + 1) 4B(++
which rearranges to
4B((1 m7) & 4BB(L+ 1) + +4B²(1 + 1)v v3 07 4B(1 +m)
Therefore,
Φ41 S $4B(t+ 1) + (AB 1)V ui oz BV 6 67 4B(1 + m1)
Thus, recalling B s 1, to complete the induction it suffices to show the following:
(1 + (1+4 67 oz 4(1 +7))
Choosing VCmax
min
1 11 222 46
which is universal constant, and choosing S [.(w))
T
have:
4B + $4BT 4n (w) C(450 1)2F ( 1)ē 1.
By the inductive hypothesis, this gives de vh. In turn this implies that
4(1 m/) 4th2 2 2xh (1 4B(++ 1)) 1/2 02:
finishing the induction.
Finishing the proof from here: We thus obtain S 4Bt 4/ for all t, where that 4BT $ 1 as proven above, which just follows from our choice of parameters. Therefore.
1 (1 mm) BV2 1
YT) 2 the
(46)
The last step follows upon noting < (7L2(w)) 1) s Cmmxx (450 (450c+1))mlog (dx) The inequality is strict as ?17 0.
2/2
Finally, recalling that ||v||| < 300C2, t/o 2 zva
r and using (46), we have for all
300(C.
a) |
2 t/
1 + ?17
2 v/u
+ ?m
8
(47)
2
2/d
log dx
Note that 8 E (0, de
implies log
du 5
2 1. Applying (47) for T we obtain:
T < 1 + log
6600x clog
dr
log (11 1 m
55

---

Algorithm 2 Restarted SGD, from Fang et al. (2019)
Initialize at wo, and consider Ko (( n= @ B 6(60.5). ). 20' (wo). all explicitly
defined in Subsection E.I.
Let 0 (the total number of iterates), & 0 (the restart counter), x" wo (the point we consider the escape from).
while &s < Ku do Let x =x -nnn-n((v f ((+1) + aA where A 41 is uniform from B 1) and independent
of everything else, and Çet1 is an i.i.d. minibatch sample
- ++ 1. k + k
if 12 x² > B then
x0 x², k+0
end if end while
Return Kg 2k-0 x
$ 1 (600k 10 Elog
dk
1
791
1
+1+ 11+2..0 2.0((10(6)000)) 1.01 logkk/)))
(dk/
?11
(1 ++ 2.0301 F2 s 2F2.
40
These last steps follow by:
Gum Taking Cmax small enough universal constant so that 7m 60 L, (wa)
Cau
satisfies 60
2.01 > (0 which valid for all 0 x < 0.02.
x
Remark 9, which states that can assume WLOG log(dk/0) is larger than universal con- stant. particular we can assume WLOG that log( log(dz/6) solves log < 00.01 (hence log(sv/0 log(d</)) s 1.01 log(dx/))), that 2.01 1o11lo(((()) (og(6)))) = 2.01 log(6600) s
1og(dk/6) (recall é= 11), and that F2 log(d=/8) 2 40. 7
This completes the proof.
E Restarted SGD finding Second Order Stationary Points
Here, we formally prove Theorem 3.5. We formally instantiate Algorithm 2 here. One may notice slight difference in Algorithm 2 vs the algorithm of Fang et al. (2019): we artificially inject bounded noise at particular scale ō. This ensures set & F.F(w))) Note we may not be able to escape saddle points that are not in F. F(wo) but that does not matter thanks to our framework Theorem 2.1, which effectively lets us consider only behavior within F(r) Also note practitioner can find such a noise scaling & (depending on suboptimality at initialization I' ((wo)) via appropriate cross-validation.
can escape saddle points that are in the ((Wa)-suuleve
The general proof strategy here is similar to the way we adapted the proof of Jin et al. (2017) in Section D. Namely, we use the self- self-bounding regularity conditions to control the derivatives F in appropriate neighborhoods of the F( -ubbleell set FF.F(w))
E.1 Notation and Parameters
We set the parameters of the algorithm as follows. We will highlight the significance of these parameters Subsection E.3.
Noise Parameters: Define
o' (www) o(F(wo) 1).
(48)
ō 20' 20'(wo)
(49)
56

---

01 (wo)) max(o'(wo) + 0,13.
(50)
Note this only depends on po (and therefore only on pı) and F F(wo). Note ē E (wo), 20' (wo)
20w)))
Also note 0 (wo) 30' (w)).
Update Rule: Define
((+1) == vf(x';((-1) + oA
Thus the SGD update rule in Algorithm (without considering the restarts) is x++1 x' v f :(+1) Note the slight abuse of notation; ((+1) not necessarily an actual gra- dient. 10 This will cause issues or ambiguity for the rest of this section.
{(+1)
Effective Smoothness Parameters in F(woo)-ublever -sublevel set: We define the 'local smoothness parameters' as follows, slightly differently compared the proof of Theorem 3.4. Define
L1 (ww)) == max ma (:((w)) 1), Ps(Po + 1) o' (wo), F(wo) + 1)),
(51)
(2(w)) max (2F(wo) 1), Po (F(w))(WW)))) 1)² max 4, (o (wo) + po (wo) + +))
(52)
Note all of these parameters only depend on F(wo), through pI(+), P2()) ps(:)),s(s:))))) (recall po(-) can be defined in terms of p1(-)).
Parameters of Algorithm 2: We define the remaining parameters of Algorithm as follows.
Consider any E 0 and p e (0, 1). We choose:
C 2| log( (3/) 1 log
24vd
(0.80.811)
1
v L2(wE
52 = 165,
B 8
L2(w))
Ko Čin 5z
B28
17 5
(53)
512 max (wo)? 1) log(48Kn/p)
3(1 +
Also define
24vd
log(3/p) (0.80) 1]Ko.
K. 2log
" 5,
thus Ko =
1
Remark 11. To choose 77 satisfying the above inequality, one can perform the same analysis as on footnote 4, page 7 of Fang et al. (2019). We first choose ñ appropriately by setting
B²8
4096 max (wo) log( 48/p) log(p)
log(0.8-1) 1
log(3/p)
and then set log -3 (1/r))
Remark 12. Analogously the proof of Theorem 3.4, note it suffices show the result for E. " : for [2(wo) we can just apply the result for Lz(wa) and the result remains the same up F F(wa)-depended most some universal constant. We also can take L1 (ww)). Lz(w)), 01 (wy) to be the max between their currently definition and an appropriate universal constant. Thus due to the choice of parameters above, we may assume that
parameters in the 0(-). Thus we can suppose that 6g (and 5) are
Č1 Kú 2 1,
'In fact. this is the only condition need on ō. In practice, such a ã fine-enough validation in terms of only F(wo). Whhis choice of notation is made to demonstrate the artificial noise injections ō^ ++1 are not fundamentally needed. They not necessary if the stochastic gradient vf(;)) enjoys suitable anticoncentration properties.
57

---

log( o (1o)) ) 2 1,
(wo)
1
B s min
1, (ww
L. (wo))
(w)
S min
1, (wwo2
From here note we have nL1 (wo) S 1. As these assumptions come with no loss of generality, we make these assumptions for the rest of the proof.
Notation: Consider sequence iterates x") x ,... beginning at x" comprising an instance of the while loop in Algorithm 2. For such a sequence, let 8 be the o-algebra defined by all the prior iterates and the noise up through æ", namely (=" ,S,A', stopping time given by
A*) Let Ko be
Ko = inf (k= | -x x01 BJ. #
Note x and 1ookk 1oosk are 30--masurable Thus, 1gsk-1 = Kozk is - -mesurabbe..
E.2 Result
We now formally prove Theorem 3.5. The following Theorem E.1 can readily be seen imply Theorem 3.5.
Theorem E.1. Suppose F satisfies Assumption 1.2 and the stochastic gradient oracle satisfies Assumption 3.1 and Assumption 3.2. Run Algorithm initialized at wo run with parameters chosen as per Subsection E.I.
(F(wa)+1)7nKG, upon making Consider any p (0, 1). With probability at least 1 Ip-
13a
T (F(w))++ 1) oracle calls to vf()),
Ko
B²
Algorithm 2 will output Ó (F 13a
candidatee vectors w, one of which satisfies
[VF(W) s 18L2 (wo) AMIN (V2 1178
Remark 13. Before proceeding, justify why Theorem E.1 implies Theorem 3.5. Simply take E 2 (89) in Theorem E.1. Plugging this in, we obtain a result on finding a SOSP as per the definition in (2). 1I The oracle complexity has the desired dependence on and polylog dependence on d, p. The probability is at least 1-p-1(1ppp 1p-@(e--i)))) where the θ are hiding polylog terms in d, 1/e, 1/p and dependence F(wo) (through #1 (-), P2()), p3()), This holds for any (0, 1).
Now consider the final desired success probability 1 1 governed in terms of 8 (0, 1) in Theorem 3.5. Let 1-5, polylog (d, 1/e) in the guarantee from the above paragraph. This gives Theorem 3.5, with the requested probability and oracle complexity.
We now prove Theorem E.1 via our framework, Theorem 2.1.
Proof of Theorem E.1 and thus Theorem 3.5. We again use our framework Theorem 2.1. Consider any e (0, 1), and choose parameters as per Subsection E.
Let
S= (w: (oo[[))F()]] s 18L2 AMIN (V2F(W)) A
-178).
Define A follows, identically to how we defined them for Restarted SGD in Subsection 2.3. Consider any given Uhg e Rd Let Po = uo. We define a sequence (p:) via p: P:-1 ((Vf(pi-1i()) (:) + JA7). Note this sequence can be equivalently defined by repeatedly composing the function
n (u: + öA).
Recall this definition refers to such that [VF(w) s ve,w"F()) -Vl.
58

---

If it exists, let i, < i Ku be the minimal index such that lp:- - 1Pol > either case, we define
B. Otherwise let i Ku- In
1-1 hence Ai(u0) A2(n)) = Σ
i-1
A(uo)= = pi:
Ep: P..)).
Pt.
[-0
We now let
B
foracte(1s)) Ko, and A
Kn
Following the notation from Algorithm 2, notice that A(uo) corresponds to next vector set x in the while loop of Algorithm 2, when the while loop begins at x
Crucial this proof are the following two Lemmas. While inspired from Fang et al. (2019), crucial difference is that they hold only in the F(wo)- -sublevel set LF.F(wo)-
Lemma E.1 (Equivalent of Proposition 10, Fang et al. (2019)). Consider x" in the while loop of Algorithm 2. Suppose x LF.F(w)). With probability at least 1 -p. if does not move out of the
ball [xx,, , B) within the first Ko iterations in the while loop of Algorithmm 2, letting T Ko 2
Ko-1 x
we have
[VF( 18L2(wo) B² AMAN ( -176.
Lemma E.2 (Equivalent of Proposition 9, Fang et al. (2019)). Consider x" in the while loop of Algorithm Suppose x e F,FF(w))) With probability at least 1 Lp. if x moves out of B(x", B) in Kg iterations or fewer in the while loop of Algorithm 2, we have
B²
Fo F(x")-
Tq
Finishing the proof: The main point is to prove the following Claim.
Claim 7. For any uo FFFF(Wo)) A is (S, Ko. A, [.,. -decrease procedure.
Proof of Claim 7. Apply Lemma E. and Lemma E.2 to the sequence (p:)osis recalling that A(us) corresponds to next vector begins at x
x in the while loop of Algorithm 2 when the while loop ug. By Union Bound over the events of Lemma E. and Lemma E.2, with probability least 1 P. we have the following:
Suppose there exists t Kg such that pe & B(pu. B) B(u, B). Let be the minimal such t. By Lemma E.2, we have
B²
F(A1(u)) =(pr)s((p))))
F()))
= F(uo)- - AA.
7nKo
Otherwise, we have A2(un) where p= Ka En=0 Ps. In this case, by Lemma E. have
A2(un) S.
Consequently, A is (S, Ko, A, Ip, u) decrease procedure.
Now with Claim 7. directly applying Theorem 2.1 and plugging in the relevant parameters, we obtain Theorem E.
Remark 14. To sanity check these results, note the rate from Lemma E.2 will get worse as gets smaller because Kon- 2| log(3/p) 1 1] 24/ 85 will increase as 77 gets smaller.
Tog(0.8
The rest Section will now be devoted to the proofs of Lemma and Lemma E.2. For the rest of Section E, we suppose F satisfies Assumption 1.2 and the stochastic gradient oracle satisfies Assumption 3.1 and Assumption 3.2. These proofs are similar to that Fang et al. (2019), but hinges crucially on the fact that the analysis in Fang et al. (2019) is 'local'.
59

---

E.3 Preliminaries
We now establish useful properties of the parameters of the algorithm defined in Subsection E. analogously to Lemma D.I.
Locality of balls [xxx", , B):
Lemma E.3. We have B s 2po 2po(F(m))++)) In particular, for any u E B(w, B) for w L FFFF()))) we have u - wil $ (P0(F(1))- $ 2po(F(w)+1)*
Proof. As per Remark 12, we have e S 1. Thus by the choice of parameters in (52),
B L2 (ww $
(L((wo) S (P + 1)
This completes the proof.
Control over the stochastic gradient oracle:
Lemma E.4. For all u such that u B(w, po(F(wo)+1) ) for w e LFFF(w)) we have (V s o' (wo) for all 5. Proof. By Assumption 3.1, we have
Now as w (F.F(w.)) we have
Po ((oo) + +1 Thus by Lemma 3.1 and again as w LF,F(wo)) we have
Po(F(w) +)
F(u)
+1.
Combining these gives Lemma E.4.
Lemma E.5. For all such that ((,, po(F( for w CF -V 01(w) (www) for all Ç.
Proof. This immediately follows from Lemma E.4 and the definition of ff(u:)). as ē cō.
Locality after one step of SGD:
Lemma E.6. Consider any B(w, B) for F(wo)) Then for all points p in the line segment between and u 1/V ()) for any Ç. we have p TB w. po(F(w.)+1))
Proof. It suffices to show u - 1/V f(u: E B W, 2(po ((o(F()))++)) after establishing this, the result then follows by Triangle Inequality and Lemma E.3. To this end, by Triangle Inequality, it suffices to show that
(Fo(F(wo) + +)
Indeed, the same reasoning as in the proof of Lemma E.3 gives
F(u) F(ww) + 1.
Thus, Assumption 3.2 gives
[FF(u) (F 1),
60

---

and so Lemma E.5 gives
[V s <w((wo) + pa (o(FFw)) + 1).
As per Remark 12, have
1
1
63
n
マ
B
s
2
(2(w))² 2 2 (wo) )0.5
Combining all the above gives
1
n/ n|v](u;
(a) (wo) (o + 1))
222(w
2po (Fw()) (w)))(w)) (F + (01(w0) (o(((ww)) +))
2pp (F(w)) 1)*
which by our earlier remarks completes the proof.
Properties of the effective smoothness parameters:
Lemma E.7. Consider any x LF.F(wo)) Then we have |[ s L1 [ww)) for all u such that
either:
u E B).
OO lies in the line segment between some u' E B(x", B) and u' (() any
Proof. By Lemma E.3 and Lemma E.6, irrespective which case for u the conditions of Lemma E.7 holds, we have
u
I Pa (o(F(WW) +1)
As x F.FF(W))) this implies
uu x
(o(F(w)) + +1 Po(F(z)) +1)
By Lemma 3.1 and as x0 (F,F(Wo)) follows that
F(u) F(x") 15 F(wo) +
The conclusion follows by Assumption 1.1.
Lemma E.8. Consider any x LF,F(W))) Consider any u1 U2 such that each u. 1,2 such that either:
u, B(x", B).
Or lies in the line segment between some u' E 18xx B) and u' n/ ny f(u': any Ç.
Then
op s Lz |n1 Uzll
Proof. Irrespective of which condition applies to u. By Lemma E.3 and Lemma E.6, we have
u; IB x
Pol F (Wo) + +1)
for = 1,2. Thus the line segment i 4y is contained in TB [w (o(F(wo)-I) ) As x LF.F(W.)) the result now follows from applying Lemma A.6 and Lemma 3.1.
0
61

---

Remark 15. The reason for the second case in the condition on u or from Lemma E.7, Lemma E,8 will become clear the proof of Lemma E.2. In particular, to prove Lemma E.2, we will consider 1--1 -- (w: (u:{ ç) for E B(xx,, B) where x ((w))))))
Lemma E.9. Consider any x² CFFF(W))) Then for any u B(x", B) and any S.
[w: Li (wo).
Proof. By Lemma E.3, we have
u TB x
po (F(w)) + 1)
By Lemma 3.1, because x² ((Wo))))) have
F(u) F(wo) + 1.
Moreover, as e (w.) and by Lemma E.4 and Corollary 1,
[v/(u;)) (I & [VF(u)] d'(w)) s s (o(()W)) 1) o'Wo).
Thus the result follows from Assumption 3.2.
Remark 16. While Lemma E.9 is phrased as an upper bound on the operator norm of f²f(: ()) it can be easily phrased in terms of the local Lipschitz constant of f(: similar to of the possibilities in Assumption 1.2.
Enough noise to escape saddles: Now we verify that the noise scheme here gives us enough noise to escape saddle points in the F(wo)-sublews set Fr,((w))
Definition E.1 ((q". v) -narrow property, Definition 2 in Fang et al. (2019)). A Borel set A Rd satisfies the (g" (1)-rrrow property for any é A. q 2 q". qu é A
Immediately, we obtain the following properties of this definition, as also noted in Fang et al. (2019).
Lemma E.10. If A satisfies the (q", ()",v))nane -narrrow property, then for all c1 Rd, e R, a ezA satisfies the (lcal4 v) -n-nrroww property.
We now introduce the following definition:
Definition E.2 (u-dispersive Property; Equivalent of Definition 3 in Fang et al. (2019)). We say that a random vector & has the v-dispersive property for any A satisfying the (wo))) property, we have
4v/
-narrow
P(C A) 2
Note the slight change of the constant & rather than 1 in the above definition compared that of Fang et al. (2019); this subtle difference will appear in the following proofs, although this will not change too much conceptually.
Now we prove the following Lemma, which shows that our update rule contains enough noise to escape saddle points:
Lemma E.11 (Dispersive Noise; see also Algorithm 3, Fang et al. (2019)). The update v fx St-1) admits the u-dispersive property for all unit vectors v. for any z'.
Note this does not necessarily hold for the stochastic gradient oracle itself under our assumptions, hence the artificial noise injection of &
Proof of Lemma E.11. First, we prove that the random vector 7 AAt+1 property for all unit vectors Consider any A satisfying the aa (www)) have
f+1 satisfies the Dispersive Noise
4/a .v) -narrow property. Note
P(ōA t+1 e A = =P(A*) E A)
62

---

0i (wwo)/AV Vor B(,,))
Vol BB,
oi (wwo)/AVd Vd=
01 (wo)
48
Here, the inequality follows from elementary calculation with multivariate calculus, analogous the calculation in the proof of Lemma D.3, which we detailed in full in this article. An analogous calculation can also be found in Jin al. (2017), proof of Lemma 14, and in Appendix Fang et al. (2019).
Now, note ō o'ww), we have
i (wo)
o'(wo) +
4ō
47
and so
1
P(GA#1 E A) S 5
Consequently the random vector A^ satisfies the Dispersive Noise property for unit vectors v.
( satisfies the u-dispersive property as wanted. The proof is analogous to part iii, Proposition 4 of Fang et al. (2019). Consider any unit vector v. Recall that A and ff ((+1) are independent. Since the (g" ."" v - property evidently preserved with the same parameters by adding fixed vector to A, we obtain the following bound on the following conditional probability:
Now, we show that v fx("
F(Vf(=': ((+1)) A(V =
+5 flV :(+1))
= E-V AlV (('::(1))))
2
This holds irrespective of conditioning, which implies that V ((m1) satisfies the v-dispersive property.
E.4 Escaping Saddles
We first aim prove that we can efficiently escape strict saddle points in the F((wo)-sullvel set, similarly to Fang et al. (2019). In particular, we aim to prove the following Lemma E. The contrapositive of Lemma E.12 will turn be used to prove Lemma E.I, which establishes that Algorithm 2 can find SOSPs.
Lemma E.12 (Equivalent of Proposition 7 in Fang et al. (2019)). Consider sequence of iterates x x beginning at x comprising an instance of the while loop in Algorithim 2. Suppose x. (.FFF( and that )mns ( s -Ō2 for d2 O. Then when the while loop of Algorithm initialized x with probability at least 4. we have
Ko Ko 1og(3/p) log (00((0.-1)
+ +1KK,
Remark 17. For d2 very small, note the guarantee from Lemma E. will deteriorate because Ko scales with 5z
To prove Lemma 12, we use the same strategy as in Fang et al. (2019). However, as we do not have global Lipschitzness of the gradient and Hessian, we must be careful. We use that the strategy only requires control over points that are 'local', i.e. near x", since the proof strategy studies escape from the ball IB (xx B). We then appeal control over B(x", B) that we have by Subsection E.3.
Remark 18. In this section Subsection F.4, probability over the samples Çk and the artificial noise injections A+t
Now we go into the details. As Fang et al. (2019), let wx w²(u) the iterates of SGD starting from a given u using the same stochastic samples as x and the same noise additions oA k In particular
" (u) " "
63

---

Thus x" = (x").
Also for all u, let Kexin (2) be the stopping time defined by
(exir = inf(k 2 0: (ww(()) 201 B3.
Thus Ko- = (x)))
The high-level idea from Fang et al. (2019), similar to as in Jin al. (2017), is to consider the 'bad initialization region' around B(x", B) where iterates initialized in this bad region escape with low probability. We then prove that this bad initialization region 'narrow', and consequently we can escape the saddle point efficiently.
In partieular, define
Sk, (x²) {u R P((cxa) K,) s 0.4). Note by definition that 2 (a") S [bx'), B).
(1(m))y We establish the following Lemma, which verifies that S (x²) is 'narrow' in 4vd
First let Qo a suitable sense.
Lemma E.13 (Equivalent of Lemma 8 in Fang et al. (2019); also similar to Lemma 15, Jin et al. (2017)). Suppose the assumptions of Lemma E.12 hold. Let e, be an arbitrary unit eigenvector of (x") corresponding to its smallest eigenvalue -5m S -82. Then for any q 2 q0 Avd any u, u +qe1 E B(xx), B), we have that (((Kau())) Ko) and (Kesin qee) 2 K.)) 0.1.
a.(w))n and
Here probability is over the single sequence of samples used to compute stochastic gradients and the artificial noise injection.
Remark 19. The proof of Lemma E. 1.13 crucially uses that 22 has negative eigenvector, as one would expect.
Note we have, as in Fang et al. (2019), that
24vd d
log( 6/20)
log(6B/go))
K, 2 log
02
(54)
log(1 [1 n702) log( + 1702)
This follows evidently from the choice of parameters and definition of go, and Remark 12 which states that it is enough to show the result for no2 at most a universal constant, namely one satisfying log(1 2) 2 5. Now using Lemma E.13, we prove Lemma E.
Proof of Lemma E.12 given Lemma E.13. Given Lemma E.13, we first prove that the bad initialization region Sk. (x") satisfies the (go,er)-narrow property, i.e. that there are points u ge: S K. (x²)) where y go (w()) This part of the proof is identical to Proposition 7, 4vd
Fang et al. (2019). If such points existed we would have
P(Coxi()) K.) 1.Kc,P( ge:) 2 Ko) 2 0.6.
This implies
(( (U(Cexi(u) 2 K,) and (Kexir gel) K.)) 2 P(Keuir K,) + (u qe;)) 0.2,
which contradicts Lemma E.13.
From here, prove Lemma E.12. For this rest of the proof of Lemma E.12, only consider and do not consider the iterates from u gej. Recall & satisfies the (4o, e, -narrww property with
(77, (wra) as shown above. Thus we have for any u B(x",B)
qo
4v7
P(w2(( (u) E S (a²)) P(u -in-vvj(us Sk (x"))
-Pvi((u;))) E - (σ0) +
(55)
64

---

The last step follows from the definition of the w" (u), the scale and translation properties of the (go, e1) -naroow property which implies that (-S (x") + u) satisfies the ( (=(ww)
ei -narrow
4va
property, and that V ff (1) satisfies the e di-dispersive property by Lemma E.11.
Note as events we have (Ke (u)) < Ko} = (Kexi (w) s Ko). Thus by Law of Total Expectation, for all [=x,; B).
PKKexxi (u) S Ko) 2 P( (KCrii (w' (u)) < Ko)
Le [[(PKooxi (u)) < Kol koll"))((u ((w' E (S [=]
(56)
Conditioned on w (u) s (SK. (x))), we have by definition of Sk (x") that
P(Kesa(w' (u)) K.(3*) ) 2 0.4. By (55), for all E B(xx, B), have (u) (u)
P(w
SK (x )=))))
Thus combining with (56) implies for all E B(x", B).
PP(Cexit S Ko) 0.4 2
0.2.
(57)
Now consider any N' 2 1. Notice events,
(Kexi (u) > N' K.) Nw (NV (N (u)) Ko}
(w (N')
(N' (u)) Ko (Koul())) (N' - -1)Ko}.
Therefore.
P(Kexir > K.) = E ( (w (1) (u)) Kol8ko
( |[ (u) > (N' - K)
Note that conditioned on Keeit (u) (N' -1)
o. it follows that Kexi Keuu (N' -1) (w)) B(x B). SUPP''R(== (("eeal'') K.). Using (57),
Therefore P (Mesai (w (N', (2)))))))(())))))))))))))>)))( K.l0ko)
can upper bound
(u) > N' Ko) $ (K) (N' 1)K..) weB(x",B)
sup P(Kexi((u') > Ko)
$ 0.8IP (u) (N' (N'-1)EE 1)).).
(58)
Recall that Ko log(3/p) log(0.8 1)
Ko. Let N lng(3/p) ToR(0.8
1.. We obtain by repeatedly applying (58)
for N' N, N - 1,,.. that
((Kesii > NNo) s 0.8% s//3.
This gives the desired result.
Now we prove Lemma E.
Proof of Lemma E.13. Again, we proceed similarly as the proof of Lemma 8, Fang et al. (2019). The main difference is we only have control over the relevant derivatives prior to the escape from 15xx,, B) (recall x0 Ly.F(w))). However, it turns out that this is sufficient for the proof to go through.
Setup.
Recall that we have wd (u) and
" (u) w (u) 7 f fw (w):
w²(uu ge,) w k (u + qe1) fV (u+ Cx))
Now define the following stopping time:
K₁ (exir(u) (u) A K-xit (u + qez).
For solely the purpose of analysis, consider the following sequence:
(w*(u++ (u gel) (u) : K1
(59)
(1 2
k Kr
Clearly the x are 3* meaasuaabee, because the event {k kc,} is t measuuabbe...
65

---

Remark 20. Note unlike Fang et al. (2019), the first case holds when k S K1 rather than is K, That being said we expect that uses the exact same definition as Fang et al. (2019) for the 2 the proof this generalized smooth setting will still work, with slightly modified argument compared to the proof we present.
Notice by definition of wu))),, w (u+qei) and assumption of Lemma E.13 that u, u+ B(x", B), we have 1 > O. Thus,
= gei-
Controlling the 2t. Let H =2 We have the following lemma to control the 20 from (59).
For all k. define
D = -= S (2F(w" (ww < = x- (u+ (a))) qe::)e)):(s)----- (f=+ (w))()))
(u+ (u (u)))do)
(60)
(61)
Recall by definition of w" (u), have
v R-1 (u (/ ge)): aA*
v f(w V/ (u) aA
for the same noise sequence A Thus we also have
t (VF(w* gei)) - v F (u - vsw (w):
(62)
Lemma E.14 (Equivalent of Lemma 13, Fang et al. (2019)). We have that for all l s K2,
z
(I - ()) nD ngl.
Furthermore, we have the following properties of the D² and Ets defined (60), (61):
1. For all such k S K1, have
1I (2(w)) max( (/w" w 1 (u+ qei) x0 "1l||1o0 =00) s L2 L2(w))
2. For all we have
1E 1[E513"-1]-
3. For all le S K2, we have
< 2T, (wa))l=*
Proof. We prove each part one at time:
1. For k K1, using the definition of 2 it follows that
z = wn (u + gei) wn (2)
w * gel) x (atp-//////uo-a------a))--------
= n( k- (u+ (u+ -
(u+ <n((FF(W*>>
(x)) (v (()
S( v²r( - (u) 0w (u + ge,) w -- (w)) k-1 118
- mn(H - n
This proves the desired property of the k
66

---

2. For the required properties of the Di-1 consider any k S K1. First, notice w (u) (u (u+ + gei) - w (u)) Ow (e)) (1 (w) for any 0 e [0. 1]. For 11, both w (u + ge1), w
0(w"-1(u
h--11 (u) e B(x", B). Note this still remains true for K 1 Ki, the definition of Kr implies that the iterates 8-1 (u) B(x", B).
& Ki because for k
wn-1(u qq)), w
Thus for any 0 [0, 1]. (u) fww (u + gei) f points p on the line segment between x and (u) 0(w qei) ww)((u) lie in B Bxx", B). Thus by Lemma E.8,
wu))())) TB(x", B), and so all
11 = FFF(x)) Lo¹ v2F(w" 0 11
k- (u (ee))ee))))))))>>)) - - (1) 1
S |1 v2F(w" (u) 0(w x- (u ge1) w ww)) ) d0
$ (2((w)) L/¹ (10 (u qei)))))+))))))))))))))(()))(q x²) (1 0) - (w) x²) |
$ (w0)) max (100 (u gei) ) æ011, =/'1,1110* (w) 201}
$ (2 B.
The last line follows since K1, hence k - 1 K1, thus w= (u + gei), w- IB (xx", B).
(u)
3. Next as the stochastic gradient oracle v (x) is unbiased, applying Linearity of Expectation on (62), it follows that E[ []= 0 for all k.
For the bound the magnitude of th again recall by the above that for k s K1, we have
- (u + geg). w k- (u) TB(x)) B).
Thus for all p on the line segment between w k- (u ge,), ) wn k- (u), we have pe B(x", Thus by Lemma E.7, ||v? (x)) s (wo). By Lemma E.9, for any S. (/:
((",B), B).
L, (wo). Recalling (62) gives
|s*||
/VFFFW qe VF (u) (1)- gei):e)) - (u):(a))
2L, ( 1/ (u gei) w² (
2T, (Wo) || 1.
In the last step, we used the definition of 2² for k s K1
This proves all the desired parts Lemma E.14.
Controlling iterates under a high probability event. We now consider rescaled iteration as considered in Fang et al. (2019). Recall the definition of 6m 2 82 in the statement of Lemma E. For each le 0, I,..., define:
:= =- q + 1fm)) * Zk.
Lemma E.15 (Equivalent of the first part of Lemma 14, Fang et al. (2019)). Define D (1
Dr, and slightly overloading notation, define
=²= (1 mymm -
Then for & K1, we have 26 el and
I HH
x n, k-1 xh + n
+ 71mm
67

---

as well as the properties
| (2 all 0s k K1, all k K1.
|| s 2T, (wo) for
Proof. We prove all the desired parts of Lemma E.15.
The fact that s0º =e follows immediately, because 2 qei For the general recursion for eh² consider any A K1. First note that by the recursion for the 2 for k s Ki in Lemma E. we have
16 q (1 ) =*
I nH
11 (1 + 170m)
-kk-1) (
1 m7
D
o (1 ()0m) ((k-))) nu 1 (1 mymm)
+ njm
I HH 2h
+ nD
k-1 16 1/55.
1 + 17mm
Consider any S 1r, For the requisite properties of for < 11, the upper bound on the norm of D follows immediately from Lemma E.
Next from the definition of ç and Lemma E. 1.14, for k s K2 we have that
Sall q (1 )
(1 m70m) ) (b-1)
< 2T, (wo)
2 x
1 + 17mm
$ 2L, (wo (wo))lbb-111
This proves Lemma E.15.
Lemma E.16 (Equivalent of the rest of Lemma 14, Fang al. (2019)). With the step size q. from (53), there exists event Ho (namely, from (66)) with probability least 0.9, such that for all s min((C - 1, Ko) we have
1 s 4,
(63)
and
eT 1 2
(64)
Proof. Define
I - H
B
26
+ npm
Recall that H = F(x)) and 00 is in the F(wo)-sublever set LF.F(w))) Therefore, from Assump- tion 1.1, [ L1 (wo). By definition of 8m it follows that
-8mI s L (.
Since n (Wa) 1, it follows that the matrix I nH is symmetric and has all eigenvalues in [0, 1 + n. This implies
(65)
Note that 3 and kh are measurable on kk-1 This combined with Lemma E, 14 and Lemma E.15 implies that for all k K1.
E ( ( T 1
11pt-1122 B[ ( |]= 0,
68

---

and 1(BB-1) 5.2 1100-1/22 s ||- 41,((w)) (wo)
( | (8I1 (woo)
Now define the following veal-valued stochastic process:
(1B4-1) 1100-1122 : K,
Yx = (1B ca 110-
k K.1
Note Ys is 5y-measurable, and that (BB-1)7, 1100 1s2 IK-1<k, LAsIc, are all 84-1 meesuuubsre.le.. Thus, by Lemma E. 14 and the definition of 5 from Lemma E.15,
x[ 0.
Furthermore combining the above justification with the trivial case k> K1, we obtain
| s 8L1(wo).
By the (standard) Azuma's Inequality, with probability 0..1/22ko). for any given 1,1 7 Kg:
Σ vi 8L1 (wo) 20 (40Kg) s 8L1 ( S 77
1
where the last inequality follows from the given choice of parameters. Analogously, by Lemma 1. and Lemma E.15, we also have for 1 S kt s K,
B [ 1 1 '] 0, letch 1 s 4L (wo).
Define
Y== e 1 Is2 1ssk.
The (standard) Azuma's Inequality implies that with probability least 0.1/(2kk), for any given I, 1,1 1.55/5 Ko:
Σ Y s 4L1 (wo) / (40kg)
4n
By the Union Bound, there exists an event H. happening with probability at least 0.9 such that the following inequalities hold for each
1, 2..,... Ko:
Σ Y S 17
(66)
4n
R-1
In particular under the event Ho. for any s min - 1, Ko). using the definitions of Yx, Y we obtain
Σ Soush 1 1ss
$ -
1
Σ eich 110-11152 S
1
(67)
7/
4nj
Now from Lemma E.15, it follows for all ks K2 that
||
- H 1 mo
ab + nD a k-1 pb-
|/ 1| + 2 1---ish-111 + 1? DA ctll' + 2n
11 QI. Q2.k Q3.
(68)
where we define
QI. == 1 DI k-1 * Q2, == n/ Dr 1h-- + ctll² Qa. == (n
For S K1, we have
1 Kr. Thus by Lemma E. and (65), we have
Q1, S 2nL2 66~
(69)
and
Q2 s 2vi k- wt-1l" 2
69

---

2nn L2 2 B²| $61151111 10= +872 + (iww)) 12
$ > -1.
(70)
The last inequality above follows as per Remark 12.
Now complete the proof. Under the event Ho from (66), we prove (63) by induction on & (recall our condition for & for Lemma 16 is that 0 S k min(K1 1, Ko)).
When A O, by Lemma E.15, 20 e1. so unit eigenvector), proving the base case.
| leill = 1 and e/ = |eil2² 1 = (recall ej is
Now for the inductive step, consider some E min(K, 1, Ko). Suppose 1,0 <lslsk k 1. Then because & K1, upon applying the above bounds (68), (69), (70) we have:
| 2 holds for all
k Σ
1 2 $ 110012
Qia
Q2 +
Σ 9o..
s=1
m=1
$ $1+27 2n
Σ L Wi B| 15 111 112 161 L1 (wo))
Σ
11bb112 +2n Σ (1B-11)(C
s=1
5-1
s-1
$ $1+2L2(WD) B 4. nk + 1617 L1 L1()))
44 k 2.
21
Σ (13" 113--1766 [Ca 110-
8=1
1
< 11+16[2( Ko 2n EΦ011 S2 1 $ ++ 2m
8=1
11
To upper bound the above, we used our choice of step size L2(w:) (L,(w,)² and B S
1
[,(w)) as per
Remark 12, above upper bounds Q1,., Q2,s, and that the event H. implies (67).
This completes the induction and proves (63).
With (63), we prove (64). Namely note for & s min(K] 1, Ka), summing and telescoping the recursion for * from Lemma E.15, have:
k-
e ej + Σ
De
2b
neisa
k-1
k-1
2 1 - Σ 2L2 B 11 + Σ
eis : 10-11122
1 1
2 1 - 77 Ku (L B 2 Σ el 1 1s2
2
1
8
8
2
Here to lower bound the final sum, we used that voo e and the upper bound on ||0| from Lemma 15, the fact that have already established |/>1|| 2 for all k as showed (63), and that the event He implies (67).
This proves all parts of Lemma E.
Finish. Now prove Lemma E.13 via the same high-level strategy as the proof of Lemma 8, Fang et al. (2019). Note on the event {K₂ K.). we have
K w K- (u + qel) w K- (u) (o-Ku( qez) - x0)) To x²).
Thus by definition of Kr, the event (K1 > Ko} implies that
ko
Ko (u Koo
gei) x + Ki (u) =2 $BB
That is.
(IG Ko) 5 {1 ko SBB}.
70

---

However, consider the event Ho. (66) from Lemma E. On the event (K1 > Ko} n Ho, we have K, $ min(Ki 1. Ko). and so by Lemma E.16, we have
e Ko
1
2
Thus by definition of a and recalling 6m 2 d2 > 0, on the event (K1 Ko} Ho we have
|z g(1 17mm)
[/ 2 go 1722) No l
6B 3B,
90
9a 2
where the last inequality uses (54). This means that
(K1> > Ko} n Ho {||2 | 3B).
Putting our work together, we see that
(Ki Ko) Ho s 11 2 23B) {||=*0|| $2B) 2.
Therefore
[K1 Ko} s H. = P(K1 Ko) <P(H)) 0.1.
Recalling the definition of 1n, we conclude Lemma E.13.
Remark 21. Note we only have eī s0 for ks K2 due to the lack of global Lipschitz bounds on the graedient and Hessian of F, unlike in the proof of Lemma 8, Fang et al. (2019).
E.5 Faster Descent
Setup: As Subsection E.4, let Ko denote the escape time of B(x B) for while loop of Algo- rithm 2 when the while loop begins at x. In this section, we aim to prove Lemma E.2.
As in Subsection E.4, the difference between Lemma E.2 and Proposition 9 of Fang al. (2019) is that this result only holds at points in the F(woe-subleeel set Cr.F(wo). For the rest of this section, we work under the assumptions of Lemma E.2; thus for the rest of this section, x" is in the F(wo)-sublevel set L (w.))
The idea here is similar to that of Subsection E.4. At high level, we have the requisite control over the gradient and Hessian since the iterates we consider are in neighborhood of a point x FF.F()))) As in the previous part and as in Fang et al. (2019), we let
H -= v==²)(<²))
and let
g c+ := vf(z** ; - vF(=", 0
(71)
Note as A k+1 has mean 0 and as the stochastic gradient oracle is unbiased, we have that for all k 0.
E k+1 33 =
Let S be the subspace spanned by all eigenvectors of F2= whose eigenvalue is greater than and S denotes the complement space. Also, let Ps Rdddd and P Redd denote the projection
matrices onto the spaces S and St, respectively. Let u Ps x²), ), and v P (x - x"). We decompose the update equation of SGD
k+1 t²
TiP :PPsF((*
sttt
k+1 t - -PsPss
s.
for k O. Clearly n = =0, 0 =0
UAU" by the Spectral Theorem where U dxdx is unitary and e Rdddd is diagonal. Let Aşo denote the diagonal matrix with diagonal entries equal to the positive (diagonal) entries of A. Let Ago denote the diagonal matrix with diagonal entries equal to the zero or negative (diagonal) entries of A. Now define
Now decompose
Hs :s UA H := U.
71

---

Thus H has range in S, and H has range in St. Note s. H are both symmetric.
From here, define the following quadratic approximations:
1 -" Hsu, Gg- (v) = 0+ 2 H.v.
(u [P>VF(<')] u
Now define the quadratic approximation G(x:) Gs(u) + Gg. where u (s - x²) v P x²).
easy to see that
G(x) (t (x- -x= H² x²).
For convenience, let
vuf(a") = PsVF(x"), v.F(x") P VF(x")
Similarly, let
E" Pst c Ps.
Also denote the stopping time
K= Ko Ko- Due to its 'local' nature around the x" in the F F(wa) -ubleeell set, still have the following result from Fang et al. (2019):
Lemma E.17 (Equivalent of Lemma 15, Fang et al. (2019)). Consider any u e F(.F( and consider any e B(u, B). Then we have
- (F(*)-VG(<)) L2(
2
Furthermore, for any symmetric matrix A, with 0 < <as we have
TAT for any == 0, 0,1,..., and j 0, 0,1,....
(I- (I-
aA); a(i+i+1)*
Proof. Notice that for all 0s0 1, fr f)u B(u, (1 B). Thus LF,F(w))) by Lemma E.8, we have
| (1-
.ス (2ww)) 01x ull for all S.
Thus have
(VF(z)-VG(2) - = |
F( - -4) - VF -
[1 FF2 + 0(x - u)) - (FF(w))d (x u)
L'' (T2(wo) 0|| ul])d0 | 1x- ul
L B2
The second part of the Lemma follows from the exact same proof of Lemma D.5 in Section D. is also proved in the proofs of Lemma 15, Fang al. (2019), and in the proof of Lemma 16 of Jin et al. (2017). ). For more detail, let the eigenvalues of be (At)- Thus for any i, 2 0, the eigenvalues of (I aA) AA'A(I aA)' (Aa(1 aAx ) We now detail calculation from Jin al. (2017).
Letting 9:(A) = X(1 - ax)' and setting its derivative to zero yields
(gr(A) (1 - aA)² - la>(1 - ax)' 0.
is easy to check that X; (I+tja is the unique maximizer, and gı (A) monotonically increasing in (-oo,1ī) A.
This gives:
1
(I (1-aA)'AR aA)*l = max (1 adx) s 2(1 at)iti
(1 (1+i+ÿ)a
where Å min(e,2ia.)
72

---

Lemma E.18. For any lo S Ko, we have
| s 0i (wo).
Proof. Note for k & Ko, we have k - Ko and so x & B(x", , B). Recall furthermore that x (F.F(()))) Thus, by Lemma E.5 and Lemma E.3,
|| - (FF=-v)(+++]]
so) swi(wo),
as desired.
Analyzing the Quadratic Approximation: We now analyze the quadratic approximation G(x) as done Fang et al. (2019). First we analyze the part in S:
Lemma E.19 (Equivalent of Lemma 16, Fang et al. (2019)). Set hyperparameters from (8). With probability at least p/4, we have
Gs(u Gs(u")
257
\1 (1o) (o)+ + log :/Tog(w))) 2
48KK
32
k=O
257
Σ
VGs( Ō(e
32
k-0
Proof. We follow similar strategy as before of combining the proof of Fang et al. (2019) with our self-bounding framework. To analyze Gs(-) we first consider an auxiliary Gradient Descent trajectory, which performs the update:
g y" - h
and yd = u yd performs Gradient Descent on Gs(+), which deterministic given x
Noting Gs has Hessian Hs. and that H is the Hessian of F at the point x e LF.F(wo)) we obtain from Assumption 1.1 that
sll s | L1 (wo).
Since the following only concern Gs, then identically the proof of Lemma 16, Fang al. (2019), we obtain the following:
By Ia (wo) smoothhssss of Gs (recall Gs has Hessian Hs), obtain the so-called "Descent Lemma':
Gs(ynt1) s Gs(s") + (VGs()"). - -/² Li (Wo) ktt v²1²²
2
=Gs( - nl In (wo)
2
Telescoping the above for s s KC and by choice of which satisfies 1/ nll(ww)) 1/2 as per Remark 12, we obtain
31n
G S Gs(3")-
Σ [
(72)
32
To obtain Lemma E. upper bound the difference between xx and x²h For all k define
We aim to upper bound zx (in an appropriate sense) using the concentration argument of Fang et al. (2019):
73

---

Lemma E.20 (Equivalent of Lemma 17, Fang et al. (2019)). have
With probability at least - p/6, we
3B
1=||
())%)).
(73)
32
and
2 H (wo)(w)) 1) log 48Kg + .)T,2((0)²BB*K) = 6(e..).
(74)
Here (c-) hides F(wo) (two)-depeddence
Proof of Lemma E.20. Clearly 2" 0. From the definitions of ut y² have
(VGs (u") vGs -((o)""))))(vFF("""" vGs(u")) - n/ gh+1
- ( - -mt""" k+| k 220. 0.
(75)
Unraveling the above recursion gives:
= n ((II-HH))* - (f
k20. (76)
3-1
j-0
Setting KC, Triangle Incquality gives
K-1 (I- -
<
j=1
1=0
We separately bound these two terms:
For the first term, for any fixed I from to Ko, and any from 1 min( we have
B[n(1 nH s) " 0, || nH S no (wo).
The first equality uses | | || and that the stochastic gradient oracle is unbiased. The inequality uses that P is projection matrix, | = |Ps S (wo) which follows j Ko and Lemma E. 8, and ||(T s)) < which follows as I 2 j and H 0. (Note the importance that s Ko. which gives us enough control over noise term El.)
Now to deal with the fact that the above control only applies for certain j. we define stochastic process follows, analogously our proof of Lemma E.13. For all fixed 1 s S Ko, define stochastic process Yi, over all S j s by:
( - DH-
ijsk
Yi = rnn(I nHs)
00
:j bj>K. K.
Recalling K = Ku A Ko, it's easy to check that for any fixed 1, Yi, 8 p'-measurable. Furthermore, - 15-1<x are both - Thus combining with the earlier observations, obtain that
E [ 0, ||is s saa (wo).
Thus, by the Vector MartinlM Concentration Inequality Theorem C.I, we have with probability 1 11p(())K))
48Ko
48K
Σ Vi.i
2n (wo) Hlg
s 2nja (wo) V
Ko log
S
(77)
16
The last inequality uses our choice of parameters.
By Union Bound, with probability at least - p/12, (77) holds for all from 1 to Ko- In particular, with probability least 1 p/12 we have for K (recall K. Ko) that
Σ nII - ) -gg
Σ
Yk.
B
16'
where we define Yic,j the obvious way. This holds because with probability at least 1 p/ 12, we have the bound (77) on || Yi.il irrespective of which value < s K, that IC takes on. The first equality holds by our definition of Yi, for s (= IC
74

---

For the second term, we have
K-1 E (I n (
K-1
Σ
Faf(x')- F
1-0
K-1
< 1
Σ
VF(=')
VG('')
1-0
n)2(Wo) B² Ko
B
2
2
32
The first inequality uses the Triangle Inequality and that || - H- )
$ 1 for from O to IC 1; this follows because ||H||| & L1 (wo) and as 1) S (ww))) The second inequality uses
1-j
(OTFF(()-GG(())) s F()) VG(=)] because Pss is projection matrix. The third inequality follows from Lemma E. and the fact that for all j j 1,
x² E BB(x,, B). The last inequality uses the choice of parameters.
Combining the above gives (73), the first part of Lemma E.20.
Now prove the second part of Lemma E.20, namely (74). Using the fact that (a + b)= A(a + +b) s 2a Aa + 2b Ab for any symmetric positive definite matrix and the recursion (76) for 2², we have
)=*) H Hzz
< 2n²
Σ (I - 11-HHs) K----1
Hg
Σ [I n K
K-jgj
1-1
K-1
K-1
+ 2n²²
Σ (1 - n1 s) ) - Hs
Σ (1 - nls
n1- (
(Val(t))
1-0
K
2 11 Σ
HH 12 (I H 5) x ig
+ 2n
Σ Σ (V.F(x') -vF(t'))VGs(uu')
K-1-i 1-11 )- (VVF))))VV
1= 1-0
K +2
s 2 n Σ (I nH ( k
4
The last inequality follows by properties of projection matrices and by Lemma E.17, recalling that for j s K - 1, 1, B(=",
Now we bound each of these two terms separately:
For the first term, for any fixed 1, S I s Ko, again we define a stochastic process for any j. 1 < j $ by:
()) 1 ( (I- ()- )')
ijsk KC :j> K.
Vi, =
Analogously to earlier, recalling K. s Ko, for fixed 1, is evident that Vi, is F meeauraable // (I )
is 3d measurrblleee, and thus
E [ I] 0.
We furthermore have
|V,, < not (wo)2 + 2(1 - j)
which follows by noting for any 1 1 s Ko and j s K s Ko.
I 1/2 (I- ([-nHs)) (
|| s 1
| /2 (I nH H - kall
75

---

< n0' (wa)²
1 + ()
This uses the second part of Lemma E.17, that | L1 (ww)). that s Ky which gives
f S (wo) by Lemma E.18, and our choice (which cancels one of the 01 (wo)² factors).
For given I, by the Vector-Martingale Concentration Inequality Theorem C.I, have with probability p/21)o) that
プ Σ j=1
48Ko
1
Yi.
$ 4nj (wo)² 200222oog log
p
1+ 2(1-j)
48K0
$ 4nj (wo) (wo)) Ko) + 1) log
(78)
The last step above uses i Ko. ΣØ= 1hj s log( K1) + 1.
By the Union Bound, with probability at least 1 P. (78) holds for all / from to Kg- Because & K. Ko. using the definition of Yi.j for z K., we obtain with probability least - 12 that
(88Kg
(I-
Σ YK.
4nj (wo) (log( (ooog(K())>)) 1) log
For the second term, using the second part of Lemma E.17 and that IC s Kg. and then rearranging order of the sum and performing explicit calculation yields
11 Le (w) (2 B
E
(
1 nH))) ( (HH
4
T=D
2-0
T2 22
Kg-1 Ka-1
Σ
Σ
4
1+j+l
1-0
(2 B4 ((Ka-1) min(1 +j.2Ko - 1-
$
4
1
1:0
n2 (2o) Ko
2
Combining the above two bounds proves (74), the second part of Lemma E.20.
We introduce more Lemma, intermediate step in the proof of Fang et al. (2019).
Lemma E.21. We have with probability at least - 1/12 that
3n x
[+))2 + 88o (wo) log(48Ko/p) + 2 Ko/2.
(vGs(1 8)
16
Proof of Lemma E.21. Lety" arg min, Gs(y): this exists as G is convex in the subspace S, by the definition of S. By the optimality condition of y", have:
v.F(x") -Hsy"
(79)
Let 5h th y². From the update rule of x² and the optimality condition (79), we obtain:
H VGs (v))))) * 5³ n ".*
(80)
Consequently, using (80) and (76), we have: (vGs(v vxh x
76

---

H.
K-1 Σ
100 VuF(=*) k-0
VGs-(") (SS--
(I- ki
Now we bound both of these sums in manner similar to the proof of Lemma E.20:
For the first term: For any fixed 1sls Ku, define real-valued stochastic process for any k, 1 s k (in by:
(i k- ( (I))a(I-)Ha) (0--1
: S K. kk> K.
Yi,x (1 k-1 ( (I- 1--1x
Analogously to earlier, recalling Ko, it's easy to check that for any fixed I, Yi, is 8 measurable, and that all terms defining Vi, are 8 measurable except tk Thus,
E Vi, =
We furthermore have for any fixed 1,15 Ko and ls 1 ksks
1 2 $ o (wo VGs -
1|
To justify why the above holds, clearly this is evident for k > K. For & s K Ko, note that
|M = ||00"11 - (1- Rn
= (Hsū k-1 sall 2
(I-NHs)
= =I(vGs(y 1-1) ) sk)
(I-nH
(wo) x-1) || - mHH
(wo) --
Here used that H s is symmetrie, that (80), that - - k+1 which we have argued earlier in the proof of Lemma E.20, and that || (wo) as s I Ko by Lemma E.18 and properties of projection matrices.
Now for any 1 Ko, by the Azuma Hoenf--ig inequality, have with probability at least 1 - (12K)) that
11 Σ
YL, 5
(wn)
EIvGs (1*))²
R=D
Taking a Union Bound, it follows that with probability at least p/12, the above holds for all with S Ko.
Because s K. < Ko always holds, using the definition of Yi, for k K, we obtain with probability at least 1 - Ps2 that
(ύ H (I- 8- Aewl
Σ
=
Σ
YK
km
S
2172 (wo)) log(2KK//))
Σ \ k=0
8mos Snol(wo)) log log(48Ko/p)
16
where we used AM-GM in the last step. This holds because we have this upper bound on Elen Yi, irrespective of which value of I, s I Ko that K. takes on. The first equality holds by our definition Yi, for k K.
For the second term: note
K-1
C3" VuF -VG)(u))) Hs(T-1H5)K--
(
k=0
77

---

Σ -. (T-HHS)
V -
17
" Ex=o
(1
K-1
+ 2n
Σ -v=((=)))sGuu)))
8
k=0
Ekoo
<//o2(w0)) BB* Ko.
8
2
The first step above uses that H is symmetric and (80). The second step uses that s IC and that T n s The last step uses that K. Ko and Lemma E.17; for h K, we have x B(xx,, B). Combining these above two bounds proves Lemma E.21.
argued in the proof of Lemma E.20. The third step AM-GM.
Now we finish the proof of Lemma 19, As done in Fang et al. (2019), we combine Lemma E.20, Lemma E.21 with (72) to prove Lemma E.19 as follows. In particular, taking a Union Bound over the events from Lemma E,20 and Lemma E.21, we obtain with probability at least 1 - p/4 that
Gs(u Gs( (vGs())), x u yry
(u
)) ""( -y²)
s ( (VGs(**)) ) v/ _(u )
H su -²a)
$ GG(( + 3n
16 k-O
+ 4no (wo)² (log( (Ko) 3) 1og(48Ko/p) (2 Ko-
Here the first two lines used the definition of Gs and S. The last line above applied Lemma E.21 together with the second part of Lemma E.20.
Now combining the above with (72). we obtain
K--1 3n
G G)(
Σ k=0
16
+ 4no ( (w)) (2 (log(Ko) log(48Ko/p) + Lz(wo) Ko
25
$ &Gs(u")
Σ
32
Ko) log(48Ko/p) m]L2(wo)2 Ko. 4nj (wa)² (log( (log(Ko)))))))
where we also used yd =u. This proves Lemma 19
We now analyze the orthogonal complement of S, S in Fang et al. (2019), where the analysis again goes through since the iterates are 'local', being prior to the escape time K: Lemma E.22 (Equivalent of Lemma 18, Fang et al. (2019)). Deterministically, have:
7n K-1 Σ
Gs- Gs. (v9) &G-
Σ (PVGGs
|v (z0) Lz(wo) 2 B*nK3- k=0
Note by choice of parameters that Toz (2()))) 2 Btn δ where again the Ō(.) hides F F(wo)- dependence.
Proof. By definition of Gs-, and using definition of Sh which implies H = O we obtain
Gsi 10)+ Gs (D*) + (vGsi (v*). k - + (o v²a) H (v k+l v²
78

---

s Gs (v") + (FGsi (v*) (0 -²a)
Gs (v*) TVGs (v") vof(x*) +
Gs (v*) n/ v (v²) (00]](((VV (nVGs (of)) VGsi (t*))
-n(VGs (v*) _b011)
VTG. (v*), 2 in (Gs 22/ VGs. (u²)]
s Gs. (v") - -
The last step uses AM-GM. Substituting and telescoping the above for ls from 0 to K. 1, have:
Gs-
(v
(Gs: - Σ
K
(VGSs (0 (.
7n
K-1
Σ
VGs- (z+) 2n Σ (V
K-1
8
k-0
K
7n
K-1
L2(wo) 2B no
SGs: Σ nVVSs (0*))) ),5+))
Σ
(x*))
8
2
Here, the second incquality uses that by Lemma E.17, for all k s KC- we have x² B(x*, B) and so
- L2 (wo))
2
This completes the proof.
Completing the Proof: Now we have all the ingredients in hand to prove Lemma E.2.
Proof of Lemma E.2. Again, we follow the strategy Fang et al. (2019) and adapt it to our setting here where we do not have global bounds on the Lipschitz constants of the gradient and Hessian. With Lemma E.19 and Lemma E.22 in hand, the idea will be to show
Kp-1
Ko-1
(b+)
Σ =(())))))=(11)))))
and to bound the noise term
Σ (V
We break the proof of Lemma E.2 into two cases:
1. Vz(x)) 50 (wo).
2. VF(=))
< 50 (wo).
Case This case more straightforward as the gradient is large, and will not use the quadratic approximation we developed earlier.
Consider any K S k K - 1. Thus x² e BBx B)), and B(x B) for all u zzz By Lemma E.7, as x E LF,F(w,), we have |v2](u)| Li (wo) for all such u. Thus as VF(x")| 50 (Wo) and by our choice of parameters.
9
/|/F(((((()))))))) |VF(**) - VF (0)(wo) - L1 (wo) B2
2 or (Wo). (81)
Similarly, as ++l = t v f(x² (k+1) and again as x L CF we have |[)|| s L, (wo)
for all u é I by Lemma E.7. Applying Lemma A.1, for all 0 s k K we obtain:
F(***1) F(x*) (VF(=*)) k+l -z²) + La (Wa)
x k+1 xx1"
2
79

---

--nllv/(>*)) ((VF((")) )**))) L1 [2(w))1)
V VF((*) 5ht2p?
2
s
s-m||vF(>>
11 FF((" ) E [1(w)) (1 [F(*)|] ?++ (
15
5
||F(x*)) /- (w)) [1(
< "
16
32
257
VF(x")]'
2n1²
32
25
(F((*)))
- 32
81
Note here that need to consider a bound on the Lipschitz constant of the gradient between x-1 and xx; see Remark 15. Here, we used the update rule of SGD, AM-GM and Young's 's Inequality, that L1 (ww)) $ 16 by our choice of hyperparameters, Lemma E. 18, and finally (81) in the last step. Telescoping the above inequality from
1, we get:
25
F - -1
Σ K=0
(82)
32
81
To upper bound the right hand side above, note by Triangle Inequality that
K-1
= 17 Σ VF(x*)
A-D
K=0
k x +1
E
=
k=1
2
1
201
Σ
E*
(83)
By the Vector-Martingale Concentration Inequality Theorem C.1 and the bound ||5] s o (wo) for
all s K. by Lemma E.5, we obtain with probability least 1 1-ppppl p/11:
A Σ E*
Kg M
B
1
Loek
2noz( Ko log( 48/p) s
(84)
16"
Here, we used the fact that 1igt = I- and consequently 1azk 8 measurrblle and that E[<"|ø*-]]= 0, || $ < (wo) for all < S.
Suppose the above event implying (84) occurs, which has probability least 1 12- Under this event, suppose that x is able leave the ball TB(x", B) K₂ iterations less. this the case, then we have K. Ko Kg, and so ||a. - =0 2 B. Thus conditioned on the aforementioned event implying (84), if x is able to leave the ball [Bxx,, BB) in Ko iterations or less, we obtain
X-1 Σ |F(E)))
Σ (V
||
B
1
B
15
15
T/C
np
16
162
162nKo'
k=
where we combined (83), (84) to lower bound - F>F((* ||.
Here the first step holds by the
elementary inequality | s < & and the last step uses Ky 2 K.
Consequently by combining with (82), with probability at least 1 - P. if x is able to leave the ball B(x", B) in K, iterations or less, have
25 8
B² 16 <((x")
B²
F(x FF()))
32
81
7n
Case 2: Suppose V F(x s 50, (wo). To obtain the desired result, we first define and prove the following Lemmas. Proving these Lemmas in turn utilizes the Lemmas on quadratic approximation we have established earlier.
80

---

Lemma E.23. For all 0 S K 1, we have
11
VVGs 220 on (wo).
Proof. By the condition in this case, properties of projection matrices, and as v 0,
[VGGs =|
50 (wo).
Note for k s 1, we have
- Ps (x* x0) B.
Thus
| VGs. (v') |vGs (1*) VGs (b))
$ 5 (w)) L1 (wo)
11
The above uses our choice hyperparameters, and that
V (v") VGs: (v")
s H || - - s L1 (woo) -0%,
which in turn follows because xd Cr,F(w)) and by Assumption 1.1.
The next Lemma obtained by combining Lemma E.19 and Lemma E.22, and it gives us a way to upper bound F(z*)- F(z").
Lemma E.24 (Equivalent Lemma 19 in Fang et al. (2019)). If VF(x))] s 50 (wo), with probability 2. we have
B²
F(x*) 5F(x*)-1 - Σ
(vGs
(. +
256
80)
rKo
k-1
K-1 Tn
Σ
VGs: (b*))²
25n
Σ
8
32
k=0
Proof. For is & KK-1, we have x e B(x", B). Consequently the entire line segment < lies in B(x", B). As x FF Lemma E.7, have
VF((") vF L, (wo)|l=* - x01 (ww) B.
Thus by our choice of parameters, as per Remark 12,
11
|FF(**) |V/(=))]|| vF(x")| | ||r(=*) (wo) (B 0 (wo).
Recalling that
||sc|| oi (wo) by Lemma E.18, we obtain from our choice of parameters as per Remark 12
13 s B+ no (wo)
B
-=--00 - K-1| ||
S
(85)
100
Using this, we then bound the difference between F(**) and G(x*). As xx
x
[(x)) x-1 B(x B), and x LF.F(W)) have v²=(()=
F(x)))
Le(wo))(u (lluu-r =- for all e xk-Iz by Lemma E.8. Applying Lemma A.2 and recalling that Gs(u*) (x*) G(I* x²), we obtain
F(*²) F(*") Gs(u²) -Gs L2(wo) k 2033 -==20
B3
(86)
5
Here, we used (85) in the last step. Note here that we need to consider a bound on the Lipschitz constant of the Hessian between x K-1 and xx; see Remark 15.
81

---

We do this in Now, take a Union Bound over Lemma E.19 and Lemma E.22. We now add the bounds from Lemma 1.19 and Lemma E.22 upper bound ( )v)) and use that Gs(u²) Gs-- (v")= =
0. Combining with (86), we obtain with probability at least 1 p/4 that
48 p
F(x*) s F(x") Σ (vGs. (uk-1), + 4nj (wo) 2 (1+ log (oo) log
7n Σ VGs (b*))l
25n
\>> (l2(wo) B Ko
L L2(wo) B
(87)
32
2
5
Note by our choice of hyperparameters (analogous to the choice of hyperparameters from Fang et al. (2019)), we have the following bounds: 4nji (wo)² + 3 Ko)) log
48
Ba
3La(wa) B3
Ba
La(wa) B
B
250n
1289
5
R0y
Combining these above inequalities with (87), with probability at least 1 - p/4, we obtain
3
B²
)( s F((") - " Σ VGs (UR-I), +
256
80 nKo
7n Σ k-0
VCs. (u+))(
25n
Σ
||GGs(
8
32
k-1
This implies Lemma E.24.
By Lemma E.24, we want to lower bound the gradient norm of Gs., Gs. the following Lemma, assuming x² leaves the ball B(x", B) Ko iterations.
Lemma E,25 (Equivalent of Lemma 20 in Fang et al. (2019)). With probability go x exits B(x", B) in Ko iterations (i.e. K Ko S Kol. we have
Σ k-0
(1*))+
K-1 1-1 +1
E|vGs(0b))
2
169B
512nKo
k=O
At a high level, the proof idea is similar to the proof of Case earlier. Telescoping the recursions of u - n v/ F(**) and y* = (V we obtain
Proof.
K-1 Σ (VGs: + vGs(
E1 -1 Σ
(VGs (0*) VGs(
E-1
(ett) VGs vxF(x*)) + + - 80
2 17
Σ
k=1
K-1
ck+l + (u~-u0) - -(x -2 z0)
v + 17
Σ
k=1
-
|
K-1
1 Σ
- V. -V -v.
Here, we used that * = = y² and the Triangle Incquality.
Next, recall xt x0 = u + k for all k and un = O. Thus x² - u² v0 2 2
Furthermore notice
VGs: (1*) Fo*) = H (VG(Et)
For all s K - we have t E B(x", B), so as x0 e LF.F(WO)) Lemma E.17 gives
K-1 (VGs: (v*) v.F((*)) snK. L2(wa)B²
2
Applying these observations and Triangle Inequality again, we obtain
K-1 [vGs (+)==(+)))++
K
Lo
||== 20ll - 201 -
Σ
k=0
82

---

B
2 | x01
-
21
Σ
(88)
32
and Lemma E. 1. combined with the fact that projection matrices do not increase norm and that
xx BBxx.. B) for < K, and the final statement by the choice of hyperparameters.
Using Lemma E.20 and that 2 O, we obtain with probability at least & that
12
3B
(89)
32
Now recall that 1aSK = 1-- is B 1 measurable, which implics
E c
as the stochastic gradient oracle is unbiased. Furthermore, recall | s 01 (wo) for k S K, and projection matrices do not increase norm. Thus by the vecto--artinggle Concentration Inequality Theorem C.I, with probability at least 1 12a we have
, A=1
Σ
+ (15K)) k=1
s 120or
Kg log
48
S
B
(90)
16
Thus taking a Union Bound over the events implying (89), (89) and combining with the earlier display (88), with probability at least
n. we have
Σ K=
VGs +Vs((*)) 2 1 =01
=011 3B
16
Thus with probability least if exits B(x B) in Kn iterations (that is, if we have Ko K.), we have
17
K-1
Σ
(v')("") +V+((+*))) 1 1x=-
x11
3B
B
3B
16
16
K-O
and so
Σ VGsss (1')| + [
1
Σ
(VGs: + vGs(}*))
7
"
2n/
k-0
k-0
k-0
1
3B
2
169B²
169B²
2
2n
16
512M
512nKu
In the first step above used the elementary inequality Inequality. This proves Lemma E.25.
|
11=11aa:1 2 and Young's
We now combine Lemma E.24, Lemma E.25 to prove Lemma E.2. First recall by Lemma E.24, with probability p/4, we have
K (b=
3
1
B²
F(z*) <F(x*)) -
Σ
(VGs
)) +
256
80
nKo
h-1
7n
K-1
Σ
VGsi (o*) 1|²
25n
K--1
Σ
(91)
8
32
R=0
We first control E (vGs (v - 1, )h) by concentration. For all & from to Ko. note
B[n(vGs (1* 1exx|
because 1s 1-11K all terms in 7 V (x 1), 1) 5+) kaxc except & are - -eeasuruarrrlle. Furthermore, by Lemma E.23 and Lemma 18, for all l < K,, we have
11m0:
|n(VGS. (0 (.-1)),E))aoo
2
83

---

and
E [n JAsK) 1188-11 (wo)) vGs. (u*))l?
Taking 3log( Ko)
in the Data-Dependent Bernstein Inequality Theorem C.2, we obtain with probability least
nVVGs 1.(t)
Kg
Σ
TVGs (o(-)))())
(3log(Ko)) . (wo)
(3log(Ko)
max 1lno (wo)² (wo) log
VG (v*) log
p
k=0
(92)
We upper bound each of these terms in the maximum. With our choice of parameters and one application of AM-GM, we have
3log (Ko)
B
1lno (wo)² log
100m
and
41 02
K-1 Σ k-0
VGsi (v²) log
3log (g)
32 log
3 log Kn)
170 10,1
K-1
Σ
VGs (v+))2
p
P
8 k-0
B
K-1
17
Σ
Ko
k-n
Consequently the second upper bound dominates the maximum from (92). Substituting the above into (92), with probability at least 3' we obtain
B
K-1 VGs (w+))²
(VGs (o )
Σ
32nKo
Combining with (91), we obtain with probability at least
Tp that
F(x*)) - s
B
3n
Σ VGs (0*)
3n K-1
Σ
(
256 +
80
32
K
4
Taking a Union Bound with the event from Lemma E.25, we obtain with probability at least 3p. * moves out of the ball B(x", BB) within Ko iterations (i.e. K. = Ko S Ko). then
3 169
3
B²
B2
F(x F(x)= F(x*) F(x")
512
256
80
32
K
7n
This proves Lemma E.2 in Case Combining Case and Case 2, we obtain Lemma E.2.
E.6 Finding Second Order Stationary Points
Here, we finish the proof by showing with high probability, the algorithm does not escape B(x", B) in Ko iterates, then the average of the K2 iterates is a SOSP. In particular, aim to prove Lemma E. Here where Lemma E. 1.12 is used. the following, we define gh as in (71). Furthermore, note the proofs of Lemma 17 and Lemma E.18 still go through under the conditions of Lemma E. 1, may apply those Lemmas in our proof here.
Proof. We adopt the proof strategy of Fang et al. (2019) in similar way as we have thus far.
84

---

By Lemma E.12, with probability 1-3 (namely if the event (66) from Lemma E. occurs), then if A F s -d2, x will move out of the ball [Bx² B) within Ku iterations. By taking the contrapositive, out of the ball BBx=, B) in Kg iterations, then XMN (xx=))((==)) 2 -Ô2- In this case, have x² B(x", B) for all 1 k Ku, B(x", B). Thus by Lemma E.8 and as I E (F.F(()))>
that with probability 1 5. if x does not move
AMIN
A (v² AMIN (V²
(w -2
x -d2 (2(w)) B 117,
where the final inequality follows from our choice of parameters. That is, with probability if w does not move of the ball [B(x", B) in Kn iterations, then AMIN ( (V²F(x)
3.
- -170.
To complete the proof and show T is SOSP, we will show that | [T)) is small. To this 5*il using concentration. In deriving this bound do nor in its first Ky iterations. Consider
end, upper bound Ko
2k=1 1
yet suppose that x does not move out of B(x", B)
Ko 5
Kg Σ
5hhh 11-1
As 14-1<Ko is 1 -measurable,
E[S lesK 10
Furthermore by Lemma E.18, for $ Ko we have
| 1sskol $ sol(wo)
Thus the Dector-Martingge Concentration Inequality Theorem C.I gives with probability least - 2pp/3 that
1
20 (wo) Ko (6/p)/))
Σ
kssig
S
s Lz
(93)
Kg
K₂
The last inequality follows from our choice of parameters.
Now conditioning on the above event implying (93) which occurs with probability at least 2p/3, suppose x does not
out of the ball TB=",, B) in Ko iterations. Then have Ko > Ko. and so from (93), we have
1
Ko
1
Ko
Σ
E
Σ
5*h
1
$ (12(wo) B²
Ko
Ko
Furthermore, if x does not move out of the ball B(x", B) in Kú iterations, then we have I E We find an upper bound |VF(T) We again consider the quadratic approximation G(z) at x defined in Subsection E.5, and follow the notation from there. Noting G(.) is quadratic and so its gradient is linear map, we obtain
1 Kg-1
|G(z)
Σ
VG(**)
Kg
k-O
<
1
Ky-1
FF(*
1
Kg-1
Σ V -vF())
Kg
K2
R=U
k=
1
Ko-1
x
Σ
5h
1 Ko-1
Σ vG(x*) - (G(=t)-v((at)
Kon
Ko
k=1
k=u
B
1
L2(wo)
<
+
Σ
Kn
Kon
Ko
Kn
2
k=1
16
<
T
(w2 B2
Σ
ch
C1
2
Ko
A-1
85

---

Here we used the choice of parameters, that x² E B(x", B) for all 0 s k Ko combined with Lemma E.17 and that x & F((o)))) and Triangle Inequality repeatedly.
Note because x² (FF)(w)) and as I B(x", B), by Lemma E.17, the above implies
VFF())] s [VG L2(w)) B² (w)) B
1 Ko
(1L)
2
Consequently, with probability least 1-2p/3, x* does not move out of the ball B(x", , B)
within Ko iterations, then
[vF 5 18L)
Taking Union Bound, it follows that with probability at least 1 p. xt does not escape B(x", B) within the first Ko iterations, we have both
[VF(x) < (8L) (.AA(((2F(()) 2 -176.
This proves Lemma E.I.
F
Examples
F1
Phase Retrieval
By Theorem 3.4 and Theorem 3.5, suffices to show that 1) Fpr satisfies Assumption 1.2 and 2) Fpr is strict saddle problem (that is, all SOSPs are near-optima in suitable sense). In the rest of this subsection, denote For by F for short. As shown in Candes al. (2015); De et al. (2022), Section 2.3 and Lemma 16 part respectively, direct calculation shows F(w) takes the form
F(w)= w (I (w")
4 (1/ll 11)
2
(94)
As |w") 1, we have (ww)= 2 O. Furthermore, we have inf wER= F(w) 0. attained for example at w +w" Also note for any fixed w, is absolutely continuous on a compact neighborhood w.
F satisfies Assumption 1.2: By De Sa et al. (2022), Lemma 20, have that (2 s p1 (F(wW)
for (1:)== 9// + 10. It remains to show that
[V' sp(
for some increasing, non-negative p2, where | (r))(w) refers to operator norm of the third order tensor. Equivalently, we will show that for any w and any unit vector u, we have
F2 + 8u) - v"F(w)
lim
op S (2(F)w)).
1/|
As shown in the proof of Lemma 20, De Sa et al. (2022), we obtain from direct calculation that =1 21 2(w" (w ) 3( ww| 1)1 6ww
V²F(w)=23
(95)
Thus, by repeatedly applying Triangle Inequality and Lemma A.3 and as ||z=|| = 1,
F(w 5u) 2 F(w) llop
= =|/3(1w deil | 2) P)I+ + 6(w Su)(w - Su) - 6ww ||
s <3llw dull
|wll (I|w Jel (|w])
6l sw)(w + ōu)T w w + ōu)J w(w 5u) ww llop
< 36| (//12(2))))))) (2|w] + +) + 6 6(1lvm(w ou) ((() "1on)
86

---

s 6 6) + 6 w óull 66/
8 (18) w| + 95).
Here, we used the inequality -| yl [2 1ll- Consequently,
+ ōu)
v2 F2F
lim 6
< lim 18|w| 96 s 18| + 1.
51|2|
6-0
By Lemma 16 part d, De Sa et al. (2022), using Jensen's 's Inequality have F(w)= 2 (|w|)² 1)?.
Note for |w| 2 2, this implies
18| 1 18([w] (1ww) -1)² 18F(w).
Combining with the case |w| 2, we obtain
|| F ōu) F
lim
18 18| + +1s 18F(w) 37,
so we can just take p2(2) 18x 37.
Next, we check that F is a strict saddle problem: We check this here. Similar results, in slightly
different of setting where solve phase retrieval from samples from data, shown in Sun et al. (2018).
Suppose [[F 8 for 8 s (1)) Note by Lemma 16 part b, De Sa et al. (2022), (w", VF(w)) 3(lw] 2 (w, w") By Cauchy-Schwartz and recalling w" is unit vector, this gives
8 w " [FF(() (w", VF(w)) 3| w|| 1 kw, (tt,w")) w
(96)
Suppose (ww, w')l 2 V5. Combining this with (96) gives
v 3
| 1 - 1/5
By Lemma 16 part c, De Sa et al. (2022),
[VF(w)] 1 2 F(w) 8(1 8((w]] (w, wn 1²)
= (12|w| 2 F(w) 6( 6(1w] 1)²
where the last equality follows from the explicit form F(w) from (94). Thus using |w]l
3 we obtain
8² 2 [VF (12|w| F(w) ([[w[[]] 2
1)2 2
(4-
For 8 J, this gives
82
82
F(w) S
4V8 S
2
Otherwise, suppose (ww w²)l V0. Note by differentiating (94), shown in the proof of Lemma 16 part b, De Sa et al. (2022),
F(ww) 2w 2(w, w" 'o""" 3(|w]] 1)w -2(w,, w 'wo" + (3][w]] w.
Thus by Triangle Inequality.
/ 2 - 1/- ||w| s (VF(ww) 2 w" ">>"""""" o 208 440.
Consequently either ||l||| < 28//1 or 3 |||l 1 < 281/1
87

---

In the first case, by Cauchy Schwartz and (95), notice for any unit vector u that
u'v w'v2F(w)u u' 21 2( (w ) 3( 3(wl 2 1)I Gurw") ]u
s-lul² =3/2/²² (281/4²2 61|zu|2 (26114)
9
5 -- +3666/2222 < 10
since 85 & (20) In the second case, using (95), notice as ||w" || 1, we have
w 42 F(w)ww wn (3/ w 1)w" 2| 12 6(( w'
9
2 2 60 s
5
Consequently in either case, 22 F(w) has at least one negative eigenvalue with value at 9
most
T0
Consider smaller than universal constant, and take d ve in the above result. It follows from the analysis here that if we find an SOSP to tolerance e as per the definition (2), we obtain w with F(w) S 5-
Thus, it follows that running Perturbed GD or Restarted SGD as described in Theorem 3.4 or Theorem 3.5 respectively, will obtain with suboptimality F(w) s c, where the number of oracle calls depends on 1/e, d, F(wo) in the same way as in Theorem 3.4 or Theorem 3.5 respectively.
F.2 Matrix PCA
Again by Theorem 3.4, Theorem 3.5, it suffices to show that 1) Fpca satisfies Assumption 1.2 and 2) is a strict saddle problem (that is, all SOSPs are near-optima in suitable sense). We will show this, with the parameters governing the strict saddle property depending on the spectral gap A (M) -22 (M). !2 In the rest of this subsection, denote Fpea by for short. Recall the loss function for PCA takes the form
F(w)= | |ww M pr
where M is a symmetric PD matrix. Note for any fixed w, F is absolutely continuous on a compact neighborhood of w. Note F (w) 2 0 always holds. While it is not true that inf weRe F(w) 0, to enforce this, we can consider the shifted function := F inf wasd F(w). The derivatives of G are identical to those of F, and furthermore G(x) Ggy) F(x) F(y) for all x. y- Thus to apply Theorem 3.4, Theorem 3.5 and show that Perturbed GD or Restarted SGD can globally optimize G and therefore F by finding SOSPs, remains to show F satisfies Assumption 1.2 and is strict saddle.
F satisfies Assumption 1.2: Direct calculation, also in Jin al. (2021a), yields
v F (w) (ww M M)W, 2 F(w) = || 2 2ww - M.
(97)
We now check self- huff-bounding regularity for the Hessian and third order derivative tensor. First observe
w (ww') )w- = |
Combining with Lemma A.3, we obtain
|w| ww [//2
1/2
wwww T
- llop
|| 1lop
www
M 1/2 + |M
11
$ 2F(ww 1/4 M 1/2
op
(98)
Thuus our result will be vacuous when the spectral gap 0.
88

---

Now we check the self bounding conditions. For the Hessian, note from (97) and (98) and using Lemma A.3, F<) op s ///w|² || op
33(2F
|| 1/ + MM
Thus we can take pi (z) = 3(2x 1/4 |
y/
M
op
For the third order derivative tensor, following the strategy in Subsection F.I, we will show that for any w and any unit vector u, we have
v f( bu) FFF(w)
lim 8-00
pP((Fww))
81124|
Applying (97) and Lemma A.3 and note
(w + ōu) (w + ou)² www T (w ( 5u) - (w + bu)w' + (w + +du)w' ww
(w (o4)) Suw"
This gives
2 F(w + 6u) - 22 ((2)(w)l..
lim
6-0
8 u
(l/w 8ul
|w] 3)
2 2 (w 6u) www"
1lop
lim
8 u
||w + 8u
|
(2) [i
8 +6
( 8(u))
lim 6-+0
+ 8|/u/)) ) + 5 |u| (2) w/ +
lim
6-0
lim 4|w>|| + 2/||
8-0
4 4||w]
$ &FF(w) 1/1 + ||| op
Here we used the inequality || + y ||-|||| s |y/|- The last step used (98). Thus we can take 1/2
p2(x) = 1/4 +||M op
Next, we check F is strict saddle problem: We check this here. A similar verification is done in Ge et al. (2017).
Let U be the (unit) eigenvectors of M corresponding to (1 (2) 2... Aa
0 respectively (recall M is assumed to be PD). Thus the v; form an orthonormal basis of IR Furthermore for convenience let A; As(M) for all 1 isis d. As M is symmetric and PD, by the Spectral Theorem, we can write
d M Aoaoak
Suppose a SOSP tolerance E for E min 1,
(A1- ()1 - (11-12)887) )2)8/23 Note the minimizers
16
of F are = We will show that w close to these minimizers: in particular, that min ||u VAr
2 w Vhrei| |²] sc.
Write w C1U1 + +.. CaUss Thus, our goal is to show that +.... +23) >11 < /s. By (97), we have
+c)))
d [(( + .... c3) 21)
E [2F() = Mw - || [w/3w| =
1=1
That is, have
d Σ
2 ( +gg) 21)² 562
(99)
1=1
89

---

Furthermore by (97), we have
d
V'F(w)= =
(c. (((w))(({++))) 2 + aeSD,o)
Σ \vv
[=1
Since w is a SOSP, for all UR. 1 5 S d, we have
-VE Vesuj F()) = (c) + ... c 2 AR-
(100)
We now break into cases:
Suppose for all i, we have (C} + Taking k= = in (100), we obtain
cg) X11 VE. From (99), this gives Σ of e.
Σ v
c X1 S - A1 = S
contradicting that << min (1, A
Else, suppose there exists i such that taking & = 1 in (100), we obtain
(ee (.+ 27) - X1| < VE. Suppose that i 2 2. Then
o7 11 A
VE2 \1 - 22
-VES VE+ 201 d1
4
where the last inequality uses A S 22 and < 1 )²
Note furthermore that as E 2 (مددد as (c/ +... + e4) - Xol Vs, and as A S d2 < A1.
we have (c] + ... 2 - X1| 3(A1-12)
Thus (99) implies
4
\1 A2
$² 0+
(A1 -22
contradicting that E (A1 5/2
Therefore, we must have = 1 in the second case above. That is, [(e + +...+ +.)) ->il < ve, as desired.
Thus, it follows that rumning Perturbed GD or Restarted SGD as described in Theorem 3.4 or Theo- rem 3.5 respectively, we will obtain w that is distance at most /E from global minimizer of F for
8 << min 1, (1)- 16 (A1 - >/23/ Here the number oracle calls depends on 1/e, d, F(w,) the
same way as Theorem 3.4 or Theorem 3.5 respectively. For E 2 min min(1, (A1- (A1 - X₂) )3)3
16
can replace by any real strictly smaller than min 1, (A1-Aa)² 3 [(1 222 in the guarantees from Theorem 3.4 or Theorem 3.5.
16
G Simulations
Our algorithmic results Theorem 3.1, Theorem 3.2, Theorem 3.3, Theorem 3.4, and Theorem 3.5 have strong practical implications. They directly suggest that under generalized smoothness, the step sizes y that lead to convergence/successful optimization become smaller for larger initialization F(wo) and larger self-bounding functions p2()) For example in Theorem 3.1, we set 17 T. (woo where T, (wo) = max (1, Po (F( (F(w)) 1), Po (F(wo))Po( (FF())))))))))))) + 1), (F(w)) 1)) was defined in (4).
That is, our work suggests that larger suboptimality at initialization and larger self-bounding functions shrink the 'window' for choosing a working in practice, when the loss function satisfies generalized smoothness. This has strong practical implications: it implies that for losses with non-Lipschitz gradient/Hessian, one should tune 7 based on suboptimality at initialization. This contrasts sharply with the Lipschitz gradient/Hessian case, see e.g. (Bubeck et al., 2015; Jin et al., 2017; Fang et al., 2019), where the range of working 7) is fixed in terms of the Lipschitz constant of the gradient and/or Hessian, and does not depend on the initialization.
In this section, we empirically validate this implication of our work.
90

---

G.1 Synthetic Simulations with GD
Simulation Details: We consider F(w) = |Aw] for = 2,3,4,5,6, where A 30: 1,, When p= 2, F(w) is smooth. When p 3, F(w) is not smooth, but is straightforward to verify that it satisfies Assumption 1.1, similar our verifications in Subsec- tion A.2. One can furthermore verify that as increases, the corresponding self- celf-bounding function pi(.) from Assumption 1.1 increase. This choice of generalized smooth function was motivated by Gaash et al. (2025), who used Aw witt the exact same their experiments to study optimization with first-order methods under generalized smoothness.
diag( 1
For each p= 2,3. 3, 4, 5, 6, we consider the following settings for GD:
Step sizes: We consider 30 step sizes (1)) (m E=1 / < 1/30 evenly spaced on a log scale between 10-s and 10², inclusive.
Initialization: For each step size ni, we initialize GD 4 distributions x, N NO,O c2 for Cj (2.5, 5, 7.5, 10). For each of these 4 distributions nj we draw 100 points Wo x to use as our initialization.
Number of steps: For each 7/2 and each Wo ~ Ty, we run GD initialized at wo with step size 7) for T = 1000 iterations. Here as F is known, we analytically compute the gradient.
For each p and initialization πj consider all 30 possible 7). which plot on the æ-axis. For each 1/s, we consider all 100 initializations Wo ~ T.. For each initialization Wo, letting (w.} be the resulting sequence of iterates of GI, we compute [V#())) for T 1000. For yy: that led to faithful F(wo)
convergence of GD, on the y-axis, we then plot the mean of [V over those 100 initializations F(wo)
as a blue dot, with blue vertical error bars indicating +2 standard deviations. We considered the ratio [[ because for L-soooth functions, established optimization theory predicts that this F(wo)
converges at a rate independent of F(wo) and only depending on and L (Bubeck et al., 2015).
The simulations for Subsection G.1 were run Jupyter notebook in Python in Google Colab Pro, connected to a single NVIDIA T4 GPU. Our code can be found in the attached files.
Divergence of GD and working step sizes: We observe that for some πu larger than some threshold depending on p and Ty. the iterates of GD diverge. In particular, the resulting ratio [VF(w))] becomes F(w.) massive, often on the order of 10t or more, indicating that N was too large for GD to converge. To identify the smallest 77 where this first occurs, or equivalently find the largest working step size among {T) ( for a given Ty and IJ, we computed the average F(wp)
[VF(W))) over the 100 initializations.
If this average was 100 or more times larger than this average for 77-1, we took this as an indication that the iterates of GD with this step size 7); or larger step sizes diverge, and for this p and Ty. we stopped considering any larger mp > i. We then save this 7): to indicate the smallest f). for which divergence occurred. This 7/i is indicated with a red line in the following plots.
This smallest n, for which divergence occurred plays crucial role in validating our theoretical claims. Established optimization theory predicts that for smooth functions (here, when = 2), this 7/s is identical across different initializations (Bubeck et al., 2015). Meanwhile for generalized smooth functions, as per our remarks earlier and from Subsection 3.6, we predict that as F (ww) increases, the range of working step sizes, and consequently also the smallest 7); for which divergence occurs, will decrease. Note cj increases (recall πу (O, 2,, and сj {2.5, 5, 7.5, 10)), we expect F(wo) to increase, at least on average or with high probability over the 100 initializations Wo Tz-
Results: Our simulations validate this theory very accurately. Note in the following figures that the y-axis is normalized, as we plot [V(())) where T = 1000. Thus larger oj lead to comparable values on the y-axis.
F(we)
When 2: In Figure 1, we plot the results in the manner described above for all 4 initializations J.. As is predicted by established optimization theory for smooth functions (Bubeck et al., 2015), the first step size leading to divergence 7); is identical across all the тy.
When p= 3, 4,5, 4,5,0 6: We plot the results in the manner described above for all initializations Ty in Figure 2, Figure 3, Figure 4, Figure 5 respectively. Unlike the p 2 case, in all of
91

---

Meen +52 5D
Mean +/2 5D
Diverged 17
Diverged at at 1.1e000000
(a) JTy 20, The first divergence is 1.17.
(b) ς; =, 5.0....Z.).. The first divergence
?) 1.17.
Moan +12
Moan +/2 5D
Diverged 0=1177700
Diverged 1117e000
(c) T, = (O. The divergence at R 1.17.
(d) m. = (O, 10lzo). first divergence at ?i = 1.17.
Figure I: GD simulation results for p For all Tj. the smallest Ni leading divergence 1.17.
these cases, the first step size leading to divergence πι generally decreases as the covariance T0 π increases from 2.5 10.
We also notice the following, both line with our thcoretical claims:
For given p, consider how this first step size leading to divergence decreases as the covariance 20 of πy increases from 2.5 10. We find that the rate of this decrease increases increases. The ratio of the first π leading to divergence for лi vs is approximately 4.18, 4. 4.18, 17.43 for p 3, 4, 5, 6 respectively.
As remarked earlier, for larger p. the corresponding self- hofndinnning function p1 (-) is larger for F(w)= ||wl|| (see Subsection A.2 for a similar verification). Thus this behavior is consistent with our results, as the step size from all of our results depends on ((ww) through (-)...
Fixing i and comparing across p. we see that the first step size leading divergence 7) decreases increases. Again this is not surprise considering our theoretical results, as for larger p. both F(wo) for Wy ny and the self-bounding function p1 (-) become larger.
For each p (2,3, 4, 5, 6} and Ty, we also record the smallest 77; for which divergence occurred in Table 1 on page 92, which highlights the aforementioned trends.
R, = (Ō,
7y= -10,(00
n, =0, 7.5I
= 107
p=
1.17 10
1.17 10
1.17- 10
1.17 10
P=3
2,81 10-1
1.37 10
-
6.72-10--
p= 4
3.29 10
3.29 10
1.61 10-2
7.88 10-3
p=5
7.88 10-3
3.86 10-3
9.24 10
9.24 10-4
p=
9.24- 10
4.52 10
5.30 10
5.30 10-5
Table 1: The smallest 7, leading to divergence for a given p and initialization Tj.
92

---

Moan
Moan Diverged 3t.0-137--01
Diverged (.022.81000
301
(a)
The first divergence is at
(b) πy -O, 2.). The first divergence is at 0.137.
0.281.
Diverged at (-.1-337
Diverged at 6-7.2
(c) T, = (O 20). The first divergence is at 0.137.
(d) = NÓ, 104 The first divergence is at 7) 0.0672.
Figure 2: GD simulation results for For Formy 2..5. 20), the first divergence is at % 0.281. For π -Ó 20 , ,W 2.), the first divergence is at 77s 0.137. For πy N(00, 10 20), the first divergence is at 77 0.0672.
+/2
+/2
Diverged qu: 29
Diverged at ga 2-
(a) TT 2.) 3.29 10
The first divergence is
(b) π. =,, 2.). The first divergence is 3.29 10
Mean
Moan 1/22 SD
1/2 5D
Divanged
Divenged
(c) π. = =Ō 7.5I20). The first divergence is at 1.61 10
(d) π. = (O 10I2o). The first divergence is at 7.88 10-3
Figure 3: GD simulation results for p 4. For Ty (05 5I20), the first divergence at 7i 3.29 10-2 For ny A/ 2.) the first divergence is at 7 1.61 10-2, For T = NO, 10 20). the first divergence at 77, R 7.88 10-3
93

---

Heon
Meen +/2 5D
The first divergence is at +/2 5D
Diverged 1.000--0
Diverged 2-3.06---
(a) T 20 The first divergence is at 7
(b) T. -N 20). 7): 3.86 10-3
The first divergence at
7.88 10-3
+32
Diverged st (-0 2.0.244
Diverged at 9-2.44
(c) T, = =O, 2.5 The first divergence is at 7. = 9.21 10"4.
(d) n2 = NÓ, 10420). 7i = 9 10
Figure 4: GD simulation results for p == 5. For T, = ((, 2.5. the first divergence is at 7.88 - 10-3, For Ti = NO, 20), the first divergence is at m s 3.86 10-3, For my (Ū (O 20), the first divergence is at 17, 2 9.24 224-10-4. 10-4.
Meen
Nean +/2 5o
+,22 5D
Diverged 92220000
Diverged 52m-D4
(a) TT 20.) The first divergence is at 9.21-
(b) n. =, 2.0l
The first divergence at
7) 4.52-100
+/2
+/2
Diverged n- 35
Divenged qu5 30e-05
(c) T, = (O, 2.) The first divergence is at
(d) n, = (Ó, 10/2v) The first divergence is at Mi x 5.30 10
yy s 5.30 10
Figure 5: GD simulation results for p = 6. For n, = NO 2.5 the first divergence is at M # 9.24 - 10- For Fj = (ō, 20)), the first divergence is at nu s 4.52 10"4, For Ny 20), (0, the first divergence is at m, x 5.30 10-5
(Ó 20) (Ó,
94

---

G.2 Synthetic Simulations with SGD
Simulation Details: We adopt the exact same settings as in Subsection G.I. The only difference that we study SGD rather than GD, and hence simulate stochastic gradients. We do similarly to Gaash et al. (2025): artificially add .N( (O, 0.01 to VF at each iteration of SGD. 13 The simulations for Subsection G.2 were again run on a Jupyter notebook in Python in Google Colab Pro, connected single NVIDIA T4 GPU. Our code is in the attached files.
Results: Our conclusions are similar to those from Subsection G.I. When = 2, as predicted by established optimization theory for smooth functions, the first step size leading divergence 7) is identical across the Ty (see Figure 6). In contrast for 3, 4, 5, 6, this generally decreases as the covariance 2y120 of iT increases from 2.5 to 10 (see Figure 7, Figure 8, Figure 9, Figure 10). We note that while the general trends are similar to those from Subsection G.I, we can clearly see the presence of the stochastic gradients in these plots. In many of these plots, [VF(wr]] becomes roughly constant F(wo)
for 1j large enough such that T 1000 yields reasonable convergence; for such v), by T 1000, the true gradients are small enough and the noise from the stochastic gradients takes over.
Once more, consider how the first step size leading to divergence тy: decreases as the covariance 22/20 of тj increases from 2.5 to 10. We find that the rate of this decrease generally increases as p increases. We also again that fixing и and comparing across p, the first step size leading to divergence decreases as increases. As discussed in Subsection G.I, both of these phenomena are consistent with our theoretical results. For each p (2,3, 4, 5, 6} and TT, we again record the smallest 77, for which divergence occurred in Table 2 on page 95.
Jj = 2,,
TT (0,
= (0,
N 101
p 2
1.17-10
1.17-
1.17- 10
1.17 10
= 3
2.81 10-1
1.37 10
6.72- 10
1.37 10
p=
3.29 10
3.29 10-2
1.61 10-2
7.88 10-3
p=5
7.88 10-3
1.89 10-3
9.24 10
4.52 10-4
P=6
4.52- 10-4
4.52 10-4
1.08 10-4
5.30 10-5
Table 2: Smallest 17, leading divergence for given p and initialization TT.-
Note result for convergence of SGD FOSPs, Theorem 3.3, applies for Gaussian noise per Remark 7.
95

---

+/2
4/5
Moan Diverged g-1 17
Diverged at 1. 17e400
(a) JT 2.5
The first divergence is
(b) ςΙ -O 5.0.o.....). The first divergence is 7) 1.17.
7 1.17.
+/2
+/2 5D
Diverged at ge1.7770000
Diverged at 1e
(c) JT (Ō, 2.5 The first divergence is 7) a 1.17.
(d) π. (V,010022)
10/2)).
The first divergence is
?) = 1.17.
Figure 6: SGD simulation results for 2. For all ny. the smallest leading to divergence is 1.17.
Moan
Diverged at 30.22.811
Diverged st.0=1377
207
32*
15"
(a) (O, 2.5. The first divergence is at
(b) T. 0.1.7.
-O 2.. The first divergence is at
0.281.
17-2 SD Diverged at 1.37-01
Diverged at 72
(c) T, (O, 2.). The first divergence is at Vk 6.72. 1
(d) प. N' 10/ The first divergence is ?i 0.737.
Figure SGD simulation results for p = 3. For T. = (.5l the first divergence is at x 0.281. For TΙ NO, 2.5 the first divergence is at x 6.72 10 10 For the other Tj, the first divergence is at 1 0.137.
96

---

Moan Diverged 20.g=2.20..2
Moan Diverged st.0=3.23c.0
25*
(a) Jj (0, 2o) The first divergence is at 3.29. 10
(b) πy -N 20) The first divergence is at
7
7) 3.29. 10
+12
+/2 5D
Diverged 0-1.61e 02
Diverged st 0- 03
(c) πT (O, 2.) The first divergence is = 1.61 10
(d) π. N(O, 10/ 7.88 10 10-
The first divergence is
Figure 8: SGD simulation results for p 4. For = N/ (O, 2.5l WN 2.). the first divergence is at 3.29 10 For πj (O, 20), the first divergence is at 7 1.61 10 For T N(, 10Izo), the first divergence 7/s 7.88 10-3
1/-2 SD
11-2 SD
Diverged 2. 7.88e-03
Diverged 1.
(a) Ty (O, 2.5. The first divergence is 7.88. 10-3
(b) ... A 20. The first divergence is 1 10-3.
Moan
Mean +/2 Diverged n-4
Diverged 040.
(c) TT = (O, 7.5 2. The first divergence is at
(d) m. (Ó, 10 The first divergence is at ?it 1.52 10
7). 9.21 10
for 10 the first divergence is at 7 7,88 10-3 1.89 10- 9.244 - 4.52. 10-4 respectively.
Figure 9:
SGD simulation results
5. For z
(O 2.5I (1. 20)
3,924
97

---

1+2.50
Diverged at.nw4.5a 64
Diverged q=4 $2e
(a) TT 2..50.) The first divergence is at
(b) πÿ - (O 5.0 The first divergence is at
77. 4.52 10"4.
?i R 1.52-10"
Mean +12 so
Mean
+/2 5D
Diverged
(c) T. -O. 7.5I20). The first divergence at 1.08 10
(d) T. (Ō 10 The first divergence at 5
results for (O, 2.51 2o. 2.5 (0, 10)))). the first
Figure 10:
SGD simulation
For T divergence are at
! 4.52 10-4,
444.2 10 1.08 10-4, 5..30 10-5 respectively.
98


Reviews:
[{"review_id": "1yf6IlS6vY", "reviewer": "Reviewer_LCyX", "summary": "This purely theoretical paper addresses the problem of finding first- and second-order stationary points (FOSP and SOSP) using first-order optimization methods under weak regularity assumptions: second and third order self-bounding regularity. To that end, a decrease procedure is introduced showing when first order methods decrease the value function, leading to convergence guarantees. It is shown that many common first order algorithms (GD, Adaptive GD, SGD, Perturbed GD and Restarted SGD) are covered by the framework and be analyzed accordingly.", "questions": "- How common are the self-bounding regularity conditions in modern ML, eg in deep learning? \n- You notice that the choice of the step size \\eta should depend on suboptimality at initialization, how sensitive is the method in practice ?", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The problem seems important for the ML community, especially for non-convex optimziation\n- Authors provide a thorough and unified convergence analysis for a wide variety of first-order algorithms\n- The high level introduction of the decreasing procedure is clear and very helpful, improving the paper's readability.\n\nWeaknesses\n\n- Experimental results could have been introduced in the main paper, even briefly.\n- Generality of the self-bounding regularity is not extensively discussed, it is a generalization of (L_0, l_1)-smoothness but are there many known functions satisfying self-bounding regularity and not (L_0, L_1)-smoothness? How frequently do such functions arise in deep learning?", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer, we thank you for your review and comments. We sincerely appreciate your supportive review, thoughtful questions, and belief that we are solving an important problem in machine learning and that we “provide a thorough and unified convergence analysis for a wide variety of first-order algorithms”. We will be sure to add further discussion on our experiments/simulations in our manuscript as you suggested.\n\nWe would just like to respond to the questions and weaknesses you raised as follows. All the sources here are the same as in our manuscript.\n\n**Generality of self-bounding regularity:** This is a good question, and we thank the reviewer for raising it. As discussed in Section 1.1 (see Proposition A.1), second-order self-bounding regularity is strictly **more general than** the $(L_0, L_1)$-smooth conditions which arise frequently in machine learning. \n\n-The $(L_0, L_1)$ smoothness condition arises frequently in machine learning, and therefore by the following discussion, self-bounding regularity arises in the exact same situations as well. Namely $(L_0, L_1)$ smoothness was experimentally shown to hold for LSTMs in Zhang 2019 et al and transformers in Crawshaw et al 2022, and has been subject to extensive study in recent years as a more realistic set of regularity assumptions for optimization in machine learning. \n\n-We demonstrate in Proposition A.1 that $(L_0, L_1)$-smoothness **implies** self-bounding regularity with $\\rho_1(x) = \\frac32 L_0 + 4 L_1^2 x$. Li et al. 2023a generalized $(L_0, L_1)$-smoothness and once more, our self-bounding regularity conditions subsumes the condition of Li et al 2023a; see our Proposition A.1. We also demonstrate in Example 1 that there are natural univariate functions which do not satisfy $(L_0, L_1)$ smoothness and do not satisfy the condition of Li et al 2023a, but do satisfy self-bounding regularity.\n\nThus we believe self-bounding regularity is quite general and arises frequently in modern machine learning. Moreover, there is growing evidence that conditions analogous to self-bounding regularity imposing quantitative control of the Hessian in terms of gradient or function value are necessary for optimization to succeed via first-order methods (even for finding stationary points). Namely, see Kornowski et al 2024 Theorem 2.1 and De Sa et al 2022 Theorem 3. That said, we emphasize that we work with self-bounding regularity not just because it is more general than $(L_0, L_1)$ smoothness, but because we believe it is a more natural way of analyzing ubiquitous first-order optimization algorithms under generalizations of smoothness.\n\nFor third-order self-bounding regularity, we demonstrate several theoretical examples in optimization for machine learning, namely phase retrieval and matrix PCA, satisfy this condition and also satisfy second-order self-bounding regularity. We also demonstrate in Example 2 that this condition covers several natural growth rates of interest. Moreover, Xie et al 2024 very interestingly demonstrates that under mild assumptions, the objective of Distributionally Robust Optimization (DRO) satisfies their Assumption 3 (see Theorem 3 in their paper), which is subsumed by our third-order self-bounding regularity condition as per our Example 2. Thus our results apply to DRO. DRO is a general optimization problem that has significant applications in fairness in machine learning and in learning under distribution shifts; see Xie et al 2024 for more discussion. We will be sure to add this discussion to our manuscript.\n\n**Dependence on initialization:** It is true that the step size will depend on initialization. This holds true also for many works studying optimization with GD and SGD under generalizations of smoothness, such as Li et al 2023a. We also note that the step size provided is an upper bound on possible working step sizes. Thus, one can find a working step size with cross validation in the learning setting. We will add this point to our manuscript at the reviewer’s suggestion.\n\nIn fact, this dependence on initialization carries important practical implications, as we describe in Section 3.6 and detail fully in our experiments/simulations in Section 9. There, we empirically verify that when optimizing natural generalized smooth functions with GD and SGD, the larger the loss $F(w_0)$ is at initialization, the smaller the largest working step size is (in contrast to optimizing smooth functions). These results show that the dependence on initialization via $\\rho_1(F(w_0))$ in the range of working step sizes from our theorems matches behavior in practice. Thus our experiments/simulations validate the practical implications of our theoretical results on which step sizes successfully optimize generalized smooth functions.\n\nPlease let us know if you have further questions; we are very open to discussion. Thank you again for your time and feedback!"}, {"review_id": "6WxQweqw2v", "reviewer": "Reviewer_er1q", "summary": "An open problem in ML is the development of optimisers that can provably avoid strong saddle points. The authors define a condition SOSP of the estimated optimal point, saying that the norm of the gradient at the should be less than epsilon, and the minimal eigenvalue of the Hessian should be more than -sqrt(epsilon). The paper proposes some new variants of gradient descent, adaptive gradient descent, and stochastic gradient descent, and shows that these variants, under suitable assumptions on the target function, are able to find solutions of the SOSP problem, and give complexity bounds for these solutions.", "questions": "Would it be possible to develop a truly adaptive version of the algorithm where the algorithm's steps do not depend on the parameters in Assumptions 1.1-1.2, but these only affect the convergence rates?", "limitations": "Limitations have been adequately addressed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper has some novel theoretical results for finding FOSP and SOSP about several deterministic and stochastic optimisation algorithms. Many of these bounds are sharp.\n\nWeaknesses: Assumption 1.1 of the paper on the Hessian being upper bounded by a function of function value (||Hess f(x)||<= rho_1(f(x))$ are not unreasonable, but it is unfortunate that the algorithms explicitly depends on this function rho_1 (see equation (4)).\nSince in practical ML problems, Assumption 1.1 may be difficult to verify.\nThere are no convincing numerical experiments showing the usefulness of the algorithms developed in this paper.", "was_revised": true, "final_justification": "I have increased my score based on carefully considering the rebuttal, that made me better appreciate the contributions of the paper.\nThe authors have done a significant amount of work on this paper, and obtained many interesting mathematical proofs that prove sharp convergence rates in the order of the precision parameter $\\epsilon$  for most algorithms. These results are sufficiently interesting to merit publication in NeurIPS.", "rebuttal": "Dear reviewer, we thank you for your review and comments. We sincerely appreciate your reading and feedback, your engagement with our manuscript, and the recognition of our “quite interesting theoretical results about the developed algorithms” in the work. We will be sure to take your feedback into account in the presentation of our manuscript.\n\nWe would like to respond to the weakness and question you posed as follows. We believe this response will help clarify the results of our manuscript and we hope for a productive discussion. All the sources here are the same as in our manuscript.\n\n**We first would like to clarify Assumption 1.1.** Our Assumption 1.1 is not that $||\\nabla^2 F(w)|| \\le \\rho_1(||\\nabla F(w)||)$, but rather $||\\nabla^2 F(w)|| \\le \\rho_1(F(w))$ (the difference being an upper bound in terms of function value rather than gradient), and in fact our Assumption 1.1 is **more general**. Namely, the assumption $||\\nabla^2 F(w)|| \\le \\rho_1(||\\nabla F(w)||)$ for sub-quadratic $\\rho_1(\\cdot)$ (from Li et al 2023a, generalizing Zhang et al 2020) is subsumed by our assumption, see Proposition A.1. In particular when $\\rho_1(x)=L_1 x + L_0$, the $(L_0, L_1)$-smoothness assumption pioneered in Zhang et al 2020 and followed up in many subsequent works, this implies Assumption 1.1 with $\\rho_1(x) = \\frac32 L_0 + 4 L_1^2 x$ (Proposition A.1). Moreover, there are natural univariate functions where our Assumption 1.1 holds but the $||\\nabla^2 F(w)|| \\le \\rho_1(||\\nabla F(w)||)$ condition does not hold for sub-quadratic $\\rho_1(\\cdot)$, see Example 1.\n\n**We respectfully disagree with the assessment that our algorithms are not practical in their current form.** In our results, $\\eta$ is a fixed step size which only depends on $\\rho_1(F(w_0))$, a fixed value **depending only on initialization**. Moreover, the expressions depending on $\\rho_1(F(w_0))$ are only an **upper bound** for working step sizes. We do **not** need to know these exact values. Therefore to implement our algorithms, all that is needed is an upper bound on fixed quantities such as $\\rho_1(F(w_0))$. Thus a working step size for our algorithms can be found using cross validation or binary search. We will be sure to add this discussion to our manuscript and we thank the reviewer for bringing this point up.\n\n**Furthermore as mentioned above, $(L_0, L_1)$-smoothness implies our Assumption 1.1 with $\\rho_1(x) = \\frac32 L_0 + 4 L_1^2 x$.** Thus under $(L_0, L_1)$ smoothness, it is simple to back out a range of working step sizes in terms of $L_0, L_1, F(w_0)$ for all of our Theorems. This dependence on $L_0, L_1, F(w_0)$ is similar to the dependence in the step sizes provided in Zhang et al 2020, Jin et al 2021b, Crawshaw et al 2022, Li et al 2023a, Li et al 2023b, and many other works.\n\n**On adaptivity:** Indeed as the reviewer pointed out, it would be interesting to get a completely adaptive algorithm. That said, one can interpret cross validation or binary search over $\\eta$ as adaptive algorithms in their own right. This leads to results for cross validation or binary search over $\\eta$ that are analogous to our current results, and it is relatively straightforward to make these results formal. In the learning from data setting, one can make the cross validation result formal using classic techniques. Again, we will be sure to add this point to our manuscript and we thank the reviewer for bringing this point up.\n\n**Finally, we wish to clarify the goal of our manuscript. Our goal is not to propose new algorithms. Rather, we perform a theoretical analysis of existing, practical, and widely used first-order optimization algorithms.** We systematically establish stronger theoretical results for these widely used algorithms – in particular, novel results on SOSPs – in the more realistic and challenging generalized smooth setting. Our manuscript is not focused on demonstrating the validity of new algorithms.\n\n**We note that finding SOSPs is a significant and difficult problem established in the literature for over a decade**, which carries strong theoretical and practical implications in optimization for machine learning.\nWe furthermore note that our work contains simulations. Our simulations show that the dependence on initialization via $\\rho_1(F(w_0))$ in the range of working step sizes from our theorems matches behavior on which step sizes successfully optimize generalized smooth functions in practice.\n\nPlease let us know if you have further questions; we are very open to discussion. Thank you again for your time and feedback!"}, {"review_id": "DHQAJUIKyy", "reviewer": "Reviewer_SgYJ", "summary": "This paper proposes a general framework for establishing high-probability convergence of an algorithm to a target solution set $\\mathcal{S}$ and for analyzing its oracle complexity.\nUsing this framework, the authors prove convergence of several algorithms to first-order or second-order stationary points, assuming the objective function $F$ satisfies self-bounding regularity properties, a generalization of $(L\\_0, L\\_1)$-smoothness.", "questions": "- How meaningful is the third-order self-bounding regularity? While I understand that the second-order version is related to $(L\\_0, L\\_1)$-smoothness (which is already well understood and whose relevance to applications is widely accepted in the literature) it is unclear whether the same holds for the third-order condition. Although the authors demonstrate that it holds for phase retrieval and matrix PCA, it would be helpful to provide a more general discussion regarding its practical significance.\n\n- How general is Assumption 3.1? It is clearly more general than the assumption of uniformly bounded variance, but it may be beneficial if the authors could further clarify its scope by drawing more explicit connections to prior work such as [1], devoted to relaxing assumptions on the noise.\n\n- Are there no experiments on phase retrieval or matrix PCA? If so, the last paragraph of Subsection 3.6 (lines 370–374) may be better separated from the rest of the subsection, as it gave the misleading impression that it was pointing to experimental results on those problems.\n\n[1] Gower et al., SGD: General Analysis and Improved Rates. ICML, 2019.", "limitations": "The paper does not explicitly discuss its limitations, but this seems acceptable given the theoretical nature of the work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe proposed perspective of unifying convergence proofs offers a systematic and fundamental view of how such arguments are structured, making it a valuable contribution to the literature.\nThe central question of finding first- and second-order stationary points without assuming Lipschitz continuity of the gradient or Hessian is well-motivated and clearly explained.\nGiven the fact that self-bounding regularity conditions generalize the recently popular $(L_0, L_1)$-smoothness, the main results showing convergence to SOSPs under second- and third-order self-bounding conditions seem compelling.\n\n\n**Weaknesses**\n\nThe unification comes at a cost. Section 2.2 is difficult to follow and contains formalisms that appear unnecessarily complex.\nThe precise roles and meaning of $\\mathcal{A}\\_2$ and $\\mathcal{R}$ are not clearly explained and lead to confusion (lines 156–158).\nFor instance, why not simply define $\\mathcal{A}$ as a procedure that outputs $\\mathcal{A}\\_1$ (the output with high probability decrease of $F$) and $\\mathcal{R}(\\mathcal{A}\\_2)$ (the candidate solution), given that $\\mathcal{R}$ and $\\mathcal{A}\\_2$ always appear together?\nThis would eliminate the need to repeatedly use cumbersome notation involving the set of sequences $\\cup\\_{n=0}^\\infty (\\mathbb{R}^d)^n$ in defining $\\mathcal{A}$.\nOverall, the writing and notation in this section can, and should, be significantly improved for clarity and simplicity.\n\nThere are also numerous issues with notation, typos, and minor errors in the proofs. A few examples include:\n- The notation $\\mathcal{A}(u\\_0) = (u\\_0 - \\eta \\nabla F(u\\_0)) \\times u\\_0$ is not appropriate for denoting an element of a product set and should instead be written as a tuple; the current form is confusing.\n- The definition of a decrease procedure does not clearly distinguish between randomness due to the algorithm itself and noise from sampling (e.g., for SGD and restarted SGD).\n- In line 229, is it necessary to define $\\mathcal{R}$ for sequences of any length?\n- In the proof of Theorem 2.1, using $\\mathcal{A}$ to denote an event overlaps confusingly with the notation for the algorithm.\n- Also in that proof, the authors write $\\mathcal{E}_n \\cap \\mathcal{B} \\cap \\mathcal{C}$ even though $\\mathcal{C} \\subseteq \\mathcal{B} \\subseteq \\mathcal{E}_n$, which is needlessly confusing.\n- In lines 1181 and 1182, $p\\_{n-1}$ should likely be $p\\_{n+1}$.\n- In line 1205, the first inequality appears to have an incorrect sign.\n- In line 1206, the authors presumably meant $k'=1$ is not possible so $k' \\ge 2$, as with $k'=0$ the summation up to $k'-1$ is vacuous?\n- In line 1209, $p_i$ is in place of $w_i$.\n- In line 1211, the left side of the implication should be $N \\le \\sum_{i=0}^{k'} t_{oracle}(w_i)$?\n\nEven though the paper is lengthy and involves many intricate parts, I believe it is the authors' responsibility to ensure that the paper is presented in a clear and polished manner to merit publication.", "was_revised": true, "final_justification": "The authors have committed to clean up the notations to improve the presentation of the paper, which was my main concern. While I previously stated that I will maintain my previous rating as I have not seen authors' concrete plans on how they will address the presentation issues, based on their last comment and the final remarks, I decided to trust the authors that they will take care of it.", "rebuttal": "Dear reviewer, we thank you for your review and comments. We sincerely appreciate your supportive review, careful reading and feedback, and belief that our main results seem compelling to a well-motivated problem and that our work “offers a systematic and fundamental view of how such arguments are structured, making it a valuable contribution to the literature”. We will be sure to improve the notation and presentation by taking your suggestions fully into account. \n\nWe would like to respond to the questions and weaknesses you raised as follows. All the sources here are the same as in our manuscript or your review.\n\n**Third-order self-bounding regularity:** This is a good question, and we thank the reviewer for raising it. The third-order self-bounding regularity condition does carry further significance. Namely, Xie et al 2024 very interestingly demonstrates that under mild assumptions, the objective of Distributionally Robust Optimization (DRO) satisfies their Assumption 3 (see Theorem 3 in their paper), which is subsumed by our third-order self-bounding regularity condition as per our Example 2. Thus our results apply to DRO. DRO is a general optimization problem that has significant applications in fairness in machine learning and in learning under distribution shifts; see Xie et al 2024 for more discussion. We will be sure to add this discussion to our manuscript. We also demonstrate in Example 2 that this condition covers several natural growth rates of interest. \n\n**Notation for the framework:** We thank you very much for the detailed comments on the presentation. We will be sure to clean it up as best we can. Regarding $\\mathcal{R}(\\mathcal{A}_2(\\cdot))$, this was a presentation choice we made. We believe defining $\\mathcal{R}$ separately is more natural when presenting high probability results for the algorithm returning exactly one candidate solution in $\\mathcal{S}$ (which we did not present in our submission for simplicity). If the reviewer feels strongly that this notation is cumbersome, we are happy to change this in our manuscript.\n\nThat said, we believe some of the framework’s notation is both helpful and necessary. In particular, we define $\\mathcal{R}$ for sequences of any length because for Restarted SGD, $\\mathcal{R}$ takes in the average of $K_0$ points, which can be of arbitrary length. Likewise for SGD, $\\mathcal{R}$ outputs a sequence of $K_0$ consecutive iterates, which also can be of arbitrary length.\n\n**Generality of assumption 3.1:** We believe Assumption 3.1 is quite general; it allows for the variance of gradient noise to increase with function value, considered a more realistic setting for gradient noise studied in Wojtowytsch 2023, 2024 and De Sa et al 2022. We can also extend Theorem 3.3 to sub-Gaussian noise with sub-Gaussian parameter depending on function value as we discuss in Remark 4, which was also considered in De Sa et al 2022 as a more general assumption for gradient noise in SGD. As per your suggestion, we will be sure to add more comparisons of Assumption 3.1 to other works studying relaxed gradient noise assumptions, such as Gower et al 2019.\n\n\n**Re experiments/simulations:** Indeed, they are not on phase retrieval or matrix PCA. Instead our experiments/simulations empirically verify that when optimizing natural generalized smooth functions with GD and SGD, the larger the loss $F(w_0)$ is at initialization, the smaller the largest working step size is (in contrast to optimizing smooth functions). These results show that the dependence on initialization via $\\rho_1(F(w_0))$ in the range of working step sizes from our theorems matches behavior in practice. Thus our experiments/simulations validate the practical implications of our theoretical results.\nWe thank you for the feedback and we will separate the last paragraph of Subsection 3.6 in our manuscript as per your suggestion.\n\nPlease let us know if you have further questions; we are very open to discussion. Thank you again for your time and feedback!"}]

Author rebuttal:

Meta-review: The paper provides new (theoretical) results on escaping strict saddle points in nonconvex optimization. While this is an extensively studied topic in the OPT/ML community, the existing nonasymptotic results strongly rely on traditional smoothness assumptions (Lipschitzness imposed on both the gradient and the Hessian). The paper instead provides nonasymptotic results under generalized smoothness assumptions, which can capture problems like matrix PCA, phase retrieval, and certain examples of distributionally robust optimization problems. Despite initial concerns, all reviewers were in agreement that the paper presents strong technical contributions and should thus be accepted. The authors have committed to improving the presentation clarity and I hope will make good on this commitment.
Decision: Accept (poster)