betaFeedback

WorksMathematics

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

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 O(d3)O(d^3) to O(d2)O(d^2), 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.

Introduction

We consider the stochastic optimization problem:

min⁡x∈Rdf(x)=Eξ∼P[F(x;ξ)],(1)\min_{x\in\mathbb{R}^{d}} f(x) = \mathbb{E}_{\xi\sim\mathcal{P}}[F(x;\xi)], \tag*{(1)}

where f:Rd→Rf:\mathbb{R}^{d}\to\mathbb{R} is a stochastic objective and F(⋅;ξ):Rd→RF(\cdot;\xi):\mathbb{R}^{d}\to\mathbb{R} is its realization with ξ∼P\xi\sim\mathcal{P}. Problem (1) is one of the most fundamental building blocks for many decision-making tasks in statistics and machine learning, such as online recommendation [22], precision medicine [19], and portfolio allocation [11]. In these applications, (1) is interpreted as a parameter estimation problem, where xx denotes the model parameter, ξ\xi denotes an observation, and the minimizer x⋆=arg min⁡x∈Rdf(x)x^\star=\operatorname*{arg\,min}_{x\in\mathbb{R}^{d}}f(x) denotes the true model parameter.

The ubiquity of streaming data has made online methods increasingly attractive, where only one single sample is processed at each step. Stochastic gradient descent (SGD) and its many acceleration variates are prevalent examples [29], with extensively studied convergence properties [27, 23]. Although first-order methods enjoy inexpensive updates, their performance can be sensitive to ill-conditioning and heterogeneous gradient noise. Moreover, online inference with SGD still requires updating a proper covariance matrix, incurring O(d2)O(d^2) time and memory complexity. The resulting confidence intervals can also exhibit substantial undercoverage even in relatively low-dimensional regression problems [36]. Online Newton methods address these issues by preconditioning each stochastic gradient with curvature information [3]:

xt+1=xt+φtΔxt,withBtΔxt=−∇F(xt;ξt),(2)x_{t+1}=x_t+\varphi_t\Delta x_t,\qquad\text{with}\qquad B_t\Delta x_t=-\nabla F(x_t;\xi_t), \tag*{(2)}

*School of Industrial and Systems Engineering, Georgia Institute of Technology.

†School of Mathematics, Georgia Institute of Technology. where BtB_t approximates the Hessian ∇2f(xt)\nabla^2 f(x_t).

Beyond convergence, reliable decision-making also requires uncertainty quantification for the resulting estimator. A standard approach for SGD is Polyak–Ruppert averaging, which averages the iterates to yield an asymptotically normal estimator [30, 28]. Building on prior works, the asymptotic properties of the last and averaged iterates of online Newton methods have also been established in unconstrained and constrained settings [21, 12]. In particular, under suitable regularity conditions and Bt→B⋆=∇2f(x⋆)B_t \to B^\star= \nabla^2 f(x^\star), we have

1φt(xt−x⋆)→dN(0,ι⋅Ω)andt(xˉt−x⋆)→dN(0,Ω),(3)\frac{1}{\sqrt{\varphi_t}}(x_t-x^\star) \xrightarrow{d} \mathcal{N}(0,\iota\cdot\Omega) \qquad\text{and} \qquad\sqrt{t}(\bar{x}_t-x^\star) \xrightarrow{d} \mathcal{N}(0,\Omega), \tag*{(3)}

where xˉt:=1t∑i=0t−1xi\bar{x}_t := \frac{1}{t}\sum_{i=0}^{t-1}x_i, Ω=(B⋆)−1Cov⁡(∇F(x⋆;ξ))(B⋆)−1\Omega=(B^\star)^{-1}\operatorname{Cov}(\nabla F(x^\star;\xi))(B^\star)^{-1} (see (9)), and ι=Cφ/(2Cφ−1)\iota=C_\varphi/(2C_\varphi-1) if φt=Cφ/(t+1)φ\varphi_t=C_\varphi/(t+1)^\varphi with φ=1\varphi=1 while ι=0.5\iota=0.5 if φ∈(0.5,1)\varphi\in(0.5,1). The limiting covariance Ω\Omega is further known to be asymptotic minimax optimal in Hájek and Le Cam sense [9, 5]. Though averaged SGD also attains Ω\Omega [30, 28], the last iterate of SGD is not asymptotically optimal and its limiting covariance solves a Lyapunov equation involving the Hessian. For online Newton, preconditioning gives the scalar form ιΩ\iota\Omega in (3). In particular, when φt=1/(t+1)\varphi_t=1/(t+1), the last iterate attains Ω\Omega, so inference can be based directly on it without iterate averaging [1, 21]. Appendix A compares the rate orders and last-iterate stepsize conditions of SGD and online Newton. Online inference also requires covariance estimation. For averaged SGD, the batch-means estimator studied in Zhu et al. [36] has rate O(1/tφt)O(1/\sqrt{t\varphi_t}). For online Newton methods, the weighted sample covariance estimators studied in Kuang et al. [20]; ); Wang et al. [34] achieve O(1/tφt)O(1/\sqrt{t\varphi_t}), a quadratic improvement over the batch-means rate. Despite promising statistical properties, a key computational bottleneck of online Newton methods is solving the Newton system in (2), which requires O(d3)O(d^3) flops at each step.

