acceptodds
Under review as a conference paper at ICLR 2027

A Free Lunch: Gradient Averaging Achieves Optimal Statistical Efficiency in Newton Sketch

18 views

Abstract

We study statistical inference for online sketched Newton methods, in which each Newton system is approximately solved by an inner randomized sketching solver. Existing work reveals a computational–statistical trade-off: the sketching solver (and its accelerated variants) reduces the per-step cost of Newton methods from to , but the randomness introduced by sketching also inflates the limiting covariance of both the last and the averaged Newton iterates. In this work, we address this trade-off via gradient averaging. We show that simply replacing the stochastic gradient with a moving average at each step can mitigate, and in some cases eliminate, the trade-off in Newton sketch. Importantly, gradient averaging requires no additional oracle evaluations and leaves the contraction bound of the inner sketching solver unchanged. In particular, we prove that the last sketched Newton iterate with gradient averaging attains a limiting covariance no larger than that without gradient averaging, while the averaged iterate even attains the *minimax optimal* limiting covariance, matching that of the exact Newton method. To our knowledge, this is the first analysis showing that randomness introduced to improve computational efficiency need not compromise statistical efficiency as long as proper gradient estimates are used. The key analytical challenge is that gradient averaging destroys the crucial martingale difference structure underlying central limit theorem arguments. We overcome this challenge by analyzing the coupled two-timescale recursions governing the iterate and the gradient estimator. Numerical experiments on linear and logistic regression support our theoretical covariance comparisons.

Primary area:
optimization
Keywords:
Online Newton methods, Randomized sketching, Gradient averaging, Minimax statistical efficiency

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_dyQgOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the computational–statistical trade-off in online sketched Newton methods and proposes gradient averaging to mitigate the statistical inefficiency introduced by randomized sketching. The authors establish improved asymptotic covariance guarantees, showing that averaged iterates can achieve the minimax-optimal covariance of exact Newton methods.

Critical strengths

The paper is clearly written, and although I have not verified the proofs in detail, the theoretical results appear intuitive and well-motivated.

Critical weaknesses

See Questions.

Questions for authors
  1. I suggest highlighting the main theoretical results more clearly, as the large number of theorems makes it difficult to identify the key contributions and takeaways.

  2. Could the authors provide a more detailed computational complexity analysis? In particular, Theorems 3.5 and 4.3 impose conditions on τ\tau. Do these conditions affect the claimed reduction in per-step computational complexity?

  3. Could the authors report the actual runtime of each method in the experiments to better demonstrate the computational benefits?

5 comments

(We have consolidated our responses into fewer replies to make them easier for the reviewer to read.)

We sincerely thank the reviewer for your careful reading and positive assessment of our work. All three questions are valuable to us and have been properly addressed in the revised manuscript, where the changes are marked in red. In short, the revision (i) adds a summary of the main theoretical results and their takeaways in Section 1, Lines 120–140; (ii) clarifies that the conditions on τ\tau require only a fixed number of sketching steps that does not grow with the iteration count, and provides a detailed account of the per-iteration cost in Section 3 (around Lines 315) and Section 4 (around Lines 335); and (iii) reports the running time of each method in a new section on online inference (Appendix E.6, Tables 5–6). We believe that our responses and revisions resolve the reviewer's questions, and further strengthen the reviewer's support for the paper.

(Q1) Thank you for this helpful suggestion. We have added a summary of the key contributions and their takeaways in Section 1 (around Lines 120–140), so that readers can see how the results fit together before turning to their detailed statements and proofs. We have also highlighted these takeaways where the main results are stated in Sections 3 and 4 (around Lines 309–319 and 405–457).

In short, the message of the paper is as follows. Prior work has observed that, although sketching reduces the per-iteration cost of online Newton methods, the randomness of the sketching solver inflates the limiting covariance of the iterates. We show that, if the sketching solver is applied to a better gradient estimate, namely a moving average of the stochastic gradients (i.e., gradient momentum), then the uncertainty induced by sketching is mitigated for the last iterate and eliminated for the averaged iterate. These correspond to the two main results of the paper.

  1. Last iterate: reduced covariance (Theorem 4.5 and Proposition 4.6). The last iterate is asymptotically normal with the limiting covariance Σm,asl\Sigma^l_{\mathbf{m},\mathrm{as}} no larger than the limiting covariance Σg,asl\Sigma^l_{\mathbf{g},\mathrm{as}} of the sketched Newton without gradient averaging, i.e., Σm,asl⪯Σg,asl\Sigma^l_{\mathbf{m},\mathrm{as}}\preceq\Sigma^l_{\mathbf{g},\mathrm{as}}. In other words, gradient averaging reduces the uncertainty induced by sketching, although Σm,asl\Sigma^l_{\mathbf{m},\mathrm{as}} still depends on the sketching solver.

  2. Averaged iterate: optimal covariance (Theorem 4.7). The averaged iterate is asymptotically normal with limiting covariance Σm,asa=Ω\Sigma^a_{\mathbf{m},\mathrm{as}}=\Omega, which is the minimax optimal covariance attained by exact Newton method. That is, the uncertainty induced by sketching vanishes entirely, while it persists in the limiting covariance of the averaged iterate when gradient averaging is not used.

The mechanism behind these two results is that, when gradient averaging is employed, the iterates admit a linear representation in which the random sketching factor I−K~i⋆I-\tilde K_i^\star of the vanilla sketched Newton method is replaced by its mean I−K⋆I-K^\star. In other words, gradient averaging removes the centered sketching fluctuation from the leading noise term, so that sketching enters the limiting covariance only through its mean effect.

