Uniform convergence for a class of finite dimension

Question

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}$.

Answer 1

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.