nips nips2005 nips2005-95 nips2005-95-reference knowledge-graph by maker-knowledge-mining

95 nips-2005-Improved risk tail bounds for on-line algorithms

Source: pdf

Author: Nicolò Cesa-bianchi, Claudio Gentile

Abstract: We prove the strongest known bound for the risk of hypotheses selected from the ensemble generated by running a learning algorithm incrementally 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.

reference text

[1] A. Blum, A. Kalai, and J. Langford. Beating the hold-out. In Proc.12th COLT, 1999.

[2] N. Cesa-Bianchi , A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Trans. on Information Theory, 50(9):2050-2057,2004.

[3] L. Devroye, L. Gy6rfi , and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer Verlag, 1996.

[4] D. A. Freedman . On tail probabilities for martingales. The Annals of Probability , 3: 100-118,1975.

[5] N. Littlestone. From on-line to batch learning. In Proc. 2nd COLT, 1989.

[6] T. Zhang. Data dependent concentration bounds for sequential prediction algorithms. In Proc. 18th COLT, 2005.