{'fraction_non_alphanumeric': 0.05752795324798162, 'fraction_numerical': 0.016923960409417963, 'mean_word_length': 3.948019388266756, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Escaping strict saddle points of the Moreau envelope in nonsmooth optimization

Recent work has shown that stochastically perturbed gradient methods can efficiently escape strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms for nonsmooth optimization can escape strict saddle points of the Moreau envelope at a controlled rate. The main technical insight is that typical algorithms applied to the proximal subproblem yield directions that approximate the gradient of the Moreau envelope in relative terms.


Introduction
Though nonconvex optimization problems are NP hard in general, simple nonconvex optimization techniques, e.g., gradient descent, are broadly used and often highly successful in high-dimensional statistical estimation and machine learning problems. A common explanation for their success is that smooth nonconvex functions g : R d → R found in machine learning have amenable geometry: all local minima are (nearly) global minima and all saddle points are strict (i.e., have a direction of negative curvature). This explanation is well grounded: several important estimation and learning problems have amenable geometry [3,16,17,43,44,47], and simple randomly initialized iterative methods, such as gradient descent, asymptotically avoid strict saddle points [27,28]. Moreover, "randomly perturbed" variants [24] "efficiently" converge to (ε 1 , ε 2 )-approximate second-order critical points, meaning those satisfying ∇g(x) ≤ ε 1 and λ min (∇ 2 g(x)) ≥ −ε 2 . (1.1) While impressive, the aforementioned works crucially rely on smoothness of objective functions or constraint sets. This is not an artifact of their proof techniques: there are simple C 1 functions for which randomly initialized gradient descent with constant probability converges to points that admit directions of second order descent [11,Figure 1]. Despite this example, recent work [11] shows that randomly initialized proximal methods avoid certain "active" strict saddle points of (nonsmooth) weakly convex functions. The class of weakly convex functions is broad, capturing, for example those formed by composing convex functions h with smooth nonlinear maps c, which often appear in statistical recovery problems. They moreover show that for "generic" semialgebraic problems, every critical point is either a local minimizer or an active strict saddle. A key limitation of [11], however, is that the result is asymptotic, and in fact pure proximal methods may take exponentially many iterations to find local minimizers [13]. Motivated by [11], the recent work [21] develops efficiency estimates for certain randomly perturbed proximal methods. The work [21] has two limitations: its measure of complexity appears to be algorithmically dependent and the results do not extend to subgradient methods.
The purpose of this paper is to develop "efficient" methods for escaping saddle points of weakly convex functions. Much like [21], our approach is based on [11], but the resulting algorithms and their convergence guarantees are distinct from those in [21]. We begin with a useful observation from [11]: near active strict saddle pointsx, a certain C 1 smoothing, called the Moreau envelope, is C 2 and has a strict saddle point atx. If one could exactly execute the perturbed gradient method of [24], efficiency guarantees would then immediately follow. While this is not possible in general, it is possible to inexactly evaluate the gradient of the Moreau envelope by solving a strongly convex optimization problem. Leveraging this idea, we extend the work [24] to allow for inexact gradient evaluations, proving similar efficiency guarantees.
Setting the stage, we consider a minimization problem where f : R d → R ∪ {+∞} is closed and ρ-weakly convex, meaning the mapping x → f (x) + ρ 2 x 2 is convex. Although such functions are nonsmooth in general, they admit a global C 1 smoothing furnished by the Moreau envelope. For all µ < ρ −1 , the Moreau envelope and the proximal mapping are defined to be y − x 2 and prox µf (x) = argmin respectively. The minimizing properties of f and f µ are moreover closely aligned, for example, their first-order critical points and local/global minimizers coincide. Inspired by this relationship, this work thus seeks (ε 1 , ε 2 )-approximate second-order critical points x of f µ , satisfying: An immediate difficulty is that f µ is not C 2 in general. Indeed, the seminal work [29] shows f µ is C 2 -smooth globally, if and only if, f is C 2 -smooth globally. Therefore assuming that f µ is C 2 globally is meaningless for nonsmooth optimization. Nevertheless, known results in [12] imply that for "generic" semialgebraic functions, f µ is locally C 2 near x whenever ∇f µ (x) is sufficiently small. Turning to algorithm design, a natural strategy is to apply a "saddle escaping" gradient method [24] directly to f µ . This strategy fails in general, since it is not possible to evaluate the gradient in closed form. Somewhat expectedly, however, our first contribution is to show that one may extend the results of [24] to allow for inexact evaluations G(x) ≈ ∇f µ (x) satisfying for appropriately small a, b ≥ 0. The algorithm (Algorithm 1) returns a point x satisfying (1.4), withÕ(max{ε −2 1 , ε −4 2 }) evaluations of G, matching the complexity of [24]. Our second contribution constructs approximate oracles G(x), tailored to common problem structures. Each oracle satisfies where ProxOracle µf is an approximate minimizer of the strongly convex subproblem defining prox µf (x). Since the subproblem is strongly convex, we construct ProxOracle µf from K iterations of off-the-shelf first-order methods for convex optimization. We focus in particular on the class of model-based methods [10]. Starting from initial point x 0 = x, these methods attempt to minimize f (y) + 1 2µ y − x 2 by iterating where θ k > 0 is a control sequence and for all z ∈ R d , the function f z : R d → R ∪ {+∞} is a local weakly convex model of f . In Table 1, we show three models, adapted to possible decompositions of f . In Table 2, we show how the model function f z influences the total complexitỹ O(K × max{ε −2 1 , ε −4 2 }) of finding a second order stationary point of f µ (1.4). In short, proxgradient and prox-linear methods requireÕ(max{ε −2 1 , ε −4 2 }) iterations of (1.6), while proxsubgradient methods requireÕ(d max{ε −6 1 ε −6 2 , ε −18 2 }). The efficiency of the prox-gradient method directly matches the analogous guarantees for the perturbed gradient method in the smooth setting [24]. The convergence guarantee of the prox-subgradient method has no direct analogue in the literature. Extensions for stochastic variants of these algorithms follow trivially, when the proximal subproblem (1.6) can be approximately solved with high probability (e.g. using [19,20,26,39]). The rates for the prox-gradient and prox-linear method are analogous to those in [21], which uses an algorithm-dependent measure of stationarity. Although the algorithms and the results in our paper and in [21] are mostly of theoretical interest, they do suggest that efficiently escaping from saddle points is possible in nonsmooth optimization.
Related work. We highlight several approaches for finding second-order critical points. Asymptotic guarantees have been developed in deterministic [11,27,28] and stochastic settings [38]. Other approaches explicitly leverage second order information about the objective
Road map. In Section 2 we introduce the preliminaries. Section 3 presents a result for finding second-order stationary points with inexact gradient evaluations. Section 4 develops several oracle mappings that approximately evaluate the gradient of the Moreau Envelope and derives the complexity estimates of Table 2.

Preliminaries
This section summarizes the notation that we use throughout the paper. We endow R d with the standard inner product x, y := x y and the induced norm x 2 := x, x . The closed unit ball in R d will be denoted by B d := {x ∈ R d | x ≤ 1}, while a closed ball of radius r > 0 around a point x will be written as B d r (x). When the dimension is clear from the context we write B. Given a function ϕ : R d → R ∪ {∞}, the domain and the epigraphs of ϕ are given by dom ϕ = {x ∈ R d | ϕ(x) < ∞} and epi ϕ = {(x, r) | ϕ(x) ≤ r}. A function ϕ is called closed if epi ϕ is a closed set. The distance of a point x ∈ R d to a set M ⊆ R d is denoted by dist(x, M) = inf y∈M x − y . The symbol A denotes the operator norm of a matrix A, while the maximal and minimal eigenvalues of a symmetric matrix A will be denoted by λ max (A) and λ min (A), respectively. For any bounded measurable set Q ⊂ R d , we let Unif(Q) be the uniform distribution over Q.
We will require some basic constructions from Variational Analysis as described for example in the monographs [4,32,40]. Consider a closed function f : R d → R ∪ {∞} and a point x, with f (x) finite. The subdifferential of f at x, denoted by ∂f (x), is the set of all vectors v ∈ R d satisfying (2.1) We set ∂f (x) = ∅ when x / ∈ dom f . When f is C 1 at x ∈ R d , the subdifferential ∂f (x) consists of the gradient {∇f (x)}. When f is convex, it reduces to the subdifferential in the sense of convex analysis. In this work, we will primarily be interested in the class of ρ-weakly convex functions, meaning those for which x → f (x) + ρ 2 x 2 is convex. For ρ-weakly convex functions the subdifferential satisfies: Finally, we mention that a point x is a first-order critical point of f whenever the inclusion 0 ∈ ∂f (x) holds.

Escaping saddle points with inexact gradients
In this section, we analyze an inexact gradient method on smooth functions, focusing on convergence to second-order stationary points. The consequences for nonsmooth optimization, which will follow from a smoothing technique, will be explored in Section 3. We begin with the following standard assumption, which asserts that the function f in question has a globally Lipchitz continuous gradient.
Assumption A (Globally Lipschitz gradient). Fix a function g : R d → R that is bounded from below and whose gradient is globally Lipschitz continuous with constant L 1 , meaning The next assumption is more subtle: it requires the Hessian ∇ 2 g to be Lipschitz continuous on a neighborhood of any point where the gradient is sufficiently small. When we discuss consequences for nonsmooth optimization in the later sections, the fact that f is assumed to be C 2 -smooth only locally will be crucial to our analysis.
Assumption B (Locally Lipschitz Hessian). Fix a function g : R d → R and assume that there exist positive constants α, β, L 2 satisfying the following: For any pointx with ∇g(x) ≤ α, the function g is C 2 -smooth on B β (x) and satisfies the Lipschitz condition: We aim to analyze an inexact gradient method for minimizing the function f under Assumptions A and B. The type of inexactness we allow is summarized by the following oracle model.

Algorithm 1: Perturbed inexact gradient descent
Data: Step t = 0, . . . , T : Turning to algorithm design, the method we introduce (Algorithm 1) directly extends the perturbed gradient method introduced in [24] to inexact gradient oracles in the sense of Definition 3.1. The convergence guarantees for the algorithm will be based on the following explicit setting of parameters. Fix target accuracies ε 1 , ε 2 > 0 and choose any ∆ g ≥ g(x 0 ) − inf g. We first define the auxiliary parameters: The parameters required by the algorithm are then set as The following is the main result of the section. The proof follows closely the argument in [24] and therefore appears in Appendix A.
Theorem 3.2 (Perturbed inexact gradient descent). Suppose that g : R d → R is a function satisfying Assumptions A and B and G : Then with probability at least 1 − δ, at least one iterate generated by Algorithm 1 with parameters (3.3) is a (ε 1 , ε 2 )-second-order critical point of g after The necessary bounds for a and b can be estimated as where the symbol " " denotes inequality up to polylogarithmic factors. Thus, Algorithm 1 is guaranteed to find a second order stationary point efficiently, provided that the gradient oracles are highly accurate. In particular, when a = b = 0 we recover the known rates from [24].

Escaping saddle points of the Moreau envelope
In this section, we apply Algorithm 1 to the Moreau Envelope (1.3) of the weakly convex optimization problem (1.2) in order to find a second order stationary point of f µ (1.4). We will see that a variety of standard algorithms for nonsmooth convex optimization can be used as inexact gradient oracles for the Moreau envelope. Before developing those algorithms, we summarize our main assumptions on f µ , describe why approximate second order stationary points of f µ are meaningful for f , and show that Assumption B, while not automatic for general f µ , holds for a large class of semialgebraic functions. As stated in the introduction, for µ < ρ −1 , the Moreau envelope is an everywhere C 1 smooth with Lipschitz continuous gradient. In particular, See for example [11] for a short proof. Assumption B, however, is not automatic, so we impose the following assumption throughout.
Assumption C. Let f : R d → R ∪ {∞} be a closed ρ-weakly convex function whose Moreau envelope f µ satisfies Assumption B with constants α, β, L 2 .
Turning to stationarity conditions, a natural question is whether the second order condition (1.4) is meaningful for f . The next proposition shows that the condition (1.4) implies the existence of an approximate quadratic minorant of f with small slope and curvature at a nearby point.
We defer the proof to Appendix B.
. Then there exists a quadratic function q : R d → R and a neighborhood U = B 3ε 2 /4L 2 ( x) of x for which the following hold.

(Nearby point)
The point x is close to x: x − x ≤ µ · ε 1 .

(Minorant)
For any y ∈ U, we have q(y) ≤ f (y). ) with x an (ε 1 , ε 2 )-second-order critical point of f µ and its corresponding quadratic q(·). On the right: The set of first-order critical points of f (yellow) and the set of (ε 1 , ε 2 )-second-order critical points of f µ (red).

