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

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


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

  • $\begingroup$ 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$? $\endgroup$
    – omerbp
    Nov 27 '17 at 9:08
  • $\begingroup$ It was used to establish the first large-display inequality. $\endgroup$ Nov 27 '17 at 10:35
  • $\begingroup$ Could you please elaborate on why the last inequality holds for $f$? I can only see why it holds for $\tilde f$... $\endgroup$
    – omerbp
    Nov 27 '17 at 10:37
  • $\begingroup$ Because f is sandwiched between 1/2 tilde f and tilde f. $\endgroup$ Nov 27 '17 at 10:40
  • 1
    $\begingroup$ You're right -- see my edit. $\endgroup$ Nov 28 '17 at 9:57

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.