The takeaway is that the statistical price of sketching is not intrinsic: it arises from combining the sketching randomness with a noisy single-sample gradient. With a simple moving average of the gradients, the sketched Newton method retains the computational savings of sketching while its averaged iterate still attains the optimal covariance of the exact Newton method, without any additional assumptions or oracle calls.

(Q2) Thank you for this question. The conditions on τ\tau do not affect the claimed reduction in the per-iteration cost: Theorems 3.5 and 4.3 require only a fixed number of sketching steps, which does not grow with the iteration tt. We have revised the discussion following Theorem 3.5 (Section 3, around Lines 315) to state this explicitly and provide a detailed analysis of the per-iteration computational cost in Section 4 (around Lines 335–352) and Appendix A. We also emphasize that gradient averaging changes only the right-hand side of the Newton system, so the sketching solver and its contraction bound (Lemma 2.1) are exactly the same as those in existing sketched Newton methods without gradient averaging. We do not have any stronger conditions on τ\tau.

In particular, we would like to clarify the following points.

(a) The conditions require only a fixed τ\tau, independent of the iteration. Theorems 3.5 and 4.3 take a fixed τ\tau satisfying τ(1−μt/νt)τ−2≤γB,t/(8ΥB,t)\tau(1-\sqrt{\mu_t/\nu_t})^{\tau-2}\le\gamma_{B,t}/(8\Upsilon_{B,t}) for all tt. Both sides of this inequality are controlled uniformly in tt: on the left-hand side, Assumption 3.4 ensures that 1−μt/νt≤1−γS<11-\sqrt{\mu_t/\nu_t}\le1-\gamma_S<1; on the right-hand side, Assumption 3.1 ensures that sup⁡t≥0ΥB,t/γB,t<∞\sup_{t\ge0}\Upsilon_{B,t}/\gamma_{B,t}<\infty almost surely. Since the left-hand side decays geometrically in τ\tau, the number of sketching steps needed for the inequality to hold is bounded uniformly in tt almost surely, as discussed after Theorem 3.5. Therefore, the inner solve is not required to become more accurate as the outer iteration proceeds, and the per-iteration sketching cost does not grow with tt. This is the most important property: we do not require the approximation error in solving the Newton systems to vanish.

(b) Number of sketching steps, with and without sketching acceleration. We first clarify that the following discussion is not specific to this paper, and that none of it is tied to the design of our method. Our gradient averaging leaves the sketching solver unchanged, so the number of sketching steps and the cost of each step are the same as those in existing sketched Newton methods [4–6]. That being said, to make the paper self-contained, we simply follow the literature on sketch-and-project solvers [1–3] and review the difference between sketching with and without Nesterov acceleration.

The number of sketching steps is governed by the two constants μt\mu_t and νt\nu_t in (2.3), which satisfy 1≤νt≤1/μt1\le\nu_t\le1/\mu_t [2]. In each sketching step, the expected squared error of the approximate Newton direction contracts by the factor 1−μt1-\mu_t without acceleration [1], and by the factor 1−μt/νt1-\sqrt{\mu_t/\nu_t} with Nesterov's acceleration (Lemma 2.1). The latter is never larger than the former. Both constants depend on the sketching distribution, the sketch size ss, the dimension dd, and the condition number κt=λmax⁡(Bt)/λmin⁡(Bt)\kappa_t=\lambda_{\max}(B_t)/\lambda_{\min}(B_t) of the Newton system [1–3]. In general (e.g., randomized coordinate sketching), one has μt≥s/(dκt2)\mu_t\ge s/(d\kappa_t^2) and νt=d/s\nu_t=d/s. Hence, Nesterov acceleration improves the contraction factor from 1−s/(dκt2)1-s/(d\kappa_t^2) to 1−s/(dκt)1-s/(d\kappa_t) and reduces the number of sketching steps needed to reach a fixed accuracy ϵ\epsilon from O(dκt2/s⋅log⁡(1/ϵ))O(d\kappa_t^2/s\cdot\log(1/\epsilon)) to O(dκt/s⋅log⁡(1/ϵ))O(d\kappa_t/s\cdot\log(1/\epsilon)). That is, the dependence on the condition number improves from κt2\kappa_t^2 to κt\kappa_t [2, 3]. Furthermore, the conditions on τ\tau in Theorems 3.5 and 4.3 require only a fixed accuracy: they enter our analysis solely through the bound ∣Kt∣≤2τ(1−μt/νt)τ−2≤γB,t/(4ΥB,t)\\|K_t\\|\le2\tau(1-\sqrt{\mu_t/\nu_t})^{\tau-2}\le\gamma_{B,t}/(4\Upsilon_{B,t}), where KtK_t is the expected coefficient matrix of the sketching approximation error (Section 4.1). Thus, these conditions are met by τ\tau of order dκt/sd\kappa_t/s, up to a logarithmic factor, where κt≤ΥB,t/γB,t\kappa_t\le\Upsilon_{B,t}/\gamma_{B,t} is bounded uniformly in tt; see (a). We also note that these are sufficient, worst-case conditions, which are conservative in practice. In our experiments, τ∈5,10\tau\in\\{5,10\\} already yields the predicted covariance reduction across all settings (Table 1, Figure 1). The actual running times are reported in the new section on online inference; see (Q3).

