Uniform Convergence

Definition

$R_n(f)$ converges to $R(f)$ uniformly over $\mathcal{F}$ if $\forall \epsilon >0:{\lim }_{n\to \infty }P({\sup }_{f\in \mathcal{F}}|R_n(f)-R(f)|>\epsilon )=0$.

Formula

$$P(|R(f_n)-R(f_{\mathcal{F}})|\ge \epsilon )\le P(\underset{f\in \mathcal{F}}{\sup }|R(f)-R_n(f)|\ge \epsilon /2)$$

• Sufficient for consistency of ERM (Proposition 6, via $R_n(f_n)\le R_n(f_{\mathcal{F}})$), and also necessary (Vapnik and Chervonenkis 1971).
• It solves the problem of Lecture 1.2: the data-dependent $f_n$ is covered because the bound holds for all $f$ at once.
• Controlled by the size of $\mathcal{F}$: number of functions, shattering coefficient, VC dimension, Rademacher complexity.

Appears in

• Lecture 3, definition and Proposition 6
• Lecture 3, Theorem 7
• Lecture 1.2, why the LLN alone is not enough

Related concepts

• Consistency
• Generalization Bound
• Empirical Risk Minimization