Uniform deviation for squared-projection slabs

The supremum is measurable. Fix $S$ with $d=\mathrm{\mid }S\mathrm{\mid }$. By [F9], rational vectors supported in $S$ can be enumerated by enumerating their finite tuples of rational indices in increasing sum; their nonzero normalizations form a countable subclass of $V_S$. For $u\in V_S$ and each $k\ge 1$, choose the first rational tuple $q_k$ in that enumeration satisfying $\mathrm{\mid }(q_k{)}_i-u_i\mathrm{\mid }<1\mathrm{/}(4d{k}^2)$ for $i\in S$. Such a tuple exists by rational density, and $\mathrm{\parallel }{q}_k-u{\mathrm{\parallel }}_2<1\mathrm{/}(4k^2)$, so $q_k\mathrm{\ne }0$. With $u_k=q_k\mathrm{/}\mathrm{\parallel }{q}_k{\mathrm{\parallel }}_2$, [F7] gives $\mathrm{\parallel }{u}_k-u{\mathrm{\parallel }}_2\le \mathrm{\mid }1-\mathrm{\parallel }{q}_k{\mathrm{\parallel }}_2\mathrm{\mid }+\mathrm{\parallel }{q}_k-u{\mathrm{\parallel }}_2\le 2\mathrm{\parallel }{q}_k-u{\mathrm{\parallel }}_2\le k^{-2}$. For $t\ge 0$, choose the first rational $t_k\in (t+1\mathrm{/}k,t+2\mathrm{/}k)$ in the fixed enumeration. Cauchy--Schwarz yields $\mathrm{\mid }(u_k^{T}x{)}^2-(u^{T}x{)}^2\mathrm{\mid }\le 2\mathrm{\parallel }x{\mathrm{\parallel }}_2^2{k}^{-2}\mathrm{.}$ Thus ${\mathbf{1}}_{A_{u_k,t_k}}(x)\to {\mathbf{1}}_{A_{u,t}}(x)$ for every $x$, including boundary points: at equality the threshold margin $1\mathrm{/}k$ eventually exceeds this error, while away from equality convergence preserves the strict sign. By [F3] their $P$-probabilities converge; finite empirical probabilities converge too. Negative thresholds give the empty set, already represented by rational thresholds. Hence the supremum equals that over the countable subclass of normalized rational vectors and rational thresholds, and is measurable. The first-element rules use no choice axiom.

Fix a support $S$ of size $k\le s$. Trace patterns of affine halfspaces on $r$ fixed points are sign patterns of $r$ affine hyperplanes in a $(k+1)$-dimensional parameter space. The number of open regions is at most ${\sum }_{\mathrm{\ell }=0}^{k+1}\left(\genfrac{}{}{0px}{}{r}{\mathrm{\ell }}\right)$: adding one hyperplane creates at most the number of regions cut on that hyperplane, so induction on $r$ and the dimension gives Pascal's recurrence and this sum. Weak-boundary traces are also counted, since on a finite point set a halfspace threshold can be increased slightly without changing its trace.

A slab $A_{u,t}$ with $t\ge 0$ is the intersection of the halfspaces $u^{T}x\le \sqrt{t}$ and $-u^{T}x\le \sqrt{t}$ in the same $k$ coordinates; when $t<0$ it is empty. Hence its trace count on $r$ points is at most $({\sum }_{\mathrm{\ell }=0}^{k+1}\left(\genfrac{}{}{0px}{}{r}{\mathrm{\ell }}\right){)}^2$. For $r\ge q:=k+1$, set $x=q\mathrm{/}r$. Since $x^{\mathrm{\ell }}\ge x^q$ for $\mathrm{\ell }\le q$, ${\sum }_{\mathrm{\ell }=0}^q\left(\genfrac{}{}{0px}{}{r}{\mathrm{\ell }}\right)\le x^{-q}(1+x{)}^r\le (er\mathrm{/}q{)}^q\mathrm{.}$ If $r\ge 16q$, then $2^r>(er\mathrm{/}q{)}^{2q}$: the logarithmic difference is positive at $r\mathrm{/}q=16$ and has positive derivative thereafter. Thus $r$ points cannot be shattered by the slab class, so its VC dimension is at most $16(k+1)\le 16(s+1)$.