(c) Per-step computational cost. As in (b), the discussion below simply follows the existing literature [1–6] and is not tied to the design of our method. In general, the cost of each sketching step depends on the sparsity of the sketching matrix. For example, under randomized coordinate sketching with a fixed sketch size ss (we use s=1s=1 in our experiments), each sketching step costs only O(d)O(d), with or without acceleration. Combining this with the number of sketching steps in (b), we see that the sketching solver costs O(d)×O(d)=O(d2)O(d)\times O(d)=O(d^2) per iteration, up to a logarithmic factor, compared with O(d3)O(d^3) for an exact Newton solve. The constant in the O(d2)O(d^2) cost depends on the condition number, which is where accelerated sketching improves upon unaccelerated sketching. For the other components of the Newton method, updating the Hessian average costs O(d2)O(d^2) per iteration; the spectral clipping of BtB_t can be refreshed once every dd iterations, leading to an O(d2)O(d^2) amortized cost (Section 4); and gradient averaging adds only an O(d)O(d) vector update, with no additional gradient, Hessian, or sketching evaluations. Hence, the method retains the claimed O(d2)O(d^2) per-iteration cost in terms of the dimension, which follows the same cost accounting as existing sketched Newton methods [4–6].

(Q3) Indeed. Thank you for the suggestion. As also suggested by Reviewer 8ZLh (Q2), we have added a new section on online inference (Appendix E.6, Tables 5–6) that reports the actual running times of ASGD, exact Newton, and sketched Newton with and without gradient averaging. For each method, we report the total running time of the complete inference procedure, including both iterate updates and online covariance estimation, along with the empirical coverage probabilities and lengths of the resulting confidence intervals.

In particular, we would like to clarify how the running times are reported and what they show.

(a) Running times are compared for inference, not for estimation alone. For estimation alone, comparing running times provides limited insight: ASGD incurs only O(d)O(d) cost per iteration and is naturally the fastest. However, when inference is included, its per-iteration cost increases to O(d2)O(d^2) due to the online estimation of the limiting covariance matrix [7], matching the order of a sketched Newton step. Since statistical inference is the primary goal of this paper, a fair comparison should account for the computational cost of the complete inference procedure.

(b) What the results show. The new section considers d=40d=40 in linear and logistic regression. The results show that sketched Newton is substantially faster than exact Newton: across the six settings, it uses about 7373–7474\\% fewer FLOPs and reduces running time by 2424–5353\\% after 10510^5 updates (Table 5). On the other hand, we do not expect sketched Newton to match the running time of ASGD inference. Although both have an O(d2)O(d^2) per-iteration cost, sketched Newton requires additional sketching steps, resulting in a larger constant factor than that of ASGD. Finally, gradient averaging itself introduces negligible computational overhead, requiring only one additional dd-dimensional vector update per iteration. As reported in Appendix E.5, across the 48 matched sketching settings in Section 5, the median ratio of per-iteration running times with and without gradient averaging is 1.0381.038, corresponding to a median increase of only 3.83.8\\%.

(c) Running time to achieve a target coverage rate. Finally, comparing running times over the same number of iterations still does not fully account for differences in inferential accuracy, as the resulting confidence intervals can have substantially different coverage rates. In particular, the undercoverage of ASGD confidence intervals is well documented (64.564.5\\%–9292\\% at a nominal level of 9595\\% with d=20d=20 [4, 6, 7]), while the coverage of Newton-type confidence intervals remains close to the nominal level with fewer samples. A more informative comparison is therefore the running time required to achieve a prescribed coverage rate. For the 9090\\% empirical-coverage target, all exact and sketched Newton methods reach the target within 10510^5 updates, with mean running times of 0.1110.111–2.1512.151 seconds per run. ASGD does not reach the target in any of the six settings within the 30-second limit per run (Table 6). This comparison highlights the finite-sample advantage of sketched Newton over ASGD for statistical inference; see also our response (W1&Q2) to Reviewer 8ZLh.

References

[1] Gower and Richtárik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 2015.

[2] Gower et al. Accelerated stochastic matrix inversion: General theory and speeding up BFGS rules for faster second-order optimization. Advances in Neural Information Processing Systems, 2018.

[3] Dereziński et al. Fine-grained analysis and faster algorithms for iteratively solving linear systems. Journal of Machine Learning Research, 2025.

[4] Wang et al. Inference of online Newton methods with Nesterov's accelerated sketching. International Conference on Machine Learning, 2026.

[5] Du et al. Inference for Newton methods with accelerated sketch-and-project via random scaling. arXiv preprint arXiv:2609.12421, 2026.

[6] Kuang et al. Online covariance matrix estimation in sketched Newton methods. Information and Inference: A Journal of the IMA, 2026.

[7] Zhu et al. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 2021.

Reviewer_8ZLhOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper considers stochastic gradient methods using the sketched Newton method, where the Hessian at the given iterate is approximated by accelerated sketching. The paper highlights that sketching creates some extra randomness that makes the asymptotic variance of the resulting estimator not optimal. A form of gradient averaging is presented that corrects this and achieves the optimal estimation variance.

Critical strengths

I like the fact that the paper identifies an artefact due to the fast sketching and that it corrects it.

