# On the Relation Between Interval Regret and Dynamic Regret

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 33 references that are in the map.
- First posted on arXiv 28 Sep 2026.

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

- [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)
- [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)
- [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)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [Open-environment Machine Learning](https://mlsanity.com/paper/2206.00423/) (2022)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [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)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions](https://mlsanity.com/paper/1906.10851/) (2019)
- [Efficient Methods for Non-stationary Online Learning](https://mlsanity.com/paper/2309.08911/) (2023)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Quasi-Newton Steps for Efficient Online Exp-Concave Optimization](https://mlsanity.com/paper/2211.01357/) (2022)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability](https://mlsanity.com/paper/2506.10616/) (2025)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)

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

- [Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2610.20187/) (2026)

## Abstract (arXiv)

Non-stationary online learning has attracted much attention in recent years, as static regret is insufficient to guide algorithm design in changing environments. To address this limitation, interval regret and dynamic regret have been introduced as two representative performance metrics that strengthen static regret in complementary directions. Interval regret requires an online algorithm to achieve competitive static regret over every local time interval, whereas dynamic regret evaluates performance against an arbitrary sequence of time-varying comparators. Despite their importance, the relation between these metrics has long remained unclear. Prior work has often regarded interval regret as the stronger notion, based on the intuition that local guarantees should naturally induce global guarantees. Consequently, it is widely conjectured that an algorithm with optimal interval regret should automatically attain optimal dynamic regret. In this paper, we first establish a negative result that refutes this intuition of a metric-level implication. Specifically, for both convex and curved functions (including exp-concave and strongly convex functions), we show that there exist instances in which an algorithm with optimal interval regret nevertheless fails to achieve optimal dynamic regret. We then show how to leverage local adaptivity to obtain optimal dynamic regret. In particular, optimal dynamic regret can be attained by invoking an interval regret minimization process over an enlarged Euclidean ball containing the original convex feasible domain and using a suitable domain-converted surrogate loss. This reduction applies to both convex and curved functions. As a byproduct, we obtain the first proper and efficient algorithm with optimal dynamic regret for exp-concave functions, improving prior results while significantly simplifying the analysis.