Uniform Convergence for Vectors

Question

$\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?

Answer 1

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