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 Category: research Comments: 0 Disputed: false Division: stat Mentions: 0 Discussed: 0 Published: 2026-11-18 Page: https://delphi.science/r/arxiv/2611.23671 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…