# ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2019.

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

- [A Novel Convergence Analysis for Algorithms of the Adam Family](https://mlsanity.com/paper/2112.03459/) (2021)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [Variance-reduced Clipping for Non-convex Optimization](https://mlsanity.com/paper/2303.00883/) (2023)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator](https://mlsanity.com/paper/2104.14840/) (2021)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Training Structured Neural Networks Through Manifold Identification and Variance Reduction](https://mlsanity.com/paper/2112.02612/) (2021)
- [Learned Alternating Minimization Algorithm for Dual-domain Sparse-View CT Reconstruction](https://mlsanity.com/paper/2306.02644/) (2023)
- [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)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization](https://mlsanity.com/paper/2302.09766/) (2023)
- [Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization](https://mlsanity.com/paper/2301.00631/) (2023)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Collaborative Representation Learning for Alignment of Tactile, Language, and Vision Modalities](https://mlsanity.com/paper/2511.11512/) (2025)
- [Faster Perturbed Stochastic Gradient Methods for Finding Local Minima](https://mlsanity.com/paper/2110.13144/) (2021)
- [Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2208.04579/) (2022)
- [Gradient Descent-Type Methods: Background and Simple Unified Convergence Analysis](https://mlsanity.com/paper/2212.09413/) (2022)
- [A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness](https://mlsanity.com/paper/2403.15244/) (2024)
- [Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2502.21099/) (2025)
- [Non-Convex Federated Optimization under Cost-Aware Client Selection](https://mlsanity.com/paper/2512.05327/) (2025)
- [Beyond Student: An Asymmetric Network for Neural Network Inheritance](https://mlsanity.com/paper/2602.09509/) (2026)
- [On the Convergence of Stochastic Low-Rank Adaptation](https://mlsanity.com/paper/2607.21975/) (2026)
- [A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization](https://mlsanity.com/paper/2206.06531/) (2022)
- [SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization](https://mlsanity.com/paper/2207.08195/) (2022)

## Abstract (arXiv)

We propose a new stochastic first-order algorithmic framework to solve stochastic composite nonconvex optimization problems that covers both finite-sum and expectation settings. Our algorithms rely on the SARAH estimator introduced in (Nguyen et al, 2017) and consist of two steps: a proximal gradient and an averaging step making them different from existing nonconvex proximal-type algorithms. The algorithms only require an average smoothness assumption of the nonconvex objective term and additional bounded variance assumption if applied to expectation problems. They work with both constant and adaptive step-sizes, while allowing single sample and mini-batches. In all these cases, we prove that our algorithms can achieve the best-known complexity bounds. One key step of our methods is new constant and adaptive step-sizes that help to achieve desired complexity bounds while improving practical performance. Our constant step-size is much larger than existing methods including proximal SVRG schemes in the single sample case. We also specify the algorithm to the non-composite case that covers existing state-of-the-arts in terms of complexity bounds. Our update also allows one to trade-off between step-sizes and mini-batch sizes to improve performance. We test the proposed algorithms on two composite nonconvex problems and neural networks using several well-known datasets.