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+ε)-moment is bounded by θ>0 for some ε∈(0,1]. In this setting, existing algorithms designed for the case ε=1 can be suboptimal when ε<1, suffering an additional polynomial dependence on K. We characterize the minimax pseudo-regret rate as Θ((θT)^1/(1+ε)(log K)^ε/(1+ε)) and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either ε or θ, 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 ε nor θ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when ε and θ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.

On prediction from expert advice with more than five experts
Jeff Calder, Nadejda Drenska
arXiv4 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Optimisation & controlarXiv
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Yang Cai, Vineet Gupta, Yanchen Jiang +4
arXiv23 Sep 2026PreprintCC BY-NC-SA 4.0Full textStatisticsarXiv
StochLOB: Heavy-Tailed Score Matching for Robust Limit Order Book Trend Prediction
Arshia Abolghasemi, Seyed Reza Tavakoli, Parsa Naderi +7
arXiv24 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Limit theory for a class of non-stationary linear processes with weakly dependent heavy-tailed innovations
Danijel Krizmanic
arXiv26 Sep 2026PreprintarXiv licenceFull textProbabilityarXiv
Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
Weiming Ou, Xiao Wang
arXiv26 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{shibukawa2026prediction,
  title = {{Prediction with Expert Advice under Heavy-Tailed Losses}},
  author = {Yuki Shibukawa and Shinji Ito},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.14904},
  eprint = {2610.14904},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.14904},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Prediction with Expert Advice under Heavy-Tailed Losses
AU  - Yuki Shibukawa
AU  - Shinji Ito
PY  - 2026
DA  - 2026/10/10
PB  - arXiv
DO  - 10.48550/arxiv.2610.14904
UR  - https://arxiv.org/abs/2610.14904
AB  - We study prediction with expert advice over T rounds with K experts under heavy-tailed losses whose (1+ε)-moment is bounded by θ>0 for some ε∈(0,1]. In this setting, existing algorithms designed for the case ε=1 can be suboptimal when ε<1, suffering an additional polynomial dependence on K. We characterize the minimax pseudo-regret rate as Θ((θT)^1/(1+ε)(log K)^ε/(1+ε)) and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either ε or θ, 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 ε nor θ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when ε and θ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.
ER  -

Abstract

Related

Cite