(Small subgradient)
The quadratic has a small gradient at x:

(Small negative curvature)
The quadratic has small negative curvature:

(Approximate match)
The quadratic almost matches the function at x: In Figure 1, we illustrate the proposition with the following nonsmooth function: The Moreau envelope of this function has three first-order critical points: a strict saddle point (0, 0) and two global minima (−1, 0), and (1, 0). As shown in the right plot of Figure 1, approximate second-order critical points of f µ cluster around minimizers of f . In addition, the left plot of Figure 1 shows the lower bounding quadratic from Proposition 4.1.
Finally, we complete this section by showing that Assumption C is reasonable: it holds for generic semialgebraic functions. 1 Theorem 4.2. Let f : R d → R ∪ {∞} be a semi-algebraic ρ-weakly-convex function. Then, the set of vectors v ∈ R d for which the tilted function g(x; v) = f (x) + v, x satisfies Assumption C has full Lebesgue measure.
The proof appears in Appendix C, and is a small modification of the argument in [11].

Inexact Oracles for the Moreau Envelope
In this section, we develop inexact gradient oracles for ∇f µ = µ −1 (x−prox µf (x)). Leveraging this expression, our oracles will satisfy where ProxOracle µf is the output of a numerical scheme that solves (1.3). To ensure G meets the conditions of Definition 3.1, we require that for some constants a ∈ (0, 1) and b > 0.
We now use this strong convexity to derive efficient proximal oracles via a class of algorithms called model-based methods [10], which we now briefly summarize. Given a minimization problem min x∈R d g(x), where g is strongly convex, a model-based method is an algorithm that recursively updates where g x k : R d → R ∪ {∞} is a function that approximates g near x k . Returning to the proximal subproblem, say we wish to compute prox µf (x 0 ) for some given x 0 . We consider an inner loop update of the form where f x k : R d → R∪{∞} is a function that locally approximates f (see Table 1 for three examples). Completing the square, this update can be equivalently written as a proximal step on f x k , where the reference point is a weighted average of x 0 and x k as summarized in Algorithm 2. Turning to complexity, we note that the approximation quality of a model governs the speed at which iteration (4.4) converges. In what follows, we will present two families of models with different approximation properties, namely one-and two-sided models.
We will see that models with double-sided accuracy require fewer iterations to approximate prox µf (x 0 ).

