Glocal Smoothness: Line search and adaptive step sizes can help in theory too!
Not on the map. Why?
Abstract (arXiv)
Iteration complexities for optimizing smooth functions with first-order algorithms are typically stated in terms of a global Lipschitz constant of the gradient, and near-optimal results are then achieved using fixed step sizes. But many objective functions that arise in practice have regions with small Lipschitz constants where larger step sizes can be used. Many local Lipschitz assumptions have been proposed, which have led to results showing that adaptive step sizes and/or line searches yield improved convergence rates over fixed step sizes. However, these faster rates tend to depend on the iterates of the algorithm, which makes it difficult to compare the iteration complexities of different methods. We consider a simple characterization of global and local ("glocal") smoothness that only depends on properties of the function. This allows upper bounds on iteration complexities in terms of iterate-independent constants and enables us to compare iteration complexities between algorithms. Under this assumption it is straightforward to show the advantages of line searches over fixed step sizes and that, in some settings, gradient descent with line search has a better iteration complexity than accelerated methods with fixed step sizes. We further show that glocal smoothness can lead to improved complexities for the Polyak and AdGD step sizes, as well other algorithms including coordinate optimization, stochastic gradient methods, accelerated gradient methods, and non-linear conjugate gradient methods.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 46 of its 80 references that are in the map. First posted on arXiv 14 Jun 2025.
Builds on
46 of 80 references.
References · 46
- 2021Convex optimizationcited by 2,515
- 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,417
- 2014Convex Optimization: Algorithms and Complexitycited by 575
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
- 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
- 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 233
- 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
- 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
- 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
- 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
- 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
- 2019Adaptive Gradient Descent without Descentcited by 79
34 more
- 2019Revisiting the Polyak step sizecited by 55
- 2021Acceleration Methodscited by 48
- 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
- 2021A Loss Curvature Perspective on Training Instability in Deep Learningcited by 40
- 2015Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selectioncited by 39
- 2023Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimizationcited by 35
- 2024Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivitycited by 25
- 2013Gradient methods for convex minimization: better rates under weaker conditionscited by 23
- 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
- 2023Normalized Gradients for Allcited by 20
- 2017Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuitycited by 19
- 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
- 2024Directional Smoothness and Gradient Methods: Convergence and Adaptivitycited by 17
- 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
- 2021AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methodscited by 15
- 2023Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Modelscited by 15
- 2013Semi-Stochastic Gradient Descent Methodscited by 13
- 2022Gradient Descent in the Absence of Global Lipschitz Continuity of the Gradientscited by 11
- 2023Accelerated stochastic approximation with state-dependent noisecited by 11
- 2024Gradient Methods with Online Scalingcited by 11
- 2022Special Properties of Gradient Descent with Large Learning Ratescited by 10
- 2016On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functionscited by 9
- 2023Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtrackingcited by 9
- 2018On Matching Pursuit and Coordinate Descentcited by 7
- 2020Curiosities and counterexamples in smooth convex optimizationcited by 7
- 2022Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradientcited by 5
- 2023Non-Uniform Smoothness for Gradient Descentcited by 5
- 2023Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analysescited by 4
- 2017A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descentcited by 3
- 2018On the Properties of Convex Functions over Open Setscited by 3
- 2020Preconditioned accelerated gradient descent methods for locally Lipschitz smooth objectives with applications to the solution of nonlinear PDEscited by 3
- 2018Regional Complexity Analysis of Algorithms for Nonconvex Smooth Optimizationcited by 1
- 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
- 2024Why Line Search when you can Plane Search? SO-Friendly Neural Networks allow Per-Iteration Optimization of Learning and Momentum Rates for Every Layercited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.