2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    May 5 at 18:07
  • 1
    $\begingroup$ Please make your question self-contained, and define all notation. What is Pdim? What is $\mathcal{A}$? $\endgroup$
    – D.W.
    May 5 at 18:08
  • 1
    $\begingroup$ 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! $\endgroup$
    – D.W.
    May 5 at 18:09
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/139919/755, mathoverflow.net/q/391973/37212. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    May 5 at 18:10
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.