# Online Learning with Gradient-Variation Interval Regret

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 65 references that are in the map.
- First posted on arXiv 2 Jun 2026.

## Builds on (most cited first, 30 of 39)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [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)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Open-environment Machine Learning](https://mlsanity.com/paper/2206.00423/) (2022)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [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)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [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)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [Efficient Methods for Non-stationary Online Learning](https://mlsanity.com/paper/2309.08911/) (2023)
- [Online Learning for Changing Environments using Coin Betting](https://mlsanity.com/paper/1711.02545/) (2017)
- [Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness](https://mlsanity.com/paper/2305.13946/) (2023)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)

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

- [On the Relation Between Interval Regret and Dynamic Regret](https://mlsanity.com/paper/2609.34423/) (2026)
- [Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise](https://mlsanity.com/paper/2610.02258/) (2026)

## Abstract (arXiv)

This paper investigates non-stationary online learning using the metric of interval regret, which requires an online algorithm to perform well over every time interval. We propose the first online learning algorithm that achieves an interval regret bound scaling with gradient variation, a fundamental measure of the cumulative change in online function gradients, which relates to various problem-dependent quantities and is closely connected to stochastic optimization and other problems. Our method employs a simple and efficient two-layer online ensemble structure that achieves strong theoretical guarantees. Specifically, it enjoys a regret bound that simultaneously adapts to various problem-dependent quantities while also preserving the minimax-optimal rate in the worst case. Moreover, recognizing the challenge of hyperparameter tuning, we introduce a Lipschitz- and smoothness-agnostic variant that automatically adapts to these potentially unknown constants. This is primarily enabled by a novel Lipschitz-adaptive meta algorithm, which may be of independent interest. Beyond interval regret, our method also yields broader implications: it provides versatile bounds for interval dynamic regret, a stronger measure that competes with changing comparators over any interval, and yields the first piecewise characterization for stochastic extended adversarial optimization. Theoretical findings are validated by experiments.