Critical weaknesses
  • The paper fails to compare the proposed approach to classical averaged SGD, which achieves the minimax covariance with an algorithm that is much easier to analyze.
  • The recent line of work on considering only asymptotic convergence for SGD and its variants, is complementary to non-asymptotic approaches. However, when they come at unrealistic assumptions, this is really a step backward. For example, Assumption 3.1 makes the paper analysis irrelevant. Strong convexity of each of the local functions used in SGD is never true, even in small dimensions. This can only be true if a regularizer is added, but then this creates an extra hyperparameter. The paper states that this assumption comes from the literature. I checked the first reference and did not find it.
  • Theorem 3.4: since the strong convexity constant \gamma_H will be either zero or very small, this makes the assumption almost vacuous.
  • I would not characterize the findings of this paper as "free lunch"

POST REBUTTAL The convexity issue has been resolved, so I increase my overal score.

Questions for authors
  • Step size \varphi_t: which one was chosen in simulations, and what is recommended for practitioners? Most algorithms consider constant step-sizes instead of decaying. This should be compared against.
  • Can you add wall-clock times for empirical comparisons and compare to plain averaged SGD.
9 comments

(We have consolidated our responses into fewer replies to make them easier for the reviewer to read.)

We sincerely thank the reviewer for your careful reading of our paper. We have taken every comment seriously. All comments have been properly incorporated into the revised manuscript, where the changes are marked in red. These revisions have indeed substantially strengthened the quality of the paper. We sincerely hope the reviewer will re-evaluate the paper based on the revised version, to align with the assessments of the other two reviewers, especially taking into account that our contribution to existing literature on online inference via second-order methods is straightly clear: without any extra assumptions, simple gradient averaging achieves optimal covariance for sketched Newton methods. Before the itemized responses, we would like to make the following general remarks on revisions.

  1. Presentation. We are, honestly, puzzled by the Presentation score of 1. The other two reviewers both rate the presentation 3 (“clear and easy to follow”) and describe the writing as “clearly written and easy to follow”. Moreover, the weaknesses listed in the review regard the assumptions and the comparison with ASGD, rather than specific passages that are hard to follow. So we could not identify from the review how this is evaluated. That being said, we have taken the score seriously and, as requested, significantly improved the writing in the revision:

    • a summary of main theoretical results and their takeaways in Section 1 (as suggested by Reviewer dyQg, Q1);
    • an explicit statement of the sense in which gradient averaging is a “free lunch” in the abstract, Section 1, and the Conclusion (W4);
    • the experimental stepsizes in Appendix E.1 and a discussion of stepsize choices with a recommendation for practitioners in Appendix A (Q1);
    • covariance notation defined at first use (Section 1, around Lines 100) (Reviewer WgvF, Q2);
    • a discussion of the condition on τ\tau (Section 3, around Lines 315) and an analysis of the per-iteration cost (Section 4, around Lines 351; Appendix A, around Lines 782–803) (Reviewer dyQg, Q2).

    If the reviewer thinks that other parts of the writing can be further strengthened, we would be happy to address during the discussion period.

  2. Assumptions. We have completely resolved the reviewer's main concern regarding Assumption 3.1. Although this assumption in the submitted version was taken directly from recent work on sketched Newton methods [2–4], so that our analysis was on the same footing as this line of work, we agree with the reviewer that it is stronger than necessary, and we have further weakened it in this paper. The revised Assumption 3.1 has two parts, and each part matches the weakest condition used in the corresponding literature:

    • the conditions on the objective, namely strong convexity and smoothness of the population objective ff without uniform spectral bounds on individual sample Hessians, are standard conditions for SGD [5–7];
    • the condition on the preconditioning matrix BtB_t, namely Ft−1\mathcal F_{t-1}-measurable spectral bounds, is taken directly from preconditioned SGD [8, Assumption 9]. With this revision, the present Assumption 3.1 is now strictly weaker than those in the existing sketched Newton literature [2–4]. For example, linear regression with Gaussian covariates, whose sample Hessians are rank one and unbounded, is now covered without any regularizer; see (W2&W3). In this sense, the result is indeed a free lunch: with gradient averaging, sketched Newton attains the optimal covariance Ω\Omega under the conditions used for SGD and preconditioned SGD, without requiring stronger conditions beyond what is assumed in the existing literature.
  1. Comparison with ASGD and running time. Please refer to our response to (W1&Q2) and, in more detail, to our response (W1&Q3) to Reviewer WgvF for the motivation behind extensive existing literature on second-order methods, although ASGD already attains Ω\Omega. In short, second-order methods still offer theoretical advantages (iterate stability under a weaker stepsize condition and faster convergence rate of covariance estimation), as well as better practical inference gains. As requested, the revision also adds comparisons among ASGD and sketched and exact Newton methods in Appendix E.6 (Tables 5–6) and reports their running times; see (W1&Q2). We would like to clarify how the running times are reported, since a naive comparison could be misleading:
    • For estimation alone, comparing running times offers limited insight: ASGD costs O(d)O(d) per iteration and is naturally the fastest. However, its per-iteration cost increases to O(d2)O(d^2) when inference is included, due to the online estimation of the limiting covariance matrix. Since inference is the goal of this paper, a fair comparison should account for the full inference procedures.

    • The revision adds a new section on online inference (Appendix E.6, Tables 5–6) comparing ASGD, exact Newton, and sketched Newton with and without gradient averaging. It reports the running time of the complete inference procedure (iterate updates plus online covariance estimation), along with the coverage and length of the resulting confidence intervals.

    • The new section considers d=40d=40 across linear and logistic regression with all three covariate covariance structures. In these settings, sketching reduces both FLOPs and running time relative to exact Newton.

    • The results show that sketched Newton substantially reduces the running time of exact Newton; its per-iteration cost is of the same order O(d2)O(d^2) as that of ASGD-based inference (see our response (Q3) to Reviewer dyQg). However, ASGD exhibits substantial undercoverage at d=40d=40, while Newton-type intervals maintain coverage close to the nominal level of 9595\\%. All Newton methods reach 9090\\% empirical coverage within 10510^5 updates, whereas ASGD does not reach that target within 30 seconds per run; see point (c) of our response (Q3) to Reviewer dyQg.

