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

CREATORAntoine Moulin, Emmanuel Esposito, Dirk van der Hoeven
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01722

Browse the full library · About the Tower of Babel