Return to 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)= \frac {(a,b)}{|a+b|}.$$

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?

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

$\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)= \frac {(a,b)}{|a+b|}.$$

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 to use the $VC$ dimension in order to do so, nor how to use standard uniform convergence arguments.

Any ideas?

$\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)= \frac {(a,b)}{|a+b|}.$$

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?