# A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2018.

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

- [Dash: Semi-Supervised Learning with Dynamic Thresholding](https://mlsanity.com/paper/2109.00650/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [Improved Fine-Tuning by Better Leveraging Pre-Training Data](https://mlsanity.com/paper/2111.12292/) (2021)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021)
- [Robust Semi-supervised Learning by Wisely Leveraging Open-set Data](https://mlsanity.com/paper/2405.06979/) (2024)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Variance Reduced Training with Stratified Sampling for Forecasting Models](https://mlsanity.com/paper/2103.02062/) (2021)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [Fusion of Global and Local Knowledge for Personalized Federated Learning](https://mlsanity.com/paper/2302.11051/) (2023)
- [Prior Mismatch and Adaptation in PnP-ADMM with a Nonconvex Convergence Analysis](https://mlsanity.com/paper/2310.00133/) (2023)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback](https://mlsanity.com/paper/2110.03294/) (2021)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data](https://mlsanity.com/paper/2504.11903/) (2025)
- [Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization](https://mlsanity.com/paper/2301.00631/) (2023)
- [Convergence of Nonconvex PnP-ADMM with MMSE Denoisers](https://mlsanity.com/paper/2311.18810/) (2023)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Demystifying the Myths and Legends of Nonconvex Convergence of SGD](https://mlsanity.com/paper/2310.12969/) (2023)
- [Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems](https://mlsanity.com/paper/2401.15890/) (2024)
- [A Theoretical Analysis of Learning with Noisily Labeled Data](https://mlsanity.com/paper/2104.04114/) (2021)
- [Why Does Multi-Epoch Training Help?](https://mlsanity.com/paper/2105.06015/) (2021)
- [The Perturbed Prox-Preconditioned SPIDER algorithm for EM-based large scale learning](https://mlsanity.com/paper/2105.11732/) (2021)
- [Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2111.12961/) (2021)
- [Differentially Private Domain Adaptation with Theoretical Guarantees](https://mlsanity.com/paper/2306.08838/) (2023)

## Abstract (arXiv)

We analyze stochastic gradient algorithms for optimizing nonconvex, nonsmooth finite-sum problems. In particular, the objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a possibly non-differentiable but convex component. We propose a proximal stochastic gradient algorithm based on variance reduction, called ProxSVRG+. Our main contribution lies in the analysis of ProxSVRG+. It recovers several existing convergence results and improves/generalizes them (in terms of the number of stochastic gradient oracle calls and proximal oracle calls). In particular, ProxSVRG+ generalizes the best results given by the SCSG algorithm, recently proposed by [Lei et al., 2017] for the smooth nonconvex case. ProxSVRG+ is also more straightforward than SCSG and yields simpler analysis. Moreover, ProxSVRG+ outperforms the deterministic proximal gradient descent (ProxGD) for a wide range of minibatch sizes, which partially solves an open problem proposed in [Reddi et al., 2016b]. Also, ProxSVRG+ uses much less proximal oracle calls than ProxSVRG [Reddi et al., 2016b]. Moreover, for nonconvex functions satisfied Polyak-Lojasiewicz condition, we prove that ProxSVRG+ achieves a global linear convergence rate without restart unlike ProxSVRG. Thus, it can automatically switch to the faster linear convergence in some regions as long as the objective function satisfies the PL condition locally in these regions. ProxSVRG+ also improves ProxGD and ProxSVRG/SAGA, and generalizes the results of SCSG in this case. Finally, we conduct several experiments and the experimental results are consistent with the theoretical results.