# Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 45 references that are in the map.
- First posted on arXiv 28 Feb 2025.

## Builds on (most cited first, 26 of 26)

- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [ProxQuant: Quantized Neural Networks via Proximal Operators](https://mlsanity.com/paper/1810.00861/) (2018)
- [A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2006.02032/) (2020)
- [Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/1702.02505/) (2017)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [iPiano: Inertial Proximal Algorithm for Non-Convex Optimization](https://mlsanity.com/paper/1404.4805/) (2014)
- [A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1907.03793/) (2019)
- [Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization](https://mlsanity.com/paper/1705.04925/) (2017)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems](https://mlsanity.com/paper/1902.07672/) (2019)
- [Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization](https://mlsanity.com/paper/2006.00425/) (2020)
- [Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions](https://mlsanity.com/paper/2406.01959/) (2024)
- [STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization](https://mlsanity.com/paper/2111.01040/) (2021)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)
- [A Fast and Provable Algorithm for Sparse Phase Retrieval](https://mlsanity.com/paper/2309.02046/) (2023)

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

- [Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization](https://mlsanity.com/paper/2607.25785/) (2026)

## Abstract (arXiv)

We propose sf ALFPG, an Adaptive Lipschitz-Free Proximal Gradient framework for stochastic composite nonconvex minimization. The framework adapts its stepsizes using information collected along the optimization trajectory, without requiring prior knowledge of smoothness constants or performing line search. For finite-sum problems, ALFPG-FS combines coordinate-wise stepsizes, Nesterov's extrapolation, and the SPIDER estimator, with ALFPG-D as its full-batch specialization. Under component-wise smoothness and a bounded effective domain, ALFPG-FS achieves ε-stationarity in expectation using mathcal O(N+√Nε-2) component-gradient evaluations. For expectation problems, we develop ALFPG-MVR1 and sf ALFPG-MVR2, where MVR stands for momentum-based variance reduction. Both use one fresh sample per iteration: ALFPG-MVR1 uses one stochastic-gradient evaluation, whereas sf ALFPG-MVR2 uses at most two evaluations at different points with the same sample. ALFPG-MVR1 requires smoothness of the expected loss; sf ALFPG-MVR2 additionally requires uniformly smooth sample losses. When the regularizer is convex or Lipschitz continuous on its effective domain, and stochastic gradients are almost surely bounded, the two methods achieve ε-stationarity in expectation using widetildemathcal O(σ2ε-4+ε-2) and widetildemathcal O(σε-3+ε-2) stochastic-gradient evaluations, respectively. Here, N is the number of component functions, σ2 bounds the gradient noise variance, and widetildemathcal O hides logarithmic factors. Neither expectation variant requires prior knowledge of σ, and both recover widetildemathcal O(ε-2) complexity in the zero-noise regime.