Balancing Gradient and Hessian Queries in Non-Convex Optimization
Authors: Deeksha Adil
Brian Bullins
Aaron Sidford
Chenyi Zhang
Venue: NeurIPS 2025 poster ()
Keywords: non-convex optimization
critical point
gradient query
Hessian query
dimension-dependent method
Primary area: optimization
TL;DR: We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function

Abstract: We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function. We provide a method that for a twice-differentiable $f\colon \mathbb{R}^d \rightarrow \mathbb{R}$ with $L_2$-Lipschitz Hessian, and input initial point with  $\Delta$-bounded sub-optimality and sufficiently small $\epsilon > 0$ outputs an $\epsilon$-critical point, i.e., a point $x$ such that $\|\nabla f(x)\| \leq \epsilon$, using $\tilde{O}(\Delta L_2^{1/4} n_H^{-1/2}\epsilon^{-9/4})$ queries to a gradient oracle and $n_H$ queries to a Hessian oracle. As a consequence, we obtain an improved gradient query complexity of  $\tilde{O}(d^{1/3}L_2^{1/2}\Delta\epsilon^{-3/2})$ in the case of bounded dimension and of $\tilde{O}(\Delta^{3/2} L_2^{3/4}\epsilon^{-9/4})$ in the case where we are allowed only a single Hessian query. We obtain these results through a more general algorithm which can handle approximate Hessian computations and recovers known prior state-of-the-art bounds of computing an $\epsilon$-critical point, under the additional assumption that $f$ has an $L_1$-Lipschitz gradient, with $O(\Delta L_2^{1/4}\epsilon^{-7/4})$-gradient queries.

