arXiv preprint ·
Prediction with Expert Advice under Heavy-Tailed Losses
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $ε\in(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)^{\frac{1}{1+ε}}(\log K)^{\fracε{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Prior-Informed Generalizable Low-Rank Representation Learning via Regularized Adversarial Reweighting
Imperfect Verifiers, Exact Targets: Inference-Time Scaling for Continuous Generation
ByteMark: A Unified Byte-Level Watermark for Detection Across Language Models
What a Data Release Must Preserve for Off-Policy Evaluation
Copula Active Subspaces II: Error Decomposition, A Posteriori Estimation, and Sharpness of the Bounds
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.