Improved second-order bounds for prediction with expert advice |
| |
Authors: | Nicolò Cesa-Bianchi Yishay Mansour Gilles Stoltz |
| |
Affiliation: | (1) DSI, Università di Milano, via Comelico 39, 20135 Milano, Italy;(2) School of Computer Science, Tel-Aviv University, Tel Aviv, Israel;(3) CNRS and Département de Mathématiques et Applications, Ecole Normale Supérieure, 75005 Paris, France |
| |
Abstract: | This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret
measures the difference between the payoff obtained by the forecasting strategy and the payoff of the best action. In this
setting, we derive new and sharper regret bounds for the well-known exponentially weighted average forecaster and for a second
forecaster with a different multiplicative update rule. Our analysis has two main advantages: first, no preliminary knowledge
about the payoff sequence is needed, not even its range; second, our bounds are expressed in terms of sums of squared payoffs,
replacing larger first-order quantities appearing in previous bounds. In addition, our most refined bounds have the natural
and desirable property of being stable under rescalings and general translations of the payoff sequence.
Editor: Avrim Blum
An extended abstract appeared in the Proceedings of the 18th Annual Conference on Learning Theory, Springer, 2005. The work of all authors was supported in part by the IST Programme of the European Community, under the
PASCAL Network of Excellence, IST-2002-506778.
The work was done while Yishay Mansour was a fellow in the Institute of Advance studies, Hebrew University. His work was also
supported by a grant no. 1079/04 from the Israel Science Foundation and an IBM faculty award. |
| |
Keywords: | Individual sequences Prediction with expert advice Exponentially weighted averages |
本文献已被 SpringerLink 等数据库收录! |
|