mlsanityData to 7 Oct 2026

On-Average Stability of Multipass Preconditioned SGD and Effective Dimension

arXiv 2603.11989 ↗First posted 12 Mar 2026cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study trade-offs between the population risk curvature, geometry of the noise, and preconditioning on the generalisation ability of the multipass Preconditioned Stochastic Gradient Descent (PSGD). Many practical optimisation heuristics implicitly navigate this trade-off in different ways -- for instance, some aim to whiten gradient noise, while others aim to align updates with expected loss curvature. When the geometry of the population risk curvature and the geometry of the gradient noise do not match, an aggressive choice that improves one aspect can amplify instability along the other, leading to suboptimal statistical behavior. In this paper we employ on-average algorithmic stability to connect generalisation of PSGD to the effective dimension that depends on these sources of curvature. While existing techniques for on-average stability of SGD are limited to a single pass, as first contribution we develop a new on-average stability analysis for multipass SGD that handles the correlations induced by data reuse. This allows us to derive excess risk bounds that depend on the effective dimension. In particular, we show that an improperly chosen preconditioner can yield suboptimal effective dimension dependence in both optimisation and generalisation. Finally, we complement our upper bounds with matching, instance-dependent lower bounds.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 42 references that are in the map. First posted on arXiv 12 Mar 2026.

Builds on

29 of 42 references.

References · 29

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  4. 2015Optimizing Neural Networks with Kronecker-factored Approximate Curvaturecited by 776
  5. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  6. 2017Exploring Generalization in Deep Learningcited by 595
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  8. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  9. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  10. 2014New insights and perspectives on the natural gradient methodcited by 435
  11. 2020ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learningcited by 201
  12. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
17 more
  1. 2019Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Modelcited by 116
  2. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  3. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  4. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  5. 2019Sharper bounds for uniformly stable algorithmscited by 91
  6. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  7. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  8. 2019On the interplay between noise and curvature and its effect on optimization and generalizationcited by 44
  9. 2018Iterate averaging as regularization for stochastic gradient descentcited by 27
  10. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  11. 2019Distribution-Dependent Analysis of Gibbs-ERM Principlecited by 17
  12. 2024High-probability minimax lower boundscited by 11
  13. 2023PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimatescited by 10
  14. 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
  15. 2016Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimizationcited by 6
  16. 2023Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimizationcited by 6
  17. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4

Built on by

Not cited yet.