Consider logistic regression. We have the logistic loss function, $\phi: R\rightarrow [0,1], \phi(u)=\log(1+\exp(-u))$, which is Lipschitz, and we have the linear function class $F=\{f_w:R^d \rightarrow R, f_w(x)=w^Tx, \forall x\in R^d\}$. Given a training set, $S=\{(x_1,y_1),...,(x_N,y_N)\}$, we do empirical risk minimization to estimate the parameter $\hat{w}$: $\hat{f}_{\hat{w}} = argmin_{f_w} \sum_{n=1}^N\phi(y_nf_w(x_n))$.

I am interested in a bound on the generalisation error of of $\hat{f}_{\hat{w}}$. Can this be obtained using Rademacher complexities without introducing restrictions of boundedness on the parameter space and on the input space? Alternatively, I would also be interested in a VC bound (since no such boundedness assumptions would be needed), but as far as I understand, for that I would need to use hard-thresholded values of the values of $f$ and work with the 0/1 loss (which is different from what the ERM algorithm is optimising).

The Rademacher approach that I was able to find unfortunately makes the following modification to the problem: It assumes that $\forall f\in F, \|f\|_\infty < B$ for some $0<B<\infty$. The function class is hence replaced with another one: $F_{trunc}=\{f_w:S^{d-1} \rightarrow [-B,B], f_w(x)=w^Tx, \forall x\in S^{d-1}; \|w\|<B \}$. I understand this is related to regularisation.

My problem is that this modification doesn't suit the problem that I am working on, and I wonder if there is any way to avoid it. I can see that it would be very convenient for the Rademacher complexity based bounding technique, since then by the Ledoux-Talagrand contraction inequality we get $\hat{R}_N(\phi\circ F_{trunc})\le L_{\phi}\hat{R}_N(F_{trunc})$ (where $\hat{R}_N(.)$ denotes the empirical Rademacher complexity, $N$ is the number of training points, and $L_{\phi}$ is the Lipschitz constant of $\phi$), and $\hat{R}_N(F_{trunc})$ can be estimated neatly as $\hat{R}_N(F_{trunc})\le B/\sqrt{N}$. However, I am interested in $\hat{R}_N(\phi\circ F)$.

  • 1
    $\begingroup$ I don't understand your question. Rademacher definition is general for any function: web.engr.illinois.edu/~khashab2/learn/rademacher.pdf $\endgroup$ – Daniel Nov 9 '14 at 18:20
  • 1
    $\begingroup$ When we can find the VC-dimension of logistic regression directly why do we need to bound it using Rademacher sum? $\endgroup$ – Daniel Nov 10 '14 at 8:05
  • $\begingroup$ Or maybe I am still not getting what you are saying... $\endgroup$ – Daniel Nov 10 '14 at 8:06
  • $\begingroup$ If we could find a good VC bound then we wouldn't need a Rademacher bound. $\endgroup$ – axk Nov 10 '14 at 8:09
  • 3
    $\begingroup$ Rademacher sum is one way to bound VC-dimension based risk. But for logistic regression why not finding the generalization bound directly? Have you seen the derivations to find the generalization bound in this? ai.stanford.edu/~ang/papers/nips01-discriminativegenerative.pdf $\endgroup$ – Daniel Nov 10 '14 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.