Some Properties of Empirical Risk Minimization Over Donsker Classes

Abstract

We study properties of algorithms which minimize (or almost-minimise) empirical error over a Donsker class of functions. we show that the L2-diameter of the set of almost-minimizers is converging to zero in probability. Therefore, as the number of samples grows, it is becoming unlikely that adding a point (or a number of points) to the training set will result in a large jump (in L2 distance) to a new hypothesis. We also show that under some conditions the expected errors of the almost-minimizers are becoming close with a rate faster than pi(exp -1/2).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2005
Accession Number
ADA454986

Entities

People

  • Alexander Rakhlin
  • Andrea Caponnetto

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Autonomy
  • Biomedical
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Artificial Intelligence
  • Cognitive Science
  • Computer Science
  • Contracts
  • Convergence
  • Covariance
  • Diameters
  • European Communities
  • Gaussian Processes
  • Learning
  • Machine Learning
  • Military Research
  • Numbers
  • Probability
  • Theorems

Readers

  • Approximation Theory.
  • Mathematical Modeling and Probability Theory.