Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Lecture notes in computer sciencePublished 1 January 2001
Peter L. Bartlett, Shahar Mendelson
Citations2,111
SJR quartileQ2
SJR score0.35
SNIP0.55
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
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.
Abstract
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. We consider function classes that can be expressed as combinations of functions from basis classes and show how the Rademacher and gaussian complexities of such a function class can be bounded in terms of the complexity of the basis classes.We give examples of the application of these techniques in finding data-dependent risk bounds for decision trees, neural networks and support vector machines.
Keywords
Computer Science
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
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.
The Annals of StatisticsBoosting the margin: a new explanation for the effectiveness of voting methods
2,313 Citations1998Peter L. Bartlett, Yoav Freund +2 more
It is shown that techniques used in the analysis of Vapnik's support vector classifiers and of neural networks with small weights can be applied to voting methods to relate the margin distribution to the test error.
Cambridge University Press eBooksOn the method of bounded differences
1,428 Citations1989Colin McDiarmid
Probability in Banach Spaces
1,414 Citations1991Michel Ledoux, Michel Talagrand
Neural network learning theoretical foundations
1,357 Citations2009Martin Anthony, Peter L. Bartlett
The authors explain the role of scale-sensitive versions of the Vapnik Chervonenkis dimension in large margin classification, and in real prediction, and discuss the computational complexity of neural network learning.
Probability in Banach Spaces: Isoperimetry and Processes
1,276 Citations1991Michel Ledoux, Michel Talagrand
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.
Cambridge University Press eBooksThe Volume of Convex Bodies and Banach Space Geometry
1,001 Citations1989Gilles Pisier
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 TheoryRademacher penalties and structural risk minimization
371 Citations2001Vladimir Koltchinskii
This work suggests a penalty function to be used in various problems of structural risk minimization, based on the sup-norm of the so-called Rademacher process indexed by the underlying class of functions (sets), and obtains oracle inequalities for the theoretical risk of estimators, obtained by structural minimization of the empirical risk withRademacher penalties.
Elsevier eBooksError-Correcting Output Coding Corrects Bias and Variance
357 Citations1995Eun Bae Kong, Thomas G. Dietterich
An investigation of why the ECOC technique works, particularly when employed with decision-tree learning algorithms, shows that it can reduce the variance of the learning algorithm.
Machine LearningModel Selection and Error Estimation
295 Citations2002Peter L. Bartlett, Stéphane Boucheron +1 more
A tight relationship between error estimation and data-based complexity penalization is pointed out: any good error estimate may be converted into a data- based penalty function and the performance of the estimate is governed by the quality of the error estimate.
Using output codes to boost multiclass learning problems
263 Citations1997Robert E. Schapire
This paper describes a new technique for multiclass learning problems by combining Freund and Schapire's boosting algorithm with the main ideas of Diet- terich and Bakiri's method of error-correcting output codes (ECOC), and shows that the new hybrid method has advantages of both.
Birkhäuser Boston eBooksRademacher Processes and Bounding the Risk of Function Learning
211 Citations2000Vladimir Koltchinskii, Dmitriy Panchenko
The bounds are based on local norms of the Rademacher process indexed by the underlying function class, and they do not require prior knowledge about the distribution of training examples or any specific properties of the function class.
An experimental and theoretical comparison of model selection methods
170 Citations1995Michael Kearns, Yishay Mansour +2 more
IEEE Transactions on Information TheoryGeneralization performance of regularization networks and support vector machines via entropy numbers of compact operators
169 Citations2001Robert C. Williamson, Alex Smola +1 more
New bounds for the generalization error of kernel machines, such as support vector machines and related regularization networks, are derived by obtaining new bounds on their covering numbers by using the eigenvalues of an integral operator induced by the kernel function used by the machine.
Machine LearningImproved Generalization Through Explicit Optimization of Margins
131 Citations2000Llew Mason, Peter L. Bartlett +1 more
A theorem bounding the generalization performance of convex combinations in terms of general cost functions of the margin is proved, in contrast to previous results, which were stated in Terms of the particular cost function sgn(θ − margin).
SSRN Electronic JournalModel Selection and Error Estimation
94 Citations2000Peter L. Bartlett, Stéphane Boucheron +1 more
IEEE Transactions on Information TheoryRademacher averages and phase transitions in Glivenko-Cantelli classes
83 Citations2002Shahar Mendelson
The best known estimates on the covering numbers of a class when considered as a subset of L/sub p/ spaces are proved and the fat-shattering dimension of the convex hull of a given class is estimated.
Machine LearningAn Experimental and Theoretical Comparison of Model Selection Methods
67 Citations1997Michael Kearns, Yishay Mansour +2 more
A detailed comparison of three well-known model selection methods — a variation of Vapnik's Guaranteed Risk Minimization (GRM), an instance of Rissanen's Minimum Description Length Principle (MDL), and (hold-out) cross validation (CV) are compared.
Generalization in Decision Trees and DNF: Does Size Matter?
28 Citations1997Mostefa Golea, Peter L. Bartlett +2 more
This paper shows that with high probability any decision tree of depth no more than d that is consistent with m training examples has misclassification probabilityNo more than O((1/m(Neff VCdim(U) log2 m log d))1/2), where U is the class of node decision functions, and Neff ≤ N can be thought of as the effective number of leaves.
Positivityℓ-norm and its Application to Learning Theory
5 Citations2001Shahar Mendelson
It is shown that if the ℓ-norm of a set of functions is bounded in some sense, then the set satisfies the uniform law of large numbers and the Vapnik–Chervonenkis (VC) dimension.