Prediction with Expert Advice under Heavy-Tailed Losses

Abstract

We study prediction with expert advice over $T$ rounds with $K$ experts under heavy-tailed losses whose $(1+\epsilon )$-moment is bounded by $\theta >0$ for some $\epsilon \in (0,1]$. In this setting, existing algorithms designed for the case $\epsilon =1$ can be suboptimal when $\epsilon <1$, suffering an additional polynomial dependence on $K$. We characterize the minimax pseudo-regret rate as $\Theta ((\theta T{)}^{\frac{1}{1+\epsilon }}(\log K{)}^{\frac{\epsilon }{1+\epsilon }})$ and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either $\epsilon$ or $\theta$, we propose Adaptive Heavy-Tailed FTRL, which uses robust data-dependent scale adaptation together with truncation. We further develop Adaptive Heavy-Tailed OMD, which likewise requires neither $\epsilon$ nor $\theta$ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when $\epsilon$ and $\theta$ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.

arXiv comment49 pages