Stochastic Newton Proximal Extragradient Method
Authors: Ruichen Jiang
Michal Derezinski
Aryan Mokhtari
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic second-order methods
superlinear convergence
hybrid proximal extragradient
Primary area: optimization
TL;DR: With oracle access to exact gradients and noisy Hessians, we propose a stochastic Newton proximal extragradient method with both fast global and local convergence rates for strongly convex functions.

Abstract: Stochastic second-order methods are known to achieve fast local convergence in strongly convex optimization by relying on noisy Hessian estimates to precondition the gradient. Yet, most of these methods achieve superlinear convergence only when the stochastic Hessian noise diminishes, requiring an increase in the per-iteration cost as time progresses. Recent work in \cite{na2022hessian} addressed this issue via a Hessian averaging scheme that achieves a superlinear convergence rate without increasing the per-iteration cost. However, the considered method exhibits a slow global convergence rate, requiring up to $\tilde{\mathcal{O}}(\kappa^2)$ iterations to reach the superlinear rate of $\tilde{\mathcal{O}}((1/t)^{t/2})$, where $\kappa$ is the problem's condition number. In this paper, we propose a novel stochastic Newton proximal extragradient method that significantly improves these bounds, achieving a faster global linear rate and reaching the same fast superlinear rate in  $\tilde{\mathcal{O}}(\kappa)$ iterations. We achieve this by developing a novel extension of the Hybrid Proximal Extragradient (HPE) framework, which simultaneously achieves fast global and local convergence rates for strongly convex functions with access to a noisy Hessian oracle.