Balancing Gradient and Hessian Queries in Non-Convex Optimization
Deeksha Adil" Brian Bullinst Aaron Sidford Chenyi Zhang
Abstract
We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non- convex function. We provide a method that for twice-differentiable f: Rd with Læ-Lipschitz Hessian, input initial point with A-bounded sub-optimality, and a sufficiently small e > O, outputs an c-critical point, i.e., a point x such that 1/2 -9/4) queries to gradient oracle and n
IV f+))] E, using Ó 1/4 RH
queries to Hessian oracle. As a consequence, we obtain an improved gradient query complexity of 0 - -3/2) in the case of bounded dimension and of Ō 3/44 -9/44 in case where we are allowed only single Hessian query. We obtain these results through more general algorithm which can handle ap- proximate Hessian computations and recovers known prior state-of-the-ar bounds of computing e-critical point, under the additional assumption that has an Li-iissciitz gradient, with O L/// 7/4) gradient queries.
Introduction
We consider the problem of computing an e-critical point of a differentiable function f: IR + R. that x with [[=](])] S c, given an initial point E IRd with bounded function error or sub- optimality, A = ((x(0)) - inf f(x) This critical point computation problem-also referred as making the gradient well-studied optimization problem. is ubiquitous in machine learning research and has been studied extensively for decades; see e.g.. [0 for references.
small 2 33
finding stationary points Di-is foundational and
Obtaining an e-critical point is natural stopping condition for many optimization methods. For general smooth non-convex functions, guarantees of this type-as opposed to reaching globally provably established without incurring exponential dimension dependence in the rates [10 I1). Furthermore, there even instances of non-convex objectives, such regression tasks with non-cone non-convex regularization [3] and matrix completion [2]] for which reaching what is which generalize e-critical points-suffices to
optimal point-mel
known a second-order critical point 9 26 27 establish global optimality.
In certain foundational settings, optimal query complexities for critical point computation are known. For example, consider the following simple variant of gradient descent, c.g.,
1 (z)(()))
L 1|x(00 x]|
(t)
argmin T (x)
L
IIstitttee for Theoretical Studies, ETH Zürich deeksha. adi feill@eth-its ethz. ch
1 Department of Computer Science, Purdue University bbullinssnaa wwwllliisnuuuue...m edu
$ "Stanford University {sidford, chenyiz)(stanffrre
Preprint available at 215 10.20786
"Throughout the paper let I-ll denote Euclidean norm, and when applicd to square matrix, we let it denote the f2-operator norm, i.e., |||||| supzeg |||||//|| for all A E gdxd
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where T (0))()) (z) is the pth-order Taylor approximation of f evaluated at 2(() and f is Lm-sthhth, Le., has L1 Li-Lisschitz gradient where [V[(x) vf(i)l Lı|= 1 yا for all 2, y E RR. Eq. ①] computes an e-critical point with at most OLLi iterations [32]. and it is known that for sufficiently large d. any method (even a randomized one that succeeds with high probability) must compute at least (LL gradients in the worst case [TQ]. More broadly, for I that has Lp- Lipschitz pth-order derivatives define a pth-order oracle one that when queried point x returns all partial derivatives of f at up to order p. It is known that the method
x (1+1) t argmin z(1) (z) + copp||=(0) - 2| 11|2t1
for suitable choice of constant cp > 0, solves the problem in Oc ( Aet(t/eee//) queries and iterations [7]. and these rates are optimal in terms of dimension dimension-independeen query complexity [TO].
Unfortunately, the faster rates for critical point computation obtained via higher-order oracles, e.g.. pth-order oracles, generally come at a cost. Simply specifying the output of a pth-order oracle at point involves outputting d' numbers in the worst case, which even for small constant p can be prohibitively expensive when the problem dimension is large. Correspondingly, there has been 34] on what rates are obtainable given various assumptions on and access only to gradient oracle, i.e., an oracle that when queried at x E R outputs V f(x), the gradient of f at x, and a Hessian oracle, i.e., an oracle that when queried at x E Rd outputs æ. One particularly relevant line of work has shown that with only gradient oracle for f that has I Lipsiisciitz gradient and L2- Lz-Lhipschtz Hessian, it is possible to obtain 1/2
extensive research D1 10 II
(1)( the Hessian of
rate of ((L) L2 1/4 De 7/4) Ae if 0 < e S min 2//3 L [ 29], and [[]] provided an
Q(L3/TT 12 Ac-12/7) lower bound for this setting. In other words, when the Hessian of the function is also Lipschitz continuous, it is possible to improve upon the O(L, Ac-)) query complexity of gradient descent. Meanwhile, if we further allow for querying Hessian information, this rate can be improved to O 12 A3/322
which is optimal under this stronger oracle model 10
In this paper, we perform a more fine-grained study of the problem of critical point computation. We ask, what trade-offs are possible between the number of gradient and Hessian computations that are needed to compute e-critical points for functions with L₃ Li-Liihchitz gradients and Li-Lipschitz Hessians? ? Our main result is an algorithm which offers new such trade-off, even when the Hessian computed only approximately. Furthermore, we show that this result generalizes the bounds of 29 and yields further improvements in dimension-depender settings.
1.1
Our Results
Our main result is new trade-off in the number of approximate Hessian oracle queries and gradient queries for f needed for e-critical point computation. Here we define the approximate Hessian oracle we consider and provide our main theorem.
Definition (Approximate Hessian Oracle), We call a procedure a d-approximate Hessian oracle for twice differentiable f Rd + R if when queried at x E Rd it outputs symmetric H. E gaxd such that 11 (²f(z) S 8.
Theorem (Main Result), Let f: Idd + R have L1 Ln-Lipschitz gradient and Lz-Lipschitz Hessian.
There is an algorithm which given any 100) E Rd with A A--buuded sub-optimality with respect to positive integer nh, and 0 <<< min(I] 2 11/33, outputs an e-critical point of f with at most RH queries to a δ-approximate Hessian oracle and at most
AL 1/2
C8
CF
O
2/4 poly log
queries to a gradient oracle for f. where
AL2 nHE
L3A3
A 2
Cs min L
and == min L1,
+
e
As outlined in our overview in Section 2 Theorem follows from a careful combination of Theorem S respectively.
and Corollary 2 which characterize Algorithm 2 and Algorithm 3
In the remainder of this section we compare this result to previous studied problems and discuss its implications.

---

Generalizing Prior Gradient Methods. First, we note that Theorem ! recovers known prior results on gradient-only methods. Observe that V2 f()]] S L1 if and only if has an -Liischhitz gradient, and consequently, an Ia appproooeee Hessian oracle for f can be implemented with no queries, by simply outputting the all-7ero matrix. In this case, the approximation error is ő = IT, which leads to computes an e-critical point using O 1/2 L De Ae-7/4) queries, which matches the prior best known (
C = T1- Thus, as a corollary of Theorem
|
we obtain method which
algorithms in this setting [ 9 29]
Seadient-Hessiare Trade-offs for Functions with Unbounded Smoothness. Interestingly. our results apply even without bound on L1- In this case, it follows from Theorem I that, with exact Hessian queries, i.e., when 8 = 0. it is possible to obtain methods that compute é-critical point with
-1 112 ny Hessian queries and 3/2 / nH 1011///0///// e09/4) gradient queries Excitingly, this result shows
is possible to compute an e-critical point with only single Hessian query and Ó(A3/2 Ly 3/4 --9/4) gradient queries. The previous best algorithms this setting are essentially due to Doikov et al. [[]. Though their paper studies different setting, their results seem imply an e-critical point with n Hessian queries and 2 23 gradient queries, and so for a single Hessian query, we improve these results, up to polylogarithmic factors, by a factor of O(A
Dimension-Dependera Critical Point Computation. As another application of Theorem I we obtain improved bounds on the number of gradients needed to compute critical point of functions where d, the dimension, is bounded. Specifically, we note that by a finite differencing argument (e.g.. L/2 Lemma 3 in [23 for h = 2 L ). a 6-approximate Hessian oracle for f can be implemented with just 2d queries to gradient oracle by approximateing each column of the Hessian using by finite differences and wo gradient queries. Applying this fact with Theorem I and optimizing over the choice of пи yields the following corollary.
Corollary 1. Let f: H& R have Li-Lipschitz gradient and Lx-Lisschitz Hessian. There is method which given any (U) E Rd with A-bounded sub-optimality with respect to I and 0 < S m 2//3 L 1/3,, outputs e-critical point of f with most (dd 13 Li De 3/2 + d) queries to a gradient oracle for f.
Interestingly, while optimal query complexities are known for the low-dimensional d = 15] and 2 cases- the latter following from the more general (mmax{2* (2d c 2d/(d+)))) query com- plexity results of Vavasis [37]- for d 2 7, our results improve, up to polylogarithmic factors, upon the previous state-of-the-ar dimension--dependen bound of O O(vālzAAe
for this problem [18]
for any e S m LZ 2/33 L ///3). In addition, we improve upon the O(L ( 1//aa""""""" -7/1) bounds of Li and Lin (29] for e s min O (5 d
This expands the range of for which the rate of (29 can be improved over 18] which offers improve- ment when s 0(L3 -d 2); see Table I for details. Work by Jiang et al. [25] also provides dimension-dependdnnt results of O(d 1/4 L,3/
A A 13/8) gradient queries under the additional assumption that < AL2 LI. However, as shown in Appendix B for any d 2 and S
min min 1..1,,200 2/3 1//3 AL }, this is always at least the minimum of O( -3/2 -3/2+d) 18
and ( T 1/ -744) 29
It remains unclear whether our bound, particularly the d dependence, is asymptotically opti- mal. Although there are relevant lower bounds in the camension-independeeee cimension-dependeee complexity of critical point computation is still not well understood: Existing dimension-depentee lower bounds apply only to low-dimensional settings and do not have Hessian Lipschitzness assumptions, e.g., [15 24]. The development of tight lower bounds in regime as an independent and interesting open problem.
setting [10 IT. the
While not the focus of the paper, we briefly comment on the computational complexity of our algorithm. Each iteration involves an approximate eigendecomposition step, which may seem more involved than the computation in the classical Newton method, where dense linear system is solved in each iteration. Nevertheless, in the worst case, can be implemented in O(d)) time, where w
'e use Ō(-) to hide polylogarithmic factors in nu, max (L, 1 max/A, A A1), maxx(e,c=!) and 6.
3

---

Algorithm
# Gradient Queries
Assumption
Vavasis 37
0 + c O 1/ AE
L
Li & Lin 29
Li L2
Nesterov & Polyak
O(dv/A2e -3/2)
In
Doikov et al. 18
O(vdL2Ac- 3/2 172+00 +d)
L2
O 1//88 - 11/88/8
Jiang et al. 25
L1, Lz
Corollary 1 (Ours)
O -1 Ae 3/2 + d)
L2
Table 1: Comparison with previous results in terms of the number of gradient queries needed to reach an e-critical point, i.e., [(=) e, under Lı-Lipschitz gradient, Iz--Lipschitz Hessian assumptions, for
0 < min A L This standard range of to consider noted in [8. If L
gradient descent achieves better query complexity. If A 2/3 r. our algorithm halts after most single iteration and makes at most (dd//a) queries. Up to polylogarithmic factors, results improve upon 29 when / /2/²)
S min(O(L) 8/2 L2 1/3)) L A
and upon [8] for any I min [ii A L 1/3
denotes the matrix multiplication exponent Newton method.
This is the same as the per-iteration cost of the
Additional Related Work. The efficiency of critical point computation has been explored in a wide variety of non-convex optimization contexts and settings, some of which we now highlight. Although this work is concerned with exact gradient information, there has also been significant effort in understanding optimal complexities when instead given access stochastic oracles 4
2.
20 22 40). In addition, other works have considered methods based on alternative structural assumptions, such as a type of graded non-convexity [19, a particular spectral decay the Hessian [30] or, in the case of non-smooth non-convex objectives, relaxed notions of approximate
3 5 6
critical points [6
28 36 39). There is also a broader literature related to general Taylor descent
algorithms
7 10 including works that focus on efficient and adaptive methods [13 14
2 Our Algorithms
Our approach is inspired by the advances in obtaining O(L)/2 レ3 AE 7/44 rates over the last few years [ 9 29 In particular, algorithm builds on the work of [29], which proves that can apply accelerated gradient descent with restarts to obtain improved rates. Our algorithm uses a similar method, but works with norm induced by computations of the approximate Hessian H. In particular, we work in the norm induced by o(H) where ó is a carefully chosen function which returns a symmetric matrix. We show that by applying their method in this carefully designed norm and recomputing the Hessian intermittently, we obtain our result.
First, in Section 2.1 we present variant of accelerated gradient descent (Algorithm I. This is similar to the algorithms of 29 without restarts, but in the norm induced by H o(H) (Eq. 2). We prove that with single Hessian computation and a bounded number of gradient computations, the algorithm either finds critical point significantly reduces the function value (Theorem 2
Second, make use of this result, we either perform negative curvature descent whenever the approximate Hessian H has sufficiently negative eigenvalue, apply restart strategy similar to (29). (Algorithm 2). Our algorithm additionally keeps track of the movement the iterates and when the movement is too large, recomputes the approximate Hessian H/ and the corresponding H. In Section 2.2 we analyze Algorithm 2 which essentially obtains main result up logarithmic factors (Theorem 33
Unfortunately, the logarithmic factors for Algorithm (ecchmmm@@pppee depend on L1. Interestingly, we show that there is a fairly generic procedure that allows us to remove this dependence with at most one additional Hessian computation. In Section 2.3 prove general reduction that given an algorithm that finds critical points for a function with L Li-Lipschizz gradient and Lg-Lipschitz Hessian, there is an
'This result holds under the additional assumption that O(ALz/Li). See Appendix B for detailed
comparison between this work and [8] 29

---

algorithm that uses one additional Hessian computation and finds a critical point for any function with only an Li-Lisschizz Hessian (Theorem ( Finally, with all of these tools in hand, we prove our main result, Theorem Several proofs are deferred to the appendix.
2.1 Critical Progress using Approximate Hessians
In this section, we describe the core subroutine of our critical point computation algorithm,
Critical-or-Progress which is version of accelerated gradient descent (Algorithm [T. This
procedure either finds an e-critical point or decreases the function value by at least (/ L2 1/2) Sup-
pose that we are given _0)), 6-approximate Hessian at (²(), such that |_ (z)()( s 8,
and additionally 2577 go 3 I. Let the spectral decomposition of H Hg be
H2
f=1
where (li.... haj is an orthonormal basis. Define
á = o
(2)
where
[log2 (L1/
o(A) = (328 + [A]
(3)
[log2 max [A], 20)
We consider an algorithm that performs AGD in the norm induced by H, as shown in Algorithm The parameters used in Algorithm Mree chosen as follows.
Pmax max
==
17 = 4'
p
(4)
K v8
B
32 L
(ZL2)
Algorithm 1: Soweiccal-o--Pooreee
Input: initial iterate (0)),, a 6-approximate Hessian Hz,,, target accuracy e, gradient Lipschitzness L,, Hessian Lipschitzness L2;
Initialize x(-1) ()));
3 Set A according to 2 and set B,0, K according to (4)
for k 0,... ..... K do
(K) (k) + (1 0 (z) (((-1));
(k+1) + (0) n Å (y
if k-1 1/22 2 (x+1) x(())) 1| 126 B² then Output out (N)
Ko + argmin 3x ك K
11 2/2 (2(6+1) - (())
Output oot
Ko Dk=lK/20 [ ((A)
Ko 1o+l- - K/2)
The main result of this section is the following Theorem 2 which shows that Algorithm single query to d-approximate Hessian oracle and bounded number of gradient queries for f. either finds an e-critical point decreases the function value by at least (
L using
Theorem 2. Let d < Ln, S 82 L2/L2. and -81 Hz 3 2L,1. Using the parameters in
Algorithum 7 makes query to a 8- --approximate Hessian oracle and at most K queries to a gradient oracle for I and outputs out E Rdd with I|æzut [0(0 || < 7B such that either out is c-critical for
or
) f() < -L 11112/2/ -L 1122 -12 3/2
1222122
Pmax
5

---

For any 2, y. E RR, define the variables = -/11/x,, ÿ = H and the function in the norm induced by H.
f(8) = F(H
(5)
which satisfies
- v (1(()-1/22)
(6)
In this norm induced by H, the updates in Line and Line of Algorithm
become
g(k) -- (b) + (1 () - 1))- ((++1) + g( V (()(()))(()))
which are similar to the standard accelerated gradient descent updates.
The proof of Theorem proceeds by analyzing whether the "if condition" in Line 7 triggered. In the case where the iterates move relatively far in K iterations and the "if condition" is triggered, using a similar proof strategy as [29], we demonstrate that the function value must have decreased by at least 12(1.22/2 3/2). (//2),1//////))
On the other hand, in the case where the iterates stay relatively close
to x and the "if condition" is not triggered, we show that averaging over several iterates yields point with a small gradient. This part of the analysis is more intricate and relies sensitively on the choice of the matrix H. We first establish that Vf(oot,, the gradient of the output measured in the norm induced by H. is small. However, this does not immediately imply that V fa( is small. To bridge this gap, we leverage the specific structure of H defined in (2). where spectral gaps are intentionally introduced through the use of piecewise function defined its construction. Using results from matrix perturbation theory, show that this construction guarantees that the eigenvectors of 2 fz: with large eigenvalues is nearly identical to that of H and fzx(2)))). Consequently, we can bound the component of Vz( in the strongly convex subspace using the corresponding component of V f( and analyze the component in the non-strongly convex subspace similarly.
2.2 Restarted Approximate Hessian AGD
In this section, we present our main algorithm, Algorithm 2 In each iteration, Algorithm 2 maintains a Hessian estimate of V (x(()) with bounded error. If the estimate has a negative eigenvalue smaller than -35, we identify direction of negative curvature and update along it. Otherwise, we invoke Pritical-or-Progee
(Algorithm I] and set its output as the next iterate. We show that if ((++1) not an e-critical point, the function value decreases efficiently. a result, the algorithm finds an e-critical point in a bounded number of iterations.
The Hessian estimate Algorithm 2 is maintained via lazy updates. initializes with (0) as the reference point è and sets the Hessian estimate to Hz Whenever the current iterate (²)) moves more than threshold Rt away from we update the reference point (1)) and the Hessian estimate to Hg Since f has an Lu-Lipschitz Hessian, the error of the Hessian estimate is bounded by max max(2L,, L2 in each iteration.
The parameters in Algorithm are chosen as follows.
3A
L
R +-
log
8 3T2 (nnc) + 16
THE
(8)
5 min L2R, 2L1).
$ max [log(L1/))),
The following theorem shows that Algorithm outputs e-critical point using bounded number of queries to d-approximate Hessian oracle and gradient oracle.
Theorem Let f: RRd + have Ia -ipschitt gradients and Tog-Lipschitz Hessian. For any
(0)) E [R with A-bounded sub-optimality with respect f, positive integer ng, and 0 e

---

Algorithm 2: -pppaarted-Aproo-HHeee -essiann-sii
Input: initial iterate x (0) accuracy of the approximate Hessian oracle 6, target accuracy gradient Lipschitzness L1. Hessian Lipschitzness L2;
2 Initialize <- x0() .. +- H;;
for i == 1, do
if V S then Output z!0;
(1:)) I 2 R then - x((( and H <- Ha:
H < 35I then
Choose unit vector E Rdd such that v T TH S -25 and (v, Vf(x())) s 0:
x((+1) + x( Rv
else ((++1) Prrtical-or-Progressse H, L1, L2);
m Algorithm 2 outputs an e-critical point with at most ng queries to 22/3
5-approximate Hessian oracle and al most
20L2 1/22
1/2 C8
[1
log!
18
16
c7/4
C8
queries to gradient oracle for f, where
AL
es == min L1, d
nHE
The following describes the change in function value in every iteration Algorithm 2 and useful for proving Theorem 3 Lemma 1. Suppose e S L2 In euch iteration of Algorithm before il terminates, we have f(xl(+1)) (xx(0)) 55112 V
if (1+1) is not e-critical for f, where we denote p = max {
[oo (00gg(1//)11 16)
D before Algorithm 2 terminates, in each iteration the function value decreases by least 5-12 L2./L2. Hence, Algorithm terminates in at most 5 A / Lg/e3 iterations. From Theorem 2 the number of gradient queries in each iteration is at most
Proof of Theorem 3 By Lemma
V8:8
K
(L2e)
Therefore, the total number of gradient queries is at most
Ta V8 AT.
2818AT,
1/1
Al2
p12 A 3 (Lze)1/4
min 12,5 5
7//
nhe
2 1/4
AL2
L + 16
min L1,8
log 18
J/1
n1e
2A 1/4
Al2
La
min L1,8 8
nge }
log
18
+ 16
c7/
given that C5 < 8. Furthermore, from Theorem
and 4). in every iteration t we have
(1=00)1))==)) - 20 < 3 L2
Therefore, the number of Hessian computations is at most
7 c
3 L
which is at most ny when using the values of the parameters in

---

2.3 Removing the L1 -i-Liscchizz Gradient Assumption
In this section, we give an algorithm that computes an e-critical point for functions with Ly- -ipLschciitz Hessians but no guarantees on the Lipschitzness of the gradient. In order to do so, we first provide a general reduction point for a function with --p-hipscitzz gradient and Ta-ILisshhtz Hessian, A an approximate critical point for any function with only T--L.ipschizz Hessian while maintaining the number of queries to gradient oracle and using at most one more query to the Hessian oracle, if the output of Alg is not very far away from the initial iterate and has bounded suboptimality.
Algorithm 3 Given an algorithm Alg for computing an approximate critical
compute
For any symmetric M E Rddd with spectral decomposition M = Eje( Aouzy] we denote M = Ejeta T{{ # 0} NUJ be its Mooro-Penrose pseudoinverse, where I[.)) is the indicator function.
Algorithm 3: Reduction To- To-Unnooudedd-Hee
Input: initial iterate (0))) target accuracy c, Hessian Lipschitzness L2;
Choose an eigenvalue threshold E
3 Initialize H + i zot Alg(fse, L, L2, A)e);
5 Output y t rout (IseHllys) V
Given a 8-approximate Hessian Hg with spectral decomposition Hzi = Σj 1 Ayhzh3, where {hi...., ha} is an orthonormal basis, we partition the indices into two sets based on the eigenvalue threshold é picked in Line
Se (i: | {) Sye (i: Ai > 1).
(9)
and define corresponding projection matrices
llkt Σ h llse Σ
hih iESce
(10)
iESS
Moreover, we define the restricted function
+ Ngg(( ()))
(11)
Algorithm 3 begins by invoking the subroutine Alg to find an e/2-stationary point nut of the restricted function fee. It then performs Newton step in the subspace spanned by hy : Szc
f out - (II>:H IIe) V out
using Ho as the approximation of )ur Since ||æ - | < Routs we show that H remains sufficiently accurate estimate. Moreover, L' is chosen large enough so that the size of this Newton step is small. Otherwise it would incur a function value decrease larger than A Auut. contradicting the suboptimality condition of out As result, Vf(v) close to VT 3. (y) since f is -essian Lipschitz, and the latter is at most c/2. Formally, we prove the following:
Theorem 4. Let Alg(f<L. L1, L2, c, be a procedure that, for any function fsm. Rd + + with Li Lipschitzz gradient, Li-Licchhitz Hessian, and b--ouuded suboptimality, uses
* nH queries to 5-approximate Hessian oracle for fsL. and,
* (2,(L,,2,21 8, A, e) queries to gradient oracle for fzL..
and returns an e/ 22-critical point out satisfying Il - x _000|| || S Rout and f( - inf, f(z) < Dout- Then, for any ff with Li-Lippchitz Hessian and A 2-bouuded suboptimality, any S
min(T?T A 2/3 r 1/3 and any that satisfies
1000
(L2Bou + 8)2, 48 24A 1/3 L. 28
Z max
(12)
2
out
Algorithm 3 returns e-critical point using
8

---

HH + 1 queries to a ò-approximate Hessian oracle for f. and,
(l L2, 8, A,E) e) queries to a gradient oracle for f.
The proof of Theorem i in Appendix G Corollary 2 is obtained by running Algorithm where we use Algorithm Ls the subroutine Alg. The proof of Corollary 2 is in Appendix F
Corollary 2. Let f: Rd + R. Lz-Lipschitz Hessian. Given any x0 R with A A-bounded sub-
optimality with respect to any positive integer nn 2 and < S 2 A2/ L 1/3 Algorithm
using Algorithmm2un Jas the subroutine Alg ouiputs an e-critical point of f with at most nhg queries to 5-approximate Hessian oracle and
(
ATg 2/4
Al. nhe
(1
1 c8
A
+8))
Vo+
poly log
2 +
ct
queries to a gradient oracle for f.
2.4 Proof of Theorem
Proof. We consider the following algorithm. When
L243
A6
L S
+
e²
we rum Algorithm 2 which outputs an e-critical point with at most ny queries to 8-approximate Hessian oracle and at most
1/4 2 L
C8
log" 18
L1
16
=0
A
1/4 1/2 A
%
poly log
ct ca)
e/4
2/4
Otherwise, we run Algorithm Jusing Algorithm 2 the subroutine Alg, which outputs an e-critical point of f with at most nH queries to a d-approximate Hessian oracle and
o
(
AL 1/4
AL₂ THE
( c5
)
AL2 1/4 1/2 C8
Ci
7/4
poly log
=
2/4
ppoly log
queries gradient oracle for f. where the last equality follows from the fact that
L3A
A6
AL2
L
2 +
+828+
nHE
and thus Cs = 5 + AL2 We conclude by noticing that the number of Hessian queries in both cases is
age
ng, while the number of gradient queries in both cases is
AL 1/4 1/2
66
Cr
poly log
7/4
C6
3
Conclusion
In this paper we provided new algorithms for computing critical points of twice differentiablee functions using gradient and ò-approximate Hessian queries. We provided general result which offered new trade-off's between the number of queries made to these oracles to compute an e-critical point of functions with -ipischii gradients and Ly-Lipschizz Hessians given an intial point of bounded suboptimality. As a consequence of this result, for sufficiently small c, we recovered known bounds the number gradient queries needed to compute critical points and improved upon the prior state-of-ther the-the-rt bounds in the case where the function is either of bounded dimension or when a single Hessian query is available.
Though our work provides new algorithms and tools for critical point computation, there are several limitations to the result. First, this work is primarily theoretical, no practical implementation or

---

experiments are provided, and in certain cases our bounds incur multiple logarithmic factors. Second, many functions in practice may be con-differentiable or of large enough size that computing the Hessian is prohibitively expensive, limiting the direct applicability of the results. Third, though there are interesting relevant lower bounds [T0] 11, unknown whether our query complexities are asymptotically optimal. Each of these limitations suggests natural open problems and directions for future work, c.g., finding practical applications of our techniques and seeking improved upper and lower bounds for the problems we consider. However, we hope this paper provides valuable tools for this potential future work.
Acknowledgments
Thank you to anonymous reviewers for their feedback. Deeksha Adil is supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. Aaron Sidford was supported part by NSF Grant CCF-1955039, Chenyi Zhang was supported in part by the Shoucheng Zhang graduate fellowship.
References
[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1195-1199, 2017.
[2] Zeyuan Allen-Zhu, How to make the gradients small stochastically: Even faster convex and nonconvex SGD. Advances in Neural Information Processing Systems, 31, 2018.
[3] Zeyuan Allen-Zhu. Natasha 2:
Faster non-convex optimization than SGD. In Advances in Neural Information Processing Systems, pages 2675-2686, 2018.
[4] Zeyuan Allen-Zhu and Yuanzhi Li. Ncon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, pages 37 3716-3726, 2018.
[5] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Srid- haran. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299. PMLR, 2020.
[6] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 195(1):165-214, 2023.
[7] Ernesto G. Birgin, J. L. Gardenghi, José Mario Martínez, Sandra Augusta Santos, and Ph. L. Toint. Worst-case evaluation complexity for unconstrained nonlinear optimization using high- order regularized models. Mathematical Programming, 163(1):359-368, 2017.
[8] Yair Carmon. John C. Duchi, Oliver Hinder, and Aaron Sidford. "Convex until proven guilty": Dimension-free free acceleration of gradient descent on non-convex functions. In International conference on machine learning, pages 653-663. PMIR, 2017.
[9] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 1751)775 2018.
[10] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points Mathematical Programming, 184(1):71-120, 2020.
[1]] 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-33) 2021.
[12] Coralia Cartis, Nicholas I. M. Gould, and Ph. L. Toint. On the complexity of steepest de- scent, Newton's s and regularized Newton's 's methods for nonconvex unconstrained optimization problems. SIAM Journal Optimization, 20(6):2833 -2522,222222222 2010.
[13] Coralia Cartis, Nicholas I. M. Gould, and Philippe L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part I: motivation, convergence and numerical results. Mathematical Programming, 127(2))245-255, 2011.
10

---

[14] Coralia Cartis, Nicholas I. M. Gould, and Philippe L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. part worst-case function-and derivative-evaluation complexity. Mathematical programming, 130(2):295-319, 2011.
[15] Sinho Chewi, Sébastien Bubeck, and Adil Salim. On the complexity of finding stationary points of smooth functions in one dimension. In International Conference on Algorithmic Learning Theory, pages 358-374. PMLR, 2023.
[16) Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. A gradient sampling method with complexity guarantees for lipschitz functions high and low dimensions. Advances in Neural Information Processing Systems, 11:6692-6703, 2022.
[17] James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra stable. Numerische Mathemarik, 108(1):59-99) 2007.
[18] Nikita Doikov, El Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy Hessians. In International Conference on Machine Learning, pages 8138-8161. PMLR, 2023.
[19] Nikita Doikov, Sebastian U. Stich, and Martin Jaggi. Spectral preconditioning for gradient methods on graded non-conved functions. In Proceedings of the 41st International Conference on Machine Learning, pages 1 11227-11252, 2024.
[20] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances Neural Information Processing Systems, 31, 2018.
[21] Rong Ge, Jason Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems, pages 2981-2988 2016.
[22] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-236) 2013.
[23] Geovani Nunes Grapiglia, Max I.. N. Gonçalves, and G. N. Silva. cubic regularization of Newton's 's method with finite difference Hessian approximations, Numerical Algorithms, pages 1-24, 2022.
[24] Alexandros Hollender and Emmanouil Zampetakis. The computational complexity of finding stationary points in non-convex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 5571 PMLR, 2023,
[25] Ruichen Jiang, Aryan Mokhtari, and Francisco Patitucci. Improved complexity for smooth nonconvex optimization: A two-level online learning approach with quasi-Newton methods. arXiv preprint arXiv:2412.02217 2025.
[26] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 1724-17322 2017.
[27] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference Learning Theory, pages 1042-1085. 2018.
[28] Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, and Manolis Zampetakis. Determin- istic nonsmooth nonconvex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 4570-4597 PMLR, 2023.
[29] Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polylogarithmic factor in the in the O774/) complexity. Journal of Machine Learning Research, 24(157): 1-3, 2023.
[30] Yuanshi Liu, Hanzhen Zhao, Yang Xu, Pengyun Yue, and Cong Fang. Accelerated gradient algorithms with adaptive subspace search for instance-fasee optimization. arXiv preprint 2xXiv.2312.03218, 2023.
11

---

[31] Po-Ling Loh and Martin J. Wainwright. Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima. The Journal of Machine Learning Research, 16(1):559- 616, 2015.
[32] Yurii Nesterov. Introductory lectures corvex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[33] Yurii Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, (88):10-11, 2012.
[34] Yurii Nesterov and Boris T. Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
[35] Gilbert W. Stewart and Ji-guang Sun. Matrix perturbation theory. 1990.
[36] Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computation of approximate stationarity concepts of Lipschitz functions. International Conference Machine Learning, pages 21360-21311 PMLR, 2022.
[37] Stephen A. Vavasis. Black-box complexity of local minimization. SIAM Journal Optimiza- tion, 3(1):60-88) 80,0000010 1993.
[38] Yi Yu, Tengyao Wang, and Richard J. Samworth. A useful variant of the Davis-Kahan theorem for statisticians. Biometrika, 102(2):315-323, 2015.
[39] Jingzhao Zhang. Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pages 11173-1111 PMLR, 2020.
[40] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. Journal of Machine Learning Research, 21(103):1 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Refer to the Introduction section.
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 in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Refer to the Conclusions section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" 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 on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Refer to the Theorem statements and the 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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should 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 of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not 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 is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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, as described in supplemental material?
14

---

Answer:
[NA]
Justification:
There are no experiments in the paper.
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
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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).
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
/ cppppi.ccppulli//uuuiu wwwticccguie//eeieeeeeeii CoodeSubeiiieeee ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: 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 to understand the results?
Answer: [NA]
Justification:
There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no experiments in the paper.
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, statistical significance tests, at least for the experiments that support 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).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

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 enrors is not verified.
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 error rates).
If error bars are reported in tables or plots, The authors should explain in 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: There experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs 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 NeurIPS Code of Ethics htap:::///euripss/ http//uuursscccppuiipiee http://....cpp.....ttttttttteeea
Answer: [Yes]
Justification:
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a 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: [NA]
Justification: The paper builds theoretical foundations and has direct societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

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 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 or unintentional) misuse of the technology.
there are negative socictal 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 a system learns from feedback over time, improving the efficiency and accessibility of 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:
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 to 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. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
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 (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee www.ree.wthhhe....c. com/ datasets 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 has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 as the institution conducting the review.
16. Declaration of LLM usage
Question: 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 of the research, declaration is not required.
Answer: [NA]
18

---

Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy htteas/s//eerrippoccc///o/rreerp for what should or should not be described.
19

---

A Overview and Notation of the Appendix
The appendix is organized as follows. Appendix B provides a comparison between
25 and prior
works. Appendix C presents key properties of the matrix H defined in (2). Appendix collects useful results from matrix perturbation theory, which used to analyze the spectral properties
of the matrices appearing in Algorithm| I Then, we give the analysis of Algorithm and prove
Theorem 2 in Appendix The analyses of Algorithm 2 and Algorithm 3 are given in Appendix and Appendix respectively.
Notation. For any symmetrie matrix M R with spectral decomposition M = EyEl 25U507. and any subset S IR. we denote
lss(M) = Σ HM Stozo]
sE[d]
to be the projector onto the eigenspace of M with eigenvalues in S. For any matrix M E R4 xd2, we use (Ad) to denote its smallest eigenvalue. For any two invertible symmetric matrices M, E Raxd that commute, i.e., MN = NM, denote N = MN-1 = N-1M. Moreover, we define
Pmax == max (4r)) 16),
Pmin = 16.
as in
where L, is the gradient Lipschitzness f. For any positive integer p E N+ we define
4 1
p+1
p+1
1 2-
Tp
1 2-
(13)
Pmax
Pmax
and
Sp =
1p 1p
Eps
Vp E N+.
(14)
2p 2f/2Punaxx Pinax
B Comparison Between 25 and Prior Works
In this section, we provide comparison between 25 and prior works 18 and 29 In particular,
25 achieves query complexity of O(d'/4 L33/ Ae na-13/85, with an implicit requirement that
E (( L1). This condition arises from the fact that, in the first displayed equation of [25] Section C.3]. the third term in the bracket needs to dominate the first two. Substituting the choices of D and M specified in [25] Theorem 4.1] yields the corresponding inequality. In the following
lemma, show that within the parameter regime S min / A 2/3 L AL2/L1 L1 the query
complexity of 25 is asymptotically at least the minimum of 18 and
29
Lemma 2. For d, L1, L2, A, e > 0 satisfying
e S min { L2/L2, 23/3 1//3 AL2/L/
we have
min / 3/2 d, [,12 1//2T1//1 A Ac 7/4] = 0 1//1////111/// A 133/8).
Proof. Define
A == V Al 3/2
B = I 2//2 AE 7/4
1/4 1 ////8/111///// Ae 13/8 G= /1
and let á = B/A and d/A. Since G = VAB,
min A + d, B}
(1+u
Vol.
min
G
V0
where
1/2
Vd
12/2
3/4
1/4
3/2
/ VaL 1/4
u
VT.AA
L
3/4
20

---

Using the condition that e I min [ A2/3 1/3 L2 / we obtain
1 S (2,, C3,,
C
L
C2 = L A 1. C3 = 22 L 3/4
L3
When L1 A L2 we have C1 = C2 = C3 = 1. Moreover, since C1 and C2 increase with 1 while C3 decreases,
2/3
min C2, C3} < 1
for all L1, L2, A, and thus S 1/6. Hence,
min + d, B)
1 + 1/6
1+ v3
min OER
V Φ
S V
G
VΦ
2
which gives
minf /dlze 3/2 d, 2 1/4 Ac Ac 7/4] Odd I Ac -11/8).
C Properties of Ā
In this section, we present several properties of the matrix Ā used in Algorithm Let us recall the setting of Section 2.1 We are given H H, 6-approximate Hessian at (0)) that satisfies
|| 22 (I I and -351 Hgw I L1I. Let the spectral decomposition be
12 A
j=1
where (hi...., hab is orthonormal basis. Then, H is defined as
á = o(,
in where
[og (L//6)]
o(A) = (326 + [a])
[log2 max [A], 26}
as in
Lemma 3. For any positive integer p E N+ and any À such that 2P6 < [^] S 2P+18, we have
Ip ((A) Srp
Proof. Given that Φ is symmetric with respect to 0, without loss of generality, we assume À > 0. Then, have
A
1ogg((/0))
p
1 2 (-p-4) Tpr
(A))
1 1 325A
Pmax
Pinax
and
X
[og, (A/8)1
p+1 Pmax 1 2 (p-5) (-p-5) Lp.
(())
1 328A-1
Pmax
Lemma 4. Xo(A) is monotonically increasing for X E [-L1, L1}.
21

---

Proof. Note that X ((A) is a odd function. Therefore, it suffices to prove that
[max X, 26)/6)]
A (-)(A) (326 + +
[log2 (L (L1/0)
is increasing for x E [0, T1], where suffices to check monotonicity of
X [loge (max ( 283/6)1
328 + À
First observe that the function is strictly increasing for any [0, 26). For any positive integer p 2 and any À E [2"5, 2-+11) 5), we have
A loga (max X, 26)/6)]
320 A
328 + X
where
d A.P ) p (320 A) (320 + A)
(328 X) - x
p p-328
0.
dd
326 +
Thus, the function is strictly increasing each interval [2 2 8). Moreover, at each boundary
point À == 2" the function increases from 2-6((p-1) 8
We can thus conclude that A
(A)
32642'8 3264228'
monotonically increasing.
L
Lemma 5. The function o defined in 3 satisfies
min
((A) 2
126pmax-
AE
Proof. Since Φ is symmetric with respect to we only need to consider values [0, +0o). We analyze the function in pieces. For X [0, 26), we have
((A) (328 + A)
[log(228/0] (328 + A) Pmax:
Pmax
which is minimized at À = 0, yielding
((0) = 325 Pmaxx-
For [2 22)) with & 2 1, we have
[log2(A/6]] (328 + A) Pmax
Pinax
((A) = (328 + A)
k
which is minimized at À = 2,, giving
6(2h0) 32 2*
8pmaxx
Hence, we have
32
2* k
(()) min 32, min xE(-z0+oo)
min
6pmax 128
121
Corollary 3. For any symmetric H E Badxd the matrix A defined in (2 satisfies f 2 126pmax
and H = (128pmaxx)
D Tools from Matrix Perturbation Theory and Extensions
In this section, present several useful results from matrix perturbation theory that characterize how the eigenspaces of symmetric matrices change under perturbations. Recall the setting from Section 2.1 where we are given a 6-approximate Hessian H__,)) at the point (0)),, satisfying || |
< 8 and -357 < H. 3 T. Throughout this section, we denote G 4 (x))
Our goal is to show that the spectra of and π G/ -1/2 can be partitioned into (pmaax) contiguous subsets such that, for any Pmin < p S Pmax. the principal angles between the eigenspaces spanned by the p-th spectral subsets of 7 and A additional properties of these cigenspaces, which used in the analysis in Appendix
are small. We also derive several
22

---

D.1 Definition of Projectors
This part includes the definition of a series of projectors that we use to analyze the spectrum of H
and G/f 1//2 Define
I (, (H (H
i 1 26.1 26.1 (Hz
(15)
and
πp = (
(16)
Similarly, define
H = - I 1l 100 Gf- 1/2),
(17)
and
n, = IT Opdpeel (
(18)
Furthermore, we define
base 1T p-1-
(19)
D.2 The Davis-Kahan Theorem
In this subsection, we present the celebrated Davis-Kahan theorem, and provide an equivalent formulation that we use in our paper.
Definition 2 (Principal angles of subspaces). Let V, V. c R be k-dimensional subspaces. The principal angles 01 (V, V), (V, V) between V and V are defined recursively by
(Uzz B2) = arg max "EEV,
(Uz, B5), 0g (V,V) = arccos(uj. ūz);
subject to the constraint
|0 ||ارا| 1, (1) 00 (z), O,
visicj.
Lemma (Davis-Kahan Theorem, see e.g., Theorem of (8) Let M, M Raxd be two symmetric matrices satisfying | - M I forrr some & > 0. For any a b, we use = fui...., U&} and S (U....., {g} to denote the set of normalized eigenvectors of M and M associated with eigenvalues contained in the interval b) and [a -0, E, El, respectively, and denote
V = span(S)), V = span(S)).
Then, if the remaining eigenvalues of M lie outside the interval (a b + 7] we have k = le and
|| sin (0(V, (VVV ?
where
sin (v. V) = diag (sin 01 (V. V)....... sin 0x (v.
(20)
Lemma 7 (Theorem I.5.5 of 335
Let V. V R be k-dimensional subspaces and let II, ñ be their
projectors.
Then, we have
sin @V, F) sin , (V.
where sin (V, is defined in 20
Lemma 8 (Equivalent form of the Davis-Kahan Theorem). Let M, M RRdxd be symmetric
matrices satisfying || M|| < & for some & For any < and y > E, if there are no
eigenvalues of M in intervals [a 7, a) and (b, b + 7). we have k = 1 and
k
k
[| (M) 11 b
(M) = >
2
$ 5
Proof. The proof follows by combining Lemma 6 and Lemma
Intuitively, Lemma and and Lemma 8 states that small perturbation to symmetric matrix leads to only a small change its eigenspaces, provided the corresponding eigenvalues are well separated from the other cigenvalues.
23

---

D.3 Properties of I and I
Proposition 1. For any positive integer p 2 5, we have
| p S 22 222 v/b
Before proving Proposition] T we first present the following two lemmas. Lemma 9. For any positive integer p 2 5, denote
G= 1 H2 1 (1 -1-11; (1 )
with m defined in 15 Then, we have
|| A 1/2 GG- s Ep:
where H is defined in 2
Proof. Given that H coo and H have the same set of eigenvectors, we have
= ( -i; = 0.
Then, G can also be written
G = H
(I f H (I - + (1- - (ī²) = Ho0 + (I - iG Hoo (1-1-11))) (I f,,))
which implies
G G = (G- - (,) (1 - (1-
)11
= 1 Hy,,)) + GG H |1 - f (C Ha:
Therefore,
(
S A 1/2
(G ||
(0) A 1/2| + A 1/2 2 )ī; F 1/2
|| 1/ (G Hg:0o) iī Å 1/2
From the definitions of H and in equations 2 and 3 it follows that Φ(1) 2 128 for all A E [-L, L.J, yielding
| S V 120pmax
8pmax
and
| 17 1// /
p 2P8pmax
Combining these bounds gives
A 10-1/221 Hz:0)) 1 = 111 H )Í, A S
VP
x 2D/ Pmax
and
|| 1/ - Ho 1 A
1/2 1112
<
vp
2 Pmax
Thus, we can conclude that
- <
p
Ep.
20/² Piaxx
Lemma 10. For any positive integer p 2 5, we have
A 112 2 1o) Å- -1/ 2 Lp AT
and
Tp-1.
12pmax
where Ît and H are defined in 15 and 2 respectively.
24

---

Proof. Given that _ and H share the same eigenvectors, the minimal eigenvalue of H 1 oor 11/ restricted to the subspace projected by 11 is bounded below by
min AØ (A) 1p. 23226
established in Lemma Consequently, have
n 1-11/211 1/2 = 1p -1.
By the triangle inequality, follows that
- |
< || 11 1122 2001 11 (1,
+ ||(T - H- Hz)0) -
By the definition of H in (2) and Lemma 3 we have the bound
( 1:0) (T-1
fT;
1 2 (p- -pp-1
Pinax
Moreover, since
| SV [
128pmax
obtain
-- Hoo0) -
- f1) - -
1/--112(0 H. )H-
A 1/2 1/212 ||G - H.:0) S
12pmax
By combining these bounds we can conclude that
[1 - (u-n
-ī]]l S
+ rp-1
12pmax
Proof of Proposition Define
T G= H, + - +
Since H and fi, share the same set of eigenvectors, the basis (hi,..., ha), where the eigenvectors arranged in descending order according to their eigenvalues, the matrix H 111 1/2 takes the following block-diagonal form:
i M 1/2 10) 1-1 1/2
-1/22
(T
By Lemma 10 the top left block has eigenvalues bounded below by 4p. while the bottom right block has eigenvalues bounded above by rp-1 + 12 (Lg2)1 with eigenvalue gap
1p Tp- 12pmnax
Ep-1-
3pmax
Additionally, by Lemma we have the bound
1/ -1 < Ep.
We can then conclude by applying Lemma & which gives
| 11, < 22-2/2 Vp.
25

---

D.4 Properties of i HI, and Hp, IIp
Lemma 11. For any positive integer 2 5, we have
p/2 I 11 s 2/2 Vp.
Proof. Given that
n + 11 p+1 = -T + II p+1 = I,
we have
- 1pp1 || = || Hlttal || s 522-1/2
Lemma 12. For any positive integer > 1, we have
[ī, n S 2/
p/2 Vp.
Proof. Given that
1 + 1Ip + p+1 = 1, I +1p +1, p+1 =1
we have
[ - Hpll S 1p-1 -pp-lllllll + || p+1 nhtlll S 2221122 p/2 vp + 22-1/2 p/2 vD S 2-pp2 Vv.
Lemma 13. For any positive integer p and any ē E IRd, we have
1 p+1 Tp S V8 Pmax |T,
and
| p+l H e|l S V8- Pmax [Tp 5||
Proof.
For the first inequality, observe that
Pmav
11 < Σ
p=p+1
where for each q > p we have
[1 < 2/2
9/2 V9ll 1/1,1
|1pp@||
S 22--//2 9/2 (2(
[
by Lemma Summing over g gives
Puzex
Pinux
22-p/2 ((20+18)
Σ 22-9/2, /(32 + 29) 8pmax
8=
g=p+1
S V Pmax
Therefore,
1 1 Hp S v Pmax |
The proof of the second inequality similar. Note that
Pmaax Σ g=p+1
M IT,
b1|
|
IT, E||
where for each q > p have
| TT, ol| S 22 22--0/2 1/2 V M M |||
IIT, ill 22 p/2
2/2 V // ||T &l
by Lemma II Summing over 9 gives
Ponax
Fmaax
Σ 22-1/2 ((20+18) =
Σ
22- 1332 + 29) 6pmax S Vo.. Pinax.
g
p-
Therefore,
+
II a|| S V8 Pmax [T, 5|1.
26

---

Proposition 2. For any positive integer p 2 5 and any ê E R,, we have
|| I 22/22 Pmax |
and
|| 1T 6 2 |T,
Moreover, we have
A TT,
2
17 n, 2 2 1/22p+1g 1))
Proof. For the first inequality, note that
Pmas
n2O = T + Σ np,
g
which gives
Pmaa Σ
|
| nTp0
1 1p
9 p=p+1
where
1 S |, [, s Vo(2+t18) [I,0
and
Piaa
T,, S Vo Punxx ||T
p=
by Lemma 13 Hence,
| I 20/2 V8 Pmax |T,
The second incquality follows from
v V((2))
| 2 1/ H il 2 11
| 6|| 2
2
As for the third incquality,
II, = II + 11 1- II + 11 p+1 I,,0,
which leads
1 pp
2 1/2 p
i| >
| [
v /0(2++18)
where
H. e||
2
- ||
I, 2 ブ |1,6|
by which we can conclude that
1/2 (T,
2
(22+ 18) Tp
2
27

---

D.5 The Connection between 1/2 and T
In this subsection, we prove the following result.
Proposition 3. For any positive integer p 2 Pmin and any i E R., we have
2-5
(21)
+ p- Pmmx
Denote up = 2 up = 1 8, and ox = //2TTT1+1
p c. Then, we have 1/2 = Up + "p + 2p. up = 0, 21) holds directly. Hence, we only need to prove the case where Up # 0.
The following inequalitie are useful for proving Proposition 3
Lemma 14. For any integer p 2 and any â E R2, the following inequalities hold.
1 6 2 ( (1, /1//
2. [ [1 2-- n/2 v po (2)5) n,
3.
| - أ| s 22 p/-p/2 p 2 8)
8||
4.
| i 11 1 i||
V Pmax
|
5. 1 p+l - 0|| $ V8 Pmax
|
6. | e|| - 2- p/2
2 8)
p+ 8||
7. 1 II 0+ a||
2-- p/2
pol
2P
1+1
8. / p+1 p-1 al| 2 1 15
IT
p+1 /2
Proof. Proof of the first entry:
|| | II oll 2 v (2)8)
IT pl 2 v 6
Vo(220)
H, 8 [ HT)
|T,o0
2
by Lemma 12
Proof of the second entry:
|| |
0,00| S 1 p-1 -
S / 0(205)
s 22 22-p/2 Vp (0-()22)) TT
by Lemma I1
Proof of the third entry:
M fT πT
p- i|| S 1
iT IT p-
S v 0022++10
|| p 8
$ 22-p/2 1/2
v (2 8)
IT
by Lemma 12
Proof of the fourth entry:
0 2 1
H 1/2
Пî [
II.
11/21
2 120 log (L/5)]
IT
2
/ (L/ (L/))
28

---

by Lemma
Proof of the fifth entry:
1
p+l 06 S Vo
Pmax 1
by Lemma 13
Proof of the sixth entry:
1+10 011 S 11 1|( - 11 -1
S 22-P// n/2 ( +1
by Lemma 12
Proof of the seventh entry:
1 1/2
1 - |1171/211
p- -1p-))1
< 221-p/2 1//l////llf////////llpp
by Lemma I1
Proof of the eighth entry:
1/2
bll 2 V /2(2++11) 5)(
II
b11
-|
IT, III T 61)
p+1
((2++88)
p+1
2
by Proposition I
Lemma 15. For any positive integer 2 Pmin and any E Rd, we have
A f HI
a||
2 sin
1 II 1p
Pmin
Proof. Note that
A 11 2 H1, 1
If either H or A V HT 0 equals 0, the inequality holds directly. Otherwise, by entries
1 through 4 of Lemma 14
have
1 0) /1/11/21,, 1I, i1 1/2 1I 611
(A n,, 7 1/2
arccos
16'
which leads to
6 > sin( 166 - , T p |
Lemma 16. For any positive integer p and any 0 E Rdd we have
| p+1
IT El| < || / nT oll-
Proof. By Lemma 13 we have
A
IT. 6 S Vo
Puna |T E||.
Moreover, by entry of Lemma 14 we have
A /2 II
8|1
> V8
Pmax [T, b||
which leads to
1/2
8ll
11, 11, 611
29

---

Lemma 17. For any positive integer 2 and E R,, we have
| ö|| s (2 p/4 Pmax |7 11
Proof.
| I $1 11 + |1 11,0||
||/
p+1
11,
where
A -,
S
22-p/22
p/2 po (6((2)) n,
12-- 11,00
by the first two inequalities in Lemma 14 and
f 1/2
11 0
S v0 Pmax |1
5 Puuax || [1
s 2 V 6(P0)
$ 2 p/4 VPmax
1/2 III
by Proposition 2 and the first inequality of Lemma
14
We can therefore conclude that
| (2 2-4 Pmaxx)
f mp
Equipped with these results, we are ready to prove Proposition
Proof of Proposition 3 Note that M1/26 = 72/2211 i + 11/2111 2.10. By entries 6 through of
Lemma 14 we have
i IT 6l S 2t-1/211
p
indicating that the angle between 11121 1 and the subspace projected by π, is most
arcsin( On the other hand, by Lemma 16 know that the angle between H //1, and the subspace projected by 01, is at least 7/4, which leads to
||/1/22||| = -/20 II, 1 + 11
2 1 6|
sin
π
2 2-
2
Pmin
by Lemma 15 Then by Lemma 17
we can conclude that
2-5
1//2 Z
1 2-p/1
Pmna
D.6 Properties of Ihaase
Lemma 18. For any è E IRd, we have
A 12 Thase
S 40p3/2 || 1//2
Proof. Given that
Pmaa
1/2 1/ Ihase -
Σ
A 11
p=Paii
30

---

we have
Puana
|| I1 Uhaso
0||
|
+ Σ
|
where
2
|1 2 1 2 n/4 Pmaxx
11
||
1/ 11001
Vpmin p S Pmax
by Proposition
3 We can thus conclude that
f 1/2T basc
I (1 + Prnax (32 + 2 Pinax)
| - 40p 3/2 max
///20/11
Corollary 4. For any è E Rdd, we have
base 1
S Pmax Vō [base 0 ||
Proof. The proof follows from Lemma by noticing that
base II
II Ibse
II
Piiin =
Puin 1
given the definition of Sbase in 30
E
Analysis of Algorithm 1
E.1 Quadratic Approximation of Near (0())
Given that f is Le-Hessian Lipschitz, in the neighborhood of (0)), it close to 2220. (x), is the 2nd order Taylor approximation of f evaluated at (0) Throughout this section, denote x0 (22)
g(x) = (x)
(x) = f(x + (V](x!)) x x0)) + +/2 --(x-=0 =00) (")
Similarly to the definition of f. we define و = -f1-1/2;),, which satisfies
VØ(.) 1/2 Vg 1122g)
and
V 1/2 g
A 1/2 4-2 1/2 1-1122 V2 (²)(6((0) A/-1/2
For any iteration k; we define
(k) = - (1))
x0= - Vo(1(H))
-V)((())
Then, we have (8) = 1/2g(0)
E.2 Movement Bounds of the Iterates
In the case where Line 7 is triggered during Algorithm | we denote
K. == argmin (t- 211)
> > B²
Otherwise, we denote K. = K + Lemma 19. For any iteration & < K,, we have
1. k E ||,((+|] 201 B2:
2. (k)) - x(00 B:
31

---

3. [1(0)) - x000 - 2B:
4. |000|| || - 2LyB²
Proof. The first entry follows from Corollary
| (k+1) (1:11)=x00
k
(1
k
-1
|10 - -2(0) < B².
120pmax max
Then by Cauchy-Schwartz, we have
||0((h] - x000 S
(110)1(++1)=011)) s BB
which leads to
(b)k) - 1.101| S -11=(8))~00)) + (1 - 0)| || SBB
Since f is Le-Hessian Lipschitz, we can further derive that
|1000|| = =| S 2 / x100 S 2LzB3
Lemma 20. Let 1) S 1/4. In the case where the "if condition" in Line of Algorithm 7 is triggered, we have [|x/(K) - [0) S 7B.
Proof. By Lemma
19 for any & < KC we have [|x((() - 1000 S B and 10(00xx00) s 2B. Hence, x0y)
to bound [x(())
||. it suffices bound ||x(A] - y(x--1)11 which satisfies
||x(k) (1 (1g
where
Å 1
- (x s (2f(y)dy
-
= - ( + A (yy(k-1) 2)) + - 1-1 (H V2 f()))d (23)
The first and the second term satisfy
A 17-Vi(W'' (K- ())(((22)) =1|1((--11)
y(x--2)
2) $11 /n S <3B/u.
and
-
S || ((- -y(c-1)| S 4B, -1 by Corollary 3 and
respectively, As for the third term, given that | S (126pmaxx)
| -
f2v(v)
2 8 + 4 < 28,
it follows that Therefore,
||peery 7- - (
S B.
p=yle= 2)
||x((k) ykk- ||| - (3+ + 4n 1)B = 5B,
and we can conclude that
[kx)(0)) 100 S || - ا1 + ||x(0k) y(x-1)|1 7B.
32

---

E.3 Function Value Decrease Case
In this subsection, we discuss the decrease in the function value of Algorithm 1 in the case where the "if condition" in Line iis triggered.
Given that H is symmetric, we can find set of orthonormal basis {hi..... ha} such that each h, is an eigenvector of H with eigenvalue A; We decompose these coordinates into two sets
Sne = {i 8:
Sac : A
(24)
where sc and ne abbreviate strongly convex and not strongly convex, respectively. We further define the corresponding projectors
Σ iEScc
Ine Σ hag..
(255)
iESuc
For any i E Rd, denote
8sc == 1n
Onc == nneo
and
Jsc (0) (Vf()(0)) 00c =:001 +
2 (Use -310) T H δsc -100
1
(26)
Jne (0) (V (z)) 8nc = + Onnc )100) T H (Uue- 100
Then, we have g(0) = (an(() + Ine (0).
E.3.1 Function Value Decrease of Usc
The proof structure in this part is similar the proof of [29 Lemma 2].
Lemma 21. Let S 1/4. Then for any 0 I k < K. - and any a > 0, we have
H (2(k) 91hh) + 1
Onn (x(k+2))) gee (2 s
(a(k)
((k))
2a
+ (1=2/6)
1
on
|
=.(k) 1²).
2n
126pmax
Proof. Given that Jes is quadratic, for any two consecutive iterations, we have (((++) Jec ( Ôdc (8) + Gsc (V) (,,)),(((+)))))) =:(h))
(R+1). - =:(6)) T H( (k+1)
(k) 3 6c
2 (o
where
V Gsc (z(())) V (1)( + (ū) - ffc + (V (2*) V Dsc (br)))
(k(k+1) 1) -((h)) + ($((K) ((K)) (1k)
Hence,
Isc (++++)))
Jan (k))
(K++1
yuc - (k++1) =((1)
(k) (k++) 2(K))
+ (1:(k) (k) 11bb) H H+x0(+3)
(k+1)
{((()) + 2
(kk+1) =0(0)) H (k+1) _ =.(k))
where
(k(++))
((6) (k+1) - 2.((0) = -112(80
(1))
112
|1
(k+1)
(R) 2
(k-1) 1) (1)
Use
y
33

---

and
(#l))
) H
[I - (b())) + ($(k+1))
- - H (a((+1)) - -
(s(k++)) Usc! H [s(++1]) 1)_ - Usec)
sc
2
( (k)
20
Dsc
H (0 D/c
Furthermore, for any a O we have
- -(d ((++1)
- = - (0(()) s(k+1) - -
1
1/11/2112= + at _ 111 (1 =1000 ) l|
-
20
a
|| 2/661
+
2a
240pmax
by Corollary 3 It then follows that
Jec (ac((1+))) - ())))
1
)
T H (00(tt1)
1 (s
vv(²)) 11 (x(b
-v(6))
||e(ko112
2 sc
20x
1
|1:0500 (k) D0c 1/00112
|| (1)
Dac 1|a (1
o0
||
-:(k)
12)
21)
120 p2
016o) + (A)
(k(k)
T H (s.(k)
<
2
2a
1
1 Use (1)) (1 128pmaxx
on
[g(k+1)
(.(0) 11²)
21
where the last inequality follows from
2
(alk)
sc
yoc (k))
H( - usc (k))
21
1
|
S 0.
since H 1 I and 17 $ 1/4. We can therefore conclude that
Jnc (x((+1)) - Jac (x)) <
(i(k)
)((T)
TH
H (2
+
2a
+
1
(1
((kk) 112 -01
on
(k--1)
((() 122.
2n
126pmax
Lemma 22. Let v S 1/4 and
0 S In the case where the "if condition" " Line 7 of
Algorithm 7 is triggered, we have
K-1
DL3BKK
(x) - g00 (z(1)) <
(k(k+)
4n
308pmax
Proof. By Lemma 21 for any a > the following inequality holds:
11)
Oec (2(1+1))-
gc (z:11))
(a(())
v((h) T H
(k(k) g(hh)
2a
+
1
(1
(/(h) 1|2 - (1 120pmax
CUT
(k--1)
2(00) 12)
21
where
1
0
(p((k)
(((h)
H
(+((k)
)(tt)
2n
34

---

as per the definition of See in (24) and Il in (25). which leads to
Ise 1x)+ - Iso (x(A))
S
1
OCT
[a((+1) 80
- (((k)
1| +
1
20j
128pmax
2x
+
(1 + 0)(1
21j
0)2
1:0000
1.(1-1) 121
sc
given that Uie
(k) (1) (1 - () (k)
(kk 1)) per 7
Define the potential function
Psc (x(()) + (1 + () - 0)
(k) =
|
(2- 11
Ssc.
21
and set 60pmax 0/n.. Then, we have
Ssc
c(
0
(+++1)
1|2 +
1)12
417
126pmax
Summing over all the iterations in this epoch, we can conclude that
( - (E(
0
(k+1)
1122
ssc
41
120pmax
K
B
(1++1)
+
4n
8
E.3.2 Function Value Decrease of Onn
Lemma 23. Let S 1/4 and 0 < 0 S 1. In the case where the "if condition" in Line of
Algorithm iis triggered, we have
K-1
BL3B*K.
(no() (x 5 277 k=
(k+11
=060112 +
600pmax
Proof.
The proof of this lemma follows a similar structure as the proof 29
Lemma 3]. Denote
(000) H V (E:()) which allows to rewrite (n)
@no(0) = 2 (nnc -i) H(ue - a) - 2 (vgec(((0)) " Vino (x(0), VO Ra.
Then for any < K - we have
Inc ( (
Inc (2:(k))
1
(5 nc
(k+
(1) T (+ (k+1)
û) (1((M) - û) (((())) - i
2
2
(a(k+1)
[2(K)) T H (i(k+1) + (k((k) i)
mc
(a(k+1) _s((t) H
(k+1) x((0) + (a(k+1) - [((k) H (a((k) i
Fnc
where the first term is upper bounded by
(+(k+1)
{.(K))
(k+1) =(0)) <
|
0
- -:(()
2
2m
following the definition of Snc in 22 and Ihe in 25 As for the second term, note that
(k+1) - ((())
g(th) x(k)
V Ône (g(())
(k)
= (1 (+(k)) ((k-1) 1) 17
(EF(1/00 (i(()
ne
(1 (2(()) -((k-1)
1/ (2
á + (1 ()(((()) -2(00-1)) - 7000
35

---

where the second line follows from the observation that
H (The - -û) H (iitt) ) + H (2:00 - (i)
Vîne (b(h)) - V gnc (z(10) + 1111 (2oo = ())
Hence,
(olk+1)
- = T H (216) -a)
(1 - ( = H [b]b) - -) n| H (z! - 1
(27)
- 77(1 1 0) (1 (2 - 1 H (1(ld) - i) - </ H (s! - i)).
where we have
0) m1(11111000
-
nc - 1)} H (s ú)
< 71 8)
(1: - 1( 1)
|| + |||
( - -a) 1²)
2
and
100 H (
-)) S 2(1 + 1 | + (1 + 0)
"1
H (s 01)1
nc
2
Combined with 27 we obtain
(ol(+
- (+t) H (kk - i)
$ (1 8) (k)
a(k-1))
1)
T H HH ((h) i)
nc
+ 11 0)
H (1 ne ((--1))11 + 2(1 + 0)
71
|
2
(1 0) (1)
_((-1))}
H ( 1) -0) + (1 ()
=
T H ( -3(6-12)
+ 71 0)
H (i)
-he 11 2 +
11
| ||
2
2(1 + 0) i)
$ (1 (x!
H (s(t )(!-1)))
1)
| 2
+ 2(1 + 0)
where the last inequality follows from the fact that
(1 - (3 nc - -hc 1()-11) T
TH ne
a(k-1) + 111 0)
H
(1
516 1) 20
2
ne
since 17 S 1/4 and |||||| S 1. Hence,
( (a(h+11) {
T H (s(k) - a)
< (1 0 (a(t)) 1 T H7-l1110 ii) + 2(1 0)
(1
0) 8
5
(k)
2
'nc
1=1
7 > 10--0)11116
2
where the last inequality follows from
(#!l) { H (())
me i) - (ūn( H. (H V Juc 00 (o) S O.
Furthermore, for each 0 < k < K. - 1, by Lemma 19 andd Corollary 3 we have
L3 36 36pmax
|| ||
[(() 2
1/1-1/2 1 Ā 1/2 1|cck0112 v
which leads to
1 mc Ba
Σ
(1 - 8) k-
2
2
600pmax
1=
36

---

and
TT Ba
Inc inc (i(ktt))
Inc (3)(
[(k+1)
S
211
Gmpppax
We thus conclude that
K-1
BLBBK
Inc(# - Ince ( (1: S
[((+1)
=.(k112
+
217 k=
660pmux
E.3.3 Function Value Decrease of f
Proposition 4. Let S 1/4 and Algorithm iis triggered, have
< 0 S 1. In the case where the "if condition" in Line 7 of
30 [00 [ (L1/
f(x(()) - s(x <
+ 36L2BB S --V T22'
Kn
where ė = e/Pinxx is defined in
Proof. Combining Lemma 22 and Lemma 23
we obtain
K-1
[k(++ - 100 2rL3BBK
308pmax B²
((x(K)) -0( S An
308pmax
n/K
308pmax
following the condition in Line
7
Then, we can conclude that
f(x(1)) f(x(0)) g(x(10) g(x:10) + (f(x((0) g(x((1)) (f(xx -((x(0)))((((())
g(x((1)))
30ppmax B²
2TL3B*K
+ 60LgB3 S
S-V L2
i/K
308pmax
given that f is Le-Hessian Lipschitz, and ||x((0) - 200) S 7B by Lemma 20
E.4 Small Gradient Case
In this subsection, we provide an upper bound on the gradient of the output of Algorithm D in the case where the last iterate stays close enough (0) or more concretely, the "if condition" in Line i not triggered. Similar to Section E.3 we use (hI,.... ., hae to denote the set of orthonormal vectors such that h2 is the eigenvector of with eigenvalue A4. We decompose these coordinates into O (Pmaax) sets:
S, = :i: A < 101),
Vp E N and Pmin S p S Pmax:
(28)
where the definition of I, is given (4). with indices in Sp, equals
Then, the projector onto the eigenspace of eigenvectors
Σ
hagh Hp,
Vp E N and Pmin S p S Pmax
(29)
iES,
where II, is defined in (88)
Moreover, define
Sbase == {i: A [pmin
(30)
Then, the projector onto the eigenspace of cigenvectors with indices in Sp equals
Σ high
Ibase:
(31)
iEShao
37

---

where hase is defined in 19. For any
E R denote
base Ibsee 0, and 8p = =1,0, Vp No and Pmin S S Pmax-
Moreover, for any E N+ and Pmin
S p S Pmax. we define
Op(0) = v f(x(0)), ). 6p - x 2 (ūp - - T H(0p - 2
(32)
and
Traso (0) = (V (V)()())) Ubase
Dasse + 2
1
Ühase Abane
H
(hase base
(33)
Then, we have g(ū) = Ibase (8) +
Penax
(0) and
Pmmin
Pinox
Vg(0) Trase (0)
Vgg(O.
p=Paii
E,4.1 Small Gradient of Op at oot
In this part, we show that the gradient of (z:0t) is small for any p E N+ and Pmin S S Pmax- We define
= nH, Mp= = =1p M 1pp
Lemma 24. For any o(k) Ra with the initial condition the following recursion formula
v(-1) v(() and (111) 1) O, that satisfies
y(++1) aa - - b- Mo(k-1) ((K)
for some symmetric matrix M E Iddd and a, b E R. we have
k P(M) 0(M)*-j
(1k) (M))
P(M) - 2(M) ,00)
where
1- 2(M)
P(M) 2(M)h+), v620, 0,
vx(M) = P(M) - 2(M)
-(())+1
(34)
P(M) ((M)
and
P(M)= = aM + Va 4bM
Q(M) = a. Va 4bM
(35)
2
2
Proof. The solution to the homogeneous part (x++1) = Mo(k) - b. (R- is
(R() = (M)))))
where
1- 2(M) P(MM)-
P(M) 2(M)*-1
(Mc = P(M) - 2(M)
P(M) 2(M)
with
P(M) aM Va=M² - 4bM
Q(M) a. Va²M² 46M
Counting in the inhomogeneous part, for each 261) leads to the following additional term in (4)
for any l: 2 j:
P(M) * 700) P(M) - 2(M)
We can conclude that
P(M)-~ ²(M)*
(R) 1hx (M) +
.00
P(M) - 2(M)
38

---

= 1 8. If S 1/4 and 0 (2pax)) for any p N and Pmin S p S Pmaxi the matrices P(Mp) and ((Mp) defined in satisfy
Lemma 25 (Properties of P(Mp) and ((Mp)), Let = 2 b
35
1.
IP(M))] (1Q(M,) blI $ 7/ Pmaxi
2.
-
Praxx
71
3.
I-Q(),) -(M,)-Q(MP)
P(M,) -
Pmax 2
P(Mp)) ((1)
7
Proof. Observe that
P(Mp) M.Mp + / M² 4bMP
aMp V M3 4bM,
((Mpp)
2
Given the definition of Hp in 16 Mp satisfies
(1 - I 1 Mい 3 (1 - n1ppT
(36)
in S 1/4 and 0 < / (2pmax), we have a²M² - 4bM, I O, which leads to
aMp. + i M² + 46Mp
2(Mp)= = aMp 2 a² M3 + 46Mp
P(M,) =
2
2
Therefore, we have
IP(M) - - [(aM)))) + (-a2 46M,,)11
S /b1MMbpl 1/Paaxx
As for the second entry, since
P(Mp) 2(Mp) iv / -a²M3 + 4bbMp
by 36 and the value of a, b we have
1
Pmax
5
P(M,) - 2(Mp)
17
which leads
T 2(Mp)
P(Mp) -
- -(M,)-Q(M)
P(Mp) - 2(M,)
S (1+ (P(M))))
Pmax
P(M,) 2(Mp)
Lemma 26 (Bound on the difference between f and Vgp). For any p E N+ and Punin Pinax- in the case where the "if condition" in Line 7is not triggered, for any iteration i of Algorithm 7
we
have [kk 26-p/2 pmax
V/V8.
Proof. It follows from Proposition that
2
((Ck))
|T S
Vo(2%5)
where
2-5 + 2 p/4 Pmax
7122 (k)
M 1/
/ II 11,0
64pmax
by Proposition 3 which leads to
26-p/ Pmaxx
26-p/2
(b)
A 1///2
Pmnx [1]0
/
39

---

Lemma 27. 1f S 1 and 0 S (2 then for any P E N+ with Puin S S Pmax and any
j<j k- 1 we have
(P(M)- 2(M
P(M) P 2(M)
128pmax
5/2
77 k-j Pmax
11.0011
Proof. It follows from Lemma 25 that
(( (P(M) - 2(M) h-j
(
1 P(MM) |P(M)) @(M))
||: ||((M)) -11-11111 -11-7911
2
P(M) 2(M)
-1((M,) 8ー | 1//1
P(Mp) 2(Mp)
Pinax
(1- 77 k-j |,600
2
Pmax
where
26 p/2
|| -
Pmax |2:5
vo
by Lemma 26 Since
P(MM)- - ²(M)*-) P(M) - Q(M)
(P(M)+---(AA -(M)
H
(1.) = H1H
P(M) - - Q(M)
we have
H12h7 (P(M))- - 2(M))
P(M) - Q(M)
(P(M) R- 1 2(M)
M H H.
P(M) - 2(M)
(P(M) h-j - 2(M)
< Pmax Vo. -
2200
P(M) 2(M)
0
k-j ||:011
< 2) 21+p/2
17
Pmax
128pmax
7
||:00l1
V
Pmax
where the first inequality is by Proposition < 1.
2 and the second inequality follows from the fact that
Lemma 28. If S and 0 S (2/2m)))), then for any p E N+ with Pmin S p S Pmax, any vector
6 E Rdd, and any integer k 2 O, we have
18 (1-
1 k+1 Pmaxx
|| (M)) < 22tp/2pp2//
3/2
10p11
Pinxx
V 17
Proof. By the definition of 1b in 34 we have
I (M,)
P(M,) -
(M,))) = P(MP) 2(Mp))
P((M) 1pp + P(M)) 2(Mp)) (21,)
and
1- 2(M,) P(MM)) - (M))))
(M,))0l -
|P(MM) )+1,)++111 || |111|pp1 ||
P(M)) - 1
+
1| ||0(M,)* 5+1 -160|1
P(Mp) - 2(M,)
< 4
Pmax
n
k+1
|10p11
7
Pmax
40

---

by Lemma 25 Since (M,)0, = H (Mp) we have
| (Mp) - =1 || TI. 2/ (Mp)0pl
- 2 p Pmax V H1 (M,
S 2 Pmax vōl 10 (Mp
8 (1(1111
k+1
$ 2/2 pinax
|ppl-
Pinax
where the first inequality is by Proposition 2 and the second inequality follows from the fact that
H Σ 1.
Lemma 29. 1f S 1/4 and 0 < n/ (2mma)m))))) for any p E N and Puiin S P S Pmax in the case where the "if condition" in Line is not triggered, for any iteration k 2 0 of Algorithm 2 we have
2 B (1
k+1
256 B Ba
7/2
M 9p (1
1312
Pmax
17 171/2
Proof. For any iteration k, by we have
((k+1)
(()) V ()))
-5/ 5/(²) 1 (11 - - () mp
a(())
V Sp((0))))) + (1 - () - 1.(b-11)
(1(()) 1 (1 (1 P
5/p ((k-11))) 170
Denote 2/th)
10) (1:00) Then, the above equation equivalent to 2
(k+1) (k)) + (1 (1 (k) 9 - { (k-1)) )) - H (k) + (1 - (3((
x - ()(
(1 H ((2 0) - (1 0)z((~1) mmbh
Let =0: 0, = 1 O. By Lemma 24 we have
P(M) ²(M)) 11.)
2/100 Uh (M,) 2000 7
(37)
P(M) Q(M)
where
I- 2(Mp)
P(MP) -
th (Mp) = P(M,) 2(M,))
P((M,) +
P(M,) 1(M,)
which leads
(1/2) 1 /1/2H/ H th (M)
P(M) - Q(M)
712..
199
(38)
P(M) 2(M)
For the first term in
38 by Lemma 28 we have
(M, 1011
22tp/2
p
3/2 miax
27 Piaxx
k+1
|
where
H (z(0)) S VPina V vf
and
|| - f(()
4 A B
|
< v
f(
77
7
41

---

which leads to
| Mp
1
24+p/2 80p28ppmmm
6pma B
(1
k+1
1/3/2
Pmax
As for the second term of (38) by Lemma 27
we have
Σ 712 P(M) - O(M)*
A-1
k-1
-
- 2(M)*
P(M) - 2(M) (14)
P(M) - Q(M)
1=0
f=U
k-1
1 k-s
S 128p 5/2
1/2
Σ
1
11:5011
!)
Pmax
j=0
where for each j we have
|000|| S -211v())=00011
x001/ S B²
given that f is L2 Hessian Lipschitz. Hence,
k-1
H H- P(M))-j - 2(M)*- ((1)
n
P(M) Q(M)
j=0
k-1 3/2 1/2 < 226L2BB B² P
k-j
I BaoLLBBPrit, /1)
Pmax
1=0
We therefore conclude that
(p) S
2 2
8p
B
(1-
11 Pmaxx
k+1
256 B
B²rinxx Pinxx
7/2
173/2
191/2
Lemma 30. In S. 1/4 and 0 < (2Paaa))))) for any E N+ and Punin I S Pmaxo in the case where the "if condition" in Line i s not triggered, we have
12
||
26t pptp//6ppt B
17 Pmax
K/2
+ 1/2/2
2 L2B22ppna
7/2
1/3/2
Proof. Given that g(() = ((k) + (1 - have
()((()) (1-0)(5(1))
-((k-1))
and that 9p quadratic, for any k 2 1
(0())) = (G(()( + (1 - () (V - Vo,
(
which leads to
f 1/2 (1)
s (2 - (2-00)lAi 1/2 < 2| 11
(1- 1/ 12/ gp (k- -1]]]]
0r 1/2 ( + || 3p 9p 11)
/0+p/28p2 B
20 L L2B² B² Pmnax
1/3/2
Pmax
1/2/2
by Lemma 29
Furthermore, since
Ko
sout
g())
Kg
K/2|
KK/2
we have
Ko
12 (zott))
1/2 go (1("))))
Ko + 1 - [K/2|
k=|K/2
20+p/28ph B (1
n
K/2
7/2 210 L L2B²² Pmax
173/2
Pinax
17 1/2/2
42

---

E.4.2 Small Gradient of Jbase at rour
Lemma 31. 1f S 1/4 and 0 - n/2, in the case where the "if condition" in Line 7 is not triggered, we have
328 / Opmaxx B
801 800/0ppmax
M Jiasso (jout)
+ 80p
max L2B²
nk²
n
for any l that satisfies
1 8. |10basell,
vo IRd.
(39)
Proof. The proof this lemma has a similar structure as the proof of 29 Lemma 5]. Given that Thase i8 quadratie, V Giass (2out) can be expressed
V Tbaso (oout)
Tbase (K))
Ko + K/2 [K/2]
where we have
goase (g((k)
1
(a(ttt))
(base) + &base
7)
(o((t+)))
2. basee
- (1 - (2) buse
- (lase + Basse
and
Kn
-m(Ko K/2) Tosse (oleeae((00)) (sout)
1. basse
(Ko+1)
2. (Ko)
buse
+ 0 ((K) (K/22)
17
Ebaser
k=
[K/21
where the last term satisfies
Kn
A/2
S 40p2//2
3/2
Σ
||/1/20||
base
max
k=|K/2]
k= KK22
KK22
< 880(Ks Ko
2/2 B2
by Lemma 18 Hence,
M 1/2/ Trass (i
H 12 (12 (2
base
(Ko+1)
1 (Ko)
>1
+
n
48
| 1/2 (12((k)))
(K//2) base
+ 2/2 L2
48
base (KK)
400
1. (Ko) (Ko)
2 (K/2))
80p3/2 3/2 B2
71K
base
48
[|
(Ko)
400
|. 3. ((K/2)
80p T L22
nk
where the second inequality is due to the condition given in argmin (ag - [ - _((00] ||. have
339 By the condition Ko
486pmax B K2
- (/100) -
Σ
(k+1)
Tase ||
(k)
Tase
K 3K/4 km [3K/4]
given that the "if condition" in Line is not triggered, which leads to 32l 2opmase B
80E /00maxx B
A 1/2 Abase (aout))
3/2 L2B²
nK²
Corollary if S 1/4 and 0 S 5/2,, in the case where the "if condition" in Line 7 not triggered, we have
32pmax SB
80pmax 8B
|| A 1/2 Toaso (1 (oout))
n + 3/2 max L2B²
n22
Proof. The desired inequality follows by combining Lemma 31 with Corollary
43

---

E.4.3 Small Gradient of f at vo
Proposition 5. With the choice of parameters in Theorem in the case where the "if condition" in Line not triggered, we have [ S.
Proof. By Lemma 30 and Corollary 5 we have
Pinax
Vg(2=m)) || || g(6
17 Vg(Cout)
Σ
Vop(z
Pmaxx
H / Obasse (Bout) ||
11// V0p (p:ut)))
Panio
26+p/ 8p
B
11
32p 32pmax 5B K/2
3/2
80pmax 8B
2 L L2
9/2 Pinx
173/2
Pinax
n
n
17
26+p/2 3
B
11
K/2
40pmaz661 B
2 Lg B8
9/2 Pinxx 1 1//2
1812
Pinax
n2²
and
V |
|| - V (z I|| + (
< Vg(2=
I| 22
20+p/2 25p
7
K/2 +
40p 5B
2 Log Bapuax Pmix
+
(40)
1/3/2
Pmax
nk²
1/
Given that
Ppmax
x
26+p/2 8p mmxax B
K
log
1/3/22
the first term of 40 satisfies
26 ti+p/22 op
B
K/2
40pmaxx ÓB
211 Lo 2
3/2
Pinax
n22
11
3
Furthermore, the second and the third term satisfy
102220 8B
3/2
2 Lo 132 Pmax
13223p
S
nK2
3
17 1/2/2
respectively. We can thus conclude that [[ || Se.
E.5 Putting Everything Together
In this section, we give the proof of Theorem 2 and present additional Lemma that characterizes the suboptimality of out the output of Algorithm
By combining Proposition 4 and Proposition 5 we know that at least one the two conditions in the theorem statement must hold. As for the distance between gut and (0))) in the case where the "if condition" in Line is triggered, we have
Proof of Theorem 2
2010 ||x((()
201' - 7B
by Lemma 20 Otherwise,
Ko
out 200
1 (2) 200
S 2BB
Ko +
[K/2]
LK/2]
by Lemma 19
44

---

Lemma 32. In the case where the "if cooddiiion" in Line 7 is triggered, the output xn of Algorithm ! satisfies
6ôe
L2 1//2 23/2
L2
162
Proof. In the case where the "if condition" in Line is triggered, we have
x out
1
Σ y (K))
Ko 1 1K|1
[K|2
where in each iteration we have |////22 - x =0)) s 2112112222110 x100)||
+ -100)) 11/112(660111) - -1(00)] < <6v30pmax B,
which leads
Ko
| ox (s - -
(y()
- -x(00) S 6V 36p B.
Ko + 1 K222
k= LK/2]
Hence,
g( - 9(xx(0)) -
out - x1(0)) T 42 (²)(=(0)) 10
out - x(01) T 11 (z - x1(1)) S
B²
6de
L
Mcanwhile,
fx g(x < 22 1|
L2
x000)
100133
63/2
6T.- 1/2
by which we can conclude that
6dc
3/2
faxut) - f(x(0)) s
+
L 6T
F Analysis of Algorithm
2
Lemma 1. Suppose e S L2/L2. In each iteration of Algorithm 2 before it terminates, we have
f(x(++)) - f(x")) 5 L/2
if (1(+) is not e-critical for f, where we denote p = m [ /8)1
Proof. If the current H satisfies H x ~2211 by Line 7 and Line
we have
R²
L2
f(x((+1)) -fa1)) ((x(0) < (z) Ro) +
22
(zx(
2
R²
8R²
<
v
2
(x
1 +
2
where
22
)- (z(
T Hv 0 T (V2 ((x!))) - (1
H)r
S 28 + [²) - H|l
S 5-2 + min |/|22 (()(t) -V* - 211
= - + min (2,,+,,
8,21, = --
45

---

which leads to
1 / e
- s _012 -
1 - r S g2l Lo2
Otherwise,
x (t+1)
Critical-or-Progees -rogrressssssss (1 H,25, c, L1. L2).
which by Theorem satisfies
1 ed
( 1
h12 L
[ [ > e.
Lemma 33. Let 0 < <mmmmin
2/////122 ( The output ou of Algorithm satisfies
3A log (
[1
+ 16
C8
and
f(xou)) - f(x(10) 1
54csE
log"
L1 + 16)
+16]
e/2
L2
C8
6T.2/2"
where == min (T,, 6 + (l2/(
Proof. Suppose Algorithm@21 2 terminates at the T-th iteration. For any < T 1, by Proposition have
f - f(x(1)) - 5T Ls
indicating that
T 2 AV L2/E3
Since
[1((+11) 2001 01
7
37
Tu2
in each iteration by 4 and Theorem we have
3A
(
1 out
(0) ||x (0)
|| S 3p A/E
log
8
+
+16
16
cb
As for the function value change in last iteration, by Lemma 32
we have
54de
L22
f(x (x)(T) < (()
T22
6 1/2
Summing over all the iterations, conclude that
18CsE
L1
3/2
f(x (0) <
log"
16
+
La
cs
6T.
1/2
46

---

G Analysis of Algorithm
Lemma 34. Given f R2d IR with Li-Liccchitz Hessian, for any x E TRd and any symmetric H
satisfying | - f2f(x) S 8, denote
y (argg HT (V
Ift ( L23 28} for A f(x) inf f(2), we have
3A, +
6L22z
large vf(1)) 2 t
l
and
3A,
6L2Az
[mmaall Vf(v)l [mall vf(())]++ 26
+
e
Proof. Denote u == y - I = - -11 (1lrgr) /V Vx(x). We first show that the contrary, we have
||||| S 1//22. Assume
1 (" a
l L2 [u|l -(0)) f(t)((
-
2
8 8
La
))) S
(=))==
1
8
L2
+
2 L2
+
6 L2
12L3
22
contradiction. Then, have
1 V=)() b2lllul|
2/21
A. f f(x) <
6
12
which leads to ||u|| s /2/33.11 Then, we have
[[age ff(v)l < [[agg vf(x) - lharge Hull + ||ll ( + +211u111
3D. L2 12|1u112 s 2
6I,2Ar
ا||||| + 2
+
Similarly, we have
small Vf(y)l & IT small vf(x)] + [Taall Hull [ (2f(x))ull
Ir2llul1
3 x
6L2Az
| small Vf(x)] 28
Theorem 4. Let Alg(feL, L1, L2, 8, c) be a procedure that, for any function fsL, Rd with L, Lipisschitz gradient, Læ-Lipschitz Hessian, and A b-bounded suboptimality, uses
nh queries to 6-approximate Hessian oracle for fein and,
(gg[T, L2, 8, c) queries to gradient oracle for fSL.
and returns an c/ c/2-critical point out satisfying uua - x: 2000 S Rout and f2x - inf, f(2) S
Dout- Then, for any ff with Lz-Lipschitz Hessian and A-bounded suboptimality, any 0
min(T. 2/3 T.2 11/3,, and any that satisfies
1800A (LzRou + 8)2, 48L 24A out L3 28
max
(12)
2
Algorithm 3 returns an e-critical point using
nH + 1 queries to ô-approximate Hessian oracle for f. and,
(l L2, 8, E) queries gradient oracle for f.
47

---

Proof. By Lemma
we have
IV
x [arge Vf(y)]l + smaall (v))
3Aout
12L2
smaal V fxxuu) + + V2 f(xoo))lly
3Bout
12L 6
$ 2
+ 4(6 + L2Rout)
given the choice of in 12
Corollary 2. Let f: Rd + T. Lz-Lipschitz Hessian. Given any (0 E Rd with A-bounded sub-
optimality with respect to f. any positive integer ny 2 and < 2 L23 Algorithm using Algorithm a the subroutine Alg outputs an e-critical point of f with at most queries to Ó-approximate Hessian oracle and
(A
o
AL 1/4 7/1
AL2 nhe
(1
1 cb
L3A
2
6))
V
68
poly log
e +6)
et
queries to gradient oracle for S.
Proof. Set
de
(
+ 63/2
Aout 54
A+
log"
16
La
c8
6L
i Elog" 19 (é/cs),
(41)
34
i
Ront
log
+ 16
C6
where
max
800A
3L2
+ +0)= 26 =0
,0
LEA3
L
2
2 +
(42)
2
Observe that the above parameters satisfy
e 2 max
8004
Rou: + +57 48L2 24A
1/3 1//3 2/3
.225
2
out out
which gives
out - x0) < Rout, f(x²u))
inf f(x) Aout BERd
when ap- plied to fsr. Then by Theorem 4 Algorithm 3 outputs an e-critical point. Since Restarted -estarted-Appro- Approx-Hessian Hessien- AGD starts by querying the 6-approximate Hessian oracle at (0), the query in Line 3 can be reused, and there are total of at most nu queries to d-approximate Hessian oracle and
by Lemma 33 where yut is the output of segtaatedd-pppro--HHssiise
2A
AL2
( + 16)
min
e,o+
log
774
nHe/
AL!
1/4
AL2
L3A3 3
2
1))
=
8
poly log
+
+
7/1
nHe
C5
c
2
queries to gradient oracle.
48


Reviews:
[{"review_id": "DE3yFlXhZE", "reviewer": "Reviewer_BCZS", "summary": "This paper develops novel optimization algorithms that achieve improved trade-offs between gradient and Hessian oracle queries for computing ε-critical points of nonconvex functions. The key contributions are:\n\n1. ​**Main Trade-off Result (Theorem 1):​**​ For twice-differentiable functions with L₂-Lipschitz Hessians and initial Δ-bounded suboptimality, the algorithm computes an ε-critical point using nₖ Hessian queries and $\\tilde{O}(\\Delta L_2^{1/4} n_H^{-1/2} \\epsilon^{-9/4})$ gradient queries with δ-approximate Hessians. This generalizes prior gradient-only methods.\n\n2. ​**Dimension-Dependent Improvement (Corollary 1):​**​ In d-dimensional space, the algorithm achieves $\\tilde{O}(d^{1/3} L_2^{1/2} \\Delta \\epsilon^{-3/2})$ gradient-only complexity via finite differencing, improving over prior $\\tilde{O}(\\sqrt{d})$ results when $\\epsilon$ is sufficiently small.\n\n3. ​**Single-Hessian-Query Complexity:​**​ When limited to just one exact Hessian query, the method attains $\\tilde{O}(\\Delta^{3/2} L_2^{3/4} \\epsilon^{-9/4})$ gradient queries, improving previous bounds by a polynomial factor.\n\n4. ​**Technical Innovations:​**​ The approach introduces (a) a restart mechanism with adaptive Hessian updates (Algorithm 2), (b) a reduction technique to handle functions without gradient Lipschitz continuity (Algorithm 3), and (c) careful analysis of accelerated gradient descent under approximate Hessian-induced norms.\n\nThese results advance nonconvex optimization by unifying and extending prior state-of-the-art complexities while enabling new computation trade-offs between oracle types.", "questions": "**1. On the tightness of dimension-dependent complexity (Corollary 1):​**​  \nThe $\\tilde{O}(d^{1/3})$ gradient complexity in Corollary 1 improves prior $\\tilde{O}(\\sqrt{d})$ bounds but still has a polynomial dimension dependence. Could you comment on whether this exponent is theoretically tight? Specifically:  \n- Is there a matching lower bound for $d^{1/3}$ in this Hessian-approximation-via-finite-differencing setting?  \n- Does the exponent $1/3$ stem from fundamental limitations or current proof techniques?  \n*Actionable request*: Provide intuition for the $d^{1/3}$ term (e.g., whether it arises from the $\\min(c_\\delta)$ trade-off in Theorem 1 or finite differencing error propagation). A clear explanation would strengthen significance; conversely, failure to clarify may weaken perceived novelty.  \n\n​**2. Handling stochastic or inexact Hessian approximations:​**​  \nTheorem 1 assumes access to a deterministic $\\delta$-approximate Hessian oracle. Many practical implementations (e.g., via sketching or subsampling) yield *stochastic* approximations with variance $\\sigma^2$.  \n- Can your analysis accommodate stochastic Hessians with $\\mathbb{E}[\\|H_x - \\nabla^2 f(x)\\|^2] \\leq \\sigma^2$?  \n- If so, how would this affect the complexity (e.g., would terms like $\\Delta \\sigma / \\epsilon$ appear)?  \n\n\n**3. Practicality of spectral computations for $\\widehat{H}$:​**​  \nAlgorithm 1 requires spectral decomposition of $H_{x^{(0)}}$ to construct $\\widehat{H}$ (Eq. 2), which costs $O(d^3)$ and negates low-query benefits in high dimensions.  \n- Can $\\widehat{H}$ be applied implicitly (e.g., via Krylov methods) without full decomposition?  \n- Does your analysis support approximate eigenvectors (e.g., from power iteration)?", "limitations": "See weaknesses.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- ​**Originality:​**​ The paper introduces a fundamentally new perspective on balancing gradient and Hessian queries in non-convex optimization, an underexplored dimension in complexity analysis. The approach of using δ-approximate Hessians to define custom norms (Ĥ in Eq. 2) and the reduction technique for unbounded gradient Lipschitz (Algorithm 3) represent novel algorithmic innovations not seen in prior work.\n\n- ​**Technical Quality:​**​ The theoretical analysis is rigorous and comprehensive. The authors provide full proofs for all claims (Appendix A–F), leveraging advanced tools like Davis-Kahan theorem for spectral perturbation analysis (Lemma 7) and carefully structured induction arguments. The main results (Theorems 1–4) strictly generalize prior bounds (e.g., recovering [28] when $\\theta = L_1$).\n\n- ​**Significance:​**​ The results meaningfully advance non-convex optimization theory by:  \n  (i) Establishing the first trade-off rates between gradient/Hessian queries (Theorem 1),  \n  (ii) Improving dimension-dependent complexity to $\\tilde{O}(d^{1/3})$ (Corollary 1), beating the prior $\\tilde{O}(\\sqrt{d})$ barrier for $d ≥ 7$,  \n  (iii) Enabling non-trivial critical point computation with only one Hessian query – a practical scenario where the paper shows $\\tilde{O}(\\epsilon^{-9/4}) $ gradient complexity, polynomially better than prior arts.\n\n- ​**Clarity:​**​ The paper is exceptionally well-structured. The abstract and introduction clearly contextualize contributions against 15+ cited works (Table 1 is particularly effective). Algorithm descriptions are precise, and §2 provides excellent high-level intuition before technical details. Notation is consistent and well-defined throughout.\n\n## Weaknesses\n\n- ​**Practical Limitations:​**​ While theoretically novel, the algorithms rely on expensive operations like spectral decomposition of $\\tilde{H}$ (Eq. 2) and may incur large constant factors hidden in $\\tilde{O}(\\cdot)$. The logarithmic dependencies on problem parameters (e.g., $\\log(L_1/\\theta)$) could be prohibitive in real-world implementations, though this is common in theoretical optimization.\n\n- ​**Optimality Questions:​**​ While the paper improves upper bounds, it doesn't establish matching lower bounds for the new trade-off regimes. The relationship to the known $\\Omega(\\epsilon^{-12/7}$ gradient-only lower bound [11] is discussed, but Hessian-query lower bounds remain open.\n\n- ​**Scope Constraints:​**​ The analysis assumes exact access to a $\\delta$-approximate Hessian oracle. In practice, such oracles might require auxiliary computations (e.g., via finite differencing in Corollary 1), but the complexity of implementing these oracles isn't incorporated into the main trade-off results.", "was_revised": true, "final_justification": "We maintain our **Accept (5)** recommendation. The authors provided comprehensive and technically sound responses to all raised points, convincingly clarifying the origin of the $d^{1/3}$ dimension term in Corollary 1 (as a trade-off artifact rather than a fundamental limit) and outlining feasible extensions to stochastic Hessian settings. Critically, issues discussed in the rebuttal (e.g., tighter lower bounds and non-deterministic Hessian approximations) were highlighted by the authors themselves as challenging open problems worthy of standalone future work—not as resolvable weaknesses diminishing the current theoretical contribution. This paper delivers rigorously proven algorithmic advances in non-convex optimization with novel gradient/Hessian query trade-offs, meeting NeurIPS standards for significance and originality.", "rebuttal": "Thank you for your positive feedback and detailed comments!\n\nRegarding your comment on the practicality of our algorithm, particularly the large constants and logarithmic dependencies in the query complexity, we want to kindly note that our focus in this paper was on worst-case theoretical query complexity and showing how our improved query complexities are obtainable. We agree it is an interesting direction for future work to improve these dependencies and the practicality of our method. We hope our results open the door for such exploration.\n\nRegarding your question on the approximate Hessian oracle and its implementation, we would like to kindly clarify that each column of the approximate Hessian can be obtained using two queries to a gradient oracle via finite differences (even if the gradients are only computed approximately). As a result, the overall implementation cost is $2d$ gradient queries. This cost is implicitly reflected in the trade-off presented in Corollary 1. We will include a more detailed discussion of this point in the final version.\n\nRegarding your question on whether the $\\tilde{O}(d^{1/3})$ dependence is tight, we agree that this is an excellent question. To the best of our knowledge, there is no known matching lower bound. This term arises from the trade-off between gradient queries and Hessian queries in Theorem 1. Specifically, we require $n_H \\cdot d$ gradient queries to construct the $n_H$ approximate Hessians, and $O(n_H^{-1/2}\\epsilon^{-9/4})$ gradient queries to perform the AGD steps in the approximate Hessian norm. Balancing these two terms yields a total query complexity of $O(d^{1/3}\\epsilon^{-3/2})$ when choosing $n_H = \\Theta(d^{-2/3} \\epsilon^{-3/2})$. Thus, the $\\tilde{O}(d^{1/3})$ term reflects a limitation of our current analysis rather than a fundamental limitation. We will expand on this discussion around Lines 274–277 in the final version.\n\nRegarding your question regarding lower bounds for the new trade-off regimes, we would like to kindly note that dimension-dependent lower bounds for critical point computation are not completely understood. To the best of our knowledge, existing dimension dependent lower bounds are limited to the low-dimensional setting and do not assume Hessian Lipschitzness of the function. Moreover, establishing tight lower bounds in our setting would require improving the current $\\Omega(\\epsilon^{-12/7})$ lower bound for gradient computations for a function with Lipschitz gradient and Hessian, which has remained open for several years. For this reason, we view the development of tight lower bounds in our regime as an independent and interesting open problem. We will include a more detailed discussion of lower bounds in the low-dimensional and Hessian-only settings in the final version.\n\nRegarding your question on inexact Hessian approximations. While our current algorithm is presented under the assumption that the Hessian approximation is obtained deterministically, the framework naturally extends to settings where the approximation is computed via non-deterministic means, including stochastic oracles. A straightforward approach in the stochastic setting is to compute a mini-batch average of stochastic Hessians whenever a Hessian estimate is needed, ensuring that the approximation error is bounded by $\\tilde{\\delta}$, as defined in Equation (8). This would introduce terms such as $\\sigma / \\tilde{\\delta}$ in the complexity. We view it as an interesting open problem to explore whether improved bounds can be obtained in this setting using more advanced techniques.\n\nRegarding your question regarding the practicality and computational complexity of spectral computations, while this aspect is not the primary focus of our work, we agree that it is an interesting question and thank you for asking. Although certain components of our algorithm, such as the eigendecomposition step, may appear more involved than those in the classical Newton method, we note that these operations can also be implemented in $O(d^{\\omega})$ time in the worst case, where $\\omega$ denotes the matrix multiplication exponent [1]. This matches the worst-case cost of solving a dense linear system and the worst-case per-iteration cost of Newton method.  We agree with you that it is an interesting open question to develop an algorithm with the same theoretical guarantee and is more practical to implement. Notably, our algorithm only requires matrix-vector product access to $\\hat{H}^{-1}$, which suggests potential for more efficient implementations. While directly applying Krylov subspace methods in our setting may be nontrivial, we hope our results open the door to practical variants of our approach and worth further exploration.\n\n[1]. James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik 2007."}, {"review_id": "vh19EPANub", "reviewer": "Reviewer_tspV", "summary": "This paper studies the problem of finding a first-order stationary point of a smooth non-convex function using access to a gradient oracle and an approximate Hessian oracle. The core idea is to apply the restarted nonconvex accelerated gradient method of Li & Lin (2023), preconditioned by an approximate Hessian. Moreover, the Hessian estimate is updated in a lazy manner only when the distance between the current iterate and the last reference point exceeds a predefined threshold. This threshold controls the trade-off between gradient and (approximate) Hessian queries: a smaller threshold leads to more frequent Hessian updates and also fewer gradient steps due to more accurate second-order information. As a corollary, the authors derive a new dimension-dependent complexity bound using only gradient access, as well as a bound that requires only a single Hessian query.", "questions": "## Clarifying Questions\n- The construction of the modified approximate Hessian estimate $\\hat{H}$ in (3) appears somewhat ad hoc. In particular, the origin of the logarithmic terms is unclear. While the authors mention that these terms introduce spectral gaps and facilitate the use of matrix perturbation theory, a more detailed explanation or motivation for this specific form would be helpful.\n- Regarding the results in Corollary 1, since each approximate Hessian computation requires $2d$ gradient queries, I believe the complexity bound should be $\\tilde{O}(d^{1/3}L_2^{1/2}\\Delta \\epsilon^{-3/2} +d)$. Alternatively, if this cost is not counted explicitly, then the bound applies only when $\\epsilon \\leq L\\_2^{1/3} \\Delta^{2/3} d^{-4/9}$.", "limitations": "Please refer to the \"Weaknesses\" section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- This paper combines several techniques from nonconvex optimization—including restarted nonconvex accelerated gradient methods, preconditioning, and lazy Hessian updates—in a non-trivial and interesting way. The result is an algorithm that explicitly balances the trade-off between gradient and Hessian computations.\n- Notably, the proposed method achieves a new complexity bound of $\\tilde{O}(d^{1/3}\\epsilon^{-3/2}+d)$ when the function has $L_2$-Lipschitz Hessian and only gradient access. This improves the dimension dependence over Doikov et al. (2023) and yields a better dependence on $\\epsilon$ than Li & Lin (2023) when the dimension is sufficiently small.\n\n## Weaknesses\n- The paper currently lacks a detailed discussion on the computational cost. Specifically, constructing the modified approximate Hessian matrix $\\hat{H}$ requires full eigendecomposition, which will incur a cost of $O(d^3)$.", "was_revised": true, "final_justification": "The authors indicated that they will include a detailed discussion of the computational complexity in the revision, and they have also clarified my questions regarding the logarithmic terms in the approximate Hessian estimate and the dependence on $d$ in their complexity bound. Accordingly, I maintain my initial score for the paper.", "rebuttal": "Thank you for your positive feedback and detailed comments!\n\nRegarding your question regarding the computational complexity of our algorithm, while this aspect is not the primary focus of our work, we agree that it is an interesting question and thank you for asking. Although certain components of our algorithm, such as the eigendecomposition step, may appear more involved than those in the classical Newton method, we note that these operations can also be implemented in $O(d^{\\omega})$ time in the worst case, where $\\omega$ denotes the matrix multiplication exponent [1]. This matches the worst-case cost of solving a dense linear system and the worst-case per-iteration cost of Newton method.\n\nRegarding your question on the origin of the logarithmic terms in the approximate Hessian estimate, we first note the following intuition: our rescaled Hessian AGD framework is stable under constant-factor perturbations in the eigenvalues of $H$. That is, changing an eigenvalue $\\lambda$ to $2\\lambda$ or $\\lambda/2$ does not affect the asymptotic convergence. To formalize this, our analysis partitions the eigenspace of $H$ into $O(\\log(L_1/\\delta))$ groups based on eigenvalue magnitude, as detailed in Appendix C. Within each group, eigenvalues are either $\\delta$-close to zero or differ by at most a constant factor. This grouping is the source of the logarithmic term.\n\nAs for how this appears in the algorithm, our analysis requires that the spectrum of the normalized matrix $\\hat{H}^{-1/2} H \\hat{H}^{-1/2}$ closely approximates that of $H$. In particular, the relative ordering and grouping of eigenvalues must be preserved—eigenvalues that belong to the same group in $H$ must remain in the same group after normalization. The explicit truncation steps based on this logarithmic grouping ensure that this spectral structure is maintained. We agree with you that finding a simpler construction of $\\hat{H}$ that suffices is a wonderful question for future research.\n\nRegarding your question on the asymptotic $d$-dependence in the bound of Corollary 1, we thank you for pointing it out and will correct it in the final version.\n\n[1]. James Demmel Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik 2007."}, {"review_id": "QGRZGWTlJV", "reviewer": "Reviewer_tXmx", "summary": "The paper studies trading off gradient and Hessian computations for a faster convergence rate for computing the critical point in non-convex optimization. In particular, the paper develops a method that achieves the best known dimension-independent rate and improves upon prior works in finite dimensions.", "questions": "1. How easy is it to compute $\\hat{H}$ and $\\hat{H}^{-1}$ in Algorithm 1 for high-dimensional problems? Similarly, the Newton step in Algorithm 3?", "limitations": "See Weaknesses.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: \n\n1. The paper has technical contributions and significance. The proofs are based on fine-grained analysis, coupled with delicate algorithm design, e.g., the choice of parameters in Eq. (4). Moreover, the theories possess sufficient generality to cover known results for gradient methods. \n\n2. The result is strong in improving the dimensional dependence compared to prior works under the same condition (Corollary 1, Table 1). \n\n3. Balancing the use of gradient and Hessian information for better overall cost (measured in gradient queries) is interesting. \n\n\nWeaknesses: \n\n1. The paper only considers gradient queries and does not provide computational complexity analysis. In particular, some steps might take a significantly larger amount of time to compute, e.g., transformed Hessian $\\hat{H}$ in Eq. (2). It would be clearer to provide overall computational complexity in comparison with pure gradient methods and second-order methods. \n\n2. The writing is very technical. While this is not necessarily a weakness, it would be better to provide more intuition illustrating why a faster rate can be obtained.", "was_revised": true, "final_justification": "The authors' response addresses my concerns and I have no further questions.", "rebuttal": "Thank you for your positive feedback and detailed comments!\n\nRegarding your question on the computational complexity of our algorithm, while this aspect is not the primary focus of our work, we agree that it is an interesting question. Although certain components of our algorithm, such as the eigen-decomposition step, may appear more involved than those in the classical Newton method, we note that these operations can also be implemented in $O(d^{\\omega})$ time in the worst case, where $\\omega$ denotes the matrix multiplication exponent [1]. This matches the cost of solving the linear system and the per-iteration cost of Newton method. \n\nBased on this, the overall computational complexity of our algorithm under the parameter setting of Corollary 1 is $\\tilde{O}(d^{7/3}/\\epsilon^{3/2})$. For comparison, the restarted AGD algorithm [2] requires $O(d/\\epsilon^{7/4})$ time, while the Newton method requires $O(d^2/\\epsilon^{3/2})$. Thus, our algorithm improves upon the first order method when $\\epsilon=O(d^{-16/3})$, and exceeds the complexity of the Newton method by only a factor of $d^{1/3}$. We may add more discussion on this in our final version.\n\nWe appreciate your thoughtful comments on the presentation of the paper. In terms of the accessibility of the paper, this is something we care about greatly and would like to improve if we can. In the submission, in Section 1.1, we included a detailed comparison with prior work along with a table that conceptualizes our contributions, in Section 2 we provided an overview of our approach, and we provided a concluding section that summarizes our algorithms and main insights. Nevertheless, we do recognize that the paper discusses trade-offs across multiple oracle models and four parameters, which inherently leads to technical complexity. If there are specific parts of the paper that you believe could benefit from clearer presentation or if you have ideas for helping the paper’s accessibility, we would be eager to hear them. \n\nIn particular, for your question on the intuition regarding the faster rate we obtained, the key insight behind the improved rate lies in Algorithm 1, which is a variant of accelerated gradient descent (AGD) in the Hessian norm. In classical AGD, the step size is chosen to be as large as possible while still respecting the smoothness condition. However, if we have access to local second-order curvature information, it becomes possible to take larger steps along directions with small curvature, thereby accelerating convergence. Algorithm 1 formalizes this intuition. If you have further questions about other aspects of our work, we would be happy to address them as well.\n\n[1]. James Demmel Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik 2007.\n\n[2]. Huan Li and Zhouchen Lin. Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(epsilon^(-7/4)) Complexity. ICML 2023"}, {"review_id": "g8i4hiiJHy", "reviewer": "Reviewer_ZSvX", "summary": "This paper studies non-convex minimization and offers new trade-offs between the number of gradient and Hessian computations.\n\nThe previous methods use $\\mathcal{O}(\\epsilon^{-1/4})$ gradient oracles in the subroutines to decrease the function value by a factor of $\\Omega(\\epsilon^{3/2})$, which leads to the $\\mathcal{O}(\\epsilon^{-7/4})$ queries to the gradient oracle.\nThis paper enhances the subroutine to $\\mathcal{O}(\\delta^{1/2}\\epsilon^{-1/4})$ by incorporating in $\\delta$-inexact Hessian oracle, which allows the reuse of the Hessian.\nBy properly tuning $\\delta$, the proposed method can achieves better computational complexity than the lazy Hessian (Doikov et. al, 2023).\n\nI find the theoretical results presented in this paper are interesting and novel. However, this paper lacks of experiments to check the efficiency of the proposed method, while it requires additional computational cost of the Hessian and its decomposition.", "questions": "1. Theorem 2 requires the condition such that $H \\preceq L_1 I$ (line 156), I am wondering how can this be satisfied in Algorithm 2 when calling the Critical-or-Progress sub-routine?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** the theoretical results obtained by this paper is novel and significant in non-convex optimization. The new trade-off between the gradient and Hessian oracles largely improves the prior-art.\n\n**Weakness:** the paper lacks of experimental part to verify the efficiency of the proposed methods and to validate the proper trade-off between the gradient and Hessians.", "was_revised": true, "final_justification": "I decided to keep my score as it is, which is positive.", "rebuttal": "Thank you for your positive feedback and detailed comments!\n\nRegarding your question on the efficiency of the proposed methods in practice, while this aspect is not the primary focus of our work, we agree that it is an interesting question. We hope our results open the door for such exploration. As a possible direction, we note that our algorithm only requires matrix-vector product access to $\\hat{H}^{-1}$, which could admit more efficient implementations.\n \nRegarding your question on the condition $H \\preceq L_1 I$, thank you for catching this minor issue: It should instead be $H \\preceq 2L_1 I$. The corrected inequality is guaranteed by the gradient Lipschitzness of $f$ and the condition that $\\delta\\leq L_1$."}]

Author rebuttal:

Meta-review: This paper studies the problem of finding an $\varepsilon$-critical point of a non-convex function with Lipschitz continuous gradient and Hessian. The authors propose a new method that combines restarted Accelerated Gradient Descent with preconditioning and lazy Hessian updates. Theoretical analysis establishes new complexity bounds that generalize existing gradient-only results and achieve improved dimension dependence through finite-difference Hessian estimation.

All reviewers agreed that the theoretical contributions are novel and significant for the literature on non-convex optimization. Among the weaknesses noted, the most important is the requirement to compute the spectral decomposition of $\tilde H$, which should be explicitly acknowledged as a limitation (e.g., in the Conclusion section alongside other limitations). Another weakness is the absence of numerical experiments.

Overall, the strengths of this work outweigh its weaknesses. Both the reviewers and I believe that the paper makes a valuable theoretical contribution and should be accepted to NeurIPS.
Decision: Accept (poster)