# Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach

arXiv: https://arxiv.org/abs/2307.08360 · HTML: https://mlsanity.com/paper/2307.08360/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 17 Jul 2023.

## Builds on (most cited first, 17 of 17)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Adaptivity and Optimality: A Universal Algorithm for Online Convex Optimization](https://mlsanity.com/paper/1905.05917/) (2019)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Universal Online Convex Optimization Meets Second-order Bounds](https://mlsanity.com/paper/2105.03681/) (2021)

## Built on by (most cited first, 9 of 9)

- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2411.03107/) (2024)
- [Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness](https://mlsanity.com/paper/2511.02276/) (2025)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Parameter-free Algorithms for the Stochastically Extended Adversarial Model](https://mlsanity.com/paper/2510.04685/) (2025)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets](https://mlsanity.com/paper/2402.12868/) (2024)
- [Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variations](https://mlsanity.com/paper/2505.21095/) (2025)

## Abstract (arXiv)

In this paper, we propose an online convex optimization approach with two different levels of adaptivity. On a higher level, our approach is agnostic to the unknown types and curvatures of the online functions, while at a lower level, it can exploit the unknown niceness of the environments and attain problem-dependent guarantees. Specifically, we obtain O(log VT), O(d log VT) and hatO(√VT) regret bounds for strongly convex, exp-concave and convex loss functions, respectively, where d is the dimension, VT denotes problem-dependent gradient variations and the hatO(·)-notation omits log VT factors. Our result not only safeguards the worst-case guarantees but also directly implies the small-loss bounds in analysis. Moreover, when applied to adversarial/stochastic convex optimization and game theory problems, our result enhances the existing universal guarantees. Our approach is based on a multi-layer online ensemble framework incorporating novel ingredients, including a carefully designed optimism for unifying diverse function types and cascaded corrections for algorithmic stability. Notably, despite its multi-layer structure, our algorithm necessitates only one gradient query per round, making it favorable when the gradient evaluation is time-consuming. This is facilitated by a novel regret decomposition equipped with carefully designed surrogate losses.