On-Line Learning with Linear Loss Constraints
Abstract
We consider a generalization of the mistake-bound model (for learning 0, 1-valued functions) in which the learner must satisfy a general constraint on the number M"+ of incorrect 1 predictions and the number M"- of incorrect 0 predictions. We describe a general-purpose optimal algorithm for our formulation of this problem. We describe several applications of our general results, involving situations in which the learner wishes to satisfy linear inequalities in M"+ and M"-.
Cite
Text
Littlestone and Long. "On-Line Learning with Linear Loss Constraints." Annual Conference on Computational Learning Theory, 1993. doi:10.1145/168304.168386Markdown
[Littlestone and Long. "On-Line Learning with Linear Loss Constraints." Annual Conference on Computational Learning Theory, 1993.](https://mlanthology.org/colt/1993/littlestone1993colt-line/) doi:10.1145/168304.168386BibTeX
@inproceedings{littlestone1993colt-line,
title = {{On-Line Learning with Linear Loss Constraints}},
author = {Littlestone, Nick and Long, Philip M.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1993},
pages = {412-421},
doi = {10.1145/168304.168386},
url = {https://mlanthology.org/colt/1993/littlestone1993colt-line/}
}