Metraipolis › archive › dc_dc567704bc14
On the Relation Between Interval Regret and Dynamic Regret — arXiv:2609.34423
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34423
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T22:38:13.579Z
- SHA-256 of the archived text
8116a0dc8944fad61c3fe4ab0d79f541461589a5398d0d291169aefdbde3ab1f- Stable URL of this page
https://metraipolis.com/documento/dc_dc567704bc14
How to cite
On the Relation Between Interval Regret and Dynamic Regret — arXiv:2609.34423 — arXiv (en), https://arxiv.org/abs/2609.34423 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dc567704bc14 (Metraipolis archive dc_dc567704bc14, sha256 8116a0dc8944fad61c3fe4ab0d79f541461589a5398d0d291169aefdbde3ab1f)
BibTeX
@misc{dcdc567704bc14,
title = {On the Relation Between Interval Regret and Dynamic Regret — arXiv:2609.34423},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34423},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dc567704bc14; sha256 8116a0dc8944fad61c3fe4ab0d79f541461589a5398d0d291169aefdbde3ab1f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34423. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG). Categorie arXiv: Machine Learning (cs.LG) ; Optimization and Control (math.OC); Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2609.34423 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T22:14:28.178Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).