When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses
arXiv:2506.01722v3 Announce Type: replace-cross Abstract: We consider the problem setting of prediction with expert advice with possibly heavy-tailed losses, i.e. the only assumption on the losses is an upper bound on their second moments, denoted by $theta$. We develop adaptive algorithms that do not require any prior knowledge about the range or the second moment of the losses. Existing adaptive algorithms have what is typically considered a lower-order term in their regret guarantees. We show that this lower-order […]