Return to Answer

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...

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

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. $$

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...

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. $$

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. $$