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

arXiv: https://arxiv.org/abs/2301.03125 · HTML: https://mlsanity.com/paper/2301.03125/

## 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 (most cited first, 30 of 35)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Efficient Distributed Learning with Sparsity](https://mlsanity.com/paper/1605.07991/) (2016)
- [The importance of better models in stochastic optimization](https://mlsanity.com/paper/1903.08619/) (2019)
- [Communication-Efficient Distributed Dual Coordinate Ascent](https://mlsanity.com/paper/1409.1458/) (2014)
- [Competing with the Empirical Risk Minimizer in a Single Pass](https://mlsanity.com/paper/1412.6606/) (2014)
- [On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond](https://mlsanity.com/paper/1908.02246/) (2019)
- [Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Bounds](https://mlsanity.com/paper/1702.02030/) (2017)
- [A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods](https://mlsanity.com/paper/1803.00151/) (2018)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox](https://mlsanity.com/paper/1702.06269/) (2017)
- [Towards stability and optimality in stochastic gradient descent](https://mlsanity.com/paper/1505.02417/) (2015)

## Built on by (most cited first, 4 of 4)

- [Uniformly Stable Algorithms for Adversarial Training and Beyond](https://mlsanity.com/paper/2405.01817/) (2024)
- [Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learning](https://mlsanity.com/paper/2406.01115/) (2024)
- [Large-scale Score-based Variational Posterior Inference for Bayesian Deep Neural Networks](https://mlsanity.com/paper/2602.05873/) (2026)
- [Learning Theory of the SVRG: Generalization and Convergence Analysis](https://mlsanity.com/paper/2605.28513/) (2026)

## 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.