PreprintCC BY-NC-SA 4.0arXiv
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Abstract
Prediction with expert advice is a fundamental problem in online learning. When the time horizon T is known in advance, the minimax cumulative regret over n experts is asymptotically √((T ln n)/2). This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to T, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time t, the best known guarantee has been √(t ln n)---a factor of √2 worse---and it has remained unknown whether this factor of √2 is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies Rt ≤ (1 + O(√(ln ln n / ln n)))√(t ln n / 2) simultaneously for every t ≥ 1.
Related
- On prediction from expert advice with more than five experts
- When Does Sparse Routing Help? The Geometry of Expert Separation in Mixture of Experts
- Fast Training of Mixture-of-Experts for Time Series Forecasting via Expert Loss Integration
- GaP-MoE : Explicit Expert Specialization in Mixture-of-Experts via Orthogonal Gradient Accumulation and Projection
- CARE-MoE: Conflict-Aware Routing-Guided Expert Mixture-of-Experts for Continual Learning
BibTeX
@misc{cai2026prediction,
title = {{Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant}},
author = {Yang Cai and Vineet Gupta and Yanchen Jiang and Christopher Liaw and Aranyak Mehta and Grigoris Velegkas and Di Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27206},
eprint = {2609.27206},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27206},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
AU - Yang Cai
AU - Vineet Gupta
AU - Yanchen Jiang
AU - Christopher Liaw
AU - Aranyak Mehta
AU - Grigoris Velegkas
AU - Di Wang
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27206
UR - https://arxiv.org/abs/2609.27206
AB - Prediction with expert advice is a fundamental problem in online learning. When the time horizon T is known in advance, the minimax cumulative regret over n experts is asymptotically √((T ln n)/2). This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to T, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time t, the best known guarantee has been √(t ln n)---a factor of √2 worse---and it has remained unknown whether this factor of √2 is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies R_t ≤ (1 + O(√(ln ln n / ln n)))√(t ln n / 2) simultaneously for every t ≥ 1.
ER -