Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
Yuheng Zhao, Yu-Hu Yan, Kfir Y. Levy, Peng Zhao
Smoothness is known to be crucial for acceleration in offline optimization, and for problem-dependent regret that scale with gradient variations in online learning. Interestingly, these two problems are actually closely connected --  accelerated optimization can be understood from the lens of gradient-variation online learning. In this paper, we systematically investigate online learning with \emph{Hölder smooth} functions, a class encompassing both smooth and non-smooth (Lipschitz) functions, and further explore its implications for offline optimization. First, we propose an online algorithm with optimal gradient-variation regret for convex functions, which implies an optimal accelerated method for stochastic convex optimization under Hölder smoothness. Then, we extend the results in three aspects: \rom{1} strongly convex functions, \rom{2} non-stationary online learning where the comparator sequence changes over time; \rom{3} universal online learning where the curvature of functions is unknown. In all three cases, we have achieved the first gradient-variation regret that can well interpolate the results between the smooth and Lipschitz regimes, and recover the optimal results in each case. Notably, our proposed algorithms do not require prior knowledge of the Hölder smoothness parameter, greatly improving the adaptivity of existing methods that depend on this parameter, even when designed specifically for smooth functions. Finally, we demonstrate several implications for offline optimization through carefully tailored online-to-batch conversions.