2
$\begingroup$

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

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ That yes, but the 2-norm in the denominator will bring back the $\sqrt{d}$, I think? $\endgroup$
    – axk
    Apr 18, 2017 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$ Apr 18, 2017 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, 2017 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$ Apr 18, 2017 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.