Accession Number:
ADA459857
Title:
Statistical Learning: Stability is Sufficient for Generalization and Necessary and Sufficient for Consistency of Empirical Risk Minimization
Descriptive Note:
Technical paper
Corporate Author:
MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB
Personal Author(s):
Report Date:
2004-01-01
Pagination or Media Count:
56.0
Abstract:
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 leave-one-out stability, called CVEEEloo stability. Our main new results are two. We prove that for bounded loss classes CVEEEloo 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 generalization and consistency of ERM. Thus CVEEEloo stability is a weak form of stability that represents a sufficient condition for generalization for general learning algorithms while subsuming the classical conditions for consistency of ERM. We discuss alternative forms of stability. In particular, we conclude that for ERM a certain form of well-posedness is equivalent to consistency.
Descriptors:
Subject Categories:
- Theoretical Mathematics
- Statistics and Probability