Part of Advances in Neural Information Processing Systems 14 (NIPS 2001)
Nicolò Cesa-bianchi, Alex Conconi, Claudio Gentile
In this paper we show that on-line algorithms for classiﬁcation and re- gression can be naturally used to obtain hypotheses with good data- dependent tail bounds on their risk. Our results are proven without re- quiring complicated concentration-of-measure arguments and they hold for arbitrary on-line learning algorithms. Furthermore, when applied to concrete on-line algorithms, our results yield tail bounds that in many cases are comparable or better than the best known bounds.