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

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.

Subject Categories:

  • Theoretical Mathematics
  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE