Prediction with Expert Advice under Heavy-Tailed Losses

arXiv:2610.14904v1 Announce Type: new Abstract: We study prediction with expert advice over T rounds with K experts under heavy-tailed losses whose (1+epsilon)-moment is bounded by heta>0 for some epsilonin(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((heta 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 heta, 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 heta and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when epsilon and heta are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.

Related

• An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
• On prediction from expert advice with more than five experts
• Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Source: arXiv cs.LG | 2026-10-14