Relation between interval regret and dynamic regret clarified
On the Relation Between Interval Regret and Dynamic Regret
Machine Learning
Summary
In online learning, measuring how well an algorithm adapts to changing environments is important. Two ways to measure this are interval regret, which looks at performance over short periods, and dynamic regret, which looks at performance overall against shifting targets. The authors show that having a good algorithm for interval regret does not always mean it will be good for dynamic regret, which was previously assumed. They also provide a method to transform interval regret guarantees into optimal dynamic regret performance, especially for certain types of problems.
What this means in practice
- •For machine learning engineers: Design algorithms that guarantee reliable adaptation to changing data environments by achieving optimal dynamic regret from interval regret methods.
- •For financial algorithm developers: Create trading strategies that better track shifting markets by applying the paper’s method for converting local guarantees into overall adaptive performance.
A theory result. No direct application yet.
Authors
Yi-Han Wang, Peng Zhao, Zhi-Hua Zhou
Abstract
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.