One-sided models
We start by studying models that globally lower bound the function and agree with it at the reference point. Subgradient-type models are the canonical examples, and we will discuss them shortly. Step k (k ≤ K + 1): If one sided : In addition, for all x ∈ R d , the model Now we bound the number of iterations that are needed for Algorithm 2 to obtain a (a, b)inexact proximal point oracle with one-sided models. The algorithm outputs an average of the iterates with nonuniform weights that improves the convergence speed. (k + 1) then Algorithm 2 with flag one sided = true outputs an a pointx K such that provided the number of iterations is at least K ≥ 4 a + 16L 2 (1−µρ) 2 b 2 . The proof of this result follows easily from Theorem 4.5 in [10] and thus, we omit it. By exploiting this rate, we derive a complexity guarantee with one-sided models. Consider an L f -Lipschitz ρ-weaklyconvex function f : R d → R ∪ {∞} that satisfies Assumption C and a family of models f x satisfying Assumption D. Then, for all sufficiently small ε 1 > 0, and any ε 2 > 0, δ ∈ (0, 1) there exists a parameter configuration (η, r, M ) that ensures that with probability at least 1−δ one of the first T iterates generated by Algorithm 1 with gradient oracle is an (ε 1 , ε 2 )-second-order critical point of f µ provided that the inner and outer iterations satisfy The rate from Table 2 follows by noting that max Example: proximal subgradient method. Consider the setting of Assumption D, where f = l + r. Assuming that l is τ -weakly convex, it possesses an affine model: where v ∈ ∂l(x).
By weak convexity, f x = l x + r satisfies Assumption D. Moreover, the resulting update (4.4) reduces to the following proximal subgradient method: Theorem 4.4 applied to this setting thus implies the rate in Table 2.