Online sketched Newton methods approximately solve the Newton system using an inner randomized iterative solver that performs a fixed number of sketch-and-project updates, reducing the per-step cost to O(d2)O(d^2) [24]. A recent Nesterov-accelerated variant further improves the decay rate of the solver’s approximation error while preserving the same order of computational cost [6]. Despite these computational gains, the sketching solver degrades the favorable statistical efficiency of the outer Newton iterates. In particular, Wang et al. [34] and Du et al. [8] established asymptotic normality analogous to (3) for the last and averaged sketched Newton iterates, with limiting covariances Σg,asℓ\Sigma^\ell_{g,\mathrm{as}} and Σg,asa\Sigma^a_{g,\mathrm{as}}, respectively. Their results reveal an interesting computational–statistical trade-off: randomized sketching avoids the exact Newton solve but introduces an additional covariance term that inflates the limiting covariance. Specifically, the last and averaged iterates have limiting covariances satisfying Ω⪯Σg,asℓ⪯Σg,asa\Omega\preceq\Sigma^\ell_{g,\mathrm{as}} \preceq\Sigma^a_{g,\mathrm{as}}. Therefore, we ask:

Can sketching solver reduce the cost of online Newton without inflating the limiting covariance?

In this paper, we provide an affirmative answer to this question by replacing the single-sample gradient gt:=∇F(xt;ξt)g_t := \nabla F(x_t;\xi_t) with its moving average mt=(1−ηt)mt−1+ηtgtm_t=(1-\eta_t)m_{t-1}+\eta_tg_t. Gradient averaging has long been used to smooth stochastic estimates (Ruzaykin & Sly, 1983), and recent work studies its interaction with Polyak–Ruppert averaging in first-order methods [33]. Here, however, we use gradient averaging for quite a different purpose: to weaken the interaction between sampling noise and the randomness introduced by the sketching solver in Newton methods. We establish convergence and asymptotic normality of both the last and averaged sketched Newton iterates with gradient averaging. In particular, under weaker assumptions than Wang et al. [34]; Du et al. [8], we show that (i) the last-iterate covariance satisfies Σm,asℓ⪯Σg,asℓ\Sigma^\ell_{m,\mathrm{as}}\preceq\Sigma^\ell_{g,\mathrm{as}}, where Σm,asℓ\Sigma^\ell_{m,\mathrm{as}} and Σg,asℓ\Sigma^\ell_{g,\mathrm{as}} denote the last-iterate covariances of accelerated sketched Newton using moving-average and single-sample gradients, respectively; and (ii) the averaged-iterate covariance satisfies Σm,asa=Ω\Sigma^a_{m,\mathrm{as}}=\Omega. Thus, gradient averaging mitigates the computational–statistical trade-off for the last iterate, and even eliminates it for the averaged iterate. In this sense, gradient averaging provides a “free lunch” compared to existing sketched Newton methods: our covariance gains require only an O(d)O(d) vector update per iteration, without additional gradient, Hessian, or sketching evaluations, and hold under weaker assumptions.

The analysis requires addressing the following challenges introduced by gradient averaging.

(a) mtm_t averages stochastic gradients evaluated at different iterates and is therefore not conditionally unbiased for ∇f(xt)\nabla f(x_t), unlike gtg_t, whose centered noise forms crucial martingale difference structure underlying central limit theorem arguments. More precisely, the tracking error et:=mt−∇f(xt)e_t:=m_t-\nabla f(x_t) contains inherited error from earlier steps, gradient drift, and martingale noise, and must be analyzed jointly with the optimization error Δt:=xt−x⋆\Delta_t := x_t-x^\star. As such, we derive coupled recursions for (et,Δt)(e_t,\Delta_t) and control their evolution on the two timescales governed by ηt\eta_t and φt\varphi_t.

