When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses
Antoine Moulin, Emmanuel Esposito, Dirk van der Hoeven · 2025
Read When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses by Antoine Moulin, Emmanuel Esposito, Dirk van der Hoeven (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01722.txt.
Description
Learning from expert advice is a classic online problem: follow the best expert without knowing future losses. Antoine Moulin, Emmanuel Esposito, and Dirk van der Hoeven study the heavy-tailed case. Losses may spike, and only a bound on their second moment is assumed. Older adaptive methods carry a penalty term tied to the largest loss seen. The authors show that term can quietly dominate the whole regret bound.
Their new algorithms dodge the penalty. Worst-case regret grows with the square root of the moment bound times time, times a log factor. When losses come from a fixed distribution, regret shrinks further with the gap between experts. Squared loss gets its own improved bound.
Catalog record
| CREATOR | Antoine Moulin, Emmanuel Esposito, Dirk van der Hoeven |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01722