# Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2020.

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

- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees](https://mlsanity.com/paper/2409.09906/) (2024)
- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2307.07113/) (2023)
- [Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/2508.04950/) (2025)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)
- [Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2502.21099/) (2025)
- [On the Convergence of Stochastic Low-Rank Adaptation](https://mlsanity.com/paper/2607.21975/) (2026)
- [A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimization](https://mlsanity.com/paper/2412.14488/) (2024)
- [DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing](https://mlsanity.com/paper/2510.18218/) (2025)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)
- [Activation-Keyed Momentum: An Anisotropic Momentum Update via the Delta Rule](https://mlsanity.com/paper/2608.19491/) (2026)

## Abstract (arXiv)

Stochastic gradient methods (SGMs) have been extensively used for solving stochastic problems or large-scale machine learning problems. Recent works employ various techniques to improve the convergence rate of SGMs for both convex and nonconvex cases. Most of them require a large number of samples in some or all iterations of the improved SGMs. In this paper, we propose a new SGM, named PStorm, for solving nonconvex nonsmooth stochastic problems. With a momentum-based variance reduction technique, PStorm can achieve the optimal complexity result O(varepsilon-3) to produce a stochastic varepsilon-stationary solution, if a mean-squared smoothness condition holds. Different from existing optimal methods, PStorm can achieve the O(varepsilon-3) result by using only one or O(1) samples in every update. With this property, PStorm can be applied to online learning problems that favor real-time decisions based on one or O(1) new observations. In addition, for large-scale machine learning problems, PStorm can generalize better by small-batch training than other optimal methods that require large-batch training and the vanilla SGM, as we demonstrate on training a sparse fully-connected neural network and a sparse convolutional neural network.