Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Rates
Not on the map. Why?
Abstract (arXiv)
We extend the convergence analysis of AdaSLS and AdaSPS in [Jiang and Stich, 2024] to the nonconvex setting, presenting a unified convergence analysis of stochastic gradient descent with adaptive Armijo line-search (AdaSLS) and Polyak stepsize (AdaSPS) for nonconvex optimization. Our contributions include: (1) an O(1/√T) convergence rate for general nonconvex smooth functions, (2) an O(1/T) rate under quasar-convexity and interpolation, and (3) an O(1/T) rate under the strong growth condition for general nonconvex functions.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 9 of its 12 references that are in the map. First posted on arXiv 25 Nov 2025.
Builds on
9 of 12 references.
References · 9
- 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
- 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
- 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
- 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
- 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
- 2019Training Neural Networks for and by Interpolationcited by 45
- 2022Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solutioncited by 40
- 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
- 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
Built on by
Not cited yet.