Let ${\epsilon }_i$ be independent uniform signs, independent of the sample, and let $X_1^{\mathrm{\prime }},\dots ,X_N^{\mathrm{\prime }}$ be an independent copy. Jensen's inequality [F5], conditional on the original sample, gives $\mathbb{E}{\sup }_A\mathrm{\mid }{P}_N(A)-P(A)\mathrm{\mid }\le \mathbb{E}{\sup }_A\mathrm{\mid }{P}_N(A)-P_N^{\mathrm{\prime }}(A)\mathrm{\mid }\mathrm{.}$ Each pair $(X_i,X_i^{\mathrm{\prime }})$ is exchangeable, so independently swapping its coordinates with sign ${\epsilon }_i$ leaves the joint law unchanged. The triangle inequality then gives $\mathbb{E}{\sup }_A\mathrm{\mid }{P}_N(A)-P(A)\mathrm{\mid }\le 2\mathbb{E}{\sup }_A\mid N^{-1}{\sum }_{i=1}^N{\epsilon }_i{\mathbf{1}}_A(X_i)\mid \mathrm{.}$ The ghost sample and signs exist on finite product spaces by [F6]; all suprema use the countable class from step 1.1.

Replacing one observation changes every empirical set probability by at most $1\mathrm{/}N$, so the supremum $F$ changes by at most $1\mathrm{/}N$. In the Doob martingale of $F$, each conditional increment therefore has a range of width at most $1\mathrm{/}N$. If a random variable lies in an interval of width $c$, the log-mgf of its centered version has second derivative equal to a tilted variance at most $c^2\mathrm{/}4$; integrating twice gives $\mathbb{E}{e}^{\lambda (Y-\mathbb{E}Y)}\le e^{{\lambda }^2{c}^2\mathrm{/}8}$. Iterating these bounds and optimizing the exponential Markov inequality yields $\mathbb{P}(F-\mathbb{E}F>t)\le e^{-2N{t}^2}$.

On a fixed $N$-point sample the trace class is finite. For $0<\rho \le 1$, if $M$ traces are pairwise separated by more than $\rho$ in $d(A,B)=\sqrt{P_N(A\mathrm{△}B)}$, sample $r=\lceil 3{\rho }^{-2}\log (2M)\rceil$ coordinates uniformly with replacement. For a fixed pair the probability that the traces agree at all sampled coordinates is at most $e^{-r{\rho }^2}$; a union bound over pairs shows that some coordinate sample distinguishes all $M$ traces. Put $D=16(s+1)$. If $r<D$, then $M\le 2^r\le 2^D$. If $r\ge D$, step 2.1 bounds the trace count by $(er\mathrm{/}q{)}^{2q}\le (er\mathrm{/}D{)}^{2D}$, where $q=\mathrm{\mid }S\mathrm{\mid }+1\le D$; the inequality follows because $a\mapsto a\log (er\mathrm{/}a)$ is increasing for $0<a\le r$. Writing $y=\log (M)\mathrm{/}D$, the choice of $r$ gives $r\le C{\rho }^{-2}D(y+1)$ and hence $y\le 2\log (C{\rho }^{-2}(y+1))$. Put $A=\log (C{\rho }^{-2})\ge 1$. If $y\ge 10$, then $\log (y+1)\le y\mathrm{/}4$, so $y\le 4A$; if $y<10$, then $y<10A$. Thus $y\le 10A\le 20\log (C_0\mathrm{/}\rho )$ for a universal $C_0$. After increasing $C_0$, the same bound covers $r<D$. A maximal $\rho$-separated set is a $\rho$-net, so $\mathcal{N}(\rho )\le (C_0\mathrm{/}\rho {)}^{20D}$.

