A Simple and Optimal Approach for Universal Online Learning with Gradient Variations

Abstract

We investigate the problem of universal online learning with gradient-variation regret. Universal online learning aims to achieve regret guarantees without the prior knowledge of the curvature of the online functions. Moreover, we study the problem-dependent gradient-variation regret as it plays a crucial role in bridging stochastic and adversarial optimization as well as game theory. In this work, we design a universal approach with the optimal gradient-variation regret simultaneously for strongly convex, exp-concave, and convex functions, thus addressing an open problem highlighted by Yan et al. [2023]. Our approach is simple since it is algorithmically efficient-to-implement with a two-layer online ensemble structure and only 1 gradient query per round, and theoretically easy-to-analyze with a novel and alternative analysis to the gradient-variation regret. Concretely, previous works on gradient variations require controlling the algorithmic stability, which is challenging and leads to sub-optimal regret and less efficient algorithm design. Our analysis overcomes this issue by using a Bregman divergence negative term from linearization and a useful smoothness property.