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.


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

  • $\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$ – Anirbit May 18 '16 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$ – Anirbit May 18 '16 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 May 18 '16 at 19:48
  • $\begingroup$ Yes to both your queries! $\endgroup$ – Anirbit May 18 '16 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 May 23 '16 at 15:42

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.