- 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
-
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.
-
Could the authors provide a more detailed computational complexity analysis? In particular, Theorems 3.5 and 4.3 impose conditions on . Do these conditions affect the claimed reduction in per-step computational complexity?
-
Could the authors report the actual runtime of each method in the experiments to better demonstrate the computational benefits?
5 comments
(a) The conditions require only a fixed , independent of the iteration. Theorems 3.5 and 4.3 take a fixed satisfying for all . Both sides of this inequality are controlled uniformly in : on the left-hand side, Assumption 3.4 ensures that ; on the right-hand side, Assumption 3.1 ensures that almost surely. Since the left-hand side decays geometrically in , the number of sketching steps needed for the inequality to hold is bounded uniformly in 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 . 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 and in (2.3), which satisfy [2]. In each sketching step, the expected squared error of the approximate Newton direction contracts by the factor without acceleration [1], and by the factor 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 , the dimension , and the condition number of the Newton system [1–3]. In general (e.g., randomized coordinate sketching), one has and . Hence, Nesterov acceleration improves the contraction factor from to and reduces the number of sketching steps needed to reach a fixed accuracy from to . That is, the dependence on the condition number improves from to [2, 3]. Furthermore, the conditions on in Theorems 3.5 and 4.3 require only a fixed accuracy: they enter our analysis solely through the bound , where is the expected coefficient matrix of the sketching approximation error (Section 4.1). Thus, these conditions are met by of order , up to a logarithmic factor, where is bounded uniformly in ; see (a). We also note that these are sufficient, worst-case conditions, which are conservative in practice. In our experiments, 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 (we use in our experiments), each sketching step costs only , with or without acceleration. Combining this with the number of sketching steps in (b), we see that the sketching solver costs per iteration, up to a logarithmic factor, compared with for an exact Newton solve. The constant in the 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 per iteration; the spectral clipping of can be refreshed once every iterations, leading to an amortized cost (Section 4); and gradient averaging adds only an vector update, with no additional gradient, Hessian, or sketching evaluations. Hence, the method retains the claimed 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 cost per iteration and is naturally the fastest. However, when inference is included, its per-iteration cost increases to 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 in linear and logistic regression. The results show that sketched Newton is substantially faster than exact Newton: across the six settings, it uses about – fewer FLOPs and reduces running time by – after 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 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 -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 , corresponding to a median increase of only .
(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 (– at a nominal level of with [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 empirical-coverage target, all exact and sketched Newton methods reach the target within updates, with mean running times of – 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.
(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 τ 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.
Last iterate: reduced covariance (Theorem 4.5 and Proposition 4.6). The last iterate is asymptotically normal with the limiting covariance Σm,asl no larger than the limiting covariance Σg,asl of the sketched Newton without gradient averaging, i.e., Σm,asl⪯Σg,asl. In other words, gradient averaging reduces the uncertainty induced by sketching, although Σm,asl still depends on the sketching solver.
Averaged iterate: optimal covariance (Theorem 4.7). The averaged iterate is asymptotically normal with limiting covariance Σm,asa=Ω, 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⋆ of the vanilla sketched Newton method is replaced by its mean I−K⋆. 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 τ 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 t. 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 τ.
In particular, we would like to clarify the following points.