We believe that the revised manuscript and our responses address all the reviewer's comments. We sincerely hope the reviewer will re-evaluate the paper in light of these revisions.

(W1&Q2) Thank you for the suggestion. We would first like to clarify the focus of our paper. Our “free lunch” result concerns existing sketched Newton methods [2–4]. Under the same setting and conditions as these methods (in fact, under weaker conditions by relaxing Assumption 3.1 as requested), we show that simple gradient averaging improves their statistical efficiency to the optimal level, i.e., the averaged iterate attains the covariance Ω\Omega matching that of exact Newton methods. Comparisons between ASGD and (sketched) Newton methods, among different sketching methods, and of their computational costs in terms of flops and running time have already been carried out extensively in the literature [2–4, 9–11] and are therefore not the focus of this paper. For this reason, the original submission included SGD only as a baseline in the estimation plots in the appendix (Figures 4 and 5), and not in the main comparisons.

That said, we agree that including ASGD would make the paper more complete, as also suggested by Reviewer WgvF (W1/Q3). The question of running time was also raised by Reviewer dyQg (Q3). As summarized in our general remark (3) above, the revision includes SGD in the estimation-error comparisons (Appendix E.5, Figures 4–5) and introduces a new section on online inference (Appendix E.6, Tables 5–6). This section compares ASGD, exact Newton, and sketched Newton methods with and without gradient averaging at d=40d=40. We report the running time of the complete inference procedure (iterate updates plus online covariance estimation), together with the coverage and lengths of the resulting confidence intervals. We focus on running times for inference rather than for the estimation experiments in Section 5. For estimation alone, ASGD requires only O(d)O(d) operations per iteration and is naturally the fastest. However, when the limiting covariance must also be estimated online for inference, which is a key motivation behind the growing interest in second-order methods for online inference, the per-iteration cost of ASGD increases to O(d2)O(d^2), the same order as that of a sketched Newton step.

In particular, we agree that ASGD is clean and simple to analyze, and it asymptotically attains Ω\Omega, as now acknowledged in Section 1. Newton methods also provide last-iterate inference and faster covariance estimation, and their confidence intervals have better coverage in the settings studied here and in prior work [2–4, 7, 9–11]. They are less sensitive to ill-conditioning and heterogeneous noise [8–10]. We discuss these advantages and the motivation for second-order online inference in our response (W1&Q3) to Reviewer WgvF.

The new inference section confirms this picture. At d=40d=40, after 10510^5 updates, ASGD confidence intervals have only 5757–6565\\% empirical coverage, while exact and sketched Newton intervals achieve 89.589.5–98.598.5\\%, with most values close to the nominal level of 9595\\%. At the same time, sketched Newton uses about 7373–7474\\% fewer FLOPs and reduces running time by 2424–5353\\% relative to exact Newton, with a per-iteration cost of the same order O(d2)O(d^2) as that of ASGD-based inference; gradient averaging adds only one dd-vector update per iteration. Moreover, a more informative comparison is the running time required to achieve the same coverage rate. At the 9090\\% empirical-coverage target, all exact and sketched Newton methods reach the target within 10510^5 updates, taking 0.1110.111–2.1512.151 seconds per run, whereas ASGD does not reach it in any of the six settings within the 30-second limit; see our response (Q3), point (c), to Reviewer dyQg. In other words, gradient averaging enables sketched Newton to achieve the inferential reliability of exact Newton at essentially the same computational cost as existing sketched Newton methods. This is precisely the sense in which we call our method “free lunch.” Moreover, compared with ASGD, it requires substantially less running time to reach the same level of finite-sample inferential accuracy.

(W2&W3) We thank the reviewer for forcing us to weaken this assumption, which has significantly improved the quality of the paper. We first clarify the references. The reviewer is correct that the uniform sample-level condition is not stated in the first reference [1]. That work studies equality-constrained stochastic optimization via sketched sequential quadratic programming, a setting different from ours, and we have therefore removed it from the sentence following the assumptions (Section 3, around Line 285). The remaining references [2–4] do impose exactly this condition, and Assumption 3.1 in the original submission was taken directly from them. Nevertheless, we greatly appreciate the reviewer's concern and, as requested, have weakened Assumption 3.1 to the weakest conditions used in the literature; see our general remark (2) above. Theorem 3.5, Lemmas 4.1–4.2, Theorem 4.3, and their proofs in Appendices C–D have been updated accordingly. Now, the revised Assumption 3.1 consists of two parts, which we address separately in (a) and (b) below, followed in (c) by our response to concern (W3) regarding small γH\gamma_H.

