Part of Advances in Neural Information Processing Systems 18 (NIPS 2005)
Nicolò Cesa-bianchi, Claudio Gentile
We prove the strongest known bound for the risk of hypotheses selected from the ensemble generated by running a learning algorithm incremen(cid:173) tally on the training data. Our result is based on proof techniques that are remarkably different from the standard risk analysis based on uniform convergence arguments.