Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L₀, L₁)-Smoothness

2025/08/09 by Alexander Tyurin, Tyurin, Alexander
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2508.06884

openalex publication_date 2025/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We study first-order methods for convex optimization problems with functions f satisfying the recently proposed ℓ-smoothness condition ||∇²f(x)|| ≤ ℓ(||∇ f(x)||), which generalizes the L-smoothness and (L₀,L₁)-smoothness. While accelerated gradient descent AGD is known to reach the optimal complexity O(√(L) R / √(ε)) under L-smoothness, where ε 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 L₁ R, or require costly auxiliary sub-routines, leaving open whether an AGD-type O(√(ℓ(0)) R / √(ε)) rate is possible for small-ε, even in the (L₀,L₁)-smoothness case. We resolve this open question. Leveraging a new Lyapunov function and designing new algorithms, we achieve O(√(ℓ(0)) R / √(ε)) oracle complexity for small-ε and virtually any ℓ. For instance, for (L₀,L₁)-smoothness, our bound O(√(L₀) R / √(ε)) is provably optimal in the small-ε regime and removes all non-constant multiplicative factors present in prior accelerated algorithms.

Citations

• Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
• Mirror Descent Under Generalized Smoothness
• Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L₀,L₁)-Smoothness
• Toward a Unified Theory of Gradient Descent under Generalized Smoothness
• Optimizing (L₀, L₁)-Smooth Functions by Gradient Methods
• Methods for Convex (L₀,L₁)-Smooth Optimization: Clipping, Acceleration, and Adaptivity
• Gradient-Variation Online Learning under Generalized Smoothness
• Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization
• Parameter-Agnostic Optimization under Relaxed Smoothness
• Convex and Non-convex Optimization Under Generalized Smoothness
• Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions
• Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees
• Convergence of Adam Under Relaxed Assumptions
• Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization
• Robustness to Unbounded Smoothness of Generalized SignSGD
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Inexact Model: A Framework for Optimization and Variational Inequalities
• Primal-dual accelerated gradient methods with small-dimensional relaxation oracle
• Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
• Minimizing Finite Sums with the Stochastic Average Gradient

Related

• Methods for Convex (L₀,L₁)-Smooth Optimization: Clipping, Acceleration, and Adaptivity
• Accelerated Gradient Descent via Long Steps
• Optimizing (L₀, L₁)-Smooth Functions by Gradient Methods
• Linear Convergence Rate in Convex Setup is Possible! Gradient Descent Method Variants under (L₀,L₁)-Smoothness
• Higher-Order Accelerated Methods for Faster Non-Smooth Optimization