# Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L0, L1)-Smoothness

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 29 references that are in the map.
- First posted on arXiv 9 Aug 2025.

## Builds on (most cited first, 20 of 20)

- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity](https://mlsanity.com/paper/2409.14989/) (2024)
- [Optimizing (L0, L1)-Smooth Functions by Gradient Methods](https://mlsanity.com/paper/2410.10800/) (2024)
- [Primal-dual accelerated gradient methods with small-dimensional relaxation oracle](https://mlsanity.com/paper/1809.05895/) (2018)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Inexact Model: A Framework for Optimization and Variational Inequalities](https://mlsanity.com/paper/1902.00990/) (2019)
- [Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization](https://mlsanity.com/paper/2406.09772/) (2024)
- [Toward a Unified Theory of Gradient Descent under Generalized Smoothness](https://mlsanity.com/paper/2412.11773/) (2024)
- [Mirror Descent Under Generalized Smoothness](https://mlsanity.com/paper/2502.00753/) (2025)
- [Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization](https://mlsanity.com/paper/2507.09823/) (2025)
- [Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L0,L1)-Smoothness](https://mlsanity.com/paper/2412.17050/) (2024)

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

- [A Human-AI Collaborative Workflow for Mathematical Discovery: A Case Study in Grover-Compatible Riemannian Optimization](https://mlsanity.com/paper/2512.09443/) (2025)

## Abstract (arXiv)

We study first-order methods for convex optimization problems with functions f satisfying the recently proposed ℓ-smoothness condition ||nabla2f(x)|| ≤ ℓleft(||nabla f(x)||right), which generalizes the L-smoothness and (L0,L1)-smoothness. While accelerated gradient descent AGD is known to reach the optimal complexity O(√L R / √varepsilon) under L-smoothness, where varepsilon is an error tolerance and R is the distance between a starting and an optimal point, existing extensions to ℓ-smoothness either incur extra dependence on the initial gradient, suffer exponential factors in L1 R, or require costly auxiliary sub-routines, leaving open whether an AGD-type O(√ℓ(0) R / √varepsilon) rate is possible for small-varepsilon, even in the (L0,L1)-smoothness case. We resolve this open question. Leveraging a new Lyapunov function and designing new algorithms, we achieve O(√ℓ(0) R / √varepsilon) oracle complexity for small-varepsilon and virtually any ℓ. For instance, for (L0,L1)-smoothness, our bound O(√L0 R / √varepsilon) is provably optimal in the small-varepsilon regime and removes all non-constant multiplicative factors present in prior accelerated algorithms.