(b) To characterize how gradient averaging changes the leading sketching noise, we must separate sampling noise, sketching fluctuations, and variations in the Hessian approximation and sketching parameters across iterations. Since the resulting perturbation terms are sufficiently small only when (Δt,Bt−B⋆,et)(\Delta_t,B_t-B^\star,e_t) remain in a local neighborhood of zero, we introduce a stopping time at the first exit from this neighborhood and localize the convergence rate analysis (see (D.25) in the proof of Lemma 4.2). The effect of the localization is then removed by our almost-sure convergence guarantee.

(c) To isolate ∇F(x⋆;ξt)\nabla F(x^\star;\xi_t) as the leading stochastic noise in the asymptotic linear representations established in Theorem 4.3, we rewrite the outer Newton recursion in terms of the stochastic gradient gtg_t. This introduces weighted differences mt−mt−1m_t-m_{t-1} that do not appear in the analysis of vanilla online Newton methods. We use summation by parts to transfer the differences from the moving-average gradients to their weights, and then bound the resulting boundary and weighted-sum terms to show that they are asymptotically negligible under both the last- and averaged-iterate normalizations.

Our main contributions are summarized as follows.

(a) We establish global almost-sure convergence of online sketched Newton with gradient averaging. Under standard two-timescale conditions, we show that the iterate xtx_t converges to x⋆x^\star and the moving-average gradient mtm_t tracks ∇f(xt)\nabla f(x_t) almost surely (Theorem 3.5). Thus, using gradients evaluated at earlier iterates does not prevent the outer iterates from converging. Moreover, gradient averaging requires no additional oracle evaluations and preserves the inner-solver contraction bound.

(b) We establish last-iterate asymptotic normality, 1/φt⋅(xt−x⋆)⟶dN(0,Σm,asℓ)1/\sqrt{\varphi_t}\cdot(x_t-x^\star)\mathrel{\mathop{\longrightarrow}^{d}} \mathcal{N}(0,\Sigma^\ell_{m,\mathrm{as}}) (Theorem 4.5), and prove Σm,asℓ⪯Σg,asℓ\Sigma^\ell_{m,\mathrm{as}}\preceq\Sigma^\ell_{g,\mathrm{as}} (Prop. 4.6). Thus, gradient averaging yields no larger asymptotic variance in any direction than vanilla online sketched Newton. This covariance reduction (same for (c) below) uses the same inner sketching solver and the same number of sketching steps as existing methods using single-sample gradients. Our local convergence rates and asymptotic linear representations reveal the mechanism behind this variance reduction: the random matrix I−K~i⋆I-\widetilde{K}_{i}^\star, which captures the limiting effect of the inner solver on gradient noise, is replaced by its mean I−K⋆I-K^\star (Theorem 4.3). Consequently, sketching enters the limiting covariance only through its mean effect.

(c) We further establish averaged-iterate asymptotic normality, t (xˉt−x⋆)⟶dN(0,Σm,asa)\sqrt{t}\,(\bar{x}_t-x^\star)\mathrel{\mathop{\longrightarrow}^{d}}\mathcal{N}(0,\Sigma^a_{m,\mathrm{as}}), with Σm,asa=Ω⪯Σg,asa\Sigma^a_{m,\mathrm{as}}=\Omega\preceq\Sigma^a_{g,\mathrm{as}} (Theorem 4.7). Polyak–Ruppert averaging eliminates the remaining effect of sketching and recovers the covariance Ω\Omega of exact online Newton method, which is asymptotically minimax optimal ([9]). Therefore, with a fixed number of sketching steps per iteration, our method gains computational efficiency without sacrificing statistical efficiency: its averaged iterate has the same limiting covariance as if each Newton system were solved exactly.

