An inequality for uniform deviations of sample averages from their means
type: Item
instance of: scholarly article
title: An inequality for uniform deviations of sample averages from their means
zbMATH Open document ID: 0974.62007
DOI: 10.1016/S0167-7152(98)00291-0
author: Gábor Lugosi
author: Peter L. Bartlett
published in: Statistics \& Probability Letters
publication date: 2001-12-12T00:00:00Z
review text: Let \(X_1,\dots,X_n\) be independent and identically distributed random variables with values in some arbitrary set \(\mathcal{X}\), and let \(\mathcal{F}\) be a class of uniformly bounded functions from \(\mathcal{X}\) to \([0,1]\). For \(f\in\mathcal{F}\), introduce the sample averages \(P_n(f)=n^{-1}\sum_{i=1}^nf(X_i)\) and the population means \(P(f)=E(f(X_1))\). The authors derive new exponential bounds on \[ P(\sup_{f\in\mathcal{F}}(P(f)-P_n(f)-\gamma)/\sqrt{P(f)}>\varepsilon) \] and \[ P(\sup_{f\in\mathcal{F}}(P_n(f)-P(f)-\gamma)/\sqrt{P_n(f)}>\varepsilon) \] which involve an appropriate expected coverage number to measure the size of the class \(\mathcal{F}\). These results are applied to obtain tight upper bounds for the loss of a decision selected by empirical loss minimization from a class of decisions.
Mathematics Subject Classification ID: 62C99
Mathematics Subject Classification ID: 60E15
zbMATH DE Number: 1395119
zbMATH Keywords: Vapnik-Chervonenkis inequality
zbMATH Keywords: uniform laws of large numbers
zbMATH Keywords: empirical risk minimization
MaRDI profile type: Publication
cites work: Probability inequalities for empirical processes and a law of the iterated logarithm
cites work: A result of Vapnik with applications
cites work: Covering numbers for real-valued function classes
cites work: Probability Inequalities for the Sum of Independent Random Variables
cites work: Q4183968
cites work: Bounds for the uniform deviation of empirical measures
cites work: A general lower bound on the number of examples needed for learning
cites work: Decision theoretic generalizations of the PAC model for neural net and other learning applications
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Convergence of stochastic processes
cites work: Q4856004
cites work: Sharper bounds for Gaussian and empirical processes
cites work: Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Q4770512
full work available at URL: s0167-7152(98)00291-0
OpenAlex ID: W2072059627
description: scientific article; zbMATH DE number 1395119