Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L_0, L_1)-Smoothness

arXiv:2508.06884v2 Announce Type: replace-cross Abstract: We study first-order methods for convex optimization problems with functions f satisfying the recently proposed ell-smoothness condition ||nabla^{2}f(x)|| le ellleft(||nabla f(x)||right), which generalizes the L-smoothness and (L_{0},L_{1})-smoothness. While accelerated gradient descent AGD is known to reach the optimal complexity O(sqrt{L} R / sqrt{arepsilon}) under L-smoothness, where arepsilon is an error tolerance and R is the distance between a starting and an optimal point, existing extensions to ell-smoothness either incur extra dependence on the initial gradient, suffer exponential factors in L_{1} R, or require costly auxiliary sub-routines, leaving open whether an AGD-type O(sqrt{ell(0)} R / sqrt{arepsilon}) rate is possible for small-arepsilon, even in the (L_{0},L_{1})-smoothness case. We resolve this open question. Leveraging a new Lyapunov function and designing new algorithms, we achieve O(sqrt{ell(0)} R / sqrt{arepsilon}) oracle complexity for small-arepsilon and virtually any ell. For instance, for (L_{0},L_{1})-smoothness, our bound O(sqrt{L_0} R / sqrt{arepsilon}) is provably optimal in the small-arepsilon regime and removes all non-constant multiplicative factors present in prior accelerated algorithms.

Source: arXiv cs.LG | 2026-05-23