mlsanityData to 14 Oct 2026

An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning

arXiv 2106.02720 ↗First posted 4 Jun 2021cs.LG math.OCcited by 10

Not on the map. Why?

Abstract (arXiv)

We present and analyze an algorithm for optimizing smooth and convex or strongly convex objectives using minibatch stochastic gradient estimates. The algorithm is optimal with respect to its dependence on both the minibatch size and minimum expected loss simultaneously. This improves over the optimal method of Lan (2012), which is insensitive to the minimum expected loss; over the optimistic acceleration of Cotter et al. (2011), which has suboptimal dependence on the minibatch size; and over the algorithm of Liu and Belkin (2018), which is limited to least squares problems and is also similarly suboptimal with respect to the minibatch size. Applied to interpolation learning, the improvement over Cotter et al. and Liu and Belkin translates to a linear, rather than square-root, parallelization speedup.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 25 of its 49 references that are in the map. First posted on arXiv 4 Jun 2021.

Builds on

25 of 49 references.

References · 25

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  4. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  6. 2018On Lazy Training in Differentiable Programmingcited by 675
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  8. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  9. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  10. 2019SGD: General Analysis and Improved Ratescited by 207
  11. 2020Benign overfitting in ridge regressioncited by 153
  12. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
13 more
  1. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  2. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  3. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  4. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
  5. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 60
  6. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  7. 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 43
  8. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  9. 2016Optimal Black-Box Reductions Between Optimization Objectivescited by 21
  10. 2017Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Boundscited by 15
  11. 2018A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methodscited by 14
  12. 2019Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Ratecited by 14
  13. 2018Accelerating SGD with momentum for over-parameterized learningcited by 8

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 5; 2024: 2; 2025: 1.

10 papers.

  1. 2022Faster federated optimization under second-order similaritycited by 18
  2. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  3. 2023Accelerated stochastic approximation with state-dependent noisecited by 11
  4. 2023Federated Online and Bandit Convex Optimizationcited by 7
  5. 2025KerZOO: Kernel Function Informed Zeroth-Order Optimization for Accurate and Accelerated LLM Fine-Tuningcited by 5
  6. 2023Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviationcited by 4
  7. 2022Private optimization in the interpolation regime: faster rates and hardness resultscited by 3
  8. 2023Exploring Local Norms in Exp-concave Statistical Learningcited by 2
  9. 2024Accelerated zero-order SGD under high-order smoothness and overparameterized regimecited by 2
  10. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1