Online prediction matches best fixed-time error without knowing horizon
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Machine Learning
Summary
When computers try to predict outcomes by listening to many experts, they usually need to know ahead of time how long they'll be predicting. This helps them balance how much they trust each expert. The researchers figured out a way to predict just as well without knowing how long they'll have to predict. Their approach works well at every point in time, not just at the end. This improves the accuracy of predictions from many experts over time without extra information.
What this means in practice
- •For machine learning engineers: Improve online prediction systems that aggregate expert inputs without needing preset time limits for training or adaptation.
- •For financial modelers: Construct prediction models that maintain optimal performance continuously over time without prior knowledge of investment period length.
A theory result. No direct application yet.
Authors
Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang
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 $\sqrt{\frac{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 $\sqrt{t \ln n}$---a factor of $\sqrt{2}$ worse---and it has remained unknown whether this factor of $\sqrt{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 \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$ simultaneously for every $t \ge 1$.