A Few Accelerated Algorithms for Convex Optimization under $(H_0,H_1)$-Smoothness

Abstract

We develop accelerated algorithms for convex $(H_0,H_1)$-smooth optimization, where $\Vert {\nabla }^{2}f(x)\Vert \le H_0+H_1(f(x)-f^{\ast })$. This class generalizes standard smoothness and contains the $(L_0,L_1)$-smooth class. Combining a Nesterov-type accelerated gradient scheme with small-dimensional relaxation and phase restarts, we obtain a full-gradient method with iteration complexity $\tilde{O}(\sqrt{H_0{\tilde{R}}^2/\epsilon }+\sqrt{H_1{\tilde{R}}^2}\log (F_0/\epsilon ))$. We extend the same approach to randomized coordinate optimization, obtaining a coordinate method with uniform sampling whose iteration complexity carries the standard factor $d$, and a coordinate method with non-uniform sampling whose iteration complexity is governed by $S_{1/2}^{(j)}={\sum }_i\sqrt{H_{j,i}}$. These results provide, to our knowledge, the first accelerated full-gradient and coordinate guarantees for this convex class. We also provide practical implementation recommendations. Experiments confirm the predicted acceleration, gains from non-uniform sampling, and the viability of inexact relaxation.

Preprint