Minimizing Regret with Label Efficient Prediction
Abstract
We investigate label efficient prediction, a variant of the problem of prediction with expert advice, proposed by Helmbold and Panizza, in which the forecaster does not have access to the outcomes of the sequence to be predicted unless he asks for it, which he can do for a limited number of times. We determine matching upper and lower bounds for the best possible excess error when the number of allowed queries is a constant. We also prove that a query rate of order (ln n ) (ln ln n )^2/ n is sufficient for achieving Hannan consistency, a fundamental property in game-theoretic prediction models. Finally, we apply the label efficient framework to pattern classification and prove a label efficient mistake bound for a randomized variant of Littlestone’s zero-threshold Winnow algorithm.
Cite
Text
Cesa-Bianchi et al. "Minimizing Regret with Label Efficient Prediction." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_6Markdown
[Cesa-Bianchi et al. "Minimizing Regret with Label Efficient Prediction." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/cesabianchi2004colt-minimizing/) doi:10.1007/978-3-540-27819-1_6BibTeX
@inproceedings{cesabianchi2004colt-minimizing,
title = {{Minimizing Regret with Label Efficient Prediction}},
author = {Cesa-Bianchi, Nicolò and Lugosi, Gábor and Stoltz, Gilles},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {77-92},
doi = {10.1007/978-3-540-27819-1_6},
url = {https://mlanthology.org/colt/2004/cesabianchi2004colt-minimizing/}
}