Adaptive Extrapolated Proximal Gradient Methods with Variance Reduction for Composite Nonconvex Finite-Sum Minimization

[2502.21099] Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization Skip to main content Search Submit Donate Log in Mathematics > Optimization and Control arXiv:2502.21099 (math) [Submitted on 28 Feb 2025 ( v1 ), last revised 26 Sep 2026 (this version, v4)] Title: Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization Authors: Ganzhao Yuan View PDF HTML (experimental) Abstract: 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 $\epsilon$-stationarity in expectation using $\mathcal O(N+\sqrt{N}\epsilon^{-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 $\epsilon$-stationarity in expectation using $\widetilde{\mathcal O}(\sigma^2\epsilon^{-4}+\epsilon^{-2})$ and $\widetilde{\mathcal O}(\sigma\epsilon^{-3}+\epsilon^{-2})$ stochastic-gradient evaluations, respectively. Here, $N$ is the number of component functions, $\sigma^2$ bounds the gradient noise variance, and $\widetilde{\mathcal O}$ hides logarithmic factors. Neither expectation variant requires prior knowledge of $\sigma$, and both recover $\widetilde{\mathcal O}(\epsilon^{-2})$ complexity in the zero-noise regime. Comments: Substantially revised and extended, with a new title. Added ALFPG-MVR1 and ALFPG-MVR2 for expectation problems, together with noise-adaptive complexity guarantees Subjects: Optimization and Control (math.OC) ; Computer Vision and Pattern Recognition (cs.CV); Numerical Analysis (math.NA) Cite as: arXiv:2502.21099 [math.OC] (or arXiv:2502.21099v4 [math.OC] for this version) https://doi.org/10.48550/arXiv.2502.21099 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Ganzhao Yuan [ view email ] [v1] Fri, 28 Feb 2025 14:37:56 UTC (1,371 KB) [v2] Sat, 17 May 2025 09:56:02 UTC (1,156 KB) [v3] Tue, 25 Aug 2026 09:01:40 UTC (1,150 KB) [v4] Sat, 26 Sep 2026 12:26:26 UTC (90 KB) Full-text links: Access Paper: View PDF HTML (experimental) TeX Source view license Current browse context: math.OC < prev | next > new | recent | 2025-02 Change to browse by: cs cs.CV cs.NA math math.NA References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Adaptive Extrapolated Proximal Gradient Methods with Variance Reduction for Composite Nonconvex Finite-Sum Minimization#670322
• Randomized subspace correction methods for convex optimization#173322
• Barzilai–Borwein-like rules in proximal gradient schemes for ℓ1-regularized problems#814159
• On the Convergence of Stochastic Low-Rank Adaptation#1116380
• Beyond Conventional Federated Learning via High-Order Regularization#996717