Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
En palabras de los autores
Prediction with expert advice is a fundamental problem in online learning. When the time horizon is known in advance, the minimax cumulative regret over experts is asymptotically . This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to , and is known to be tight. If instead the regret bound is required to hold simultaneously at every time , the best known guarantee has been ---a factor of worse---and it has remained unknown whether this factor of is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies simultaneously for every .
Resultado principalEl resumen no menciona limitaciones.
Apareció: jueves, 24 de septiembre. arXiv. Preprint, todavía sin revisión por pares.