Two-sided models
The slow convergence of one-sided model-based algorithms motivates stronger approximation assumptions. In this section we study models that satisfy the following assumption.
Assumption E (Two-sided model). Assume that for any x ∈ R d , the function f x : R d → R ∪ {∞} is ρ-weakly convex and satisfies When equipped with double-sided models, model-based algorithms for the proximal subproblem converge linearly.
Theorem 4.5. Suppose that f : R d → R ∪ {∞} is a ρ-weakly-convex function, let f x be a family models satisfying Assumption E. Fix an accuracy level a. Set µ −1 > ρ + q and the stepsizes to θ t = θ > q, then Algorithm 2 with flag one sided = false outputs a point x K such that We defer the proof of this result to Appendix D. Given this guarantee for two-sided models, we derive the following theorem. The proof is analogous to that of Theorem 4.4: the only difference is that we use Theorem 4.5 instead of Theorem 4.3. Thus we omit the proof. Theorem 4.6 (Two-sided model-based method). Consider a weakly convex function f : R d → R ∪ {∞} that satisfies Assumption C and a family of models f x satisfying Assumption E. Then for any δ ∈ (0, 1) and sufficiently small ε 1 > 0, there exists a parameter configuration (η, r, M ) such that with probability at least 1 − δ one of the first T iterates generated by Algorithm 1 with inexact oracle is an (ε 1 , ε 2 )-second-order critical point of f µ provided that the inner and outer iterations satisfy We close the paper with two examples of two-sided models.
Example: Prox-gradient method. Suppose that where r : R d → R ∪ {+∞} is closed and ρ-weakly convex and F is C 1 with q-Lipschitz continuous derivative on dom r. Then due to the classical inequality satisfies Assumption E. Moreover, the resulting update (4.4) reduces to the following proximal gradient method: Theorem 4.6 applied to this setting thus implies the rate in Table 2.
Example: Prox-linear method. Suppose that where r : R d → R ∪ {+∞} is closed and ρ-weakly convex, h is L-Lipschitz and convex on dom r, and c is C 1 with β-Lipschitz Jacobian on dom r. Then due to the classical inequality Consequently, the model satisfies Assumption E with q = βL. Moreover, the resulting update (4.4) reduces to the following prox-linear method [14]: Theorem 4.6 applied to this setting thus implies the rate in Table 2.