(a) Conditions on the objective. The revised assumption requires strong convexity and smoothness only of the population objective ff. No uniform spectral bounds are imposed on the Hessians of the sample functions F(⋅;ξ)F(\cdot;\xi). These are standard conditions for SGD-based inference [5–7]. Although SGD can converge under much weaker conditions, even for nonconvex problems, strong convexity remains a common and convenient assumption for inference, for two reasons. First, inference is local by nature: it quantifies the uncertainty of the iterates around a strict local minimizer x⋆\mathbf{x}^\star satisfying ∇2f(x⋆)≻0\nabla^2f(\mathbf{x}^\star)\succ0, so strong convexity holds in a neighborhood of x⋆\mathbf{x}^\star. The literature [5–7] (and this paper) assumes global strong convexity only as a convenient way to establish the almost sure convergence xt→x⋆\mathbf{x}_t\to\mathbf{x}^\star; the essential curvature requirement for inference is local. Second, strong convexity at the solution is also what makes the statistical lower bound meaningful. Recent instance-dependent non-asymptotic (local minimax) lower bounds for stochastic optimization are established for strongly convex population objectives [12], since the limiting uncertainty is well defined and robust to perturbations only at a strict local minimizer. In short, our assumptions on the objective are no stronger than those commonly imposed for SGD-based inference.

Reviewer_WgvFOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper shows that by incorporating gradient averaging, online sketched Newton can have better convergence guarantees. Specifically, online sketched Newton can have similar asymptotic normality and covariance compared to online exact Newton, while staying cheaper.

Critical strengths

The writing is clear to follow, with enough explanation for each theorem and assumption. The result is meaningful, gradient averaging is simple operation and matching sketched Newton to exact Newton is meaningful.

Critical weaknesses

Turns about averaged SGD reaches the same Ω\Omega, and I think the main reason why people want second-order method like Newton is to have better finite-sample behavior, i.e. second-order methods are supposed to converge faster, or be less sensitive to ill-conditioning and step size choices. The paper has limited explanation on these parts.

Also in Figure 4 in appendix, seems SGD is better than exact Newton.

Questions for authors
  1. why in Figure 4, SGD is better than exact Newton?
  2. in line 85, Σm,asl\Sigma_{m, as}^l appears without a formal introduction of this symbol. The first explanation exists in Notation part on line 125.
  3. If averaged SGD can already achieve Ω\Omega, what's the point of the analysis in current writeup?
4 comments

We sincerely thank the reviewer for your careful reading and supportive assessment of our work. All comments are valuable to us and have been properly incorporated into the revised manuscript, where the changes are marked in red. We believe that our responses and revisions resolve the reviewer's concerns and questions, and can further strengthen the reviewer's support for the paper.

(W1&Q3) Thank you for this comment. As also suggested by Reviewer 8ZLh, we have significantly expanded the motivation for our study of second-order methods and the experimental comparisons with first-order methods. We have revised Section 1 to clarify (i) why second-order methods are used for online inference even though first-order methods are also asymptotically optimal, and (ii) that the contribution of this paper is to make existing, already well-motivated second-order methods statistically optimal without sacrificing their computational gains over exact Newton methods, rather than to propose a newly designed class of second-order methods. ASGD is now included in the online-inference comparison (Appendix E.6, Tables 5–6), although its significant undercoverage is already well known in the literature [1, 3, 4] (and this is the strong motivation of people studying second-order methods in the literature).

