# A Proximal Stochastic Gradient Method with Progressive Variance Reduction

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

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2014.

## Built on by (most cited first, 30 of 78)

- [Only Train Once: A One-Shot Neural Network Training And Pruning Framework](https://mlsanity.com/paper/2107.07467/) (2021)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [OTOV2: Automatic, Generic, User-Friendly](https://mlsanity.com/paper/2303.06862/) (2023)
- [Transformers from an Optimization Perspective](https://mlsanity.com/paper/2205.13891/) (2022)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [Implicit Diffusion: Efficient Optimization through Stochastic Sampling](https://mlsanity.com/paper/2402.05468/) (2024)
- [AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation](https://mlsanity.com/paper/2204.13170/) (2022)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization](https://mlsanity.com/paper/2106.03056/) (2021)
- [An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification](https://mlsanity.com/paper/2208.06058/) (2022)
- [Optimizing Large-Scale Hyperparameters via Automated Learning Algorithm](https://mlsanity.com/paper/2102.09026/) (2021)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Knowledge Distillation Performs Partial Variance Reduction](https://mlsanity.com/paper/2305.17581/) (2023)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Distributed Learning With Sparsified Gradient Differences](https://mlsanity.com/paper/2202.02491/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time](https://mlsanity.com/paper/2305.15546/) (2023)
- [Training Structured Neural Networks Through Manifold Identification and Variance Reduction](https://mlsanity.com/paper/2112.02612/) (2021)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [On the Complexity of a Practical Primal-Dual Coordinate Method](https://mlsanity.com/paper/2201.07684/) (2022)
- [Sparsity-guided Network Design for Frame Interpolation](https://mlsanity.com/paper/2209.04551/) (2022)
- [A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reduction](https://mlsanity.com/paper/2204.00406/) (2022)
- [Stochastic Gradient Methods with Preconditioned Updates](https://mlsanity.com/paper/2206.00285/) (2022)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)

## Abstract (arXiv)

We consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions, and the other is a general convex function that admits a simple proximal mapping. We assume the whole objective function is strongly convex. Such problems often arise in machine learning, known as regularized empirical risk minimization. We propose and analyze a new proximal stochastic gradient method, which uses a multi-stage scheme to progressively reduce the variance of the stochastic gradient. While each iteration of this algorithm has similar cost as the classical stochastic gradient method (or incremental gradient method), we show that the expected objective value converges to the optimum at a geometric rate. The overall complexity of this method is much lower than both the proximal full gradient method and the standard proximal stochastic gradient method.