A Proof of Theorem 3.2
Throughout this section, we assume the setting of Theorem 3.2. We begin by recording some inequalities that we will use later on.
Lemma A.1. The following inequalities hold.
We assume that G is an (a, b)-inexact gradient oracle for g. We derive two simple consequences of Definition 3.1.
Lemma A.2. Then we have that for any x ∈ R d the following inequalities hold: Proof. Throughout the proof we let v = ∇g(x) and u = G(x) and use that u−v ≤ a v +b. The first part of the theorem is then a consequence of the triangle inequality. The second part follows since which implies the following: where the third inequality uses a ≤ 1/2 and the second inequality follows from Young's inequality: To complete the result, set c = 1/8.
As a consequence of this Lemma, we prove that the function g decreases along the inexact gradient descent sequences with oracle G. Lemma A.3 (Descent lemma). Given y 0 ∈ R d , consider the inexact gradient descent sequence: y t+1 ← y t − η · G t (y t ). Then for all t ≥ 0, we have Proof. Since the function g has L 1 -Lipschitz gradients we have Here the second inequality follows from Lemma A.2 and the third follows from Young's inequality: 2(1 + a) ∇g(y t ) b ≤ 1 5 (1 + a) 2 ∇g(y t ) 2 + 5b 2 . Next, observe that where the second line follows since η ≤ 1/L 1 and the last inequality follows from (6/10)(1 + a) 2 ≤ (3/4)(1 − a) for a ≤ 1/20. Thus, we have shown that which implies (A.1).
As a consequence of the above Lemma, we now show that inexact gradient descent sequences {y t } either (a) significantly decrease g or (b) remain close to y 0 .
Lemma A.4 (Improve or localize). Given y 0 ∈ R d , consider the inexact gradient descent sequence: y t+1 ← y t − η · G t (y t ). Then, for all τ ≤ t, we have Proof. By Lemma A.2, we have where the last inequality follows from Jensen's inequality. Next apply Lemma A.3, to bound . Plugging this bound into the above inequality, we have This concludes the proof.
In the next two Lemmas, we show that, when randomly initialized near a critical point with negative curvature, inexact gradient descent sequences decrease the objective g with high probability. The first result (Lemma A.5) will help us estimate the failure probability.
Then by Lemma A.4, the iterates of both sequences remain close to their initializers: where the second inequality follows from two upper bound: η ≤ 1/L 1 and b 2 ≤ L 1 F M (5L 1 +1) . We now use (A.3) to show for all t ≤ M , iterates y t and y t remain close toỹ. By Lemma A.1, we get In the remainder of the proof, we will argue that inequality (A.4) cannot hold. In particular, we will show that negative curvature of g implies the sequences y t and y t must rapidly diverge from each other.
To leverage negative curvature, we first claim that g is C 2 with L 2 -Lipschitz Hessian in B R (ỹ), which contains y t and y t for t ≤ M . Indeed, sinceỹ satisfies ∇g(ỹ) ≤ ε 1 ≤ α, Assumption B ensures ∇ 2 g(y) is defined and L 2 -Lipschitz through B β (ỹ). The claim then follows since R = 1 4γ ε 2 L 2 ≤ β, which follows from the assumption ε 2 ≤ 4γβL 2 Now observe that {y t + s(y t − y t ) | s ∈ [0, 1]} ⊆ B R (ỹ) for all t ≤ M . Therefore, defining H := ∇ 2 g(ỹ), v t := ∇g(y t ) − G(y t ), v t := ∇g(y t ) − G(y t ), and y t := y t − y t , we have for all where the last equality follows from the recursive definition of y t and y t . In what follows we will argue that p(t) diverges exponentially and dominates q(t) and n(t).
2 . The proof of the claim follows by induction on t and the following bound which holds since η is small enough that I − ηH 0.
Turning to the inductive proof, we note that the base case holds since 2n(0) = q(0) = 0 ≤ ŷ 0 /4. Now assume the claim holds for all τ ≤ t. Then for all τ ≤ t we have where the final inequality follows from (A.5). Consequently, we may bound q(t + 1) as follows: where the second inequality follows from L 2 -Lipschitz continuity of ∇ 2 g on B R (ỹ), the third inequality follows from the inclusions y t , y t ∈ B R (ỹ), the fourth inequality follows from (A.5), and the fifth inequality follow from 2ηL 2 RM ≤ 1/2. This proves half of the inductive step.
To prove the other half of the inductive step, we bound n(t + 1) as follows: where the third inequality follows from L 1 Lipschitz continuity of ∇g, the inclusions y t , y t ∈ B R (ỹ), and the bound ∇g(ỹ) ≤ ε 1 ; and the fourth inequality follows from the bound I − ηH t−τ ≤ (1 + ηλ) t . To complete the proof, we recall that three inequalities: Then, we find that This concludes the proof of the claim. Consequently, the proof of the Lemma is complete.
Using the Lemma A.5, the following Lemma proves that inexact gradient descent will decrease the objective value by a large amount if it is randomly initialized near a point with negative curvature.
Consider an initial point y 0 :=ỹ +η ·u with u ∼ Unif(rB). Let {y t } be an inexact gradient descent sequence, initialized at y 0 : Then with probability at least we have g(y M ) − g(ỹ) ≤ −F/2 Proof. We show that the bound g(y M ) − g(ỹ) ≤ −F/2 follows from the inequality g(y M ) − g(y 0 ) ≤ −F . To that end, first observe that.
where the last inequality follows by Lemma A.1. Consequently, This shows that it is sufficient to study g(y M ) − g(y 0 ) ≤ −F as desired.
In the remainder of the proof, we show the event {g(y M ) − g(y 0 ) ≤ −F } holds with the claimed probability in (A.6). To that end, given any y 0 ∈ R d , let us define T M (y 0 ) = y M , where y t+1 = y t − ηG(y t ) for all t ≥ 0. Consider the set of points y ∈ B ηr (ỹ), for which M steps of the inexact gradient method with oracle G fail to decrease the g significantly: We now show that P (y 0 ∈ X stuck ) ≤ 1 − p. Indeed, Lemma A.5 shows that there exists e 0 ∈ S d−1 such that width of X stuck along e 0 is upper bounded by ηω. Thus the volume of X stuck is bounded by the volume of the cylinder [0, ω] × B d−1 ηr (0), which yields the result: where the second inequality follows from the identity Vol(ηrB d ) = (ηr) d π d/2 /Γ( d 2 + 1); the third inequality follows from the bound Γ( x for any x ≥ 0 [22]; the fourth inequality follows from the definition ω = R 2 γ−3 η ; and the fifth inequality follows from the definitions η = (1 − a)/L 1 (1 + a) 2 , R = 1 4γ ε 2 L 2 , and r = ε 2 2 400L 2 γ 3 min 1, L 1 ε 2 5ε 1 L 2 , as well as the bound 400 · 2 3 /(4 √ π) ≤ 2 9 . This concludes the proof.
To conclude this section, we now combine all the Lemmas to prove Theorem 3.2.
Proof of Theorem 3.2. Set the number of iterations to Then, we will prove the slightly stronger claim that there is at least one (ε 1 /4, ε 2 )-secondorder critical point. Let {x t } T t=0 be the sequence generated by Algorithm 1. We partition this sequence into three disjoint sets: Moreover, since |S 2 | is empty, such x t satisfy λ min (∇ 2 g(x t )) < −ε 2 . Therefore, by Lemma A.6 and a union bound, the following event does not happen with probability at most By Lemma A.1, this probability is upper bounded by δ. Therefore, throughout the remainder of the proof, we suppose the event E happens. In this event we will show that we will show that g(x t ) < inf g for some t, which yields the desired contradiction.
To that end, recall that by Lemma A.3, g cannot increase by much at each iteration: Thus, defining t last := max{t | t + M < T } and we find that To arrive at the desired contradiction, we will show that |Γ| is large. In particular, we claim that |Γ| ≥ 3T 4M .
In particular, since g i are locally Lipschitz continuous, for every v ∈ V i , there exists a constant satisfying (∂f ) −1 (B (v)) ⊂ k j=m B (g j (v)), (C.1) for all small > 0. Moreover, by [12,Corollary 4.8] we may assume that for every point v in V i and for sufficiently small > 0 the set g j (B (v)) is an active manifold around g j (v) for the tilted function f (·; v) = f (·) − v, · . Taking into account [11,Theorem 3.1], we may also assume that the Moreau envelope f µ (·; v) of f (·; v) is C p -smooth on a neighborhood of each point g j (v). Fix now a set V i a point v ∈ V i . Clearly, then there exist constants r, β, L 2 > 0, such that for any point y with dist(y, (∂f ) −1 (v)) ≤ r, the Hessian ∇ 2 f µ (·; v) is L 2 -Lipschitz on the ball B β (y). It remains to show that for all sufficiently small α > 0, any point y satisfying ∇f µ (y; v) ≤ α also satisfies dist(y, (∂f ) −1 (v)) ≤ r. To this end, consider a point y with ∇f µ (y; v) ≤ α for some α > 0. Note the proximal pointŷ of f µ (·; v) at y then satisfies dist(v, ∂f (ŷ)) ≤ α and ŷ − y ≤ µα.