In particular, we would like to clarify the following points.

  1. Why the literature studies second-order methods although ASGD is already optimal, and what our work is for?

    Indeed, averaged SGD (ASGD) and exact Newton are both asymptotically optimal and attain the minimax optimal covariance Ω\Omega. However, sketched Newton that reduces per-iteration cost of exact Newton from O(d3)O(d^3) to O(d2)O(d^2) was not optimal before our work: [4, 5] showed that both its last and averaged iterates have limiting covariances strictly larger than Ω\Omega. Our work makes it optimal (or closer to optimal): with simple gradient averaging, the averaged sketched Newton iterate attains Ω\Omega (Theorem 4.7), and the last iterate has a uniformly smaller covariance than without gradient averaging (Proposition 4.6). Notably, this improvement is achieved at only O(d)O(d) extra cost per step and with no additional gradient, Hessian, or sketching evaluations. This is the major contribution of our work: bridging the existing claimed gap of the computational–statistical trade-off of sketched Newton methods.

    With this story being clear, the study of second-order methods themselves is well documented in the existing literature [2–9]. Our contribution is to make their computationally efficient sketched version statistically optimal as well. Specifically, the existing literature studies second-order methods for online inference for the following reasons.

    (a) Theoretical gain: better stability. SGD is asymptotically optimal only after Polyak–Ruppert averaging (i.e., ASGD): its last iterate is not and the limiting covariance of the last iterate solves a Lyapunov equation that depends on the Hessian. Exact Newton methods remove this dependence through preconditioning, allowing both the last and averaged iterates to attain Ω\Omega [6–8]. Thus, Newton methods reduce uncertainty of SGD iterates by yielding smaller covariances, and inference can be based directly on the last iterate without averaging. The sensitivity of first-order methods to ill-conditioning and heterogeneous gradient noise also disappears.

    (b) Theoretical gain: faster covariance estimation. Online inference requires estimating the limiting covariance. For ASGD this is done with batch-means-type estimators constructed from the SGD iterates [1], whose convergence rate is only of order O(1/tφt4)O(1/\sqrt[4]{t\varphi_t}). Newton-type methods instead admit a simple weighted sample covariance estimator constructed from the Newton iterates, which converges at the significantly faster rate O(1/tφt)O(1/\sqrt{t\varphi_t}), i.e., a quadratic improvement over the SGD rate [3, 4]. Some recent progress on SGD aims to reach a comparable rate [10], but only under considerably more restrictive noise conditions (e.g., 8th-moment condition on the gradient noise).

    (c) Practical gain: much better inference performance. The undercoverage of ASGD confidence intervals is well documented and has been consistently observed across independent studies under very similar settings [1, 3, 4]. With d=20d=20, the reported empirical coverage of ASGD intervals is far below the nominal level of 9595\\%; e.g., 7979–8686\\% in [1, Table 1], 8787–9292\\% in [3, Tables 1–2], and 64.564.5–81.581.5\\% across the six settings in [4, Table 2]. In contrast, Newton methods perform substantially better in these experiments: exact and sketched Newton intervals achieve approximately 91.591.5–9898\\% coverage, close to the nominal level, across the same models, designs, and dimensions [3, Tables 1–2; 4, Tables 1–2]. Similar advantages have also been reported for other problems [7–9]. Our new experiments (Appendix E.6, Tables 5–6) show the same pattern at d=40d=40: after 10510^5 updates, ASGD runs faster but its intervals have only 5757–6565\\% coverage, compared with 89.589.5–98.598.5\\% for exact and sketched Newton. All Newton methods reach 9090\\% empirical coverage within 10510^5 updates, whereas ASGD does not reach it within the 30-second limit. These results demonstrate that Newton methods can deliver reliable inference in settings where ASGD exhibits substantial undercoverage, which is the main practical reason the literature studied second-order methods (though, for sure, second-order methods need Hessian estimation).

  1. SGD and Newton do not differ in convergence rates in online setting.

    The distinction between the two families lies in the uncertainty of the iterates and in covariance estimation, as recalled in (a) and (b) above, rather than in the convergence rate [11, pp. 19–20]. In the online setting with vanishing stepsizes, the rate is determined entirely by the stepsize: for both first- and second-order methods, the averaged iterate converges at rate 1/t1/\sqrt t and the last iterate at rate φt\sqrt{\varphi_t}. That being said, one difference in the stepsize choice does exist for the last iterate: with φt=Cφ/t\varphi_t=C_\varphi/t, SGD requires Cφ>1/2λmin⁡(B⋆)C_\varphi>1/\\{2\lambda_{\min}(B^\star)\\}, a constant that depends on the unknown curvature, while exact Newton requires only Cφ>0.5C_\varphi>0.5 due to affine invariance (cf. Theorem 4.5). We mention this in Appendix A.

  2. What this paper adds to second-order methods: a free-lunch perspective.

    Although SGD costs only O(d)O(d) per step for the update, its inference still requires online estimating the limiting covariance matrix, leading to O(d2)O(d^2) cost per step. Exact Newton, in turn, attains the optimal covariance for both the last and averaged iterates, but at a cost of O(d3)O(d^3) per step. This motivates sketched Newton methods, which approximately solve Newton systems using a sketching solver and reduce the per-step cost to O(d2)O(d^2). This is of the same order as SGD-based inference.

    However, existing analyses [4, 5] showed that this computational saving comes at the expense of statistical efficiency: both the last and averaged sketched Newton iterates have limiting covariances strictly larger than Ω\Omega. Our work closes this gap for the averaged iterate and reduces it for the last iterate. By simply averaging gradients, the averaged sketched Newton iterate attains optimal Ω\Omega (Theorem 4.7), while the last iterate also has a uniformly smaller covariance than without gradient averaging (Proposition 4.6). These improvements hold under the same setting as existing sketched Newton methods, and in fact under weaker assumptions and require only O(d)O(d) additional operations per step, with no additional gradient, Hessian, or sketching evaluations. The cost remains O(d2)O(d^2), while the averaged iterate recovers the optimal covariance, substantially narrowing the computational gap between SGD and exact Newton without sacrificing asymptotic statistical efficiency.

    We should emphasize that this gain is a “free lunch” compared to existing sketched Newton methods: the only addition is a moving average of the gradients, and no additional assumptions are imposed. We did not claim that Newton methods are “free” compared to SGD. Surely, Newton methods require Hessian information, while SGD does not. The two rely on the same types of assumptions on gradient noise, strong convexity, and smoothness, but each has its own advantages: SGD requires only gradient oracle, while Newton methods use Hessian oracle to obtain the benefits described in (a)–(c). The revision makes this scope explicit in the abstract, Section 1, and the Conclusion; we further clarify the precise meaning of “free lunch” in our response to Reviewer 8ZLh (W4).

(W2 & Q1) Indeed. We have revised Appendix E.5 to explain this observation and added an inference comparison of exact and sketched Newton methods with ASGD in Appendix E.6. This comparison demonstrates the practical benefits of second-order methods for inference over first-order methods, as expected. As discussed in point (c) of our response to (W1&Q3), the undercoverage of SGD confidence intervals is well documented and widely observed in the literature [1, 3, 4] and easily reproduced in regression settings.

