Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

Summary

The paper introduces GASN, an online Newton method for strongly convex stochastic optimization whose Newton direction is approximated at each step by the generalized accelerated sketch-and-project (GAS) solver, allowing a flexible projection metric in addition to Nesterov-type acceleration. The authors prove almost-sure and L2 convergence, asymptotic normality of the averaged iterate with limiting covariance Ξ*_gasn,ave, and a functional central limit theorem. They characterize the computational-statistical trade-off in three regimes: with exact linear solves the covariance equals the minimax-optimal Ω*; the gap under sketching decays exponentially in the number of sketching steps τ as O((1−√(μ*/ν*))^τ), faster than the O((1−μ*)^τ) rate of the unaccelerated USN method; and averaging improves over the last ASN iterate (Ξ*_asn,ave ⪯ Ξ*_asn,last). Building on the FCLT, they construct a self-normalized, pivotal test statistic via a random-scaling matrix Vt whose limiting distribution is parameter-free, enabling asymptotically valid online confidence intervals without covariance estimation. Experiments on synthetic linear and logistic regression (identity, Toeplitz and equicorrelated covariances, τ ∈ {5,10}) show near-nominal coverage and substantially narrower intervals than the batch-free baseline of Wang et al. (2026). Limitations include strong moment/convexity assumptions, d×d state (Bt and Vt) maintenance, and — in the text provided — experiments restricted to synthetic data.