Improved Risk Tail Bounds for On-Line Algorithms
IEEE Transactions on Information TheoryPublished 1 January 2008
Nicolò Cesa‐Bianchi, Claudio Gentile
Citations50
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Tight bounds are derived on the risk of models in the ensemble generated by incremental training of an arbitrary learning algorithm based on uniform convergence arguments, and improves on previous bounds published by the same authors.
Abstract
Tight bounds are derived on the risk of models in the ensemble generated by incremental training of an arbitrary learning algorithm. The result is based on proof techniques that are remarkably different from the standard risk analysis based on uniform convergence arguments, and improves on previous bounds published by the same authors.
Keywords
Computer Science
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
The Nature of Statistical Learning Theory
10,566 Citations2000Vladimir Vapnik
Stochastic modelling and applied probabilityA Probabilistic Theory of Pattern Recognition
3,277 Citations1996Luc Devroye, László Györfi +1 more
The Bayes Error and Vapnik-Chervonenkis theory are applied as guide for empirical classifier selection on the basis of explicit specification and explicit enforcement of the maximum likelihood principle.
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
Lecture notes in computer scienceRademacher and Gaussian Complexities: Risk Bounds and Structural Results
2,111 Citations2001Peter L. Bartlett, Shahar Mendelson
This work investigates the use of certain data-dependent estimates of the complexity of a function class called Rademacher and Gaussian complexities and proves general risk bounds in terms of these complexities in a decision theoretic setting.
IEEE Transactions on Information TheoryThe sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network
1,187 Citations1998Peter L. Bartlett
Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights.
IEEE Transactions on Information TheoryStructural risk minimization over data-dependent hierarchies
527 Citations1998John Shawe‐Taylor, Peter L. Bartlett +2 more
A result is presented that allows one to trade off errors on the training sample against improved generalization performance, and a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets.
The Annals of StatisticsEmpirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers
468 Citations2002Vladimir Koltchinskii, Dmitry Panchenko
New probabilistic upper bounds on generalization error of complex classifiers that are combinations of simple classifier combinations, based on the methods of the theory of Gaussian and empirical processes are proved.
IEEE Transactions on Information TheoryOn the Generalization Ability of On-Line Learning Algorithms
442 Citations2004Nicolò Cesa‐Bianchi, Alex Conconi +1 more
This paper proves tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M/sub n/ associated with the on-line performance of the ensemble, and obtains risk tail bounds for kernel perceptron algorithms interms of the spectrum of the empirical kernel matrix.
Beating the hold-out
263 Citations1999Avrim Blum, Adam Tauman Kalai +1 more
It is shown that for any nontrivial learning problem and learning algorithm that is insensitive to example ordering, the k-fold estimate is strictly more accurate than a single hold-out estimate on 1/k of the data, for 2 < k < n (k = n is leave-one-out), based on its variance and all higher moments.
IEEE Transactions on Information TheoryOnline Regularized Classification Algorithms
100 Citations2006Yiming Ying, Ding‐Xuan Zhou
Elsevier eBooksFrom On-line to Batch Learning
46 Citations1989Nick Littlestone
An analysis of a conversion to improve the performance of on-line learning algorithms in a batch setting, using a version of Chernoff bounds applied to supermartingales, that shows that for some target classes the converted algorithm will be asymptotically optimal.
Lecture notes in computer scienceData Dependent Concentration Bounds for Sequential Prediction Algorithms
38 Citations2005Tong Zhang
Using some newly developed probability inequalities, this work is able to bound the total generalization performance of a learning algorithm in terms of its observed total loss.