Accelerated Composite Optimization under Gradient-Dependent Curvature

We study convex composite optimization under gradient-dependent curvature characterized by $||{\nabla }^{2}f(x)||\le \ell (||\nabla f(x)||)$, which generalizes Lipschitz smoothness. Existing accelerated methods under this condition mainly focus on smooth minimization, where $\nabla f(x^{\star })=0$ and the iteration complexity is governed by $\ell (0)$. In composite optimization, the smooth gradient may not vanish at a solution, so the local curvature is generally not determined by $\ell (0)$. We show that all minimizers share the same smooth gradient, whose norm is denoted by ${\tau }_{\star }$. Based on a localization of the smooth-gradient difference around the solution, we develop an accelerated proximal method with iteration complexity $O(T_{\ell }+R\sqrt{\ell ({\tau }_{\star })/\epsilon })$, where $T_{\ell }$ is independent of $\epsilon$. An adaptive variant achieves the same complexity without requiring prior knowledge of ${\tau }_{\star }$. For $\mu$-strongly convex objectives, a restarted algorithm gives $O((1+\sqrt{\ell ({\tau }_{\star })/\mu })\log ({\Delta }_0/\epsilon )+T_{\ell ,\mu })$ iteration complexity. We also establish lower bounds matching the leading terms in both the convex and strongly convex settings. Numerical experiments are included to support our theoretical findings.