Stochastic Newton Proximal Extragradient Method
Ruichen Jiang ECE Department UT Austin rj rjaang@utexas.edu
Michal Dereziński EECS Department University of Michigan derezin@umic edu
Aryan Mokhtari
ECE Department
UT Austin mokhtari@austiin utexas. edu
Abstract
Stochastic second-order methods achieve fast local convergence in strongly convex optimization by using noisy Hessian estimates to precondition the gradient. How- ever, these methods typically reach superlinear convergence only when the stochas- tic Hessian noise diminishes, increasing per-iteration costs over time. Recent work in [ addressed this with a Hessian averaging scheme that achieves superlinear convergence without higher per-iteration costs. Nonetheless, the method has slow global convergence, requiring up to (kx)) iterations to reach the superlinear rate of ((1/1)())) where is the problem's 's condition number. In this paper, we propose a novel stochastic Newton proximal extragradient method that improves these bounds, achieving faster global linear rate and reaching the same fast superlinear rate in (x) iterations. We accomplish this by extending the Hybrid Proximal Extragradient (HPE) framework, achieving fast global and local convergence rates for strongly convex functions with access noisy Hessian oracle.
Introduction
In this paper, we focus on the of second-order methods for solving the optimization problem
min
f(x),
XE2
where f Rd + IR is strongly convex and twice differentiable. There is an extensive literature on second-order methods and their fast local convergence properties; e.g., (2-5). However, these results necessitate access to the exact Hessian, which can pose computational challenges. To address this issue, several studies have explored scenarios where only the exact gradient can be queried, while a stochastic estimate of the Hessian is available similar to the setting we investigate in this paper. This oracle model commonly encountered in large-scale machine learning problems, as computing the gradient is often much less expensive than computing the Hessian, and approximating the Hessian is a more affordable approach. Specifically, consider finite-sun minimization problem minzerd Σx= [z),, where denotes the number of data points and d denotes the dimension of the problem. To achieve fast convergence rate, standard first-order methods need compute one full gradient in each iteration, resulting in per-iteration computational cost of O(nd). In contrast, implementing second-order method such as damped Newton's 's method involves computing the full Hessian, which costs O O(nd)). An inexact Hessian estimate can be constructed efficiently at cost of O(s?)), where is the sketch size or subsampling size I 6). Hence, when the number of samples significantly exceeds d, the per-iteration cost of stochastic second-orda methods becomes comparable to that of first-order methods. Moreover, using second-order information often reduces the number of iterations needed converge, thereby lowering overall computational complexity.
common template among stochastic second-order methods to combine deterministic second- order method, such as Newton's 's method or cubic regularized Newton method, with techniques such as Hessian subsampling 7-12 or Hessian sketching [4] that only require a noisy estimate
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table
Comparison between Algorithm and the stochastic Newton method in M. in terms of how many iterations it takes to transition to each phase, and the convergence rates achieved. We drop constant factors as well as logarithmic dependence and 1/6, and assume 1 1/poly(k) S Y < (K)).
Linear phase
Initial superlinear phase
Final superlinear phase
Methods
Weights
T1
rate Ø
T2
rate 0("
Ta
rate (
Stochastic
Uniform
T
1 x=
x3
T2
Ty
lng(1)
Newton
Non-uniform
g²
1 - k
x²
x²²
T
log(()
Stochastic
Uniform
ya n=
1 - k6
x²
T2
TV logit)
NPE (Ours)
Non-uniform
y2
x
r +
(T
r²
+
r log(t)) vt
of the Hessian. We refer the reader to [14] [5]
for recent surveys and empirical comparisons. In
terms of convergence guarantees, the majority of these works, including 4 6 8 [3], have shown that stochastic second-order methods exhibit a global linear convergence and a local linear-quadratic convergence, either with high probability or in expectation. The linear- linear-quadratic behavior holds when
|xx+1 x'1l S cil|x - x + c2||x, 12,
(2)
where x" denotes the optimal solution of Problem | and C1. C2 are constants depending on the sample/sketch size at each step. In particular, the presence of the linear term in 2 implies that the algorithm can only achieve linear convergence when the iterate is sufficiently close to the optimal solution x". Consequently,
discussed in [ [0), to achieve superlinear convergence, the coefficient c1 C1,t needs to gradually decrease to zero as t increases. However, since 01 is determined by the magnitude of the stochastic noise in the Hessian estimate, this in turn demands the sample/sketch size to increase across the iterations, leading to blow-up of the per-iteration computational cost.
The only prior work addressing this limitation and achieving superlinear rate for stochastic second-order method without requiring the stochastic Hessian noise to converge to zero is by [. It uses weighted average of all past Hessian approximations as the current Hessian estimate. This approach reduces stochastic noise variance in the Hessian estimate, though it introduces bias to the Hessian approximation matrix. When combined with Newton's 's method, it shown that the pro- posed method achieves local superlinear convergence with a non-asymptotic rate of (T (T /log(t)//t) (t) with high probability, where Y characterizes the noise level of the stochastic Hessian oracle (see Assumption 4.. However, the method may require many iterations achieve superlinear convergence. Specifically, with the uniform averaging scheme, it takes ((x2) iterations before the method starts converging superlinearly and Ö(**/ /) iterations before it reaches the final superlinear rate. Here, R = L1/p denotes the condition number of the function f. where L1 is the Lipschitz constant of the gradient and μ is the strong convexity parameter. To address this, [ proposed a weighted averaging scheme that assigns more weight to recent Hessian estimates, improving both transition points to o(r² + x²) while achieving slightly slower superlinear rate of O(T log(t)/Vt).
Our contributions. In this paper, we improve the complexity of Stochastic Newton in [ with method that attains a superlinear rate in significantly fewer iterations. As shown in Table [ our method requires fewer iterations for linear convergence, denoted as Ti, by factor of x² compared to 1. Additionally, our method achieves a linear convergence rate of (1 (1/k))², outperforming the (1 - O(1 / //² rate in IT. Thus, our method reaches the local neighborhood of the optimal solution x" and transitions from linear to superlinear convergence faster. Specifically, the second transition point, T2, smaller by factor of y in both uniform and non-uniform averaging schemes when T = ( k). Similarly, our method's ' initial superlincar rate has better dependence on k, leading to fewer iterations, Ts, enter the final superlinear phase. To achieve this result, we use the brid proximal extragradient (HPE) framework [16] [7] instead of Newton's 's method as the base algorithm. The HPE framework provides principled approach for designing second-order methods with superior global convergence guarantees [7)7220] However, [16] and subsequent works focus on cases where / is merely convex, not leveraging strong convexity. Thus, we modify the HPE framework to suit our setting. Specifically, we relax the error condition for computing the proximal step in HPE, enabling a larger step size when the iterate is close to the optimal solution, crucial for achieving the final superlinear convergence rate.
2

---

2 Preliminaries
In this section, we formally present our assumptions.
Assumption 1. The function I is twice disserentiable and p--ttrongly convex.
Assumption 2. The Hessian 2 f satisfies | f(x) fyy( - M1.
Assumption 3. The Hessian 4 is Lz-Lipschitz, i.e., V f(y)ll S L2||x yl22-
Assumption is more general than the assumption that V is Li-Lipschitz. In particular, the latter assumption holds, then M1 S [1. Moreover, we define x _ Mi/1² as the condition number.
To simplify our notation, we denote the exact gradient V fx() and the exact Hessian fx)( of the objective function by g(x) and H()), respectively. As mentioned earlier, we assume that we have access to the exact gradient, but we only have access to a noisy estimate of the Hessian denoted by H()). In fact, we require mild assumption on the Hessian noise. We define the stochastic Hessian noise E(x) H(x) - Hx),, where it is assumed to be mean zero and sub- sub-exponential.
Assumption 4. If we define E(x) A H(x) H(x), then [[](x)] = 0 and [[] S 2/2
for all integers p 2 2. Also, define Y a TE/ p to be the relative noise level.
Assumption 5. The Hessian approximation matrix positive semi-definite, i.e., H(x) = Vx R.
Stochastic Hessian construction. The two most popular approaches to construct stochastic Hessian approximations are "subsampling" and "sketching". Hessian subsampling is designed for a finite-sum objective of the form f(xx = [x(x), where n is the number of samples. In each iteration, subset S 21, ...., n is drawn uniformly at random, and then the subsampled Hessian at constructed as Hx) = + Eies v In this case, if each fa is convex, then the condition in Assumption S is satisfied. Moreover, if we further assume that [[ S cM1 for some
A is satisfied with Y = (lV/o log (d) + cs log(d) ( (see M Example IJ.. The other approach is Hessian sketching, applicable when the Hessian H
> 0 and for all i, then Assumption
can be easily factorized H M M. where M E Raxd is the square-root Hessian matrix, and n is the number of samples. This is the case for generalized linear models; see (.. To form the sketched Hessian, we draw random sketch matrix S E Rx*= with sketch size from a distribution D that satisfies Ep[S S] = I. The sketched Hessian is then H = M S SM. In this case, Assumption is automatically satisfied. Moreover, for Gaussian sketch, Assumption 4 is satisfied with Y = O(K( /d//s/// d/s)) (see [ Example 2)).
Remark 1. The above assumptions are common in the study of stochastic second-order methods, appearing in works on Subsampled Newton [7 [2]. Newton Sketch 4 6 and notably, M- The strong convexity requirement is crucial stochastic second-order methods have clear advantage over first-order methods like gradient descent when the function is strongly convex. Specifically, stochastic second-order methods attain superlincar convergence rate, shown in this paper, which is superior to the linear rate of first-order methods.
3 Stochastic Newton Proximal Extragradient
Our approach involves developing a stochastic Newton-type method grounded in the Hybrid Proximal Extragradient (HPF) framework and its second-order variant. Therefore, before introducing our proposed algorithm, we will provide brief overview of the core principles of the HPE framework. Following this, we will present our method as it applies to the specific setting addressed in this paper.
Hybrid Proximal Extragradient. Next, we first present the Hybrid Proximal Extragradient (HPE) framework for strongly convex functions. To solve problem (T). the HPE algorithm consists of two steps. In the first step, given Xt, we find mid-point x, by applying an inexact proximal point update x X 1), (xx)), where 1/ the step size. More precisely, we require
-
+ M/ V (X.)) S aa & xxll-
where 7 = 1 + 21)44, μ is the strong convexity parameter, and a E (0, 1) is a user-specified parameter. Then, in the second step, we perform the extra-gradient update and compute x based on
1
f(x))) + (1 - &..
X
- [xt
(4)
7
3

---

The weights 1. in the above convex combination are chosen to optimize the convergence rate.
Remark 2. When μ = O, the algorithm outline above reduces to the original HPE framework studied
in [8. Our modification in 3 is inspired by [21 and allows larger error when performing the inexact proximal point update, which turns out to be crucial for achieving a fast superlinear convergence rate. Moreover, the modification in 44) has been adopted in (22).
Stochastic Newton Proximal Extragradient (SNPE). The HPE method described above provides a useful algorithmic framework, instead of a directly implementable method. The main challenge comes from implementing the first step in (3). which involves inexact proximal point update. Specifically, the naive approach is to solve the implicit nonlinear equation x - X, + 7% f = O, which can be as costly as solving the original problem in ( To address this issue, [8] proposed to approximate
the gradient operator V fx) by its local linearization V fx(, + f (x xt), and then compute &, by solving the linear system of equations & x, ne (V V leads to the Newton proximal extragradient method that was proposed and analyzed in [8]
fxx)
xx)) 0. This
However, in our setting, the exact Hessian 4 fxx( is not available. Thus, we construct stochastic Hessian approximation H, from our noisy Hessian oracle as surrogate of V (xx). We will elaborate on the construction of He later, but for the present discussion assume that this stochastic Hessian approximation H, is already provided. Then in the first step, will compute & by
x =x x No (x(() H -x));
(5)
where we replace ((x) by its local linear approximation vx((x)) + H&,
xt). xx)). Moreover, 5 is equivalent to solving the following linear system of equations (I + 77, H, - xx,) = (x,) For ease of presentation, we set & as the exact solution of this system, leading
x x, n. + n.H,) -
(6)
However, we note that an inexact solution to this linear system is also sufficient for our convergence guarantees so long as [[ + H.) - xx) + n [(xe)l < g
1 We refer the reader to Appendix A.3 for details. Additionally, since we employed a linear approximation to determine the mid-point X,, the condition in 33 may no longer be satisfied. Consequently, it is crucial to verify the accuracy of our approximation after selecting X,. To achieve this, we implement a sinerh scheme to ensure that the step size is not large and the linear approximation error is small.
Next, we discuss constructing the stochastic Hessian approximation H₃. A simple strategy is using (x,,) instead of ~ <xf(x;), but the Hessian noise would lead to highly inaccurate approximation of the prox operator, ruining the superlinear convergence rate. To reduce Hessian noise, we follow 1 and use an averaged Hessian estimate (xx)). We consider two schemes: (i) uniform averaging; (ii) non- uniform averaging with general weights. In the first case, H, = =+1 El=o H(x: Juniformly averages past stochastic Hessian approximations. Motivated by the central limit theorem for martingale differences, we expect H. to have smaller variance than Hx))) It can be implemented online as H. = H + F.I H(x)), without storing past Hessian estimates. However, Hxx;) is biased estimator of V f(x)), since it incorporates stale Hessian information. To address the striinar trade-off, the second case uses non-uniform averaging to weight recent Hessian estimates more. Given increasing non-negative weight sequence {w; ce with w_ 0, the running average is:
H.
Wt-1 H + (1 Wt-1
(x;).
W/
We
Equivalently, with Zz,t wy
Wi-1 H. can be written as
Σ c. H Hxx)). We discuss uniform
averaging in Section 4 and non-uniform averaging in Section
Building on the discussion thus far, we are ready to integrate all the components and present our Stochastic Newton Proximal Extragradient (SNPE) method. The steps of SNPE are summarized in Algorithm I Each iteration of our SNPE method includes two stages. In the first stage, starting with the current point Xt, we first query the noisy Hessian oracle and compute the averaged stochastic Hessian H. from 7 as stated in Step 4. Then given the gradient fxx)), the Hessian approximation H,, and an initial trial step size at, we employ a backtracking line search to obtain T) and &,, as stated in Step 6 of Algorithm Specifically, in this step, set 7) +- o; and compute x; as suggested

---

Algorithm 1 Stochastic NPE
Subroutine (1, = BLS g, H. a, 3,
1: Input: Xo E 184, weights {wi J line-search parameters a, 3 E (0, 1), initial step size do
1: Input: current iterate x E R gradient Hessian approximation H E R Rx line-search parameters a, E (0,1), initial trial step size o >0
R²,
2: Initialize: H = 0 and w-1 = 0
3: for t 0, 1, do
2: Set rj < a and x +- x 1/(1 + rH) ''
4: Obtain a stochastic Hessian H, = Hx+))
3: S 7 f- 1 2714
5: Compute H.- = " + "1_1 He
4: while || - x + V f > a/ - do
my
6: (Me, x,) = BLS(x,, (x,) He, a, a,
5: Set 17 - Bn and & + x 11 -H)
7:
Let 7/ = + 217e/1 and compute
6: Set T <- 1 + 27/1
X(+1 1 (x: to (xx)) + )x,,
7: end while
75
70
8:
Set dr+1 n1B
8: Output: 77 and x
9:
end for
in (6). If & and its corresponding step size 17, satisfy (3). meaning the linear approximation error is small, then the step size Qtd and the mid-point X; are accepted and we proceed to the second stage of SNPE. If not, we backtrack the step size 1/: and try smaller step size Br,, where /3 E (0, 1) is user-specified parameter. We repeat the process until the condition (3) is satisfied. The details of the backtracking line search scheme are summarized in Subroutine [T After completing the first stage and obtaining the pair (1,, xt), we proceed to the extragradient step and follow the update in A as in Step 7 of Algorithm [ Finally, before moving to the next time index, we follow warm-start strategy and set the next initial trial step size 0++1 as ////B 3, as shown in Step 8 of Algorithm [
Remark 3. Similar to the analysis in [22], we can show that the total number of line search steps after t iterations can be bounded by 21 - 1 + log( ) Moreover, when / is large enough, on average the line search requires 2 steps per iteration. We defer the details to Appendix A.4
Remark Our motivation behind the choice 0 n is to allow the step size to grow, which is necessary for achieving a superlinear convergence rate. Specifically, as shown in Proposition
below, we require the step size т) to go to infinity to ensure that lim,- X
||x,-1-x"|
0. Note
that this would not be possible if we simply set c+1 Ths since it would automatically result in M I 0t+1 S .7. Moreover, this condition 0++1 nt/ is explicitly utilized in Lemmas 8 and 16 in the Appendix, where we demonstrate that 7) can be lower bounded by the minimum of 0 S and another term. We should also note that this more aggressive choice of the initial step size at each round could potentially increase the number of backtracking steps. However, as mentioned above, this does not cause significant issue, since the average number of backtracking steps per iteration can be bounded by a constant close to 2.
3.1 Key properties of SNPE
This section outlines key properties of SNPE, applied in Sections and determine its convergence rates. The first result reveals the connection between SNPE's ss convergence rate and the step size T)-- Proposition 1. Let (xe1e20 and (x1 h12 be the iterates generated by Algorithm Then for any t 2 O. we have ||x x"1
< |X x" (1 21),1)
Proposition guarantees that the distance the optimal solution is monotonically decreasing, and shows a larger step size implies faster convergence. Hence, we need to provide an explicit lower bound on the step size. This task is accomplished in the next lemma. For ease of notation, we let B be the set of iteration indices where the line search scheme backtracks, i.e., B & {t m < at). Moreover. we use g(x) and H(x) to denote the gradient fx( and the Hessian V fxx, respectively.
Lemma 1. For t & B, we have πi or- For E B, let te = ne/B and X; X, H, -(x((). Then, || xell S 3/4 ||*x xell. Moreover,
5j (I
a.81 |24 xi|l
2a Bp 1x - x
2 max
[lg())) - g(x:) H - xx) [lg(x;) - g(x.) H (Xc- - x22
As Lemma demonstrates, in the first case where E B, we have 7/t = are Moreover, since we set
oe Th- for t 2 1, in this case the step size will increase by factor of 1/8. In the second case
5

---

that t E B, our lower bound on the step size nu depends inversely on the normalized approximation error & = (Ix(,,) )(x)) xxxxll Also, note that & involves an auxiliary iterate x instead the
| xi
actual iterate x, accepted by our line search. We use the first result to relate | - x+l to || x
To shed light on our analysis, we use the triangle inequality and decompose this error into two terms:
& llg({))
(xx (x, xx)Il + ||H H.l
(8)
[x
x ||
The first term in (8) represents the intrinsic error from the linear approximation in the inexact proximal update, while the second term arises from the Hessian approximation error. Using the smoothness properties of f. we can upper bound the first term, as shown in the following lemma.
Lemma 2. Under Assumptions 2 and 3
we have
llg(()) g(x,) H, (R: x:)l S min M1
Lel -xx1
&
x
28 a²
Lemma shows that the linear approximation error is upper bounded by M1- Moreover, the second upper bound is O[Ixx - []). Thus, as Algorithm I converges to the optimal solution x', the second bound in ( will become tighter than the first one, and the right hand side approaches zero.
To analyze the second term (8) we isolate the noise component in our averaged Hessian estimate. Specifically, recall H, = Ei=oza H, and H. = H. + Eg. Thus, we have H, = H, + E,, where H H2 is the aggregated Hessian and E, = Σi_ E, is the aggregated Hessian noise,
H. = E 2,, and it follows from the triangle inequality that ||H, H, first part, HH, Hell. as the bias of our Hessian estimate, and the second part, EE l. as the averaged stochastic error. There is intrinsic trade-off between the two error terms. For the fastest error concentration, we assign equal weights to all past stochastic Hessian noises, i.e., Ri,e all 0 S i S. L, corresponding bias, we assign all weights to the most recent Hessian matrix H,, i.e., ž,, = 1 and ži, = 0 for all i < t, but this incurs a large stochastic error. To balance these, we present a weighted averaging scheme in Section 5 gradually assigning more weight to recent stochastic Hessian approximations.
H. H. E We refer the
1/(t + 1) for To eliminate
the uniform averaging scheme discussed in Section
4 Analysis of uniform Hessian averaging
In this section, we present the convergence analysis of the uniform Hessian averaging scheme, where Wt = f + 1. In this case, we have H, = - Z H. As discussed in Section 3.1 our main task to lower bound the step size ne. which requires us to control the approximation error & by analyzing the two error terms in (8). The first term is bounded by Lemma 2 and the second term can be bounded as HH, H, || < H, H.ll + |E,]]_ Next, we establish a bound on ||E|]], referred to as the Averaged Stochastic Error, and a bound on [He He|/, referred to as the Bias Term.
Averaged stochastic error. To control the averaged Hessian noise of sub-exponential martingale difference, as shown in [[]
|E |l. we rely on the concentration
Lemma 3 ( Lemma 21). Let ó E (0, 1) with d/8 2 e. Then with probability - 8 /6, we have (og(d(++1)/6) for any t 2 4log(d (d/8). t-1
|E < 8T
Lemma shooss that, with high probability, the norm of averaged Hessian noise |E, approaches zero at the rate of Ö e/ /t). As discussed in Section 4.1 this eтror eventually becomes the dominant factor in the approximation error & and determines the final superlinear rate of our algorithm.
Remark Our subsequent results are conditioned on the event that the bound on || stated in Lemma 3 is satisfied for all / > 4 log(d/)). Thus, to avoid redundancy, we will omit the "with high probability" qualification in the following discussion.
Bias. We proceed to establish an upper bound on |H, H.|l The proof can be found in Appendix B.1
i-1 Eiso H, - Hill. Moreover, for any i > 0, we have H,, H.ll 5 max 2L | x" []].
Lemma 4. If H t+1
1 Eizo H. then |HH Hyll S 1

---

The analysis of the bias term is more complicated. Specifically, to obtain the best result, we break the sum in Lemma 4 into two parts, & + |H - H,ll and / + |H; Hill, where I is an integer to be specified later. The first part corresponds to the bias from stale Hessian information and converges to zero (M, shown by the first bound in Lemma 4 The second part is the bias from recent Hessian information when the iterates are near the optimal solution x". Using the second bound in Lemma | show this part contributes less to the total bias and is dominated by the first Mr2 part. Thus, we can conclude that [ H. O 2-1
Based on the previous discussions, it is evident that the terms contributing to the upper bound of & all converge to zero, albeit different rates. Furthermore, the linear approximation error and bias term display distinct global and local convergence patterns, depending on the distance ||x, - x*| ||. Hence, this necessitates multi-phase convergence analysis, which we undertake in the following section.
4.1 Convergence analysis
Similar to [ we consider four convergence phases with three transitions points Ti, T2, and Ts. whose expressions will be specified later. Due to space limitations, in the following we provide an overview of the four phases and relegate the details to Appendix B
Warm-up phase 0 < / < Ti. At the beginning of the algorithm, the averaged Hessian estimate is dominated by stochastic noise and provides little useful information for convergence. Thus, there are generally no guarantees on the convergence rate for 0 < t < T1. However, due to the line search scheme, Proposition! Conssitionnennuuu ensures that the distance to x* is non-increasing, i.e. ||x,_1 100-1-xxi xx S ||xx-xx -x") for all 2 0. During the warm-up phase, the averaged Hessian noise |Eg]|, which contributes most to the approximation error & is gradually suppressed. Once the averaged Hessian noise is sufficiently concentrated, Algorithm| transitions to the linear convergence phase, denoted by T1.
Linear convergence phase Ti S t Tz. After Ti iterations, Algorithm starts converging linearly to the optimal solution x". Moreover, during this phase, all the three errors discussed in Section 3.] continue to decrease. Specifically, Lemma (aamaaassooo shows the linear approximation error is bounded by x[|x, x" I)). which converges to zero at a linear rate. Furthermore, Lemma 3 implies that the averaged Hessian error |E,|l diminishes at a rate of Ó (z). Finally, regarding the bias term, it can
be shown HH, H.|l = O A following the discussions after Lemma 4 Thus, once all the three errors are sufficiently small, Algorithm | moves the superlinear phase, denoted by Tz.
Superlinear phases To S t < Ta and Ts S < Ta. After Tz iterations, Algorithm I converges at superlinear rate. Moreover, the superlinear rate is determined by the averaged noise |Eell, which decays the rate of Ō (TTx)) ), and the bias of our averaged Hessian estimate H,, which decays the
rate of O M,I), Hence, as the number of iterations / increases, the averaged noise will dominate and the algorithm transitions from the initial superlinear rate to the final superlinear rate.
We summarize our convergence guarantees in the following theorem and the proofs are in Appendix B
Theorem Suppose Assumptions V hold and the weights for Hessian averaging in SNPE are
uniform, and define C := 28v1-o + 5. Then, the followings hold:
(a) Warm-up phase: 1f0 S t Tú, then [|x++1 x S 1|x, - x" where Ti =
(b) Linear convergence phase: Ii S < T2, then [|x++1 - x 1|x: - x 112
200
)-1
3m
where To = Ómaxx I +x² r2)) Ö(r² + x2))
(c) Initial superlinear phase: For To < t <
Ts. we have ||x x"1 S Cpt
1 - x" 11
|x
G.T. Ö T2 /n/t? with I defined in
Ta = 8 (T2 /T²/ntx212
where Pi
28 and
av20(t+1]
T
(d) Final superlinear phase: Finally, for t 2 Ts. we have || x"1 where Pt (2)
S Cpt²)
(2)
||x - xx1
8/27
log(dit+1)/5)
log(t)
1+1
Comparison with 11. As shown in Table 1 our method in Algorithm [ with uniform averaging
achieves the same final superlinear convergence rate as the stochastic Newton method in 0. However, it transitions to the linear and superlinear phases much carlier. Specifically, the initial transition point
7

---

Ti is improved by a factor of x², and our linear rate in Lemma 6 is faster. This reduces the iterations needed reach the local neighborhood, cutting the time to reach T2 and 7z by factors of and x²?
Analysis of weighted Hessian averaging
Previously, we showed Algorithm with uniform averaging eventually achieves superlinear conver- gence. However, as per Theorem it requires O( y2) iterations reach this rate. To achieve a faster transition, we follow [ and use Hessian averaging with general weight sequence {we) We show this method also outperforms the stochastic Newton method in [1. Specifically,
set wt = w(() for all integer 2 0, where wo(-)= R + R satisfies certain regularity conditions as in [ Assumption 3].
Assumption (i) w=-) is twice differentiable; (ii) w(
1) = O, w(t) > O, Vt 2 0: (iii) w (-1) 2 0:
(iv) w" (t) vt 2 -1; (v) max
[c(t--1 w/ wl(++1) ((1)
T7, v4 0 for some V 1 1.
w'( (1)
Choosing (tt) = t" for any 2 1 satisfies Assumption 6 Additionally, as discussed in [ suitable
choice is w(() (t + 1)loR((+44), allowing us to achieve the optimal transition to the superlinear rate. Since the analysis in this section closely resembles that in Section 4 on uniform averaging, we will only present the final result here for brevity. The four stages of convergence are detailed in the following theorem, with intermediate lemmas and proofs in the appendix. To simplify our bounds,
we report results for non- non-umiform averaging with w(t) (t 1) (ogg((t+))
Theorem 2. Suppose Assumptions 75 holl and the weights for Hessian averaging in SNPE are defined as (I) = (L + 1))og((+1), and define C" 1088/201 22) + a2). Then, the following hold:
(a) Warm-up phase: If0 1 < Uh, then |xx++ x |x, x" 11. where Ui = 00(
(b) Linear convergence phase: If Ui S < U2, then ||x++] - x" 1|? S ||x xxxxx0 x*112(1+
20x3 )-1
3x
where U2 Ó(mxx T² (5 + Kc r2)
Ö(r² + ni).
(c) Initial supertinear phase: If U2 S t < Uz. then |x++1 x"1 < C'0 1|x - -x" ||, where
8 av(3u((t)
(a((T++a))leet (0) (00022/))000) /joxs) with J defined in 449 and U3 - +k).
(d) Final superlinear phase: Finally, if 2 U3 then ||xe+1 - x*| S C ||: - x" 11. where
SV
(1) log(d O m(()
T log(())
Vt
In the weighted averaging case, similar to the uniform averaging scenario, we observe four distinct phases of convergence. The warm-up phase for SNPE, during which the distance to the optimal solution does not increase, has the same duration as in the uniform averaging case but is shorter than the warm-up phase for the stochastic Newton method in [1] by factor of 1/x². The linear convergence rates of both uniform and weighted Hessian averaging methods are - K improving over the -² rate achieved by the stochastic Newton method in [I. The number of iterations to reach the initial superlinear phase is O(r² +)) smaller than the Ō(k²) needed for uniform averaging in SNPE when we focus on the regime where T = (())). The non- uniform averaging method in [ requires x² iterations to achieve the initial superlinear phase, whereas the non-uniform SNPE achieves an initial superlinear rate of O (x(oog())++ /t)², improving over the rate of (n, log(s)+1 /floR(t)) y in [I]. Finally, while the ultimate superlinear rates in all cases are comparable at approximately (((1/V))) the non-uniform version of SNPE requires ( + ss) iterations attain this fast rate, whereas I 'ss non-uniform version requires ((x²) iterations, which is less favorable.
Remark 6. As discussed in [ Example 1], with subsampling size of s, we have T = Ö(t/s) for subsampled Newton. This implies that when ((vK), we achieve T = O(VR).
6 Discussion and complexity comparison
In this section, we compare the complexity of our method with accelerated gradient descent (AGD), damped Newton, and stochastic Newton [1] methods. The iteration complexities of these methods are summarized in Table 2 which we use to establish their overall complexities. Note that since both stochastic Newton and our proposed SNPE method achieve superlinear convergence, their
8

---

Table 2: Comparisons terms of overall iteration complexity to find an e-accurate solution.
Methods
AGD
Damped Newton
Stochastic Newton
1
SNPE (Ours)
Iteration
Olg//o((1/e)
O1 +(x2++ogloge HloglogggHl (og(/)))
O(T + + log (1//e)
log)
O(T + log (17e)
log(1
than the complexity of AGD by at least a factor of log log(e log log(1/e) which is provably better
complexities depend on the target accuracy e in the form O log(3/e)
Further details are provided in Appendix D.I To better compare them, we focus on the finite-sum problem with functions:
minlzgR" fi (ar). Let e be the target accuracy, A the condition number, and T the noise level in Assumption 4 In this case, computing the exact gradient and Hessian costs ((nd) and (nd?), respectively. Thus, the per-iteration cost for AGI is (nd)) Each iteration of damped Newton's 's method requires computing the full Hessian and solving a linear system, resulting in a total per- iteration cost of Ond + d For both stochastic Newton in [1] and our SNPE method, the per-iteration cost depends on how the stochastic Hessian is constructed. For example, Subsampled Newton constructs the Hessian estimate with a cost of (sse), where s denotes the sample size. Newton Sketch has a similar computation cost (see (6). Additionally, it takes (ndd) to compute the full gradient and (dd) to solve the linear system. Since the sample/sketch size is typically chosen as s (d), the total per-iteration cost is O(nd + d)).
Compared to AGD, SNPE achieves better iteration complexity. Specifically, when the noise level T and target accuracy are relatively small (T = O(Kk) and log 52( (K)) SNPE converges in fewer iterations. Additionally, when 2 d2 (indicating many samples). the per-iteration costs of both methods are (nd), giving our method a better overall complexity.
Compared to damped Newton's 's method, our method's iteration complexity depends better on the condition number K, while damped Newton's 's depends better on e. However, when n d², the per-iteration cost of damped Newton is Ondd), significantly more than our method's ((d)..
Compared to the stochastic Newton method in [. the per-iteration costs of both methods are similar. However, Table shows that our iteration complexity is strictly better. Specifically, when the noise level is relatively small compared to the condition number, i.e., Y = ((Vr), the complexity of SNPE improves by an additional factor of over the stochastic Newton method.
7 Numerical experiments
While our focus is on improving theoretical guarantees, we also provide simple experiments to showcase our method's improvements. All simulations are implemented on Windows PC with an AMD processor and 16GB Memory. We consider minimizing the regularized log-sum-cxp
objective (xx p log(EE Σi_ exp(( xxx==1))) + _ |x|2 common test function for second-order due to its high ill-conditioning. Here, À > is regularization parameter, p is a smoothing parameter, and the entries of the vectors a...... a, E RR and b E Rd are randomly generated from the standard normal distribution and the uniform distribution over [0, 1]. respectively. In our experiments, the regularization parameter À is 10 the dimension d is 500, and the number of samples n is chosen from 50,000, 10,000, and 1 150,000, respectively.
methods 23
24
We compare our SNPE method with the stochastic Newton method in using both uniform Hessian averaging (Section 4 and weighted averaging (Section 55) In addition, we evaluate it against accelcrated gradient descent (AGD), damped Newton's 's method, and Newton Proximal Extragradient (NPE), which corresponds to our SNPE method with the exact Hessian. For the stochastic Hessian estimate, we use a subsampling strategy with subsampling size of s = 500. Empirically, we found that the extragradient step (Line in Algorithm [ tends slow down convergence. To address this, we consider a variant of our method without the extragradient step, modifying Line X X In Figure 3 of the Appendix, we further explore the effect the extragradient step. We also note that similar observations were made in 19, where the simple iteration X,+1 outperformed "accelerated" second-order methods. From Figures [annd] [ observations:
X (I + H,H
we have the following

---

12" 2APE (elley
10"
107
Iteration
iteration
Iteration
(a) 50, 000, 500
(b) 100, 000, d 500
(c) 150, 000, 500
Figure 1: Iteration complexity comparison for minimizing log-sum-exp on synthetic dataset.
10
10
1011
100
10'
10"
Scpping
(A Woot Pr
16
10
Boon
(a) 7 50, 000, d = 500
(b) 100, 000, d = 500
(c) m 150, 000, d 500
Figure 2: Runtime comparison for minimizing log-sum-exp on synthetic dataset.
Comparison with stochastic Newton. In all cases, our SNPE method outperforms stochastic Newton in both the number of iterations and runtime, due the problem's highly ill-conditioned nature and our method's better dependence on the condition number.
observe that our SNPE method, with either uniform weighted averaging, requires far fewer iterations to converge than AGD due to the use of second-order information. Consequently, while SNPE has higher per-iteration cost than AGD, it converges faster overall in terms of runtime, as demonstrated in Figure
Comparison with AGD. From Figure 1
Comparison with the damped Newton's method and NPE. As expected, since both damped Newton and NPE use exact Hessian, Figure shows that they exhibit superlinear convergence and converge in fewer iterations than the other algorithms. However, since the exact Hessian matrix is expensive to compute, they incur a high per-iteration computational cost and overall take more time than our proposed SNPE method to converge (see Figure Z. Moreover, the gap between these two methods and SNPE widens as the number of samples n increases, demonstrating the advantage of method in the large data regime.
8 Conclusions and limitations
We introduced a stochastic variant of the Newton Proximal Extragradient method (SNPE) for min- imizing a strongly convex and smooth function with access noisy Hessian. Our contributions include establishing convergence guarantees under two Hessian averaging schemes: uniform and non-uniform. We characterized the computational complexity in both cases and demonstrated that SNPE outperforms the best- results for the considered problem. A limitation of our theory is assumption of strong convexity. Extending the theory to convex setting would make it more general. This extension is left for future work due to space limitations.
Acknowledgments
The research of R. Jiang and A. Mokhtari supported in part by the NSF Grant 2007668, NSF AI Institute for Foundations of Machine Learning (IFML), and the Wireless Networking and Communications Group (WNCG) Industrial Affiliates Program at UT Austin. The research of M. Dereziński was partially supported by NSF grant CCF-2338655.
10

---

References
[1] Sen Na, Michal Derezinski, and Michael W Mahoney, Hessian averaging in stochastic Newton methods achieves superlinear convergence. Mathematical Programming, pages 1 1-48, 2022.
[2] Yu Nesterov. Accelerating the cubic regularization of Newton's method on convex problems. Mathematical Programming, 11((1):19--81, 2008.
[3] Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization,, 23(2):1092-1111 2013.
[4] Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning in linear time. The Journal of Machine Learning Research, 18(1):4148-418) 2017.
[5] Guy Kornowski and Ohad Shamir. High-order oracle complexity of smooth and strongly convex optimization. arXiv preprint arXiv:2010.06642, 2020.
[6] Mert Pilanci and Martin J Wainwright. Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence. SIAM Journal on Optimization, 27(1):205-245, 2017.
[7] Richard H Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic Hes- sian information in optimization methods for machine learning. SIAM Journal on Optimization, 21(3):977-995, 2011.
[8] Murat A Erdogdu and Andrea Montanari. Convergence rates sub-sampled Newton methods. Advances in Neural Information Processing Systems, 28, 2015.
[9] Raghu Bollapragada, Richard H Byrd, and Jorge Nocedal. Exact and inexact subsampled Newton methods for optimization. IMA Journal of Numerical Analysis, 39(2):545-573 2019.
[10] Farbod Roosta- Khorasani and Michael W Mahoney. Sub-sampled Newton methods. Mathemat- ical Programming, 174:293-326, 2019.
[11] Michal Derezinski and Michael W Mahoney. Distributed estimation of the inverse hessian by determinantal averaging. Advances in Neural Information Processing Systems, 32, 2019.
[12] Haishan Ye, Luo Luo, and Zhihua Zhang. Approximate Newton methods. Journal of Machine Learning Research, 22(66): 1-:1) 2021.
[13] Michal Derezinski, Jonathan Lacotte, Mert Pilanci, and Michael W Mahoney. Newton-LESS. Sparsification without trade-off's for the sketched Newton update. Advances in Neural Informa- tion Processing Systems, 34:2835-2841 2021.
[14] Albert S Berahas, Raghu Bollapragada, and Jorge Nocedal. An investigation of Newton-sketch and subsampled Newton methods. Optimization Methods and Software, 35(4))661-680, 2020.
[15) Michat Dereziński and Michael W Mahoney. Recent and upcoming developments in randomized numerical linear algebra for machine learning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 6470-6479, 2024.
[16] Mikhail V Solodov and Benar Svaiter. A hybrid approximate pereggraddeet-proxiiine point algorithm using the enlargement of maximal monotone operator. Set-Valued Analysis, 7(4):323- 345, 1999.
[17] Renato DC Monteiro and Benar F Svaiter. Iteration-complexity of a Newton proximal extragra- dient method for monotone variational inequalities and inclusion problems. SIAM Journal on Optimization, 22(3):914-935, 2012.
[18] Renato D. C. Monteiro and B. F. Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):2755-2787) 2010.

---

[19] Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adaptive Monteiro-Svaitee acceleration. Advances Neural Information Processing Systems, 35:20338-2005 2022.
[20] Dmitry Kovalev and Alexander Gasnikov. The first optimal acceleration of high-order methods in smooth convex optimization. Advances in Neural Information Processing Systems, 35:35339 35351, 2022.
[21] Mathieu Barré, Adrien Taylor, and Francis Bach. A note approximate accelerated forward- backward methods with absolute and relative errors, and possibly strongly convex objectives. Open Journal of Mathematical Optimization, 3:1-15, 2022.
[22] Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approxi- mation: A quasi-Newton method with global non-asymptotic superlinear convergence. arXiv preprint arXiv:2302.08855 302.00800,00... 2023.
[23] Konstantin Mishchenko. Regularized Newton method with global convergence. SIAM Journal on Optimizationn, 33(3):1440-1462. 2023.
[24] Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. Super-universal regularized Newton method. SIAM Journal on Optimization, 34(1):27-56, 2024.
[25] Yurii Nesterov. Lectures on Convex Optimization. Springer International Publishing, 2018.
12

---

Appendix
A Missing proofs in Section 3
A.1 Proof of Proposition T
In this section, we prove Proposition 1 In fact, using the same proof, we can also show an additional result that upper bounds ||x, - &e|1, which will useful in the proof of Lemma Therefore, we present the full version below for completeness.
Proposition 2 (Full version of Proposition D. Let (xe3120 and {&e fe2 be the iterates generated by Algorithm
7 Then for any t 2 O, we have ||x4+1 x 112 ||xs x=11²(1 + 21//4) and ||xe &cll S V 1|x x"1
Proof. Our proof is inspired by the approach in 12 Proposition 1J. For any x E TRd, we first write
[ & x) (Xt- + ve V (Xt): & x) (x: 8c, 8, -x).
(10)
To begin with, we bound the first term in TT) by
(x, X + 77 V&()), & x)
| - X + 17 f (xx &R. - x||
I v 1 + 217 {x /1/ x||
a²
1 + 277H4
E x=
| x11
(11)
where the first inequality is due to Cauchy-Schwand inequality, the second inequality is due to the condition in (3), and the last inequality is due Young's 's inequality. Moreover, for the second term in (TO). we use the three-point equality to get
1 2
(x1
&
x)
x|1
||x, - 8e112 211:: x112.
(12)
By combining TO
and
12
we obtain that
1 a
(x,)) &
|xxe
x||²
||x: - xxel2 + mc1llss x112
(13)
2
2
Moreover, it follows from the update rule in (4) that T/. V (Xx.) = xx Xx+1 + 27
x(+1).
This implies that, for any x E Idd.
( -x) (xt X Xx+1 - x) + 21/ Xx+1, Xx41 x)
(14)
x; x|| || Xe+ 2
+
27/
[x++] - x|| + malls x|| n//0//82
X 11
2
2
(15)
where we applied the three-point equality twice in the last equality. Thus, by combining 13 with 1 and (15 with x x", we get
Th V f(x
X
x*)
no V (xc) Xx+1 xx)
Mot V f(x)(())))))))))))))
x(+1)
X
x $12
10-=xX(-111
1 271114
|x++1 - 1x11| 2/ no - xx111 mallis
x+1113
2
H
x1+1/12
1 l-a²
||x:- - x211 m:HllisE - - x1+1113.
2
2
(16)
Since fx(x') = O and f u-strongly convex, we further have X, Combining (16) and (17) and rearranging the terms, we obtain that 21
(V (xx,), &, - x*) = ($x) - fx(x") ), x*) 2 u|| - x12
(17)
o
Xx+1 113 |xx x
2 ||x E 12.
(18)
Since a 1, the last term in (8) negative and we immediately obtain that || 11 <
X
x* (1 + 21):4) Moreover, since 1+27.0 X 112 > 0, it follows that --a² ||xe
& 2
2
|x x²1 1|3, which leads to ||x, - xc/| < --- |xx, - x²1 The proof is complete.
13

---

A.2 Proof of Lemma 1
Recall that in our backtracking line search scheme Algorithm [ the step size th starts from dr and keeps backtracking until the condition in (3) is satisfied. Hence, by the definition of B, it immediately follows that 7/t = ag if & B. Moreover, if E B, then the step size īj = m//B and the corresponding iterate &, must have failed the condition in (3) (Otherwise, our line search scheme would have accepted the step size i instead). This implies that
+ 7o fxx)) Dav14 27 xx|1
(19)
Since X = =x - 7/ (I + 77 H.)
V f (xx),
we have
x + ij H [x+ xx) - Vf
X X2 - (Vf((x)) + H1(x: xi)).
and hence the lent-hand side in 19 equals to ip V (xx)) Vs((x) - H. -x))ll Thus, we obtain from 19 that
av I + 27/ x: Xx
f (
(20)
fx(,)) H, (xx xx)ll
By substituting 7/ Bij, we further have
aB 1 20/////1 x
Te [V)() (x())) H, x:)|
Using the fact that 1 2m/1/pp B 1, we get
aB113x X,
1t
(21)
[V}(() fx(,)) H, (X, xx)Il
Moreover, using the fact that 1 20////3 B 2 2//// B, we can also conclude that
aB / - x1|l
2a 20²Buul Bulls - x,
N V (x(x)) (x; x1
Te >
VS(x)) Vx((x) H. x,)
(22)
By combining 21 and 22 we obtain the lower bound in Lemmal
Finally, when H, >= 0, it holds that I + H. ł + H, and thus (I+ + m7. H, - x
(I + - 2 0. This further implies that |I(T + H V (x) 2 |I(T + H, - V fxx))|
Hence, we can conclude that
a x,,| = 1 - (xx))l
< nh || + H, - f(x))l & -/ - x(ll 8
1
This completes the proof.
A.3 Extension to inexact linear solving
In this section, we extend our convergence results the case where the linear system in 6 is solved inexactly, i.c., we find X, such that
0 1 xell- -
[[ + (X. x²) + H
(23)
In this case, since the proof of Proposition 2 does not rely on the update rule in (6). Proposition 2 continues hold, However, we need to modify the proof of Lemma aand replace it by the following lemma. We note that the two results differ only by an absolute constant.
Lemma 5 (Extension to Lemma D. For I & B, we have 1nI at. For I. E B, let îj be the corresponding iterate rejected by our line search scheme. Then, || xell S 1 xx Moreover,
n//8 and 8
x x+
a² a²Bull 12
1h max
2))g((x)) - g(x,) H xx) 21|g(8,) g(x,) - H2 x2)
14

---

Proof. We follow a similar argument as in the proof of Lemmal | If & B, it immediately follows that Tr or. Further, if
B, then ihe and the corresponding iterate 2, must fail satisfy the condition in 3 This implies that
ن + N.. ( av + 2 x1|1 11.
(24)
Moreover, by our inexactness condition in 23 X2 satisfies
[I(T Hx x.) + 7/e V [xx)]l
2 211:5 xell-
0r
Hence, by using triangle inequality, we have
i V (Xx,) vx((x)) H -x)l
(x: x + ()) (.. - xx) /V (xx))
|2 x 7/ (x+))l |I
||(T + (x), + (xx))
1 27 |x x
Thus, we obtain that
0v1 + 27 X Xx
7t >
f(x,) - fx(x) H, (X x1)l
Combining this with (0). we observe that these two bounds differ only by a constant factor of 2. Hence, the rest of the proof for the lower bound follows similarly in Lemmal |
Next, we prove the inequality ||&, xell S 1 xell- Define 8 = x, -I + m H.)-1
and x = X2 - iI + nj fxx(),, i.e, they are the exact solutions to the corresponding linear systems. By the argument in the proof of Lemma we have || x,I| =|l&; xell- In the following, first prove that
1 =11x: - x S ト
R x S |
x
||
S 2
||
x and
||ا
x |l - 2 ||x: - x (25)
It suffices prove the first set of inequalities, since the second one follows similarly. To see this, note that the condition in (23) can be rewritten as
[I m H.) x;)1 S 2 || xe|l-
Since H. 2 O, this further implies that || - 8;11 < (I + T/. H.) - 8;)1 S 11] by the triangle inequality, we obtain that
x.|. Hence,
||*; x,|| S
| x;||
||
+
||
x,11 $ (1
| x s
19 8
|2; x,1l
2
[61 -
|| x
1x7
X ||
||
x 1
| x
IV
[x xx11:
which lead to 25 Finally, we conclude that -xel S 2||x This completes the proof.
xx|| S
xell S -
-
x:Il-
A.4 The total complexity of line search
Let 4 denote the number of line search steps in iteration f. We first note that 1)t 0-0/--1 by our line search subroutine, which implies 4 log1/s(0./ng) + Moreover, recall that o, 7/-1/B 3 for i > 1. Hence, the total number of line search steps after I iterations can be bounded by (cf. (22 Lemma 22)):
(-1
ai T
T
logi/a
+
log
17t
Moreover, it can be shown that V/- > o.3 (33/( when L = 2 /x2) in both the uniform
averaging and the non-uniform averaging cases (cf. Corollaries 2 and
3
This implies that the total
number of line search steps can be bounded by 2t 1 + log 10
15

---

A.5 Proof of Lemma 2
Recall that we use g(x) and xx) to denote the gradient V fx) and the Hessian V fx),, respectively, We first consider the inequality in (9). By the fundamental theorem of calculus, we can write
Vs(()) - Vx(x)) J V' + xx)) -xx) dr.
Therefore, we can further use the triangle inequality get
( v)(())) v2 fxx)()) xx)]I (v2 + -(x, xx)) v2 f(xi)) (Rx xx) dr
/ [(v2]((x + 7(2, - x,)) (²](xx)) (x, x,) dr
/ || Tx2 xx)) {>](x))] |ス+ xx|l dr.
(26)
Moreover, we have V2 + 7(x - x:)) - f2x - M1 for any 7 E [0. 1] by Assumption 2
Together with (26). this further implies that - [(x)) 1(8, xx)l I M,, which proves the first bound in (9)
Next, consider the second bound in ( By Assumption
3 it follows from standard arguments
that [ (xx))) (xx) x+)l < 4 X (e.g.. see 225 Lemma 1.2.4)) This leads to
[V)())) vx(x.)) (x)(xx) xx,)
To 8
xx
L &
x+ll
L |||| X - x")
|| - x+|1
2
23
23 o²
where we used || x || S || - xe|l from Lemma and
|x: x
S
1
X x* from
V1
Proposition 2 This completes the proof.
B Missing Proofs in Section
B.1 Proof of Lemma 4
1 Ei H. Hence, it follows from Recall that in the case of uniform averaging, we have H. = 24I
Jensen's inequality that HH H.ll < [+] El= H. H.|l- To prove the second claim, note that
Assumption 2 directly implies |H H, S My Moreover, we can use Assumption 3 and the
triangle inequality to bound |H - H, < |2|xx x; < L2([|x; -x'l + ||x;
x []). Since <
and X, x"1 is non-increasing in by Proposition we further have [x, x"1 S ||x: x ||.
which proves H. H;ll < 2L2 [|
B.2 Proof of Theorem 1
Warm-up phase. To determine the transition point Tr, recall that both the linear approximation error and the bias term can be bounded by M2 according to Lemmas 2 and 4 Since Lemma 3 shows
that || O(TE/ /t), we will have |E, || < M1 when t = ( MF) / /n² 2 More
specifically, the transition point is given by
2 x²
SdY
aB 4 log g logg 3M
T = max
log
(27)
Kō
where 8 E (0, 1) satisfies d/6 2 e, a, B E (0, 1) are line-search parameters, and on is the initial step size.
Linear convergence phase. In the following lemma, we prove the linear convergence of Algorithm with uniform averaging.
16

---

Lemma 6. Assume that 3 S 1/2 and recall the definition of T1 in 27
For any t 2 Ti, we have
xx11 (1 (1+ 2a/
X - x"
||x,
3k
where K. A Mifp ju is the condition number.
Proof. See Appendix B.3
Now we discuss the transition point T2. At high level, the algorithm transitions to the superlinear phase if all three erross discussed in Section 3.1 are reduced from O(M) to O(u). For this to happen, first the iterate Xr needs to reach a local neighborhood satisfying | - x = L2). As corollary of Lemma 6 this holds at most after an additional (kk) iterations. Specifically, let E (0, 1) be parameter and define
I= Ti + 211 +
3x
L2D log
(28)
2x,3
where | - x"1 is the initial distance to the optimal solution. Then Lemma 6 implies that we have 1x x S un/ L2 for all 1 2 I. Moreover, Lemma imppless that the averaged Hessian (((r2). Finally, regarding the bias term,
noise satisfies |E,| Op)) when t = (
following the discussions after Lemma 4 it can be shown that |He H.ll O Mi Thus, transition point by
|H, H, (1)) when t Q(<I). Combining all pieces together, formally define the second
{
256T D2
Sd
KI
T2 = max
log
(29)
8v
V
Since I = ((T)++)==((((/33))
we note that To = (max 2 T2 (2/===/)))) = Ô +x²).
Superlinear phase. In the following theorem, show that after Tr iterations, Algorithm | with uniform averaging converges at superlinear rate. See Appendix B.4 for proof.
Theorem 3. Let E (0,1) 1) be parameter satisfying
+
25
v S 1. and recall
20 208 (1-3(110)))
aa/23
the definition To in (29 Then for any 1. T2.
X x=1
+5 prllx p -x11,
2 a²
where
4Y Pe a/3
log d(t + 1)/8)
3KI
(30)
t+1
In Theorem 3 we observe that the rate Pt in 30 goes to zero as the number of iterations t increases, and thus implies that the iterates converge to x" superlinearly. Moreover, the rate P: consists of two terms. The first term comes from the averaged noise |EE,l, which decays at the rate of (t).vt) In addition, the second term is due to the bias of our averaged Hessian estimate H. which decays at the rate of OkII/t). Hence, when / is sufficiently large, the averaged noise will dominate and the superlinear rate settles for the slower rate of ( Specifically, the algorithm transitions from the initial superlinear rate to the final superlinear rate when the two terms in (30) are balanced. Hence, we define the third transition point Ts as the root of
9R.
64(Ts + 1) log ((Ts 1)/8)
T2
Since I Ö(T2/N² + x), Ta = 1((T) /²)) We summarize our discussions in the following corollary.
Corollary 1. For T < l < Ta - 1, we have
X1+1 x"1
23V1 az +5
1
Pr 11 Xx
x"11.
17

