1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.