# Uniform convergence for a class of finite dimension

The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. Convergence of Stochastic Processes. Springer, 1984. However, I have trouble finding the proof. Anyone knows a reference?

Let $$\Phi$$ be a distribution over $$\mathcal{X}$$. With probability $$1-\delta$$ over $$x_1,...,x_N\sim\Phi$$, for all $$a\in\mathcal{A}$$ it holds that $$\left|\frac{1}{N}\sum\limits_{i=1}^na(x_i)-\mathbb{E}_{x\sim\Phi} a(x)\right|\le\sqrt{\frac{2d}{N}\ln\frac{eN}{d}}+\sqrt{\frac{1}{2N}\ln\frac{2}{\delta}}$$

where $$\mathcal{A}: \mathcal{X} \rightarrow \mathbb{R}$$ is a set of real-valued functions and $$d$$ is the psuedo-dimensionof $$\mathcal{A}$$.

• Please credit the original source where you copied this from. Also, we ask that you avoid using images for the content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX.
– D.W.
Commented May 5, 2021 at 18:07
• Please make your question self-contained, and define all notation. What is Pdim? What is $\mathcal{A}$?
– D.W.
Commented May 5, 2021 at 18:08
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– D.W.
Commented May 5, 2021 at 18:09
• – D.W.
Commented May 5, 2021 at 18:10

The keyword to look for is Dudley's chaining integral, see e.g. Vershynin's book "High Dimensional Probability" which contains a chapter on the chaining technique. Chaining allows us to bound the empirical Rademacher complexity in terms of the empirical $$L_2$$ covering numbers of $$\mathcal{A}$$. Your result is directly obtained from the chaining integral and a result (which is think is credited to Dudley-Pollard) which relates the $$L_1$$ covering numbers (irrespective of the distribution) to the pseudo dimension, see e.g. theorem 4.2 in these notes. You still need to go from $$L_2$$ covering to $$L_1$$ somehow, this is easy when the functions are binary valued.