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. 



Request for references about computing or estimating Rademacher complexity
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?](https://mathoverflow.net/questions/186693/rademacher-complexity-of-a-lipschitz-class-are-the-boundedness-constraints-nece/187392#187392)


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>


