# Glocal Smoothness: Line search and adaptive step sizes can help in theory too!

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

## 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 (most cited first, 30 of 46)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [A Loss Curvature Perspective on Training Instability in Deep Learning](https://mlsanity.com/paper/2110.04369/) (2021)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity](https://mlsanity.com/paper/2409.14989/) (2024)
- [Gradient methods for convex minimization: better rates under weaker conditions](https://mlsanity.com/paper/1303.4645/) (2013)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity](https://mlsanity.com/paper/1712.04104/) (2017)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [Semi-Stochastic Gradient Descent Methods](https://mlsanity.com/paper/1312.1666/) (2013)
- [Gradient Descent in the Absence of Global Lipschitz Continuity of the Gradients](https://mlsanity.com/paper/2210.02418/) (2022)

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

- [Extragradient Method for (L0, L1)-Lipschitz Root-finding Problems](https://mlsanity.com/paper/2510.22421/) (2025)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)

## 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.