mlsanityData to 14 Oct 2026

Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation

arXiv 2301.03125 ↗First posted 9 Jan 2023stat.ML cs.LG math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

The stochastic proximal point (SPP) methods have gained recent attention for stochastic optimization, with strong convergence guarantees and superior robustness to the classic stochastic gradient descent (SGD) methods showcased at little to no cost of computational overhead added. In this article, we study a minibatch variant of SPP, namely M-SPP, for solving convex composite risk minimization problems. The core contribution is a set of novel excess risk bounds of M-SPP derived through the lens of algorithmic stability theory. Particularly under smoothness and quadratic growth conditions, we show that M-SPP with minibatch-size n and iteration count T enjoys an in-expectation fast rate of convergence consisting of an Oleft(frac1T2right) bias decaying term and an Oleft(frac1nTright) variance decaying term. In the small-n-large-T setting, this result substantially improves the best known results of SPP-type approaches by revealing the impact of noise level of model on convergence rate. In the complementary small-T-large-n regime, we provide a two-phase extension of M-SPP to achieve comparable convergence rates. Moreover, we derive a near-tight high probability (over the randomness of data) bound on the parameter estimation error of a sampling-without-replacement variant of M-SPP. Numerical evidences are provided to support our theoretical predictions when substantialized to Lasso and logistic regression models.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 35 of its 80 references that are in the map. First posted on arXiv 9 Jan 2023.

Builds on

35 of 80 references.

References · 35

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  2. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 674
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  5. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  7. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  8. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  9. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
  10. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  11. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  12. 2019Sharper bounds for uniformly stable algorithmscited by 93
23 more
  1. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  2. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  3. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  4. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  5. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 60
  6. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  7. 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
  8. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  9. 2016Efficient Distributed Learning with Sparsitycited by 38
  10. 2019The importance of better models in stochastic optimizationcited by 32
  11. 2014Communication-Efficient Distributed Dual Coordinate Ascentcited by 31
  12. 2014Competing with the Empirical Risk Minimizer in a Single Passcited by 20
  13. 2019On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyondcited by 18
  14. 2017Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Boundscited by 15
  15. 2018A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methodscited by 14
  16. 2021Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimizationcited by 14
  17. 2017Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Proxcited by 12
  18. 2015Towards stability and optimality in stochastic gradient descentcited by 11
  19. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  20. 2021Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimizationcited by 10
  21. 2019A Generic Acceleration Framework for Stochastic Composite Optimizationcited by 9
  22. 2022Stability and Risk Bounds of Iterative Hard Thresholdingcited by 7
  23. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 2.

4 papers.

  1. 2024Uniformly Stable Algorithms for Adversarial Training and Beyondcited by 2
  2. 2024Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learningcited by 2
  3. 2026Large-scale Score-based Variational Posterior Inference for Bayesian Deep Neural Networkscited by 1
  4. 2026Learning Theory of the SVRG: Generalization and Convergence Analysiscited by 0