Stability Results in Learning Theory

Abstract

The problem of proving generalization bounds for the performance of learning algorithms can be formulated as a problem of bounding the bias and variance of estimators of the expected error. We show how various stability assumptions can be employed for this purpose. We provide a necessary and sufficient stability condition for bounding the bias and variance for the Empirical Risk Minimization algorithm, and various sufficient conditions for bounding bias and variance of estimators for general algorithms. We discuss settings in which it is possible to obtain exponential bounds, and we prove an extension of the bounded-difference inequality for "almost always" stable algorithms.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 22, 2005
Accession Number
ADA454919

Entities

People

  • Alexander Rakhlin
  • Sayan Mukherjee
  • Tomaso Poggio

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Biomedical

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Cognitive Science
  • Computer Science
  • Contracts
  • Convergence
  • Corporations
  • Decomposition
  • Errors
  • Estimators
  • Inequalities
  • Learning
  • Military Research
  • Probability
  • Random Variables
  • Stability Conditions
  • Statistics

Readers

  • Approximation Theory.
  • Operations Research