# Uniform Convergence for Vectors

$\textbf{Problem statement:}$

Let $\mathcal H:\mathcal X \rightarrow \{0,1\}$ be a class of Boolean functions for $\mathcal X \subset \mathbb R^n$, and let the VC Dimension of $\mathcal H$ be $VC_{dim}(\mathcal H)=d < \infty$. For every binary vector $(a,b)$, we define the normalization function $g$ as follows:

$$g(a,b)= \begin{cases} \frac {(a,b)}{|a+b|} & a+b>0 \\ (0,0) &a+b = 0 \end{cases}.$$

Let $\mathcal F \triangleq g \circ (\mathcal H \times \mathcal H)$, such that $f(x)=g(h_1(x),h_2(x))$, for every $x\in \mathcal X$ and $h_1,h_2\in \mathcal H$.

Let $\mathcal D$ be a measure over $\mathcal X$. For all $f\in \mathcal F$ define: $$L_\mathcal D(f)=\int_{\mathcal X}f(x)d\mathcal D.$$ In addition, for a sample $\mathcal S$ drawn i.i.d. from $\mathcal D$ of size $m$, we define

$$\hat L_\mathcal S(f)=\frac 1 m \sum_{i=1}^m f(x_i).$$

Congrats if you got so far :). I wish to bound $$\Pr_{\mathcal S \sim \mathcal D^m}\left( \sup_{f\in \mathcal F} \mid\mid{L_\mathcal D(f) - \hat L_\mathcal S(f)\mid\mid}_1 \geq \epsilon\right)$$

as a function of $m,\epsilon$ and $d$. I am not sure how to use the $VC$ dimension in order to do so, nor how to use standard uniform convergence arguments.

Any ideas?

• I'm confused -- is the argument to $g$ a single vector or a pair of bits? – Aryeh Kontorovich Nov 22 '17 at 16:11
• Either would work, but I agree the latter makes more sense. I change it accordingly, thanks – omerbp Nov 22 '17 at 16:24
• How do you define $g(0,0)$? – Aryeh Kontorovich Nov 22 '17 at 16:53
• @AryehKontorovich to be zero vector, thanks again. – omerbp Nov 22 '17 at 16:57
• Got it thanks. Unless I’m missing something this should be simple, will hopefully write an answer soon (unless someone beats me to it). – Aryeh Kontorovich Nov 22 '17 at 17:15

Let $\tilde g(a,b)=(a,b)$ be the unnormalized'' version of $g$, define $\tilde f(x):=\tilde g(h_1(x),h_2(x))$, and note that $$\frac12 L_D(\tilde f) \le L_D(f) \le L_D(\tilde f)$$ where the inequality holds coordinate-wise; this is because $\frac12\tilde g\le g\le\tilde g$. Analogously, $\frac12 \hat L_S(\tilde f) \le \hat L_S(f) \le \hat L_S(\tilde f)$.

Now let $m=\Theta(\frac{d}{\epsilon^2}\log\frac1\delta)$ be large enough to guarantee that $$P\left\{ \sup_{h\in H} |L_D(h)-\hat L_S(h)|>\epsilon\right\}<\delta,$$ where $L_D(h),\hat L_S(h)$ are defined in the obvious way.

Thus, with probability $1-\delta$, each component of $L_D(\tilde f)$ is $\epsilon$-close to its empirical counterpart and their $\ell_1$-distance is at most $2\epsilon$.

It follows that for $m$ as chosen above, $$P\left\{ \sup_{f\in F} ||L_D(f)-\hat L_S(f)||>2\epsilon\right\}<\delta.$$

EDIT: This argument doesn't work. Note that the function $g$ is discontinuous on $[0,1]^2$: it maps $(x,x)$ to $(1/2,1/2)$, even for very small $x$. I'm not even sure I think convergence still holds, will have to think some more...

EDIT 2:

This may be an overkill, but at least I think it works. Let us bound the $\gamma$-fat shattering dimension of the function class $\mathcal{F}$, componentwise. Let $\mathcal{F}_1$ denote the set of all $u:\mathcal{X}\to[0,1]$ such that $f(x)\equiv (u(x),v(x))$ for some $f\in\mathcal{F}$. Note that $u$ can only take on the values $\{0,1/2,1\}$. It's easy to see that if $\mathcal{H}$ cannot shatter more than $d$ points, then $\mathcal{F}_1$ cannot $\gamma$-shatter more than $2d$ points, for any $\gamma>0$. (Certainly $\mathcal{F}_1$ cannot $(\gamma>1/2)$-shatter more than $d$ points, and the other component can contribute at most another $d$ points at scale $\gamma\le1/2$).

Once you have that the $\gamma$-shattering dimension of both components $\mathcal{F}_1$ (and the analogously defined an analyzed $\mathcal{F}_2$) is finite, standard uniform convergence results apply. In particular, $\hat L_S(f)$ converges to $L_D(f)$ componentwise, uniformly over $f\in\mathcal{F}$, at a distribution-free rate.

For specific rates, see e.g., Alon et al., Scale-sensitive Dimensions, Uniform Convergence, and Learnability: http://www.tau.ac.il/~nogaa/PDFS/learn3.pdf

• Thanks for the response. I can see why the last inequality holds if we replace $f$ with $\tilde f$ (as the text just above the inequality explains), but I fail to see why the inequality holds as you wrote it . Where did you use $\frac12\tilde g\le g\le\tilde g$? – omerbp Nov 27 '17 at 9:08
• It was used to establish the first large-display inequality. – Aryeh Kontorovich Nov 27 '17 at 10:35
• Could you please elaborate on why the last inequality holds for $f$? I can only see why it holds for $\tilde f$... – omerbp Nov 27 '17 at 10:37
• Because f is sandwiched between 1/2 tilde f and tilde f. – Aryeh Kontorovich Nov 27 '17 at 10:40
• You're right -- see my edit. – Aryeh Kontorovich Nov 28 '17 at 9:57