4.5 Article

Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization

Journal

ADVANCES IN COMPUTATIONAL MATHEMATICS
Volume 25, Issue 1-3, Pages 161-193

Publisher

SPRINGER
DOI: 10.1007/s10444-004-7634-z

Keywords

stability; inverse problems; generalization; consistency; empirical risk minimization; uniform Glivenko-Cantelli

Ask authors/readers for more resources

Solutions of learning problems by Empirical Risk Minimization (ERM) - and almost-ERM when the minimizer does not exist - need to be consistent, so that they may be predictive. They also need to be well-posed in the sense of being stable, so that they might be used robustly. We propose a statistical form of stability, defined as leave-one-out (LOO) stability. We prove that for bounded loss classes LOO stability is (a) sufficient for generalization, that is convergence in probability of the empirical error to the expected error, for any algorithm satisfying it and, (b) necessary and sufficient for consistency of ERM. Thus LOO stability is a weak form of stability that represents a sufficient condition for generalization for symmetric learning algorithms while subsuming the classical conditions for consistency of ERM. In particular, we conclude that a certain form of well-posedness and consistency are equivalent for ERM.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available