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

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 \ell \left(||\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{\epsilon })$ under $L$-smoothness, where $\epsilon$ 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{\epsilon })$ rate is possible for small-$\epsilon$, 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{\epsilon })$ oracle complexity for small-$\epsilon$ and virtually any $\ell$. For instance, for $(L_0,L_1)$-smoothness, our bound $O(\sqrt{L_0}R/\sqrt{\epsilon })$ is provably optimal in the small-$\epsilon$ regime and removes all non-constant multiplicative factors present in prior accelerated algorithms.