# Rademacher complexity of logistic regression

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)$.

• I don't understand your question. Rademacher definition is general for any function: web.engr.illinois.edu/~khashab2/learn/rademacher.pdf – Daniel Nov 9 '14 at 18:20
• When we can find the VC-dimension of logistic regression directly why do we need to bound it using Rademacher sum? – Daniel Nov 10 '14 at 8:05
• Or maybe I am still not getting what you are saying... – Daniel Nov 10 '14 at 8:06
• If we could find a good VC bound then we wouldn't need a Rademacher bound. – axk Nov 10 '14 at 8:09
• 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 – Daniel Nov 10 '14 at 8:13