AI & ML
A Free Lunch: Gradient Averaging Achieves Optimal Statistical Efficiency in Newton Sketch
arXiv stat.ML0 views
arXiv:2611.23671v1 Announce Type: new 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(d^3)$ to $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.
Source:https://arxiv.org/abs/2611.23671PreviousBounded-Order Non-Identifiability in Latent Structure Block Models: The Fiber in Closed FormNextImproved Leverage Score Sampling for Constrained Active Linear Regression
Related posts
![Quadruped Robot Software — Ch.12: Quadruped Case Studies [KR]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fawosw4u7jitr9h27f7c5.png)
Quadruped Robot Software — Ch.12: Quadruped Case Studies [KR]
0dev.to
How Python Is Used in Artificial Intelligence in 2026: Applications, Benefits and Career Opportunities
0dev.to

What Happens in Those Few Seconds Between Pressing the Power Button and Seeing the Windows Login Screen?
0dev.to
Getting cited by ChatGPT and Claude: what the research supports, and a free audit tool
0dev.to
Why Photoshot keeps the original color when you edit in black and white
0dev.to
ISTQB CTFL in 2027: is it still worth it? What changes, what does not
0dev.to