To obtain the sign MGF bound used for chaining, for $t\ge 0$ put $h(t)=t-\tanh t$. Then $h(0)=0$ and $h^{\mathrm{\prime }}(t)=1-{\mathrm{sech}}^{2}t={\tanh }^{2}t\ge 0$ by [F8]; the mean value theorem gives $h(t)\ge 0$. Put $g(t)=t^2\mathrm{/}2-\log (\cosh t)$. Then $g(0)=0$ and $g^{\mathrm{\prime }}(t)=h(t)\ge 0$, so $g(t)\ge 0$; evenness extends the bound to every real $t$. Hence $\cosh t\le e^{t^2\mathrm{/}2}$. Conditional on the sample, the sign process $Z_A=N^{-1}{\sum }_i{\epsilon }_i{\mathbf{1}}_A(X_i)$ therefore has increments satisfying ${\mathbb{E}}_{\epsilon }{e}^{\lambda (Z_A-Z_B)}\le e^{{\lambda }^{2}d(A,B{)}^2\mathrm{/}(2N)}$, by multiplying the independent sign MGFs with coefficients $\lambda ({\mathbf{1}}_A(X_i)-{\mathbf{1}}_B(X_i))\mathrm{/}N$. Choose empirical $L^2$ nets $T_j$ at radii $2^{-j}$. Telescope each trace through its nearest net points; adjacent levels differ by at most $3\cdot 2^{-j}$ in $d$. For $L$ centered sub-Gaussian variables with common proxy ${\sigma }^2$, $\mathbb{E}{\max }_{\mathrm{\ell }\le L}\mathrm{\mid }{W}_{\mathrm{\ell }}\mathrm{\mid }\le \sigma \sqrt{2\log (2L)}$ follows by Jensen's inequality applied to the log-sum-exp of $e^{\lambda W_{\mathrm{\ell }}}$ and $e^{-\lambda W_{\mathrm{\ell }}}$, followed by minimization in $\lambda$. Thus the conditional expected supremum is at most $\frac{C}{\sqrt{N}}(1+{\sum }_{j\ge 1}{2}^{-j}\sqrt{\log (2\mathcal{N}(2^{-j})\mathcal{N}(2^{-j+1}))})\mathrm{.}$ The finite trace class makes the sum terminate.

From step 3.1, $\log \mathcal{N}(\rho )\le 20D\log (C_0\mathrm{/}\rho )$. Therefore the dyadic sum in step 4.1 is at most $C\sqrt{D}{\sum }_{j\ge 1}{2}^{-j}\sqrt{j+1}\le C^{\mathrm{\prime }}\sqrt{D}$; the base trace contributes at most $N^{-1\mathrm{/}2}$ by Cauchy--Schwarz. Combining the symmetrization bound from step 2.2 with the chaining bound from step 4.1 yields $\mathbb{E}{\sup }_A\mathrm{\mid }{P}_N(A)-P(A)\mathrm{\mid }\le C^{\mathrm{\prime }\mathrm{\prime }}\sqrt{(s+1)\mathrm{/}N}$.

Apply step 2.3 with $t=\sqrt{\log (m\mathrm{/}\delta )\mathrm{/}(2N)}$ separately to each support class and take a union bound over its $m$ supports. Combining with step 5.1 proves the displayed probability bound after increasing the universal constant $C$.

For any $u,t$, $\{x:\mathrm{\mid }{u}^{T}x{\mathrm{\mid }}^2<t\}={\bigcup }_{k\ge 1}\{x:\mathrm{\mid }{u}^{T}x{\mathrm{\mid }}^2\le t-1\mathrm{/}k\},$ an increasing union. Continuity from below [F4] makes both $P$ and $P_N$ probabilities converge to those of the strict lower-tail set. The deviation bound in step 6.1 holds at every threshold, so it passes to this limit. Taking complements gives the same bound for the upper weak tails $\{\mathrm{\mid }{u}^{T}x{\mathrm{\mid }}^2\ge t\}$.