Adaptive SGD with Line-Search and Polyak Stepsizes: Nonconvex Convergence and Accelerated Rates

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 $\mathcal{O}(1\mathrm{/}\sqrt{T})$ convergence rate for general nonconvex smooth functions, (2) an $\mathcal{O}(1\mathrm{/}T)$ rate under quasar-convexity and interpolation, and (3) an $\mathcal{O}(1\mathrm{/}T)$ rate under the strong growth condition for general nonconvex functions.