mlsanityData to 7 Oct 2026

A Proximal Stochastic Gradient Method with Progressive Variance Reduction

arXiv 1403.4699 ↗First posted 19 Mar 2014math.OC stat.MLcited by 78

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 19; 2023: 15; 2024: 13; 2025: 6; 2026: 6.

78 papers.

Sort:

  1. 2021Only Train Once: A One-Shot Neural Network Training And Pruning Frameworkcited by 70
  2. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  3. 2023OTOV2: Automatic, Generic, User-Friendlycited by 32
  4. 2022Transformers from an Optimization Perspectivecited by 27
  5. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  6. 2024Implicit Diffusion: Efficient Optimization through Stochastic Samplingcited by 22
  7. 2022AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimationcited by 21
  8. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  9. 2022Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Datacited by 18
  10. 2021Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guaranteescited by 17
  11. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
  12. 2022An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identificationcited by 14
38 more
  1. 2021Optimizing Large-Scale Hyperparameters via Automated Learning Algorithmcited by 13
  2. 2021MURANA: A Generic Framework for Stochastic Variance-Reduced Optimizationcited by 13
  3. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  4. 2023Knowledge Distillation Performs Partial Variance Reductioncited by 11
  5. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  6. 2021Differentially Private Coordinate Descent for Composite Empirical Risk Minimizationcited by 10
  7. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  8. 2022Distributed Learning With Sparsified Gradient Differencescited by 9
  9. 2022RECAPP: Crafting a More Efficient Catalyst for Convex Optimizationcited by 8
  10. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  11. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  12. 2021Training Structured Neural Networks Through Manifold Identification and Variance Reductioncited by 7
  13. 2023A Coefficient Makes SVRG Effectivecited by 7
  14. 2022On the Complexity of a Practical Primal-Dual Coordinate Methodcited by 6
  15. 2022Sparsity-guided Network Design for Frame Interpolationcited by 6
  16. 2022A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reductioncited by 5
  17. 2022Stochastic Gradient Methods with Preconditioned Updatescited by 5
  18. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  19. 2023Balance is Essence: Accelerating Sparse Training via Adaptive Gradient Correctioncited by 5
  20. 2023A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Propertiescited by 5
  21. 2021Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sumscited by 4
  22. 2021Stochastic Primal-Dual Deep Unrollingcited by 4
  23. 2022High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descentcited by 4
  24. 2023Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviationcited by 4
  25. 2024Communication-Efficient Adaptive Batch Size Strategies for Distributed Local Gradient Methodscited by 4
  26. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  27. 2025Joint Selection for Large-Scale Pre-Training Data via Policy Gradient-based Mask Learningcited by 4
  28. 2024Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradientscited by 3
  29. 2024Quantum Algorithms and Lower Bounds for Finite-Sum Optimizationcited by 3
  30. 2021Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applicationscited by 2
  31. 2021Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimizationcited by 2
  32. 2022Stochastic Steffensen methodcited by 2
  33. 2022FSCNN: A Fast Sparse Convolution Neural Network Inference Systemcited by 2
  34. 2024Parallel Momentum Methods Under Biased Gradient Estimationscited by 2
  35. 2024Boosting the Performance of Decentralized Federated Learning via Catalyst Accelerationcited by 2
  36. 2025Random feature approximation for general spectral methodscited by 2
  37. 2021Learning Sign-Constrained Support Vector Machinescited by 1
  38. 2021Faster Perturbed Stochastic Gradient Methods for Finding Local Minimacited by 1

50 most cited of 78 All 78 (JSON)