lemmaroutine

Sampled points rarely hide in light boxes

Lemma·com:ghost·§6.1 From sampled histories to the actual point

Statement (paper)

Let ν\nu be a probability measure on a finite product set and let X1,…,XkX_1,\ldots,X_k be independent samples from ν\nu. For 0<α<10<\alpha<1 and kα≥8k\alpha\ge8, P(∃y:ν(Ry)<1−α, X1,…,Xk∈Ry)≤2(2k+1)2 2−kα/2. \Prob\bigl(\exists y:\nu(R_y)<1-\alpha, \ X_1,\ldots,X_k\in R_y\bigr) \le 2(2k+1)^2\,2^{-k\alpha/2}. Consequently, when kk is sufficiently large, the templates in satisfy P(∃y∈Yθ:ν~q(Ry)<1−k−1/4∣q)≤4(2k+1)2 2−k3/4/2 \Prob\bigl(\exists y\in\mathcal Y_\theta: \widetilde\nu_q(R_y)<1-k^{-1/4}\mid q\bigr) \le 4(2k+1)^2\,2^{-k^{3/4}/2} at each level, uniformly in qq.

In plain English

If X1,…,XkX_1,\ldots,X_k are independent samples from a probability measure ν\nu on a finite product set and kα≥8k\alpha\ge 8, then with probability at most 2(2k+1)22−kα/22(2k+1)^2 2^{-k\alpha/2} some RyR_y with ν(Ry)<1−α\nu(R_y)<1-\alpha contains all kk samples. For α=k−1/4\alpha=k^{-1/4} and large kk, this gives that, conditionally on qq, some template y∈Yθy\in\mathcal Y_\theta has ν~q(Ry)<1−k−1/4\widetilde\nu_q(R_y)<1-k^{-1/4} with probability at most 4(2k+1)22−k3/4/24(2k+1)^2 2^{-k^{3/4}/2}, uniformly in qq.

Why it's here

This is a union-bound-style "ghost" estimate: a set RyR_y that misses mass more than α\alpha is very unlikely to contain all kk independent samples, and the number of distinct sets RyR_y visible on the samples is only polynomial in kk, which the factor (2k+1)2(2k+1)^2 absorbs. It lets the later argument assume that every template consistent with the sampled history carries almost all of the measure, so the sampled history can stand in for the actual point.
Classified routine:
A standard VC-type ghost-sample/symmetrization estimate with a polynomial shatter-function bound, as in Vapnik–Chervonenkis uniform convergence and epsilon-net arguments (Haussler–Welzl); the paper only specializes it to its boxes R_y and to the choice alpha = k^{-1/4}.

Uses

Nothing else in the paper

Used by

claimSlice score lower bound via classification

Sources

PaperOpen
Section
§6.1 From sampled histories to the actual point
Page
—
Label
com:ghost
Line
sections/05-common-levels.tex:53
Leannot aligned

Phase 2 aligns this node to a Lean declaration.