HNAG${}^{++}$: An Accelerated Gradient Method with a Refined Asymptotic Rate for Strongly Convex Optimization

Abstract

Two accelerated first-order methods, HNAG${}^{+}$ and HNAG${}^{++}$, are introduced for smooth strongly convex optimization. They are derived from the Hessian-driven Nesterov Accelerated Gradient (HNAG) flow by optimizing the coercivity of shifted Lyapunov functions. Let $\hat{I}º=L/\hat{I}¼$, where $\hat{I}¼$ is the strong-convexity constant and $L$ is the gradient Lipschitz constant. HNAG${}^{+}$ attains the optimal global rate $1-2/\sqrt{\hat{I}}º$, matching the information-theoretic lower bound. For functions with local asymptotic symmetry at the minimizer, HNAG${}^{++}$ attains the asymptotic rate $1-2\sqrt{2/\hat{I}º}$. This matches the best known asymptotic rate under ${\mathcal{C}}^2$ regularity, while applying to a broader function class. Numerical experiments confirm the predicted rates and show favorable performance against existing accelerated schemes.

Topics & keywords