Rademacher complexity of a Lipschitz class: Are the boundedness constraints necessary?

Question

Consider the following function class: $F={f:R^d\rightarrow [a,b], f(x)=\sigma(w^Tx)}$ where $\sigma(.)$ is Lipschitz, and $w\in R^d$ is a parameter vector. The problem I'm working on is a machine learning problem where $w$ is estimated from from some data, and we can assume that there is enough data to estimate it well. (An example of this would be logistic regression.)

I am interested in $\hat{R}_N(F)$, the empirical Rademacher complexity of F. I have found upperbounds when $w$ is constrained to lie in a pre-defined ball and the data is also constrained to lie in a ball. But I cannot find anything when there is no such constraint. (If the function values were in ${0/1}$ and work with the 0/1 loss then I could use the classical VC bound, but I wouldn't like to modify the problem.)

• Is there any known technique to estimate / bound $\hat{R}_N(F)$ for the $F$ above?

• If not, is there any known explanation of why not? (is $\hat{R}_N(F)$ not guaranteed to be finite?)

• What if we modify $F$ so that $\forall f\in F, \|w\|<B$ but do not constrain the input space to be bounded?

Answer 1

If $w$ is unbounded then any nonzero sum can be dilated to an arbitrary value, so you must have some bounds on it.

If the range of $x$ is not bounded then you will not be able to give a uniform bound on $\hat R_n(F)$ for the same reason (any bound that holds for a particular $x\in R^d$ will break down when $x$ is multiplied by a sufficiently large scalar.