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.

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
• 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$? – Aryeh Kontorovich May 18 '16 at 19:48