0
$\begingroup$

Is Rademacher complexity defined for any space of functions? Or are there restrictions on the function space over which this can be defined?

For example is the Rademacher complexity defined or has it been computed over say the space of all polynomials in $n$ variables? I would be most happy to get some references towards this specific example.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In order for the Rademacher complexity to be finite, you need to restrict both the domain (say, to a cube or a ball) and the range (say, by restricting the magnitude of the coefficients): Rademacher complexity of a Lipschitz class: Are the boundedness constraints necessary?

Once you bound the domain and restrict the coefficients, you have a uniformly Lipscthiz function family. Its Rademacher complexity can be upper-bounded in terms of (1) sequence length (usually denoted $n$, but for you it's the number of variables) (2) diameter $D$ of the domain (3) Lipschitz constant $L$ (4) dimension (which is the same as the number of variables). See Thm. 18 and Example 4 in: http://www.jmlr.org/papers/volume5/luxburg04b/luxburg04b.pdf

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the helpful references! So is anything specifically known about the Rademacher complexity of the set of all polynomials? (or any specific subset of them?) Can I hope that some simplification would occur for this set as compared to the corresponding number for what these papers are assuming i.e all Lipschitz functions of maybe bounded norm? $\endgroup$
    – Student
    Commented May 18, 2016 at 18:41
  • $\begingroup$ Oh! Wow! Turns out I was infact looking at your paper when I was writing this question, arxiv.org/pdf/1111.4470.pdf :D $\endgroup$
    – Student
    Commented May 18, 2016 at 19:11
  • $\begingroup$ Re: your question about the Rademacher complexity of $n$-variate polynomials. Do you prefer to work on a cube or a sphere (or another kind of bounded set)? Are you OK with restricting all of the coefficients to have absolute value bounded by, say $K$? $\endgroup$
    – Aryeh Kontorovich
    Commented May 18, 2016 at 19:48
  • $\begingroup$ Yes to both your queries! $\endgroup$
    – Student
    Commented May 18, 2016 at 23:53
  • $\begingroup$ Hi, perhaps you can contact me off-line via email so we can discuss the precise nature of the result you're looking for... $\endgroup$
    – Aryeh Kontorovich
    Commented May 23, 2016 at 15:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .