uniform convergence bounds

Uniform convergence (UC) are a type of worst case, high probability concentration inequality that one might prove for a class of functions $\mathcal{F}$. Let $\mathcal{F}$ consist of some set of functions $f:\mathcal{X}\to \mathbb{R}$ (could replace $\mathbb{R}$ with any Banach space in theory, but that’s rarely done). A UC bound has the form:

$$\mathbb{P}\left(\underset{f\in \mathcal{F}}{\sup }|P_{n}f-Pf|\ge ϵ\right)\le \delta ,$$

where $P_{n}f=\frac{1}{n}{\sum }_{i\le n}f(X_i)$ and $Pf=\mathbb{E}f(X)$ and $X_1,\dots ,X_n\sim \mathbb{P}$ are random variables.

Uniform convergence bounds are applied in empirical process theory to show that $\mathcal{F}$ is a Glivenko-Cantelli class, for instance. They’re also applied in learning theory, eg PAC learning, to give finite-sample bounds on estimators.

Depending on the problem, we might find $ϵ$ or $\delta$ first. Eg, that bound might have the form “for all $ϵ>0$, there exists some $\delta =\delta (ϵ,n)$ that goes to 0 as $n\to \infty$” which implies that we obtain convergence in probability of ${\sup }_f|P_{n}f-Pf|$. This would be the case when showing that $\mathcal{F}$ is a Glivenko-Cantelli class. But in PAC learning, we usually want to fix $\delta$ first, and then find $ϵ=ϵ(\delta ,n)$ such that ${\sup }_f|P_{n}f-Pf|\le ϵ$.

As is common in empirical process theory, $ϵ$ will typically depend on some notion of complexity of $\mathcal{F}$, such as covering numbers, VC dimension, or Rademacher complexity.