{"id":"arxiv/2611.23671","url":"https://arxiv.org/abs/2611.23671","tags":["stat.ML","cs.LG","math.OC","stat.CO"],"score":0,"title":"A Free Lunch: Gradient Averaging Achieves Optimal Statistical Efficiency in Newton Sketch","domain":"stat.ML","source":"arxiv","authors":["Haoxuan Wang","Jianliang Ye","Sen Na"],"reviews":0,"subject":"stat.ML","summary":"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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}