# Optimizing (L0, L1)-Smooth Functions by Gradient Methods

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2024.

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

- [Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs)](https://mlsanity.com/paper/2505.13416/) (2025)
- [Beyond the Ideal: Analyzing the Inexact Muon Update](https://mlsanity.com/paper/2510.19933/) (2025)
- [Generalized Gradient Norm Clipping & Non-Euclidean (L0,L1)-Smoothness](https://mlsanity.com/paper/2506.01913/) (2025)
- [Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates](https://mlsanity.com/paper/2511.11466/) (2025)
- [On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approach](https://mlsanity.com/paper/2506.00181/) (2025)
- [Smoothed Normalization for Efficient Distributed Private Optimization](https://mlsanity.com/paper/2502.13482/) (2025)
- [Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster](https://mlsanity.com/paper/2503.00229/) (2025)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Extragradient Method for (L0, L1)-Lipschitz Root-finding Problems](https://mlsanity.com/paper/2510.22421/) (2025)
- [Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methods](https://mlsanity.com/paper/2602.10697/) (2026)
- [Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success](https://mlsanity.com/paper/2606.14560/) (2026)
- [Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L0, L1)-Smoothness](https://mlsanity.com/paper/2508.06884/) (2025)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)
- [Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness](https://mlsanity.com/paper/2509.08726/) (2025)
- [Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothness](https://mlsanity.com/paper/2601.03566/) (2026)
- [Byzantine-Robust Optimization under (L0, L1)-Smoothness](https://mlsanity.com/paper/2603.12512/) (2026)
- [Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives](https://mlsanity.com/paper/2605.11850/) (2026)
- [Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness](https://mlsanity.com/paper/2609.30276/) (2026)
- [Last-Iterate Convergence Rate of Normalized Gradient Descent under H"older Smoothness](https://mlsanity.com/paper/2610.06070/) (2026)

## Abstract (arXiv)

We study gradient methods for optimizing (L0, L1)-smooth functions, a class that generalizes Lipschitz-smooth functions and has gained attention for its relevance in machine learning. We provide new insights into the structure of this function class and develop a principled framework for analyzing optimization methods in this setting. While our convergence rate estimates recover existing results for minimizing the gradient norm in nonconvex problems, our approach significantly improves the best-known complexity bounds for convex objectives. Moreover, we show that the gradient method with Polyak stepsizes and the normalized gradient method achieve nearly the same complexity guarantees as methods that rely on explicit knowledge of~(L0, L1). Finally, we demonstrate that a carefully designed accelerated gradient method can be applied to (L0, L1)-smooth functions, further improving all previous results.