Algorithmic Stability and Generalization Performance
Olivier Bousquet, André Elisseeff, Barnhill Bioinformatics · 2000
We present a novel way of obtaining PAC-style bounds on the generalization error of learning algorithms, explicitly using their stability properties. A stable learner being one for which the learned solution does not change much for small changes in the training set. The bounds we obtain do not depend on any measure of the complexity of the hypothesis space (e.g. VC dimension) but rather depend on how the learning algorithm searches this space, and can thus be applied even when the VC dimension in innite. We demonstrate that regularization networks possess the required stability property and apply our method to obtain new bounds on their generalization performance. 1 Introduction A key issue in computational learning theory is to bound the generalization error of learning algorithms. Until recently, most of the research in that area has focused on uniform a-priori bounds giving a guarantee that the dierence between the training error and the test error is uniformly small for any hyp...
Cited by 86 works.
Authors
References
- Theory of reproducing kernels
- Regularization Algorithms for Learning That Are Equivalent to Multilayer Networks
- On the method of bounded differences
- Scale-sensitive dimensions, uniform convergence, and learnability
- A framework for structural risk minimisation
- Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation
- Distribution-free performance bounds for potential function rules
- Generalization Performance of Classifiers in Terms of Observed Covering Numbers
- Self bounding learning algorithms
- A Unified Framework for Regularization Networks and Support Vector Machines