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

  • 1
    $\begingroup$ 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. $\endgroup$ – Aryeh Kontorovich Apr 15 '17 at 22:44
  • $\begingroup$ How do you define the Rademacher complexity of a vector-valued function class? $\endgroup$ – Aryeh Kontorovich Apr 17 '17 at 18:52
  • $\begingroup$ That should have been $f_1$ one component only - fixed. $\endgroup$ – axk Apr 17 '17 at 19:36
  • $\begingroup$ 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. $\endgroup$ – Aryeh Kontorovich Apr 18 '17 at 14:13
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ That yes, but the 2-norm in the denominator will bring back the $\sqrt{d}$, I think? $\endgroup$ – axk Apr 18 '17 at 22:05
  • $\begingroup$ Indeed. One can probably still do dimension-free but linear in $|H|$ (so only valid for finite $H$) -- would that be interesting? $\endgroup$ – Aryeh Kontorovich Apr 18 '17 at 22:11
  • $\begingroup$ $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. $\endgroup$ – axk Apr 18 '17 at 22:16
  • 1
    $\begingroup$ 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$. $\endgroup$ – Aryeh Kontorovich Apr 18 '17 at 22:18

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.