{'fraction_non_alphanumeric': 0.055264744138828086, 'fraction_numerical': 0.014847244694013514, 'mean_word_length': 3.785486564445119, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finding Approximate Local Minima for Nonconvex Optimization in Linear Time

We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which is linear in the input representation. The time complexity of our algorithm to find an approximate local minimum is even faster than that of gradient descent to find a critical point. Our algorithm applies to a general class of optimization problems including training a neural network and other non-convex objectives arising in machine learning.


Introduction
Finding a global minimizer of a non-convex optimization problem is NP-hard. Thus, the standard goal of efficient non-convex optimization algorithms is instead to find a local minimum. This problem has become increasingly important as the state-of-the-art in machine learning is attained by non-convex machines, many of which are variants of deep neural networks. Experiments in [10,11,21] suggest that fast convergence to a local minimum is sufficient for training neural nets, while convergence to critical points (points with vanishing gradients) is not. Theoretical works have also affirmed the same phenomenon for other machine learning problems (see [5,6,18,19] and the references therein).
In this paper we give a provable linear-time algorithm for finding an approximate local minimum in smooth non-convex optimization. It applies to a general setting of machine learning optimization, and in particular to the optimization problem of training deep neural networks. Furthermore, the running time bound of our algorithm is the fastest known even for the more lenient task of computing a point with vanishing gradient (called a critical point), for a wide range of parameters.
Formally, the problem of unconstrained mathematical optimization is stated in general terms as that of finding the minimum value that a function attains over Euclidean space, i.e. (1.1) If f is convex, the above formulation is convex optimization and is solvable in (randomized) polynomial time even if only a valuation oracle to f is provided. A crucial property of convex functions is that "local optimality implies global optimality", allowing for greedy algorithms to reach the global optimum efficiently. Unfortunately, this is no longer the case if f is nonconvex; indeed, even a degree four polynomial can be NP-hard to optimize [23], or even just to check whether a point is not a local minimum [25]. Thus, for non-convex optimization one has to settle for the more modest goal of reaching approximate local optimality efficiently.
Note that a particular interest to machine learning is the optimization of functions f : R d → R of the finite-sum form Such functions arise when minimizing loss over a training set, where each example i in the set corresponds to one loss function f i in the summation.
We say that the function f is second-order smooth if it has Lipschitz continuous gradient and Lipschitz continuous Hessian. We say that a point x is an ε-approximate local minimum if it satisfies (following the tradition of [28]): where · denotes the Euclidean norm of a vector. We say that a point x is an ε-critical point if it satisfies the gradient condition above, but not necessarily the second-order condition. Critical points include saddle points in addition to local minima. We remark that ε-approximate local minima (even with ε = 0) are not necessarily close to any local minimum, neither in domain nor in function value. However, if we assume in addition the function satisfies the (robust) strict-saddle property [15,24] (see Section 2 for the precise definition), then an ε-approximate local minimum is guaranteed to be close to a local minimum for sufficiently small ε.
Our main theorem below states the time required for the proposed algorithm FastCubic to find an ε-approximate local minimum for second-order smooth functions.
Above, T h is the time to compute Hessian-vector product for ∇ 2 f (x) and T h,1 is that for an arbitrary ∇ 2 f i (x).
The full statement of Theorem 1 can be found in Section 2.
Hessian-vector products can be computed in linear time -meaning T h,1 = O(d) and T h,1 = O(nd)-for many machine learning problems such as generalized linear models and training neural networks [1,29]. We explain this more generally in Appendix A. Therefore, Another important aspect of our algorithm is that even in terms of just reaching an ε-critical point, i.e. a point that satisfies ∇f (x) ≤ ε without any second-order guarantee, FastCubic is faster than all previous results (see Table 1 for a comparison).
The fastest methods to find critical points for a smooth non-convex function are gradient descent and its derivatives, jointly known as first-order methods. These methods are extremely efficient in terms of per-iteration complexity; however, they necessarily suffer from a 1/ε 2 convergence rate [27], and only higher-order methods can break this 1/ε 2 bottleneck [28]. For certain ranges of parameters, our FastCubic finds local minima even faster than first-order methods, even though they only find critical points. This is depicted in Table 1.

Related work
Methods that Provably Reach Critical Points. Recall that only a gradient oracle is needed to reach a critical point. The most commonly used algorithm in practice for training non-convex learning machines such as deep neural networks is stochastic gradient descent (SGD), also known as stochastic approximation [30] and its derivatives. Some practical enhancements widely used in practice are based on Nesterov's acceleration [26] and adaptive regularization [12]. The variance reduction technique, introduced in [32], was extremely successful in convex optimization, but only recently there was a non-convex counterpart with theoretical benefits introduced [2].
Methods that Provably Reach Local Minima. The recent work of Ge et al. [17] showed that a noise-injected version of SGD in fact converges to local minima instead of critical points, as long as the underlying non-convex function is strict-saddle. Their theoretical running time is a large polynomial in the dimension and not competitive with our method (see Table 1).
The work of Lee et al. [24] shows that gradient descent, starting from a random point, almost surely converges to a local minimum of a strict-saddle function. The rates of convergence and precise step-sizes that are required are, however, yet unknown.
If second-order information (i.e., the Hessian oracle) is provided, the cubic-regularization method of Nesterov and Polyak [28] converges in O( 1 ε 3/2 ) iterations. However, each iteration of Nesterov-Polyak requires solving a cubic function which, in general, takes time super-linear in the input representation.
One natural direction is to apply an approximate trust region solver, such as the linear-time solver of [22], to approximately solve the cubic regularization subroutine of Nesterov-Polyak. However, the approximation needed by a naive calculation makes this approach even slower than vanilla gradient descent. Our main challenge is to obtain approximate second-order local-minima and simultaneously improve upon gradient descent.
Independently of this paper and concurrently 1 , Carmon et al. [7] develop an accelerated gradient descent method that achieves the same running time for finding an approximate local minimum as in our paper. Remarkably, the same running time is obtained via a very different technique.

Our Techniques
Our algorithm is based on the cubic regularization method of Nesterov and Polyak [8,9,28]. At a high level, cubic regularization states that if we can minimize a cubic function m(h) g h + 1 2 h Hh + L 6 h 3 exactly, where g = ∇f (x), H = ∇ 2 f (x), and L is the second-order smoothness of the function f , then we can iteratively perform updates x ← x + h, and this algorithm converges to an ε-approximate local minimum in O(1/ε 3/2 ) iterations. Unfortunately, solving this cubic minimization problem exactly, to the best of our knowledge, requires a running time of O(d ω ) where ω is the matrix multiplication constant. Getting around this requires five observations.
The first observation is that, minimizing m(h) up to a constant multiplicative approximation (plus a few other constraints) is sufficient for showing an iteration complexity of O(1/ε 3/2 ). 2 The proof techniques to show this observation are based on extending Nesterov and Polyak.
The second observation is that the minimizer h * of m(h) must be of the form h * = (H+λ * I) + g+ v, where λ * ≥ 0 is some constant satisfying H + λ * I 0, and v is the smallest eigenvector of H and + denotes the pseudo-inverse of a matrix. This can be viewed as moving in a mixture direction between choosing h ← v, and choosing h to follow a shifted Newton's direction h ← (H + λ * I) + g. Intuitively, we wish to reduce both the computation of (H+λ * I) + g and v to Hessian-vector products.
The first task of computing (H + λ * I) + g can be slow, and even if H + λ * I is strictly positivedefinite, computing it has a complexity depending on the (possibly huge) condition number of H + λ * I [34]. The third observation is that it suffices to pick some λ > λ * so both (1) the condition number of H + λ I is small and (2) the vectors (H + λ * I) −1 g and (H + λ I) −1 g are close. This relies on the structure of m(h).
The second task of computing v has a complexity depending on 1/ √ δ where δ is the target additive error [13,14]. The fourth observation is that the choice δ = √ ε suffices for the outer loop of cubic regularization to make sufficient progress. This reduces the complexity to compute v.
Finally, finding the correct value λ * itself is as hard as minimizing m t (h). The fifth step is to design an iterative scheme that makes only logarithmic number of guesses on λ * . This procedure either finds the correct one (via binary search), or finds an approximate one, λ , but satisfying (H + λ * I) −1 g and (H + λ I) −1 g being sufficiently close.
Putting all the observations together, and balancing all the parameters, we can obtain a cubic minimization subroutine (see FastCubicMin in Algorithm 2) that runs in time O(nd + n 3/4 d/ε 1/4 ).

Preliminaries and Main Theorem
We use · to denote the Euclidean norm of a vector and the spectral norm of a matrix. For a symmetric matrix M we denote by λ max (M) and λ min (M) respectively the maximum and minimum eigenvalues of M. We denote by A B that A − B is positive semidefinite (PSD). For a PSD matrix M, we denote by M + its pseudo-inverse if M is not strictly positive definite.
We make the following Lipschitz continuity assumptions for the gradient and Hessian of the target function f . Namely, there exist L 2 , L > 0 such that ∀x, y ∈ R d : Definition 2.1. We assume the following complexity parameters on the access to f (x): • Let T g ∈ R * be the time complexity to compute ∇f (x) for any x ∈ R d .
• Let T h ∈ R * be the time complexity to compute ∇ 2 f (x) v for any x, v ∈ R d .
. In this case, we define T h,1 to be the time complexity to compute ∇ 2 f i (x) v for arbitrary x, v ∈ R d and i ∈ [n].
Next we define the strict-saddle function for which an ε-approximate local minimum is almost equivalent to a local minimum [15,24].
For α, β, γ ≥ 0, we say f is (α, β, γ)-strict saddle if every x ∈ R d satisfies at least one of the following three conditions: 3. There exists a local minimum x that is γ-close to x in Euclidean distance.
h ← either v or λv min 2L whichever that gives smaller value for m t (h); 6: c is a constant; we proved c = 2.4 * 10 6 works 8: end for

Main Results
The finite-sum setting captures much of supervised learning, including Neural Networks and Generalized Linear Models. The main theorem which we show in our paper is as follows: Theorem 1. FastCubic (Algorithm 1) starts from a point x 0 and outputs a point x such that · T h,1 in the finite-sum setting (see Definition 2.2).
Two Known Subroutines. Our running time of FastCubic relies on the following recent results for approximate matrix inverse and approximate PCA: Theorem 2.4 (Approximate Matrix Inverse). Suppose matrix M ∈ R d×d satisfies M ≤ L 2 and λI + M δI for constants λ, δ, L 2 > 0. Let κ λ+L 2 δ . Then, we can compute vector x satisfying using Accelerated gradient descent (AGD) in O κ 1/2 log(κ/ε) iterations, each requiring O(d) time plus the time needed to multiply M with a vector.
We refer to the running time for this computation as T inverse (κ, ε) and the algorithm as A.
Above, the SVRG based running time shall be used only towards our finite-sum case in Definition 2.2.

Our Fast Cubic Regularization Algorithm
Recall that the cubic regularization method of Nesterov and Polyak [28] studies the following upper bound on the change in objective value as we move from a point x t to x t + h: (it follows simply from the Taylor series truncated to the third order) Denote by h * an arbitrary minimizer of m t (h). We propose in this paper a subroutine FastCubicMin to minimizes m t (h) approximately. Note that FastCubicMin returns two vectors v and v min . We then choose h to be either v or λv min 2L , whichever gives a smaller value for m t (h). Before discussing the details of FastCubicMin, let us first state a main theorem for FastCubicMin: 3 Theorem 2 (Guarantees of FastCubicMin). The algorithm FastCubicMin finds a vector h that satisfies (a) It produces a vector h satisfying m t (h ) ≤ 0 and Above, the first guarantee promises that we are either done (because m t (h * ) is close to zero), or we obtain a 1/3000 multiplicative approximation to m t (h * ). Our second guarantee in Theorem 2 promises that when we are done (because m t (h * ) is close to zero), the output vector h would be close to h in Euclidean norm and have a small gradient ∇m t (h ) . Our third guarantee gives the time complexity of FastCubicMin.
Now, our final algorithm FastCubic for finding the ε-approximate local minimum of f (x) is included in Algorithm 1. It simply iteratively calls FastCubicMin to find an approximate minimizer, and it then stops whenever m t (h ) > − ε 3/2 c √ L for some large constant c. Roadmap. In Section 4 we show why Theorem 2 implies Theorem 1. All the remaining sections are for the purpose of proving Theorem 2. Because our FastCubicMin is very technical, instead of stating what the algorithm is right away, we decide to take a different path. In Section 5, we first state a lemma characterizing "how h * looks like". In Section 6, we provide a set of sufficient conditions which "look similar" to the characterization of h * , and show that as long as these conditions are met, Theorem 2-a and 2-b follow easily. Finally, in Section 7, we state FastCubicMin and explain why it satisfies these sufficient conditions and why it runs in the aforementioned time.

Theorem 2 implies Theorem 1
In this section, we show that Theorem 2 implies Theorem 1. It relies on the following lemma (proved in Appendix B) regarding the sufficient condition for us to reach an ε-approximate local minimum.
Proof of Theorem 1 from Theorem 2. When FastCubic terminates, we have Combining this with Theorem 2-b and Corollary 4.1, we conclude that in the last iteration of FastCubic, our output satisfies ∇f (x t +h ) ≤ ε and λ min ( This finishes the proof with respect to the accuracy conditions. As for the running time, in every iteration except for the last one, FastCubic satisfies m t (h ) ≤ −Ω −ε 3/2 √ L . Therefore by (3.1), we must have decreased the objective by at least Ω −ε 3/2 √ L in this round, and this cannot happen for more than iterations. The final running time of FastCubic follows from this bound together with Theorem 2-c.
Therefore, in the rest of the paper it suffices to study FastCubicMin and prove Theorem 2.

Characterization Lemma of the Minimizer h *
For notational simplicity in this and the subsequent sections we focus on the following problem: Recall from the previous section that we have denoted by h * an arbitrary minimizer of m(h). We have the following lemma which characterizes h * : (a variant of this lemma has appeared in [8], and we prove it in the appendix for the sake of completeness) The objective value in this case is given by The following corollary comes from Lemma 5.1 and its proof: The value λ * in Lemma 5.1 is unique, and for every λ satisfying H + λI 0, we have In the above characterization, we have a crude upper bound on λ * : λ min (H+BI) ≤ L g B−L 2 < 2B and therefore λ * ≤ B due to Corollary 5.2.

6 Sufficient Conditions for Theorem 2-a and 2-b
Without worrying about the design of FastCubicMin at this moment, let us first state a set of sufficient conditions under which the assumptions in Theorem 2-a can be satisfied.
Main Lemma 1. Consider an algorithm that outputs a real λ ∈ [0, 2B], a vector v ∈ R d , and a unit vector v min ∈ R d . Additionally, suppose numbers κ,ε ≥ 0 satisfying the following conditions: 2) Moreover, suppose that the outputs (λ, v, v min ) satisfy one of the following two cases: The following conditions are satisfied: Then, at least one of the two choices h ∈ v, λv min Let us compare such sufficient conditions to the characterization Lemma 5.1.
• In Case 1, up to a very small errorε, we have essentially found a vector v that satisfies v ≈ −(H + λI) −1 g and v ≈ 2λ L . Therefore, this v should be close to h * for obvious reason. (This is the simple case.) • In Case 2, we have only found a vector v that satisfies v ≈ −(H + λI) −1 g and v 2λ L .
In this case, we also compute an approximate lowest eigenvector v min of λ min (H) up to an additive 1/10κ accuracy (see case 2-c). We will make sure that, as long as the conditions in 2-a hold, then either v or λv min 2L will be an approximate minimizer for m t (h). (This is the hard case.) Proof of Main Lemma 1. We first consider Case 1. According to Corollary 5.2, ifε = 0 then v is a minimizer of m(h). The following claim extends this argument to the setting whenε > 0: which satisfies the conditions of the theorem.
We now consider Case 2, and in this case we make the following two claims: 7 Main Algorithms for Theorem 2 We are now ready to state our main algorithm FastCubicMin and sketch why it satisfies the sufficient conditions in Main Lemma 1. As described in Algorithm 2, our algorithm starts with a very large choice λ 0 ← 2B and decreases it gradually. At each iteration i, it computes an approximate inverse v satisfying v + (H + λ i I) −1 g ≤ε with respect to the current λ i . Then there are three cases, depending on whether L v is approximately equal to, larger than, or smaller than 2λ i . At a high level, if it is "equal", then we have met Case 1 in Main Lemma 1; if it is "larger", then we can binary search the correct value of λ * in the interval [λ i , λ i−1 ]; and if it is "smaller", then we need to compute an approximate eigenvector and carefully choose the next point λ i+1 .
We state our main lemma below regarding the correctness and running time of FastCubicMin.
Main Lemma 3. FastCubicMin in Algorithm 2 outputs a real λ ∈ [0, 2B], a vector v ∈ R d , and a unit vector v min ∈ R d satisfying one of the two sufficient conditions in Main Lemma 1. We also have that the procedure can be implemented in a total running time of HereÕ hides logarithmic factors in L, L 2 , κ, d, B.
We prove the correctness half of Main Lemma 3, and defer its running time analysis to Appendix G.

Correctness Half of Main Lemma 3
We will now establish the correctness of our algorithm. We first observe that the BinarySearch subroutine returns (λ, v, ∅) that satisfies Case 1 of Main Lemma 1. Proof. The latter is guaranteed by line 3 in BinarySearch, and the former is implied by the latter because We also establish the following invariants regarding the values λ i . (Proof in Appendix F.) Compute v such that v + (H + λ i I) −1 g ≤ε. 6: 10: Let Power Method find vector w that is 9/10-appx leading eigenvector of (H + λ i I) −1 :

19:
Flip the sign of v min so that g v min ≤ 0.
• We now verify Case 1 and 2 in the assumption of Main Lemma 1. At the beginning of the algorithm, our choice λ 0 = 2B ensures (using Proposition 5.3) that L (H + λ 0 I) −1 g < 2λ 0 . Let us now consider the various places where the algorithm outputs: -If FastCubicMin terminates at Line 7, then we have v + (H + λ i I) −1 g ≤ε and additionally Therefore, the output meets Case 1 requirement of Main Lemma 1 with λ = λ i .

A Computing Hessian-Vector Product in Linear Time
In this section we sketch the intuition regarding why Hessian-vector products can be computed in linear time in many interesting (especially machine learning) problems. We start by showing that gradient can be computed in linear time. The algorithm is often referred to as back-propagation, which dates back to Werbos's PhD thesis [35], and has been popularized by Rumelharte et al. [31] for training neural networks. The claim follows from simple induction and chain-rule, and is left to the readers. In the training of neural networks, often the size of circuits that computes the objective f is proportional to (or equal to) the number of parameters d. Thus the gradient ∇f can be computed in time O(d) using a circuit of size d.
Next, we consider computing , v be a function from R d to R. Then, we see that if suffices to compute the gradient of g, since We observe that g(x) can be evaluated in linear time using circuit of size O(d) since we've shown ∇f (x) can. Thus, using Claim A.1 again on function g, 5 we conclude that ∇g(x) can also be computed in linear time.

B Proof of Lemma B.1 and Corollary 4.1
Proof of Lemma B.1. Let us denote by g = ∇f (x t ) and H = ∇ 2 f (x t ) in this proof. We begin by proving the first order condition. Note that we have They imply where x uses (B.1) and y uses (B.2).
We compute the norm of the gradient at a point x t + h for any h ∈ R d : where z follows from the Lipschitz continuity on the Hessian (2.1). This proves the first conclusion of the lemma. 5 We assume here that the original circuits are twice differentiable As for the second-order condition, we first note that for all h ∈ R d , by the Lipschitz continuity on the Hessian (2.1), we have because if two matrices A and B satisfies A−B ≤ p, then it must satisfy λ min (A)−λ min (B) ≤ p as well. We consider two cases: if λ min (∇ 2 f (x t )) ≥ 0, then we have Otherwise, we consider the case where λ min (∇ 2 f (x t )) = λ min (H) < 0. Let ν d be the normalized eigenvector corresponding to λ min (H), and definẽ We calculate m t (h) as follows: where x uses ν d Hν d = λ min (H) < 0, and y uses the assumption that λ min (H) < 0. Since by definition m t (h * ) ≤ m t (h), we can deduce from inequality (B.7) that Now we put together inequalities (B.5) and (B.8), and obtain  Since we also assume ∇m t (h ) ≤ ε 2 , we have from Lemma B.1 that For the second-order condition, we can again apply Lemma B.1 to get

C Proof of Lemma 5.1 and Corollary 5.2
We begin by proving a few lemmas that characterize the system of equations.
Lemma C.1. Consider the following system of equations/inequalities in variables λ, h: The following statements hold for any solution (λ , h ) of the above system: • There is a unique value λ that satisfies the above equations. λ is such that λ ≥ −λ min (H).
• If λ = −λ min (H) then g v = 0 for any vector v belonging to the eigenspace corresponding to λ min (H). Subsequently we also have that the corresponding h is of the form for some γ and v in the lowest eigenspace of H. We will now prove the uniqueness of λ by contradiction. Consider two distinct values of λ 1 , λ 2 that satisfy the system (C.1). If both λ 1 , λ 2 > −λ min (H) we get that Now note that (H + λI) −1 g is a strictly decreasing function over the domain λ ∈ (−λ min (H), ∞) and 2λ L is strictly increasing over the same domain. Therefore the above two equations cannot be satisfied for two distinct λ 1 , λ 2 > −λ min (H) which is a contradiction. Suppose now without loss of generality that λ 1 = −λ min (H). Then we have that the corresponding solution is of the form h = −(H + λI) + g + γv for some γ and v in the lowest eigenspace of H and g has no component in the lowest eigenspace of H. It follows that (H − λ min (H)I) + g ≥ (H + λI) −1 g for any λ > −λ min (H). By a similar argument as in the first case, we can now see that the following conditions, cannot both be satisfied for λ 2 > λ 1 = −λ min (H), giving us a contradiction. This finishes the proof of Lemma C.1.
Lemma C.2. Let (λ, h) be a solution of the system (C.1). Then we have that Proof of Lemma C.2. By the definition of the system (C.1), any solution λ, h to the system should be such that there exists some γ such that where v 0 is in the null space of H + λI if it exists; otherwise γ = 0. This gives us the following: The objective value in this case is given by Proof of Lemma 5.1. We first compute that For the forward direction, suppose h * is a minimizer of m(h). Let λ * = L 2 h * . Then, the necessary conditions ∇m(h * ) = 0 and ∇ 2 m(h * ) 0 can be written as From this we see (H + λ * I)h * = −g and h * = 2λ * L , and the only thing left to verify is H + λ * I 0. Note that if h * = 0, then the second inquality in (C.2) directly implies H + λ * I 0. Thus, we only need to focus on h * = 0. We want to show that w (H + λ * I)w ≥ 0 for every w ∈ R d . Now, if w h * = 0 then this trivially follows from (C.2), so it suffices to focus on those w that satisfies w h * = 0.
Since w and h * are not orthogonal, there exists γ ∈ R\{0} such that h * + γw = h * . (This can be done by squaring both sides and solving the linear system in λ.) Squaring both sides we have Now we bound the difference where x and y follow from (C.2) and (C.3), respectively. Since h * is a minimizer of m(h), we immediately have and we conclude that (H + λ * I) 0.
For the backward direction, we will make use Lemma C.1 and Lemma C.2. First we note that the function m(h) is continuous and bounded from below, and there exists at least one minimizer h * . Suppose now there exists a λ * and a corresponding h * such that (λ * , h * ) is a solution to the system C.1. The backward direction requires us to prove that h * must be a minimizer of m(h). By Lemma C.1 we get the following two cases.
We prove the backward direction by showing that the conditions in Equation C.2 determine the minimizer up to its norm. To this end we will use Lemma C.1 and Lemma C.2.
First we note that the function m(h) is continuous, bounded from below, and tends to +∞ when h → ∞, so there exists at least one minimizer h * .
Suppose now there exists a λ * and a corresponding h * such that (λ * , h * ) is a solution to the system (C.1). The backward direction requires us to prove that h * must be a minimizer of m(h). By Lemma C.1 we get the following two cases.
• If λ * > −λ min (H) then (λ * , h * ) is the only solution to the system (C.1). By the proof of the forward direction we see that any minimizer of m(h) must satisfy system (C.1) and therefore h * must be the minimizer.
• If above is not the case, then λ * = −λ min (H). Let h be any minimizer of m(h). Lemma C.1 and the proof of the forward direction ensures that (λ * , h ) also satisfies the system (C.1). By Lemma C.2 we get m(h * ) = m(h ) and therefore h * is a minimizer too.
We begin by showing the first equivalence. To see the backward direction note that if λ * > λ > −λ min (H), by the characterization of λ * in Lemma C.1 we have that (H + λ * I) −1 g = 2λ * L i.e. p(λ * ) = 0 which implies that p(λ) < 0 as p(y) is a strictly increasing function. For the forward direction note that since p(y) is continuous and strictly increasing we see that the range of the function contains [p(λ), ∞). Since p(λ) < 0 there must exist a λ * > λ such that p(λ * ) = 0 which by the characterization in Lemma C.1 finishes the proof. Now we will prove that p(λ) > 0 ⇐⇒ λ * < λ. To see the forward direction note that if λ * ≥ λ then p(λ * ) = 0 and p(λ) > 0 which contradicts the fact that p(y) is strictly increasing. For the backward direction we consider two cases. Firstly if λ * > −λ min (H) the conclusion follows similarly by the monotonicity of p(y). If λ * = −λ min then by Lemma C.1, we have that g has no component in the lowest eigenspace of H and therefore if we extend p(y) to −λ min (H) by defining This also implies (using our assumption onε) Next, consider the value m(v) We bound the two parts on the right hand side of (D.2) separately. The first part Above, inequalities x and z use the assumption onε in (6.1), and inequality y uses Note that (H + λ * I) −1 0 by Equations (D.1) and (6.2). The second part of (D.2) can be bounded as follows Above, inequality x uses λ * ≤ B (owing to Proposition 5.3) and our assumption onε from (6.1). Putting these together we get that

D.2 Proofs for Claims 6.2 and 6.3
For notational simplicity, let us rotate the space into the basis in the eigenspace of H; let the i-th dimension correspond to the i-th largest eigenvalue λ i of H. We have λ 1 ≥ λ 2 . . . ≥ λ d = λ min . Let g i denote the i-th coordinate of g in this basis.
where we denote by We begin with a few auxiliary claims.
Proof of Claim D.1. We compute that Above, x uses (D.5), and y follows because we have λ min (H) ≤ − 1 κ in the assumption and have λ * ≤ −λ min (H) + 1 κ in the assumption of Case 2 of Main Lemma 1. Let us now consider the value of the vector λv min 2L . We have that Above, x is because our assumption λ min (H) ≤ − 1 κ and assumption v min Hv min ≤ λ min (H) + 1 10κ together imply v min Hv min ≤ λ min 2 . y follows from λ min (H) ≤ − 1 κ and λ ≤ −λ min (H) + 1 κ . Now, recall that the sign of v min is chosen so g v min is non-positive, and therefore by our assumptions λ min (H) ≤ − 1 κ and λ ≤ −λ min (H) + 1 κ , we get the following inequality: We also show the following lemma, the proof of which can be seen from inequality (D.3), as part of the proof of Claim 6.1 above.
Therefore, the sum S 1 satisfies (Note that we have H + λI 0.) This finishes the proof of Claim D.3. Proof of Claim 6.2. We derive that  Proof of Claim 6.3. This time we lower bound S 2 slightly differently: where x comes from the second to last inequality from (D.7) and y comes from λ * ≤ λ ≤ −λ min (H) + 1 κ ≤ 2 κ using our assumption in Case 2 of Main Lemma 1. Putting these together we get that Above, x comes from (D.4), y uses Claim D.3, lower bound (D.10) and 2(λ * ) 3 3L 2 ≤ 16 .
If Case 2 occurs, we have Above, inequalities x and y both use the assumptions of Case 2; inequality z uses λ ≤ −λ min (H)+ 1/κ from our assumption of Case 2 as well as −λ min (H) ≤ λ * which comes from Lemma 5.1; inequality { uses h * = 2λ * L from Lemma 5.1 as well as our assumption (6.1) onε. The quantity ∇m(v) can be bounded in an analogous manner as Case 1: Above, inequality x uses our assumption (6.1) onε; inequality y uses λ ≤ λ * + 1 κ which appeared in (E.2); inequality z uses (E.1). This is true at the beginning. In each of the follow-up iterations, if we have set λ 1 ← λ mid then it must satisfy L v + Lε ≤ 2λ mid but this implies L (H + λ mid I) −1 g ≤ 2λ mid according to triangle inequality and v + (H + λ mid I) −1 g ≤ Lε; similarly, if we have set λ 2 ← λ mid then it must satisfy L (H + λ mid I) −1 g ≥ 2λ mid .
Then, at this iteration when v is computed to satisfy v + (H + λ mid I) −1 g ≤ε/2, we also have 2λ mid − Lε ≤ L v ≤ 2λ mid + Lε which means BinarySearch will stop in this iteration. In sum, we have concluded that there will be no more than O log( (λ 1 −λ 2 )B c 1 ·L·ε ) iterations.