In particular, we would like to clarify the following points.

  1. Figure 4 (and 5) shows estimation convergence, where SGD and Newton are theoretically comparable.

    As recalled in our response to (W1&Q3), with vanishing stepsizes the convergence rate of the iterates is determined by the stepsize rather than the order of the method: both methods converge at rate φt\sqrt{\varphi_t} for the last iterate and 1/t1/\sqrt{t} for the averaged iterate. Figure 4 reports only this estimation convergence (bias, MSE, and objective gap).

    Moreover, the problem in Figure 4 is a very simple one: linear regression (d=20d=20) with identity covariate covariance and population Hessian B⋆=IB^\star=I. In this setting, preconditioning has nothing to correct, yet Newton methods must still estimate BtB_t from sample Hessians. It is therefore not surprising that SGD performs somewhat better than exact Newton in this setting (i.e., a second-order method can be overkill here). That being said, we still see that the slopes of the curves in Figure 4 are essentially the same across methods, consistent with the comparable theoretical rates.

    By contrast, for more complex logistic regression problem in Figure 5, exact (and sketched) Newton is comparable to, and in many cases better than, SGD (e.g., lower MSE and objective gap). Thus, Figure 4 suggests neither that SGD is generally better than Newton nor that Newton methods are not worth studying. It suggests only that SGD suffices for simple linear regression with identity covariate covariance, while Newton can be better for more complex problems (Figure 5), in terms of estimation convergence. It says nothing about inference and variability of the iterates.

  2. The improvement of Newton methods lies in inference, which Figure 4 does not show.

    As explained in point (c) of our response to (W1&Q3), the advantage of Newton methods lies in the inference step. In particular, SGD-based confidence intervals exhibit substantial undercoverage, as demonstrated in several studies [1, 3, 4], while Newton-type intervals stay close to the nominal level in the same settings. This distinction is not visible in Figure 4, which does not assess inference at all. The new inference comparison in Appendix E.6 reports the coverage of SGD-based intervals alongside the near-nominal coverage of Newton-type intervals. These results illustrate the practical benefits that motivate the existing literature [2–9] applying Newton methods for online inference.

(Q2) Indeed. Done for revision.

References

[1] Zhu et al. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 2021.

[2] Na and Mahoney. Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming. Journal of Machine Learning Research, 2025.

[3] Kuang et al. Online covariance matrix estimation in sketched Newton methods. Information and Inference: A Journal of the IMA, 2026.

[4] Wang et al. Inference of online Newton methods with Nesterov's accelerated sketching. International Conference on Machine Learning, 2026.

[5] Du et al. Inference for Newton methods with accelerated sketch-and-project via random scaling. arXiv preprint arXiv:2609.12421, 2026.

[6] Leluc and Portier. Asymptotic analysis of conditioned stochastic gradient descent. Transactions on Machine Learning Research, 2023.

[7] Bercu et al. An efficient stochastic Newton algorithm for parameter estimation in logistic regressions. SIAM Journal on Control and Optimization, 2020.

[8] Boyer and Godichon-Baggioni. On the asymptotic rate of convergence of stochastic Newton algorithms and their weighted averaged versions. Computational Optimization and Applications, 2023.

[9] Godichon-Baggioni et al. Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms. arXiv preprint arXiv:2401.10923, 2024.

[10] Wei et al. Refining covariance matrix estimation in stochastic gradient descent through bias reduction. International Conference on Artificial Intelligence and Statistics, 2026.

[11] Schmidt. Lecture slides: https://www.cs.ubc.ca/~schmidtm/Courses/540-W19/L11.pdf

Comments on the paper

1 comment

We sincerely thank all reviewers for their careful reading and constructive comments. We have addressed all the comments and revised the manuscript accordingly, with the changes highlighted in red. We believe that these revisions have substantially strengthened the paper. In particular, the revised manuscript fully addresses the main concerns of Reviewer 8ZLh regarding the assumption. We hope that Reviewer 8ZLh will reconsider their assessment in light of these revisions, to align with the evaluations of the other two reviewers.

We summarize the major revisions below, with further details provided in the individual responses.

  1. Relaxed assumptions (Reviewer 8ZLh, W2/W3). Assumption 3.1 no longer requires uniform spectral bounds on individual sample Hessians: it now requires strong convexity and smoothness only of the population objective, and spectral bounds only on the preconditioning matrix BtB_t. The assumption is directly copied from SGD and preconditioned SGD, and is strictly weaker than those in the existing sketched Newton literature. All results are re-established under it.

  2. New experiments (Reviewers WgvF, W1/Q3; 8ZLh, W1/Q2; dyQg, Q3). SGD is included in the estimation-error comparisons (Appendix E.5, Figures 4–5). A new section on online inference (Appendix E.6, Tables 5–6) compares ASGD, exact Newton, and sketched Newton with and without gradient averaging at d=40d=40, reporting the running times and FLOPs together with the coverage rates and lengths of the confidence intervals.

  3. Motivation and the meaning of “free lunch” (Reviewers WgvF, W1/Q3; 8ZLh, W1/W4). Section 1 now explains the motivation for studying second-order methods for online inference, despite the asymptotic optimality of ASGD. We have also clarified the meaning of “free lunch” in the abstract, Section 1, and the Conclusion. Specifically, a simple gradient averaging step reduces the limiting covariance of the last sketched Newton iterate, and further enables the averaged sketched Newton iterate to attain the optimal limiting covariance Ω\Omega of exact Newton. This improvement in statistical efficiency comes for free in the sense that, compared with existing sketched Newton methods, it requires no additional assumptions or oracle calls and incurs only an O(d)O(d) extra cost per iteration.

  4. Computational cost (Reviewers dyQg, Q2; 8ZLh, W3). Section 3 now clarifies that the conditions on τ\tau require only a fixed number of sketching steps, which does not grow with the iteration, while Section 4 and Appendix A provide an analysis of the per-iteration cost.

  5. Presentation (Reviewers dyQg, Q1; 8ZLh, Q1; WgvF, W2/Q1 and Q2). We have added a summary of the main theoretical results and their takeaways in Section 1, a discussion of stepsize choices with a recommendation for practitioners in Appendix A and the experimental stepsizes in Appendix E.1, and an explanation of Figures 4–5 in Appendix E.5.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.