# Rademacher complexity of composition of functions

I am looking for a bound on the empirical Rademacher complexity of the following class: $G=\left\{x \rightarrow \frac{h^T f(x)}{\|h\|_2 \cdot \|f(x)\|_2} : h\in R^d, f()=(f_1(),\ldots,f_d()), f_j \in F \right\}$, where $F$ is some other function class.

$$\hat{R}_N(G) = E_\sigma \sup_{h\in R^d, \forall j, f_j\in F} \frac{1}{N} \left[ \sum_{n=1}^N \sigma_n \frac{h^T}{\|h\|}\cdot \frac{f(x_n)}{\|f(x_n)\|}\right] \le \text{?}$$

where $\sigma=(\sigma_1,\ldots,\sigma_N)$ are i.i.d. Rademacher variables.

The special case of $F=\{x\rightarrow x-c : c\in R^d\}$ would also be of interest.

Is it possible to get better than assuming that $\min_n \|f(x_n)\}\|$ is bounded away from 0 and have $O(\sqrt{d}\hat{R}_N(F))$?

• In the definition of Rademacher complexity, the sup over the function class is inside the expectation over $\sigma$. You have it, incorrectly, on the outside. – Aryeh Kontorovich Apr 15 '17 at 22:44
• How do you define the Rademacher complexity of a vector-valued function class? – Aryeh Kontorovich Apr 17 '17 at 18:52
• That should have been $f_1$ one component only - fixed. – axk Apr 17 '17 at 19:36
• Why do you need to assume that $||f(x_n)||$ is bounded away from zero? Also, instead of the explicit normalization, you can just restrict the vectors $h$ and $f$ to belong to the unit ball -- it's cleaner that way. – Aryeh Kontorovich Apr 18 '17 at 14:13
• The explicit division by norms comes from the problem. But other than that any assumption that helps can be made. $\|f(x_n\|$ bounded away from 0 is not needed indeed, but when it comes to evaluate the remaining Rademacher complexity it may be useful, I thought. – axk Apr 18 '17 at 15:54

Assume that $h$ belongs to a set $H$, where each vector $v\in H$ satisfies $\sum_{i=1}^d |v_i|\le1$. Then any expression of the form $h\cdot \bar f$, where $\bar f=(f_1,\ldots,f_d)\in F^d$ belongs to the absolute convex hull of $F$. Thus, under the above assumption on $H$, we have $$\frac1n\mathbb{E}_\sigma \sup_{h\in H,(\bar f=f_1,\ldots,f_d)\in F^d}\sum_{i=1}^n \sigma_i h\cdot \bar f(x_i) \le r_F,$$ where $r_F$ is the Rademacher complexity of $F$. For a proof of this claim, see Theorem 3.3 here http://www.esaim-ps.org/articles/ps/pdf/2005/01/ps0420.pdf

Note that the bound is dimension-free (i.e., independent of $d$) and only depends on the $\ell_1$ norm of $h$ --- and, of course, the Rademacher complexity of $F$.

• That yes, but the 2-norm in the denominator will bring back the $\sqrt{d}$, I think? – axk Apr 18 '17 at 22:05
• Indeed. One can probably still do dimension-free but linear in $|H|$ (so only valid for finite $H$) -- would that be interesting? – Aryeh Kontorovich Apr 18 '17 at 22:11
• $H$ has to be infinite unfortunately. What I'm thinking, if there isn't anything better, is to simply assume $||h||_1/||h||_2 \cdot 1/||f||_2$ is bounded from above. – axk Apr 18 '17 at 22:16
• You only need to assume a bound on $||h||_1/||h||_2$; no need to assume anything of $f$ since you're assuming a black-box Rademacher bound on $F$. – Aryeh Kontorovich Apr 18 '17 at 22:18