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

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.