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.
