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

We develop accelerated algorithms for convex $(H_0,H_1)$-smooth optimization, where $||{\nabla }^{2}f(x)||\le H_0+H_1(f(x)-f^{\ast })$. This class generalizes standard smoothness and contains the $(L_0,L_1)$-smooth class. The technical challenge is to combine acceleration with the resulting local quadratic model: every trial step must remain within its validity radius. Combining this condition with accelerated coupling and phase restarts, we obtain the full-gradient 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 methods, obtaining the corresponding uniform rate with the standard factor $d$, and a non-uniform rate 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. Experiments support the predicted acceleration and the advantage of non-uniform sampling.