References

  1. [1]Bernard Bercu, Antoine Godichon, and Bruno Portier. An efficient stochastic Newton algorithm for parameter estimation in logistic regressions. SIAM Journal on Control and Optimization, 58(1): 348–367, jan 2020.arxiv.org/abs/1904.07908
  2. [2]Rajendra Bhatia. Matrix Analysis. Springer New York, 1997. ISBN 9781461206538.
  3. [3]Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, jan 2018.arxiv.org/abs/1606.04838
  4. [4]Xi Chen, Jason D. Lee, Xin T. Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics, 48(1), February 2020.arxiv.org/abs/1610.08637
  5. [5]Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang. Asymptotic normality and optimality in non-smooth stochastic approximation. The Annals of Statistics, 52(4), August 2024.
  6. [6]Michal Dereziński, Daniel LeJeune, Deanna Needell, and Elizaveta Rebrova. Fine-grained analysis and faster algorithms for iteratively solving linear systems. Journal of Machine Learning Research, 26(144):1–49, 2025.arxiv.org/abs/2405.05818
  7. [7]Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. The Annals of Statistics, 48(3):1348–1382, 2020. doi: 10.1214/19-AOS1850.DOI
  8. [8]Xinchen Du, Elizaveta Rebrova, Michał Dereziński, and Sen Na. Inference for newton methods with accelerated sketch-and-project via random scaling. arXiv preprint arXiv:2609.12421, 2026.arxiv.org/abs/2609.12421
  9. [9]John C. Duchi and Feng Ruan. Asymptotic optimality in stochastic optimization. The Annals of Statistics, 49(1), February 2021.arxiv.org/abs/1612.05612
  10. [10]Marie Duflo. Random iterative models, volume 34. Springer Science & Business Media, Berlin New York, 2013. ISBN 9783540571001.
  11. [11]Jianqing Fan, Jingjin Zhang, and Ke Yu. Vast portfolio selection with gross-exposure constraints. Journal of the American Statistical Association, 107(498):592–606, jun 2012.pubmed.ncbi.nlm.nih.gov/23293404
  12. [12]Yihang Gao, Michael K Ng, Michael W Mahoney, and Sen Na. Online inference of constrained optimization: Primal-dual optimality and sequential quadratic programming. arXiv preprint arXiv:2512.08948, 2025.arxiv.org/abs/2512.08948
  13. [13]Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, January 2013. ISSN 1095-7189.arxiv.org/abs/1309.5549
  14. [14]Robert Gower, Filip Hanzely, Peter Richtárik, and Sebastian U Stich. Accelerated stochastic matrix inversion: general theory and speeding up bfgs rules for faster second-order optimization. Advances in Neural Information Processing Systems, 31, 2018.arxiv.org/abs/1802.04079
  15. [15]Robert M. Gower and Peter Richtárik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 36(4):1660–1690, January 2015.DOI
  16. [16]Peter Hall and Christopher C Heyde. Martingale limit theory and its application. Academic press, 2014.
  17. [17]Dongyan Huo, Yudong Chen, and Qiaomin Xie. Bias and extrapolation in markovian linear stochastic approximation with constant step sizes. Mathematics of Operations Research, 2026. doi: 10.1287/moor.2024.0471.
  18. [18]Liwei Jiang and Ashwin Pananjady. Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?, 2026.arxiv.org/abs/2603.25657
  19. [19]Michael R Kosorok and Eric B Laber. Precision medicine. Annual Review of Statistics and Its Application, 6(1):263–286, 2019.DOI
  20. [20]Wei Kuang, Mihai Anitescu, and Sen Na. Online covariance matrix estimation in sketched newton methods. Information and Inference: A Journal of the IMA, 15(2):iaag012, 2026. doi: 10.1093/imaiai/iaag012.
  21. [21]Rémi Leluc and François Portier. Asymptotic analysis of conditioned stochastic gradient descent. Transactions on Machine Learning Research, 2023.
  22. [22]Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pp. 661–670, 2010.DOI
  23. [23]Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in Neural Information Processing Systems, 24, 2011.
  24. [24]Sen Na and Michael Mahoney. Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming. Journal of Machine Learning Research, 26(33):1–75, 2025.
  25. [25]Sen Na, Michał Dereziński, and Michael W. Mahoney. Hessian averaging in stochastic Newton methods achieves superlinear convergence. Mathematical Programming, dec 2022.
  26. [26]Yurii Nesterov. Lectures on Convex Optimization. Springer International Publishing, 2018. ISBN 9783319915784.DOI
  27. [27]Mariane Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms. Stochastic Processes and Their Applications, 78(2):217–244, 1998.
  28. [28]B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, July 1992.DOI
  29. [29]Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400–407, September 1951.
  30. [30]David Ruppert. Efficient estimations from a slowly convergent robbins-monro process. Technical report, 1988.
  31. [32]Thomas Strohmer and Roman Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15(2):262–278, April 2008.arxiv.org/abs/math/0702226
  32. [33]Ke Jie Tang, Weidong Liu, Yichen Zhang, and Xi Chen. Acceleration of stochastic gradient descent with momentum by averaging: finite-sample rates and asymptotic normality. arXiv preprint arXiv:2305.17665, 2023.arxiv.org/abs/2305.17665
  33. [34]Haoxuan Wang, Xinchen Du, and Sen Na. Inference of online newton methods with nesterov’s accelerated sketching. International Conference on Machine Learning, 2026.arxiv.org/abs/2604.23436
  34. [36]Wanrong Zhu, Xi Chen, and Wei Biao Wu. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 118(541):393–404, July 2021.

Paper details

vlnc:W_54qcrfy6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

generative AI tools

View statement
Looking for related papers…
Contents