Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
Abstract
We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and-project solver (GAS), thereby mitigating the computational bottleneck of classical second-order methods. The GAS solver improves upon vanilla, unaccelerated sketch-and-project solvers by achieving accelerated convergence through Nesterov momentum updates, and accommodates a flexible projection metric whose proper choice further reduces computational cost. Building on this design, we establish asymptotic normality of the averaged sketched Newton iterates and characterize their limiting covariance matrix. The resulting covariance recovers that of the unaccelerated sketched Newton method under a specific choice of acceleration parameters, converges more rapidly (in the number of sketching steps) to the minimax-optimal covariance in general, and is smaller than that of the last iterate produced by the accelerated method. Finally, we strengthen these results by establishing a functional central limit theorem for the Newton iterates, which allows us to bypass explicit covariance estimation and develop an online inference procedure based on random scaling. Specifically, we construct a pivotal test statistic by appropriately rescaling the averaged iterates, so that its limiting distribution is free of any unknown parameters, enabling asymptotically valid online inference. Numerical experiments demonstrate superior performance of the proposed inference procedure.
Related
- Riemannian Newton Methods with Statistical Inference
- Grad-div stabilized finite element Picard-Newton iterative methods for the Navier-Stokes equations
- Global 𝒪(k−2) Convergence of Multilevel Gradient-Regularized Newton Methods
- Simultaneous Global Convergence Failure of Newton's and Halley's Methods in Degree Four
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
BibTeX
@misc{du2026inference,
title = {{Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling}},
author = {Xinchen Du and Elizaveta Rebrova and Michał Dereziński and Sen Na},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12421},
eprint = {2609.12421},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12421},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
AU - Xinchen Du
AU - Elizaveta Rebrova
AU - Michał Dereziński
AU - Sen Na
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12421
UR - https://arxiv.org/abs/2609.12421
AB - We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and-project solver (GAS), thereby mitigating the computational bottleneck of classical second-order methods. The GAS solver improves upon vanilla, unaccelerated sketch-and-project solvers by achieving accelerated convergence through Nesterov momentum updates, and accommodates a flexible projection metric whose proper choice further reduces computational cost. Building on this design, we establish asymptotic normality of the averaged sketched Newton iterates and characterize their limiting covariance matrix. The resulting covariance recovers that of the unaccelerated sketched Newton method under a specific choice of acceleration parameters, converges more rapidly (in the number of sketching steps) to the minimax-optimal covariance in general, and is smaller than that of the last iterate produced by the accelerated method. Finally, we strengthen these results by establishing a functional central limit theorem for the Newton iterates, which allows us to bypass explicit covariance estimation and develop an online inference procedure based on random scaling. Specifically, we construct a pivotal test statistic by appropriately rescaling the averaged iterates, so that its limiting distribution is free of any unknown parameters, enabling asymptotically valid online inference. Numerical experiments demonstrate superior performance of the proposed inference procedure.
ER -