---

where Pt
6x7
Moreover, for 2 T3. we have
av/3(1++1)
Xx+1 x=11
(2) 23V1 - a² +5) Pi Xx: x=1,
1
where Pt
(2)
BY aVB
log (o
[+1
B.3 Proof of Lemma
We divide the proof of Lemma into the following three steps. First, in Lemma provide lower bound on the the step size 1); in those iterations where our line search scheme backtracks the step size, i.e., & B. Building Lemma use induction in Lemma to prove lower bound for all t 2 O. This allows us to establish immediately follows.
()) for all & 2 Ti in Corollary [ from which Lemma
To simplify the notation, we define the function
((t) STEV log(d(t + 1)/6)
(31)
f+1
Then Lemma can be equivalently written as ||E||| S ((t) for all 4log(d/6). We now ready to state our first lemma.
Lemma 7. I E B, then we have 2 a3/(2M + (()))
Proof. If E B, by Lemma we can lower bound the step size ?) by
{ Xt
T) lg(x))
(32)
g(x,) - H. xx)ll
E
where & A [I((.)) R(x,) ) H (8. x.)ll is the normalized approximation error. Moreover, outlined
& x,
in Section 3.1 apply the triangle inequality to upper bound &,. Specifically, we have
[lg(x.)
g(x,)
H. xx)Il H. H.l Er
ε <
(33)
|
xx
By ( in Lemma 2 the first term in 33 is upper bounded by Mi. Moreover, it also follows from Lemma that HH, H.ll <
= H. H;ll < Mj. Hence, we further obtain & <
2M | 2M1 + @(t). Combining this with (32). we obtain the desired result.
Lemma 7 provides a lower bound on the step size Th. but only for the case where t E B. In the next lemma, we further use induction show lower bound for the step sizes all iterations.
Lemma 8, Assume that 3 < 1. For any L 2 O, we have
2.
a
17 min
(34)
2M
x(t) B
Proof. We prove this lemma by induction. For the base case = 0, we consider two subcases. 0 E B, then by Lemma 7 we obtain that 1o 2 2 Otherwise, if 0 & B, we have 7/o dg- In both cases, we observe that 34 is satisfied for the base case = 0.
Now assume that 34 is satisfied for t where 2 O. For t + 1, again distinguish two subcases. If E B, then by Lemma
we obtain that 1/511 2M)+ which implies that
o8
34 is satisfied. Otherwise, if s + 1 $ B, then we have
1/. min 2M, + ((s)' g
σ0 min 2M + d(s) Ba+1 5
T
7s+1 G.+1
(35)
3
where we used the induction hypothesis in the last inequality. Furthermore, note that ((s)/
which implies that ((s) < ((s + 1)/3. Hence, we have
a
a
ag
2M, + ((8) 23M, + Ó(s +1) N
2M, + (
18

---

Therefore, 335 implies that 7741 > min 2M, +o+++ 3 and thus 34) also holds in this
o8
subcase. This completes the induction and we conclude that (34) holds for all 2 0.
As a corollary of Lemma 8 we obtain the following lower bound on 7p for z Tí.
Corollary 2. Recall the definition of Ti in 27 For any 2 Tı, we have 7tt 2 / (3MM)
Proof. As shown in 0 Lemma 2}, we have <(t) S M1 when 2 max 256 Moreover, we have g 2
R log &aT 4 log d 8
aB 3M, when
log 3M,00" Hence, by Lemma we conclude that
T 2 3M, when 2 TI.
Now we are ready to prove Lemma
Proof of Lenma 6 By Proposition we have |x++1 - -x" 13 || 111 27(4) -1, By using x* 1|?
Corollary we obtain that [|x+11 2o:3/ (3k)
<
X2 x" (1 + (0BB)/(3M))) ||x, x" x
B.4 Proof of Theorem 3
In this section, we present the proof of Theorem The proof consists of four steps. begin with, in Lemma 9 we show that the iterate stays in local neighborhood of x when / 2 I, where Z is defined in 28 Next, we use this result in Lemma 10 to upper bound Vingi in those iterations where
our line search scheme backtracks the step size, i.e., B. Then we use induction in Lemma 11 to prove an upper bound for all 2 Furthermore, we again use induction in Lemma 12 establish an improved upper bound on Vumi when / 2 T2, where To is defined in (2).. After proving Lemma 12 Theorem then follows from Proposition
Lemma 9,
We have ||x x" S L2 all 2 I, where I is given in 28
Proof. By applying Lemma 6 we have ||x x 12 < XT] - x²1
+
20.8
3x Moreover,
-
since ||x x11 non-increasing in have ||x
x'1l S |xo x'11
D. Thus, we have
XTi+u < vp
= D
(1 1+
2a.3
V² 122
= u 2 2 +
3x
log
L2D
L
3k
20,
vp
This completes the proof.
Note that by Proposition which further implies that
I
we have ||x+1 - x" x²112 < ||x - x x1 2m -1 -1 1|x
1xx=-11122 (1-111/22(2m11)))
|| x"1
Xx+1 - xx
(36)
22
Hence, to characterize the convergence rate our method, is sufficient to upper bound the quantity 1/ 22m.. We achieve this goal in the subsequent lemmas.
Lemma 10. Ift E B and 2 I, then
L2 x1 - x"1
3KI
+
+
(37)
22
4a3 (1 11-022)11 0p)
20/3p
2
(tv/(l++1)
Moreover: it also holds that
o(1)
3nI 2 201B(11 +1)
+
(38)
2ne
4a8 1 0²)B
20/Bp
Proof. By using the second bound in Lemma I we obtain that
lig(;))
g(xe) H x:)I
E, 20 1p
(39)
22
20 / Bp [x: xxll
19

---

Furthermore, by combining 33 and
② in Lemma
we further have
L2 X1, x" &
H. Hell Erll
(40)
2/v1 a²
remains bound the bias term H H.ll By Lemma
we have
H. - H4
H. Hill
H. H.ll
H. H,
==0
For i = 0,1 1-11.,,I1,,, we use the first upper bound on |H,-
I-1,
H,| H, in Lemma 4 to bound H V
M1. and thus === | H.l < M,I. Moreover, for I.I + I....,t t, we use the second
upper bound in Lemma to get H. H. S 2L2||x - x*I|. Moreover, note that x; converges
linearly to x" when i I by Lemma 6 Hence, further have
2L H. -
2L2| XI - x
2a
-1/2
H
x'1
s
Σ
1
t+1
t
t+1
3k
I=I
1=0
(41)
4uH
3x
$ 1 +
1+
20r3
In the last inequality, we used the fact that ||x- - x"1 S /u/ L2 and Σi= (1 0) 0) 1/(1
(1 + Φ) -1/2) (1 + /)///2((( + 2) - 1) (1 + の) 1/2 ((1 3) /) + 11/6 < 2(1 + 1/0),
where a 2ar3/(3.) Moreover, since I> (1 2n
and v S 1. from 41 we further have ZuI Combining the above inequalities, we arrive
3x
Ei=z |He H
MI ++1
2pI
3M,
H. H.
(42)
++1 ++1
Combining 39
40
and 42
leads to the first result in (37 Finally,
38 follows from the fact that
||E+|] S (()) and x;
x
x up/ L2 for all 1
S
Lemma 11. Assume that B s 1/2. For any t 2 I, have
V
+(t)
3+Z
V + Pt.
(43)
22H 4a3v/1- a²)3
207Bu
2a 2a/B(t+
4a8 a²)3
where Pt is defined in 30
Proof. We shall use induction to prove Lemma II Wr 2 a33))M Thus, this implies that
For t I, note that by Corollary 2 have
V3K
3KI
<
12TI
/20B
2ay (I + 1)*
where we used the fact that 2 1, a 1, S 1/2 and 2 This proves the base case where
t = I.
Now assume that (43) holds for 6 - where s > I. For + 1, we distinguish two subcases. If 8 + 1 E B, then by Lemma 10 we obtain that (43) is satisfied for / = + 1. Otherwise, if 8 + 1 & B, na/8. Hence, by using the induction hypothesis, we have
then have 1/ ds+1
1
VB
V
BBp(s)
3/3KI
<
22 - 1/4
V2na
40.3 02);
20/ 3p
Lav3(s + 1)
Since 3 < 1/2 and 2 2, we have (s + 2)/(5 + 1) S (I + 2)/ (I + 1) S 1.4 S 1/V3 and
(()) < o(s + 1)/ /B. Thus, we further have
Ó + 1)
3KI
20 +
12
4a3 40 a²)3
20/3( (s + 2)
This shows that 43 also holds in this subcase. This completes the induction and we conclude that holds for all t I.
D
20

---

Before proving Lemma 12 recall the definition of Φ in (31 and first define
and T- max I' 1----1
KI
I' =up (t: p(t) 2 mnu
(44)
Note that we have ((1) S un when T2 T2. Lemma 12. Recall the definition of Pr in
256T log
AdY
Hence, by the definition of 29
holds that
30 For any 1 2 T22 we have
L L2lix X x"11
S Pt
and
S
28v1 - a² +5 Pr.
(45)
20
V2
Proof. By Lemma 10 if E B, then
1 Vum
L2 Xt x
+ Pr.
2a
2(1 - a²)
We shall prove (45) by induction. First consider the base case where t = Tg. where Ty is defined in (44). To begin with, we will show that
y S PT₃ S 5y 20/5 I' and AI, we have either Ty- = I' or T3 RI
20/3' Since Ty is the maximum of
In the former case, we can lower bound
PT; 2 2avBu ((T)) 2 V/
20 the latter case, we can lower bound PTg 2 20//8TTT+
3xT
3v
20//
Combining both cases leads the lower bound PT:- Furthermore, note that both two terms Pt. are a decreasing function in terms of t, and hence we have
1
3KI
2 201BBp
3v S
5v
PT: 201BBp
((I)) +
S 20/B(nI//)
O +11+
20
201/3
This proves the upper bound on PTz.
Now we return to the proof in the base case where t = Tg. since ||xy - x"1 S vpl Le by Lemma 9
we obtain that L2/1x7; xI'l 20/Bp
2a/B S PTg Moreover, by Lemma 11 we have
5
+ ((T))
23 2 + PTz
V 22
40. 40-//1- (1- D²)B
4a a²)8
2a/B
This shows that (45)
holds for = To
Now assume that (45) holds for t = 2 Tg. For t = 8 + 1, by using the induction hypothesis and
(36. we obtain that
|2|| -
L2 x
<
V2 23V1 a² +5 P3.
207Bu
20 nov31u 3 MoH
v2 (2ov +5) 1 S Ps/2, which is equivalent to 2 28V1-a² + Ps S Furthermore, since P. is non-increasing, we further have
Moreover, since P./2 S Pat1. it suffices to show that
1
1
5v
2
23 +
Ps 22
23v1 - a² +5 PTz v2
+5)
1,
28
20
where we used the condition stated in Theorem 3 in the last inequality, This proves the first inequality in (45).
To prove the second inequality in 45 for t = s + 1, we distinguish two subcases. If 1 E B, then
by Lemma I0, we have
1211x -
E
3KI
1
Pst1 + Ps41
12
4a3 (1 a²)
20 31
2a + +1)
23
1
23v1 a² +5) Pat1-
21

---

Otherwise, if + 1 & B, then we have N6+1 = B and hence
1
VB
2381- - a² + V3p..
v 12
V2
Since T:2 2 I 2 2 and 3 < 1/2, we have Ps/Pst1 S 2I/ (I+ +
- 1.4 1/v3. Thus, we
also proved that VPT-- 23v1-a3 + +5) Ps+1. This completes the induction.
Proof of Theorem
It immediately follows from (36 and Lemma
C Missing Proofs in Section 5
In this section, we will present the formal version of Theorem Our proof largely mirrors the developments in Section
C.1 Approximation error analysis
Averaged stochastic error. Similar to Lemma 3 we can use tools from concentration incqualities to prove the following upper bound on the averaged stochastic error.
Lemma 13 (Il Lemma 6)). Let 8 E (0, 1) with d/6 2 e. Then with probability 8 /6, we have,
for any t 2 0,
{
d(L + 1)
((()) w(())
log d(l + +1)
w (L) w((t)
[E|| < SVY max
log
(46)
C.2 Convergence analysis
Warm-up phase. Similar to the case of uniform averaging, we can only ensure that the distance to x" is monotonically non-increasing by Proposition during this phase. Moreover, Algorithm transitions to the linear phase when Eyll < MM.. Specifically, the transition point 241 is given by
U1 sup { t log 3M100
a
log
d(t +
w (t)
(IΛ
K SY
]
+1.
(47)
When w() (L + 1) llg((++)) we have w/ w((1)/w(l) = O (log(1)/(). Thus, we conclude that Un = Ö(r² 2x²
Linear convergence phase. In the following lemma, prove the linear convergence of Algorithm with weighted averaging. Lemma 14. Assume that < 1/ and recall the definition of (47). For any t 2 Ui, we have
2a -1
Xx
x" x1 S x11
1+
3K
where k & Mi/U is the condition number.
Proof. See Appendix
C
Superlinear convergence phase. Define
J J'=sup t: log d(t +11 w'(l)
2 a^ )²
)²) +1.
(48)
8 w(t)
Moreover, let E (0, 1) be a parameter and define
2x
L&D
J = max U1 + 2 [+
log vp J2
(49)
a3
22

---

Finally, let
U2 - sup t: w(t) I w(J) R
v /
(50)
When wt) (1 + 1)log(++9) we remark that J' = o(re) and thus J = O( + r2). Moreover, similar to the derivation in M. it can be shown that L12 ((J) Or T²).
Theorem 4. Let E (0, be a parameter satisfying
21 -a) +
vs V
(51)
av3
and recull the definition of U2 in (50) For any 2 U2, we have
| x
0e 0111x;
x
108 10.8 2 - a²)
v2
where
SVT
d(t + 1) w'(t)
5k
02 a//33
log
(52)
w(t)
(x/2
Proof. See Appendix C.4
C.3 Proof of Lemma 14
To simplify the notation, define the function
d(t
w'(t) (t) (())
d(t + 1)
w w'(t)
<(t) 8VT E max
log
log
5
5
w(l
Then rewrite 46 as result.
Exll S d(t) for all 1 0. Similar to Lemma have the following
Lemma 15. Ift B, then we have 7i a3/ (2 + [.lI) 2 a3/(2M + +())
Lemma 16. Assume that 3 S 1/ For any t 0, we have
a
σ )
17 min
(53)
2M
x(t) Bi
Proof. We prove this lemma by induction. Fort = 0, we distinguish two subcases. If O E B, then by Lemma 7 we obtain that vo 2 Fo(0 Otherwise, if & B, we have 7/o op- In both cases, we observe that (53) is satisfied for the base case 1 O.
ag
Now assume that (53) is satisfied for t For f 5 1, we again distinguish two subcases. If ag
s+1e E B, then by Lemma 15 obtain that 1)++1 2M, +0(++T) which implies that (53) is satisfied. Otherwise, if 8 + g B, then we have
7 0s+1
min
Mi + ((s)*
a3
do 3
min
M1 + ((8) go+1
Oo
(54)
where we used the induction hypothesis in the last inequality. Furthermore, note that
((x) < w')s(((s+ +1 w'(s + 1)w(s}
< 17 <
((s +
3
and hence
aB
Mj + o(s) 3M1 + o(s +1)
M1 + Ø(s +)
Therefore, 54 implies that 7)+1 2 min
do and thus (53 also holds in this case. ge+
Mi+els41)
This completes the induction and we conclude that (53) holds for all
0.
23

---

Corollary 3. Recall the definition of U1 in 47 For any t 2 U1 we have 2 a3/(3M1).
Proof. By definition, we have Ui
2 logg 3M.00 and thus 3d
a
aB
Moreover, we also have
3M.
((I) S Mi. Hence, by Lemma 8 conclude that y
aB 3M,
when / 2 Ui.
Now are ready to prove Lemma 14
Proof of Lemma 14. follows from Proposition T and Corollary 3
C.4 Proof of Theorem
Lemma 17. We have Exll I vu and ||x, - -x"1 S vn/ L2 for all t 2 J.
Proof. This follows from Lemmas and 14
Lemma 18. Ift B and t 2 J, then
L2 LeI[x1 - x"1
E2
kw( [J
1)
2v
+
(55)
2003 / 2(1 - a2)34
av23p
a 2B2(ttt) a
2v
and also
v
3v
kwl -1)
+
(56)
203 (48/2((1 2(1 2²)3
2v
a323(((
Proof. Similar to the proof in Lemma
10 note that
L X2 x"11
H. H.ll
E,
+
20,3 2(1 a²)
a 2B
2B
For the second term, note that
w(i) - w(i - 1)
H. H,
where zi,t
1=0
Hence, by Jensen's 's inequality, we have
H. H Z H.
Hill
Σ Zi, [He H: Σ Z4, H. H.ll
When JiSJ 1, we Assumption 2 to bound |H H < M, and thus
w(i - 11) Mr w( (JT-1)
Σ Zi H H. M1
w(t)
w(t)
1=0
Moreover, for J < < t, we use Assumption to get
H < L
- La (1|x, x'1| - -x S 2L2/ -x'1 S 2vp.
Thus, Σ 2, H. H < 2044 Eizz 2i, < 201. Combining the above incqualities, we arrive
H H.ll < M1 W(J 1)
+ 2nμ..
w(t)
This leads to the first result in 55 To show (56). we note that Eel S d(t) and | - x s vu/Lo for all 2 J.
Lemma 19. Assume that B $ 1/ For any 1 2 J, we have
3v
(2kw(J)
<
(57)
Vum
2a.3221 - a²)
av23
av/Bu(t)
24

---

Proof. We shall use induction to prove Lemma 19 For t J, note that by Corollary 3 we have nJ a3MM). Thus, this implies that
2K
22k
v 1MJ
VaB
aVB
where we used & 2 a, 3 1 and 2. This proves the base case where / J.
Now assume that (7 holds for where 2 J. For + 1, we distinguish two cases. If + B, then by Lemma 18 we obtain that (57) is satisfied for + Otherwise. if 1 & B, then we have 77++1 s++1 7./3. Hence, by using the induction hypothesis, we have
vB
3v
+ (233w((J)
V
20.3 / 2( a²)
2V
avBw(s)
Since 1//0/ we have w(s + 1)/w(s) S 11/BB.
Thus, we further have
v
3v
V2kW(J)
V S
+
2033 a
2v23
avBB(s + 1)
This shows that (7) also holds in this case.
Recall that w(12) = w(T). Then by Lemma
19 for 2 U2 we have
3v
(J)
3v
V2v
20B 2013 x2)3
2/23
a avBix((12)
20 2(1 a2)
a/23
a/B
5v
2a 221 a²)
a//2
We will choose y such that
1
+
V
(58)
20B /1 a2 av3
v
Therefore, this further implies that ||x++1 - x Lemma 20. Ift E and 2 U2 then
S |x] x* (21() for 2 U2.
1
L2 Lel1xe - x'1
6(t)
5xw JT)
(59)
V yun
20.3
2(1 )3p
2.23pp
av 2B)
Proof. Recall that we have
L2 Xt 1
|H, H.
E,
Vum 20,3 2 a²3
2B2
For the second term, we can write
J- Σ
Ua
H.
H.
zie H.
H
2 HH-H, [1||++]
3 H. H
Zi,
H.
H.
0=
1=+++1
For the first part, E-1- 24.0 H H < M1
-(F-1) w((t
< M1
For the second part,
w(!)
ik2
((b))
2M w(J) w(ll w(l)
H,
H.ll |l < 20p
Σ
Zi,t - 2vp
i=1
25

---

where we used the fact that w((4) = (( " For the third part.
w(i) w(i - 1)
H
H.
2
|xx - -x"ll
w(t)
1= 24
+1
t-1/2
wll12
- -j)- +
1) |xx,, x"1
<
2L
w0l1
(2
1=1
8-M2
w(11 + 5) | - x'11
2
w(t)
(2V)
5=1
t-M4
w(lt)
wlll2 +)
Σ
2014
w(()
(2V))
5=1
$ 20μ mu(12)
wilt2 + j) 2l26)
w(t)
1=1
S 2un ml(22) 1
w(t)
1=1 21
n=(22)
2M w]]
$ 2014 w(t)
w(t)
Therefore, we conclude that
3MIw(J)
2Miw(J) w())
5Miw(J) w(t)
H. H.I
w(t)
This completes the proof.
Lemma 21. Recall the desinition of 0e in
52 For any 1 0, we have
5T2 || Xua++
x*1
103811 a² +1) or,
0 and
S
(60)
Vpmaett
Proof. Note that by Proposition
we have
1x -11/2 < xx1
X01++4+1 x < Xt1--t x" [[(1 + 21R4++ 112
+21
By Lemma 18 if U2 + E B, then
L2 1211x1+++ - x"1
+ Oz.
+1
20 /2(1 122
We will prove (60) by induction. First consider the base case l. = O. We note that 0g 2
Swwel (T)
(12)
On the other hand, since ||x;, - x"1 S up/ Izz we obtain that 5lg Ni.
=x"1|
av25 S 6g-
2/23"
av22pp
Moreover, by Lemma 19 we have
V
3v
(2RU(T) S
V
5y
VaTuL S
+
22812(1 0²)s
23 avBw((())
2aB /2(1 a2)B
2/23
1
+1)
103V1- - a² + to.
This shows that (60) holds for = 0.
Now assume that 60) holds for t O. For t + 1. by using the induction hypothesis, obtain
5La Ku x*1 ||
5L2 | x"1
1 V2 103V1 - α² +1 +1) 82.
2/233u
av 23 2
26

---

Note that 0./V 0s+1.
Thus, suffices to show that v2 10sVI-a + 1) I 0,/V, which
equivalent to
108y1-a2 +1
1) 0, S Furthermore, note that 0g non-increasing and
v2
80 $
Thus, we only need to require
2
23
2v2
6
103VI o² +1
S
+
av3 vs v
2
2B
10a:3 v(1 (1-aa)s
which is satisfied due to (51) This proves the first inequality (60).
To prove the second inequality in (60) for = + 1, we distinguish two cases. If 8 + +1 E B, then by
Lemma 20 we have
Le +ot+ x"1
Eui++++1l
5kw(J) av23w((l + +
200 / 22111 o
av233
103vI- - - + 00+11
108vI- +1 0ct1.
Otherwise, 8 & B, then we have 1112 = 111gtt/// and hence
vB
103VI- +1) VB0..
1
VPTRe+++11
v Vpile2-
Since 0./V & 0s+1 and vB S 1/V, this implies that completes the induction.
(ioavi-as + 1) 0s11- This
Proof of Theorem
By Proposition
D we have
XTg+t x"1
[T++41 x
S XT---- x 11(1 211++111 -1/2 -1/2
V2111++0/44
The rest follows from Lemma 21
D Additional discussions
D.1 Iteration complexity SNPE
Note that for U4s Ō( + n), we have ||x41 x"1 unrolling the inequality, this implies that
=0 111x1
x*1l by Theorem 2 By
|x+1 - x"1 S |xxss
II L=
r
I XD x"1
II r
Further, for t 2 244,, we can upper bound Vs
as follows: (i)
/z
S
vea
r
$ for any s E [U3 t/2),
(ii) V
T for any s E [t/2, t]. Thus, we have 1t/2
II 143
<
t/2
1/2
To derive a complexity bound, we upper bound the required number of iterations such that
T
Taking the logarithm of both sides and with some algebraic manipulation,
V1/2 obtain
2
1 c
log
log
2T
2T
r
27

---

19
13"
10"
10"
10"
Iteration
iteration
Iteration
(a) 50, 000,
500
(b) 100, 000, d 500
(c) 150, 000, d 500
Figure 3: The effect of the extragradient step in stochastic NPE.
Using the Lambert W functior the solution can be expressed as log 2T W
2 P2 log =1=
2T (Tz log t), Finally, by applying the bound (x)) S 2mr++
[+log(=-1) for any x 2 O, we conclude
that O log(T (T (og(e-))) Note that in the above derivation, ignore the additional logarithmic
log(c"))
factor log(t) in our superlinear convergence rate. However, more careful analysis will show that it does not affect the final complexity bound. We also refer the reader to similar derivation [22]
Appendix D.2], where the authors provide the same complexity bound for similar convergence rate of (1 O(VI))
D.2 The effect of the extragradient step
In Figure 3
the effect of the extragradient step in our proposed SNPE method. We observe that in all cases, the variant without an extragradient step outperforms the original version, suggesting that the extragradient step may be beneficial for minimization problems. Nevertheless, the SNPE method with the extragradient step, which is the one analyzed in our paper, still outperforms the stochastic Newton method
www.peedaa..r/wwl//llmbeeeerrr f_fuctiion
28

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justifiictinn right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation.
While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to claborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction of the paper, we claim that we can improve the complexity of the stochastic Newton method presented in I1, and this is exactly what demonstrate. This improvement is achieved by introducing a novel stochastic variant of the Newton HPE framework, as promised in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification: In Section 8 we explicitly mentioned the limitation of our paper. Specifically, we noted that our theory assumes strong convexity. Extending the theory to the convex setting would make it more general. This extension is left for future work due to space limitations. We also highlighted in the introduction of our paper that we focus solely on the setting where the Hessian oracle is noisy, and the gradient can be queried without error.
29

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point 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 on 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed 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]
Justification: All the theorems, formulas, and proofs in the paper are numbered and cross- referenced. All assumptions for each presented result are clearly stated or referenced in the statements of the lemmas, propositions, or theorems. The proof' of all results are presented in the supplemental material. High-level ideas of the proofs are included in the main text whenever possible.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental results and the implementation details are included in Section
30

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, 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 urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a 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 describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The code and data are attached in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
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
hhipss.c//ubllc/uuudds wwtpee/e/ooooSeueoooooeeeoe
www.bbmmiiiiiooooooo.iooo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
31

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is 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: [Yes]
Justification: We explained how performed the experiments and included the implemen- tation details in Section 7
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or 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 or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
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 of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
The compute resources are reported in Section 7
Guidelines:
The answer NA means that the paper does not include experiments.
32

---

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 Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///aarrpg...cppaaaal/aaaat
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in 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: There is societal impact of the work performed.
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 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
33

---

Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 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: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
34

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does 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 NeurlPS 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.
35


Reviews:
[{"review_id": "ZFLT38IaYG", "reviewer": "Reviewer_qDEj", "summary": "Newton method is well-known for its local quadratic convergence. However, the use of Hessian introduces additional computation challenges. One approach to tackling this issue is an inexact approximation of the Hessian. In this paper, the authors consider the finite sum minimization problem. They propose a stochastic approximation of the Newton method, where instead of the full Hessian they use its subsample approximation. The idea of the proposed method is based on another known approach, that uses weighted average over a subsample of Hessians. In this paper, the authors improve this approach using the Hybrid Proximal Extragradient (HPE) framework for strongly convex problems. As a result, the proposed algorithm achieves both linear and superlinear convergence areas in fewer iterations by improving the dependence on condition number of convergence rate.", "questions": "1. Why do you use $\\sigma_{t+1} = \\eta_t/\\beta$? Please provide more details.", "limitations": "No limitations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper introduces a new type of stochastic inexact Newton method with a better convergence rate than existing analogs. The paper is written in a clear way, sketchily describing its main points, whereas most of the technical details are provided in the appendix. As for me, this is a good way to describe your idea in such a limited space. Authors provide an intuition or explanation after every lemma and theorem, which is also a good practice.", "weaknesses": "Authors consider only a strongly convex setup. However they mention extending their approach to convex case, this seems to me as a major limitation of this work. Additionally, to check condition (3) authors employ line-search, which introduces an additional logarithmic factor in the convergence rate. However this can be the burden of the HPE framework, it seems not very significant, but still an issue. \n\n## Minor remarks\n1. Line 168: remove \"follows\" from the end\n2. Line 168: not Step 5, but Step 6\n3. Sometimes you write \"stepsize\", sometimes - \"step size\". Please, be consistent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 Authors consider only a strongly convex setup and this seems to me as a major limitation of this work.** \n\n**A1** Thank you for raising this point. To begin with, we note that the strong convexity assumption is common in the study of stochastic second-order methods, including Subsampled Newton (Erdogdu \\& Montanari, 2015; Roosta-Khorasani \\& Mahoney, 2019), Newton Sketch (Pilanci \\& Wainwright, 2017; Agarwal et al., 2017), and notably, the recent work by Na et al. (2022). Hence, by establishing our results within the strongly convex setting, we can better position our contribution in relation to prior work.\n\nMoreover, the focus on strongly convex functions in these works, as well as in ours, stems from the clear advantages that stochastic second-order methods offer over first-order methods, such as gradient descent. Specifically, stochastic second-order methods achieve a superlinear convergence rate, as demonstrated in this paper, which is superior to the linear rate attained by first-order methods. We also note that the assumption of strong convexity is necessary for achieving superlinear convergence rates, as only a sublinear rate can be achieved in the convex setting, even with exact Hessian information.\n\nFinally, while we believe it is possible to extend our techniques to the convex setting, developing the necessary theory and discussing the results would require more space than is available in the submission. Therefore, this extension is beyond the scope of this paper. \n\n--- \n\n**Q2 To check condition (3) authors employ line-search, which introduces an additional logarithmic factor in the convergence rate. However, this can be the burden of the HPE framework, it seems not very significant, but still an issue.**\n\n**A2** \nThe reviewer is correct in noting that we need to employ line search to ensure Condition (3). However, we would like to mention that most stochastic second-order methods require some form of line search to ensure global convergence, and this limitation is not unique to our methods. For instance, Pilanci \\& Wainwright (2017), Roosta-Khorasani \\& Mahoney (2019), and Na et al. (2022) all used a backtracking line search to ensure a sufficient decrease condition. \n\nMoreover, we wish to clarify that the line search scheme only introduces an **additive** logarithmic factor, instead of a multiplicative one, in our final complexity bound. Specifically, as mentioned in Remark 3 and proved in Appendix A.4, after $t$ iterations when $t = \\tilde{\\Omega}(\\Upsilon^2/\\kappa^2)$, the total number of line search steps can be bounded by $2t + \\log(3M_1 \\sigma_0 /(\\alpha \\beta))$. Also, note that each line search step requires computing one gradient and one matrix inversion. Consequently, our method requires, on average, a constant number of gradient evaluations and matrix inversions per iteration, leading to a constant overhead in the complexity bound.  \n\n---\n\n**Q3 Why do you use $\\sigma_{t+1} = \\eta_t/ \\beta$?** \n\n**A3** \nThis is a good question. Our motivation behind the choice $\\sigma_{t+1} = \\eta_t/ \\beta$ is to allow the step size to grow, which is necessary for achieving a superlinear convergence rate. Specifically, our entire convergence analysis builds on Proposition 1, which demonstrates that $\\\\|x_{t+1}-x^\\*\\\\|^2 \\leq \\\\|x_{t}-x^\\*\\\\|^2 (1+2\\eta_t \\mu)^{-1}$. Consequently, we require the step size $\\eta_t$ to go to infinity to ensure that $\\lim_{t \\rightarrow \\infty} \\frac{\\\\|x_{t+1}-x^\\*\\\\|}{\\\\|x_{t}-x^\\*\\\\|} = 0$.  Note that this would not be possible if we simply set $\\sigma_{t+1} = \\eta_t$, since it would automatically result in $\\eta_{t+1} \\leq \\sigma_{t+1} \\leq \\eta_t$. Moreover, this condition $\\sigma_{t+1} = \\eta_{t}/\\beta$ is explicitly utilized in Lemmas 8 and 16 in the appendix, where we demonstrate that  $\\eta_t$ can be lower bounded by the minimum of $\\sigma_0/\\beta^t$ and another term. \n\nWe should note that this more aggressive choice of the initial step size at each round could potentially increase the number of backtracking steps. However, as mentioned in the response to **Q2** above, this does not cause a significant issue, since the average number of backtracking steps per iteration can be bounded by a constant close to 2. \n\nThank you again for the question and we will include the discussions above in our revision. \n\n--- \n\n**Q4 Minor remarks.**\n\n**A4** Thank you for catching the typos. We will fix them all in the revision. \n\n-----\n**References:**\n\nErdogdu, M. A. and Montanari, A. Convergence rates of sub-sampled newton methods. Advances in Neural Information Processing Systems, 2015.\n\nRoosta-Khorasani, F. and Mahoney, M. W. Sub-sampled Newton methods. Mathematical Programming, 2019.\n\nPilanci, M. and Wainwright, M. J. Newton sketch: A near\nlinear-time optimization algorithm with linear-quadratic\nconvergence. SIAM Journal on Optimization, 2017.\n\nAgarwal, N., Bullins, B., and Hazan, E. Second-order\nstochastic optimization for machine learning in linear\ntime. The Journal of Machine Learning Research, 2017.\n\nNa, S., Derezinski, M., and Mahoney, M. W. Hessian averaging in stochastic Newton methods achieves superlinear convergence. Mathematical Programming, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d7r8GkyGlY", "reviewer": "Reviewer_m5uq", "summary": "This paper uses the hybrid proximal extragradient framework to accelerate the convergence of Hessian average. The theoretical results significantly reduce the number of iterations to enter the linear phase, initial superlinear phase, and final superlinear phase when compared to the initial Hessian average method.", "questions": "Refer to weakness part.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical results of this paper are impressive. It improves the results of Hessian average [Na e.t.al 2022]. The idea of incorporating NPE framework and Hessian average is interesting. The paper is generally well-written and the results are easy to follow.", "weaknesses": "This paper does not provide empirical results for the proposed methods against AGD, which is necessary. \nThe proposed methods still require exact gradient oracle and its iteration complexity is $O({\\kappa}+\\log(1/\\epsilon))$, while the classical AGD method require only $O(\\sqrt{\\kappa}\\log(1/\\epsilon))$. It is very important to use numerical results to exhibit the benefits of using second-order information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback.\n\n**Q1 Empirical comparison with AGD.** \n\n**A1** Following your suggestion, we compared the performance of our SNPE method against AGD in our new experiment; please see Figures 1 and 2 in the shared PDF file. From Figure 1, we observe that our SNPE method, with either uniform or weighted averaging, requires far fewer iterations to converge than AGD due to the use of second-order information. Consequently, while SNPE has a higher per-iteration cost than AGD,  it converges faster overall in terms of runtime, as demonstrated in Figure 2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UkEc7p6VVj", "reviewer": "Reviewer_BRp1", "summary": "This work proposes a novel algorithm called the Stochastic Newton Proximal Extragradient method. Authors claim that their method reaches a superlinear convergence rate after $\\mathcal{O}(\\kappa)$ iterations, in contrast to the $\\mathcal{O}(\\kappa^2)$ iterations proved in previous work.", "questions": "Check weaknesses.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- This paper proposes a new algorithm called the Stochastic Newton Proximal Extragradient method and proves its convergence.", "weaknesses": "- The assumptions are very restrictive. For example, assumptions 3 and 5 are very strong, and few machine learning applications can satisfy such assumptions. \n- I am confused about how parts (c) and (d) of Theorem 1 prove superlinear convergence. From superlinear convergence, I expected to see $\\rho^{2^t}$ where $\\rho < 1$. How do the results show superlinear convergence?\n- In Table 2, you mentioned the complexity of Damped Newton where the dependence on $\\epsilon$ is $\\log \\log \\epsilon$. However, for SNPE, the iteration complexity $\\log \\epsilon$ is similar to AGD. The iteration complexity of Damped Newton is called superlinear, while that of SNPE is called just linear. \n- In lines 342- 344, the dominating term in the complexity is the one that depends on $\\epsilon$. The Damped Newton has better dependence than SNPE.\n- Section 7 needs more numerical experiments. I expect to see a comparison between SNPE and Damped Newton. In that comparison, putting **real-time (and not iterations)** on the $x$-axis will be fair, as SNPE does a line search in every iteration. \n- In lines 334-337, the authors ignore the complexity of line-search in algorithm 1 (BLS). In the BLS, you compute $(1 + \\eta \\tilde{H})^{-1}g$ several times, which is very expensive, and authors ignore this while computing the complexity of SNPE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 The assumptions are very restrictive. e.g., Assumptions 3 and 5.** \n\n**A1** We note that our assumptions are standard in the study of (stochastic) second-order methods, including Subsampled Newton (Erdogdu & Montanari, 2015; Roosta-Khorasani & Mahoney, 2019), Newton Sketch (Pilanci & Wainwright, 2017; Agarwal et al., 2017), and notably, the recent work by Na et al. (2022).  In particular, Assumption 3 (Lipschitz Hessians) provides the necessary regularity condition for achieving superlinear convergence and is commonly used in the study of second-order methods, e.g., in Section 9.5.3 of the textbook by Boyd & Vandenberghe (2004). For instance, it is satisfied by the regularized log-sum-exp function and the loss function of regularized logistic regression. Moreover, we also discussed in Section 2 when Assumption 5 holds for stochastic Hessian approximation. Specifically, for Hessian subsampling, this is satisfied when each component function $f_i$ is convex, while it is automatically satisfied for Hessian sketching. \n \n---\n**Q2 How do parts (c) and (d) of Theorem 1 prove superlinear convergence? I expected to see $\\rho^{2^t}$ where $\\rho<1$.** \n\n**A2** It appears that the reviewer confuses “superlinear convergence” with “quadratic convergence”. Specifically, the rate of $\\rho^{2^t}$ mentioned by the reviewer is “quadratic convergence”, which is a special case of, but not equivalent to, “superlinear convergence”. In the optimization literature, the convergence is said to be Q-superlinear if $\\lim_{t\\rightarrow\\infty}\\frac{\\\\|x_{t+1}-x^\\*\\\\| }{\\\\|x_t-x^\\*\\\\|}=0$ (see, e.g., Appendix A.2 of Nocedal & Wright (2006)). Note that in Theorem 1 (c) and (d), we showed $\\\\|x_{t+1}-x^\\*\\\\|=O(\\frac{1}{t})\\\\|x_t-x^\\*\\\\|$ and $\\\\|x_{t+1}-x^\\*\\\\|=O(\\frac{1}{\\sqrt{t}})\\\\|x_t-x^\\*\\\\|$, respectively. Since $\\lim_{t \\rightarrow \\infty}\\frac{1}{t}=\\lim_{t\\rightarrow\\infty}\\frac{1}{\\sqrt{t}}=0$, these are superlinear convergence results by definition.\n\n---\n**Q3 In Table 2, the iteration complexity of SNPE is $\\log(\\epsilon^{-1})$ similar to AGD.** \n\n**A3** Thank you for raising this point. Since our proposed SNPE method achieves superlinear convergence, it has a strictly better dependence on $\\epsilon$ compared to AGD. In fact, in the iteration complexity of SNPE presented in Table 2, the dependence on $\\epsilon$ can be replaced by $\\frac{\\log(\\epsilon^{-1})}{\\log(\\log(\\epsilon^{-1}))}$, which is provably better than the complexity of AGD by at least a factor of $\\log\\log(\\epsilon^{-1})$.  We note that similar superlinear convergence rates have also been established in the prior work on stochastic Newton methods (Na et al., 2022) and in the literature on quasi-Newton methods (Rodomanov & Nesterov, 2022; Jin & Mokhtari, 2023). In our submission, we chose to use the simpler expression $O(\\log(\\epsilon^{-1}))$ to save space. However, we will update the table and include a discussion in the revision to more accurately reflect our superlinear convergence rate.\n\n---\n**Q4 In lines 342-344, the dominating term in the complexity is the one that depends on $\\epsilon$. The Damped Newton has better dependence than SNPE.**\n\n**A4**  We agree with the reviewer that damped Newton's method has a better dependence on $\\epsilon$ than SNPE, which we also mentioned in lines 342-344. However, it is important to note that the damped Newton's method is deterministic and requires computing the exact Hessian, resulting in a per-iteration cost of $O(nd^2)$. In contrast, our method only requires a stochastic Hessian approximation and typically incurs a total per-iteration cost of $O(nd+d^3)$, as discussed in Section 6. This distinction is crucial because it allows us to achieve a better runtime compared to the damped Newton's method, especially when $n\\gg d$. Thus, while the iteration complexity of damped Newton's method exhibits a better dependence on $\\epsilon$, its overall arithmetic complexity can be much worse than ours. This is also demonstrated in our experiment presented in the shared PDF file. From Figures 1 and 2, we observe that while the damped Newton's method requires fewer iterations to converge, it takes more time overall to achieve the same accuracy as our method.\n\n---\n**Q5 Empirical comparison between SNPE and damped Newton in terms of run-time.**\n\n**A5** Thank you for your suggestion. We have included the additional experiment in the shared PDF file; please see Figure 2. We would like to remark that damped Newton also performs a backtracking line search in every iteration, resulting in an overhead similar to ours. As expected, when the number of samples $n$ and the dimension $d$ are large, our method has a significant runtime gain compared to damped Newton, and the gap widens as the number of samples increases.\n\n---\n**Q6 The authors ignore the complexity of line-search while computing the complexity of SNPE.**\n\n**A6** We respectfully disagree with the reviewer. As outlined in Remark 3 and proven in Appendix A.4, we explicitly characterize the cost of the line search in our SNPE method. Specifically, after $t$ iterations when $t = \\tilde{\\Omega}(\\Upsilon^2/\\kappa^2)$, the total number of line search steps can be bounded by $2t + \\log(3M_1\\sigma_0 /(\\alpha \\beta))$. Also, note that each line search step requires computing one gradient and one matrix inversion. Consequently, our method requires, on average, a constant number of gradient evaluations and matrix inversions per iteration. This leads to a constant overhead in the complexity bound, which is effectively hidden by the big O notation.\n\n---\n**Additional References:**\n\nBoyd, S. and Vandenberghe L. Convex Optimization. Cambridge University Press, 2004.\n\nNocedal, J. and Wright, S. J. Numerical Optimization. Springer, 2006.\n\nRodomanov, A. and Nesterov, Y. Rates of superlinear convergence for classical quasi-Newton methods. Math. Program., 2022.\n\nJin, Q. and Mokhtari, A. Non-asymptotic superlinear convergence of standard quasi-Newton methods. Math. Program., 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c7Lia0a6xc", "reviewer": "Reviewer_TogL", "summary": "The paper develops an accelerated scheme for strongly convex problems. As feedback it requires a deterministic first order oracles, but only an inexact Hessian estimator –– the main assumption being that the Hessian noise is mean zero and sub-exponential (implied by e.g. Hessian subsampling and $\\Vert\\nabla^2 f_i(x)\\Vert$ bounded or Hessian sketching with a Gaussian sketch). The main idea is in combining the Hessian averaging scheme [1] with the hybrid proximal extragradient framework [18,19].", "questions": "Method comparison & theory:\n\n- It would be informative to compare theoretically with existing (accelerated) results using exact Hessian. Does the proposed method recover the existing complexities?\n- l. 369 can you really claim better condition number dependency when you choose $x_{k+1}=\\hat{x}_k$, which is not covered by the theory? What convergence guarantees can be shown then, since the interpolation in Eq. 4 otherwise appears crucial for the acceleration?\n- How does the structure of the scheme compare with [1] when $x_{k+1}=\\hat{x}_k$? It seems that the main difference is the stepsize selection (error condition vs Armijo style backtracking line search). If this is true, the experimental comparison can seem a bit synthetic.\n- If you have full gradients, is it not possible to use Pearlmutter's implicit Hessian-vector product to (inexactly) do the second order update while still maintaining a $\\mathcal{O}(nd)$ like first-order methods? See e.g. https://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.pdf\n- Is it possible to relax the requirement of exact gradients? For first order methods it is still possible to achieve exponential convergence under e.g. relative noise (see e.g. Thm 5.1 in https://arxiv.org/pdf/2102.02921).\n\nExperimentally:\n\n- What are choices of hyperparameters $\\alpha, \\beta$ of the method? How are the baselines tuned in comparison?\n- The proposed method can also be used with a deterministic Hessian. How does the stochastic version compare with an exact Hessian? This would show the influence of the first (slow) phase and provide an idealized baseline.\n\nMinor:\n\n- Is it possible to shave off the logarithmic factors hiding in the $\\widetilde{\\mathcal O}$-notation?\n- Figure 1: is it a labeling mistake or is SNPE-UnifAvg consistently better than SNPE-WeightAvg?\n- How come stochastic NPE suffers an addition $\\Upsilon$ dependency in the superlinear rate (in comparison with stochastic Newton does not)?", "limitations": "See weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is technically strong and very clearly/transparently written.", "weaknesses": "The main weaknesses seems to be that:\n\n- It is unclear whether the scheme has relevance in practice, since the experiments seems to be run with a nonaccelerated version. For completeness I would suggest running the accelerated version, even if it performs worse (at least in the appendix). The theoretical results are strong and sufficient in themselves, so even though it would be better to find an instance that matches the theoretically guarantees, I don't see it as necessary.\n- there are no guarantees for convex as also pointed out by the authors.\n\nNeither are critical concerns – I mainly have a few remarks and questions regarding comparison with other methods and the experiments (see below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 Running the accelerated version in the experiment.**\n\n**A1** We added numerical results for the original SNPE with the extragradient step and compared it with the variant without it (Figure 3 in the shared PDF). We observe that the modified variant outperforms the original, suggesting the extragradient step may not be beneficial. However, the original SNPE still outperforms the stochastic Newton method in [1]. \n\n---\n**Q2 No guarantees for convex.**\n\n**A2** Due to space limitations, please see our response to **Q1** for Reviewer **qDEj**.\n\n--- \n**Q3 The complexity of the proposed method with exact Hessians.**\n\n**A3** With exact Hessians, our method achieves a complexity of $O((\\frac{L_2D}{\\mu})^{2/3}+\\log\\log(1/\\epsilon))$, though this requires a different analysis (we have an unpublished note). This matches the state-of-the-art complexity for second-order methods in strongly-convex strongly-concave min-max problems [R1]. However, for minimization problems, using Nesterov's acceleration achieves a better complexity of $O((\\frac{L_2D}{\\mu})^{2/7}+\\log\\log(1/\\epsilon))$ [R2].  \n\n[R1] Jiang, R. and Mokhtari, A. Generalized optimistic methods for convex-concave saddle point problems. (2022).\n\n[R2] Arjevani, Y. et al. Oracle complexity of second-order methods for smooth convex optimization. (2019).\n\n---\n**Q4 Choosing $x_{k+1} = \\hat{x}_k$ is not covered by the theory.**\n\n**A4** Good point. Our current theory only applies to SNPE in Algorithm 1 and cannot be easily extended to the modified version. However, drawing an analogy from first-order methods, it is reasonable to believe that both versions would share similar convergence guarantees. Specifically, the first-order instantiation of the HPE framework is the extragradient method, where the first step is $\\hat{x}_t=x_t-\\eta_t\\nabla f(x_t)$. Since both extragradient and gradient descent achieve the same linear rate, it is plausible that the same analogy holds for SNPE and its modification. That said, we do not have concrete proof and leave this for future work. \n\n---\n**Q5 Dffierence with stochastic Newton when $x_{k+1} = \\hat{x}_k$?**\n\n**A5** Our modified scheme has a different update rule from stochastic Newton, in addition to the difference in step size selection. Our modified scheme is $x\\_{t+1}=x\\_t-\\eta\\_t(I+\\eta_t\\tilde{H}\\_t)^{-1}\\nabla f(x_t)$ as shown in Eq. (6). In contrast, stochastic Newton follows $x_{t+1}=x_t-\\lambda_t\\tilde{H}_t^{-1}\\nabla f(x_t)$. Hence, the update directions are different, leading to distinct trajectories.\n\n---\n**Q6 Using Pearlmutter's implicit Hessian-vector product for inexact second-order updates?**\n\n**A6** Good point. First, Pearlmutter's technique is not always applicable as it requires access to the computational graph of the objective. Moreover, in the Hessian-free methods, the number of Hessian-vector products per iteration can be substantial to maintain the superior convergence rate of the second-order update, often scaling with the (square root of the) condition number of the Hessian and the desired accuracy. Thus, the stochastic Hessian approximation can sometimes be more efficient for leveraging second-order information.\n\n---\n**Q7 Relaxing the requirement of exact gradients.**\n\n**A7** Extending our analysis to noisy gradients is challenging since we cannot reliably check Condition (3), which is key in our proof. This limitation arises from the HPE framework and is not specific to our algorithm. Moreover, unless we impose strong assumptions on the gradient noise, it is unlikely to achieve superlinear convergence, which is our focus.\n\n---\n**Q8 The choices of hyperparameters.**\n\n**A8** For our Algorithm 1, the hyperparameters are the line-search parameters $\\alpha,\\beta\\in(0,1)$ and the initial step size $\\sigma_0$. We chose $\\alpha = 1,\\beta = 0.5$, and $\\sigma_0=1$ without optimizing their choices. For the stochastic Newton method, we followed the default line search parameters in the official GitHub implementation. Both algorithms are relatively robust to the choice of these hyerparameters. We will highlight this point in the revision.\n\n---\n**Q9 The stochastic version v.s. an exact Hessian?**\n\n**A9** We included the numerical results for NPE (our method with exact Hessian) in the shared PDF; see Figures 1 and 2. Figure 1 shows that NPE achieves a faster superlinear convergence rate and converges in fewer iterations due to the use of the exact Hessians. However, our SNPE method also performs comparably to NPE, demonstrating the effectiveness of the Hessian averaging scheme. Moreover, in terms of runtime, SNPE outperforms NPE due to its lower per-iteration cost.\n\n---\n**Q10 Logarithmic factors.**\n\n**A10** Eliminating the logarithmic factors seems difficult. These factors originate from Lemma 3, where we bound the average Hessian noise. The logarithmic dependence on $t$ arises from the union bound, while the dependence on $d$ is due to the matrix concentration inequality (Theorem 3 in [1]). Hence, these logarithmic factors cannot be eliminated without additional assumptions on the stochastic noise.\n\n---\n**Q11 Figure 1: is it a labeling mistake?**\n\n**A11** It is not a labeling mistake; in this experiment, SNPE-UnifAvg is indeed better than SNPE-WeightAvg. This might be due to the small subsampling size, making the stochastic Hessian noise the limiting factor. In our new experiment in the shared PDF, we set the subsampling size to match the dimension, and we observed that the weighted averaging outperforms the uniform averaging in all cases.\n\n---\n**Q12 An addition $\\Upsilon$ dependency in stochastic NPE?**\n\n**A12** The transition points and superlinear rates of stochastic Newton also depend on $\\Upsilon$. This dependence is not explicit in Table 1 because we focus on the setting where $\\Upsilon = O(\\kappa)$, which typically holds in practice. In this case, $O(\\kappa^2 + \\Upsilon^2) = O(\\kappa^2)$, simplifying the expressions in Table 1. We will add a remark in the revision to clarity this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful feedback. Overall, Reviewers **qDEj**, **m5uq** and **TogL** provided largely positive comments, highlighting the strength of our theoretical analysis and the clarity of the presentation. Reviewer **BRp1** raised some concerns regarding our complexity results, which we have addressed in detail by clarifying our superlinear convergence rates and discussing the complexity of line search. 

Following your suggestions, we have performed a new set of experiments, and the plots are included in the shared PDF file. 
We considered minimizing the regularized log-sum-exp function as in our submission, where the regularization parameter $\lambda$ is $10^{-3}$, the dimension $d$ is 500, and the number of samples $n$ is chosen from 50,000, 10,000, and 150,000, respectively. Note that we increased the dimension and the number of samples to better demonstrate the efficiency of our method in a large-scale setting. 

For Figures 1 and 2, we implemented a variant of SNPE without the extragradient step (see the discussions in Section 7) and compared it against the stochastic Newton method in [1], accelerated gradient descent (AGD), damped Newton's method, and Newton Proximal Extragradient (NPE, i.e., our SNPE method with exact Hessian). For the stochastic Hessian estimate, we use a subsampling strategy with a subsampling size of $s = d = 500$. Moreover, in Figure 3, we compare the two variants of SNPE: one with the extragradient step (as described in Algorithm 1) and one without (used in the previous plots). 

- **Comparison with AGD.** From Figure 1, we observe that our SNPE method, with either uniform or weighted averaging, requires far fewer iterations to converge than AGD due to the use of second-order information. Consequently, while SNPE has a higher per-iteration cost than AGD,  it converges faster overall in terms of runtime, as demonstrated in Figure 2.

- **Comparison with the damped Newton's method and NPE**. As expected, since both damped Newton and NPE use exact Hessian, Figure 1 shows that they exhibit superlinear convergence and converge in fewer iterations than the other algorithms. However, since the exact Hessian matrix is expensive to compute, they incur a high per-iteration computational cost and overall take more time than our proposed SNPE method to converge (see Figure 2). Moreover, the gap between these two methods and SNPE widens as the number of samples $n$ increases, demonstrating the advantage of our method in the large data regime.  
 
- **Effect of the extragradient step**. In Figure 3, we test the effect of the extragradient step in our proposed SNPE method. We observe that in all cases, the variant without an extragradient step outperforms the original version, suggesting that the extragradient step may not be beneficial for minimization problems. Nevertheless, the SNPE method with the extragradient step, which is the one analyzed in our paper, still outperforms the stochastic Newton method in [1]. 

We will revise our submission to include the new figures and discussions.

Meta-review: Overall, all reviewers were positive about this work and I support their decision.
Decision: Accept (poster)