Proof for asymptotic error in logistic regression

Question

Ng, A.Y., and Jordan, M.I. (2001). On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes. Advances in Neural Information Processing Systems, 14, pp. 841-8, MIT Press.

In the paper above, the author lists two propositions (1 & 2) saying that the asymptotical error of discriminative classifiers (e.g. logistic regression) is smaller than the one of generative classifiers (e.g. naive bayes). To prove it, the auther says, that "since the asymptotical error of h-dis converges to the one of the infimum of all linear classifiers, it must therefore asymptotically no worse than naive bayes". - How do we know, that logistic regression converges to that infimum?

The second proposition gives an estimate about the error of logistic regression. - Here I can't find out the theory about convergence bounds and the VC Dimensions. I checked out the book "Statistical Learning Threory" -Vapnik , but without success

Is anybody able to help me to find/prove those two propositions?

Answer 1

Proposition 1 is sort of a tautology. They are assuming that the generative classifier is comparing a linear (more accurately affine) function with a threshold to determine the class of the observation. Consider just their continuous example. They say this (near the bottom of page 2)

Note that this method is equivalent to Normal Discriminant Analysis assuming diagonal covariance matrices.

Reading around this statement, it is clear that they are assuming the variances to be the same under the two classes, so the classifier just reduces to the Linear Discriminant Analysis, that is, $$ h_{Gen}(x) = 1\{ \hat \beta^T x + \hat b \ge 0\} $$ for some estimated vector $\hat \beta$ and scalar $\hat b$. Instead of their $\{T,F\}$, I am using $\{0,1\}$. The discriminative classifer also has this form
$$ h_{Dis}(x) = 1\{ \tilde \beta^T x + \tilde b \ge 0\} $$ for some estimated vector $\tilde \beta$ and scalar $\tilde b$. By their definition, in the discriminative case, these two estimates are obtained by minimizing the population level ($\infty$ sample size) zero-one loss, that is, $$ (\tilde \beta, \tilde b) = \arg \min_{\beta, b} \mathbb P\big( h_{\beta, b}(x) \neq y\big) $$ where $h_{\beta,b}(x) := 1\{ \beta^T x + b \ge 0\}$. Thus, by definition, $$ \mathbb P\big( h_{\tilde \beta, \tilde b}(x) \neq y) \le \mathbb P\big( h_{\beta, b}(x) \neq y), \quad \forall \beta, b. $$ In particular, $$ \mathbb P\big( h_{\tilde \beta, \tilde b}(x) \neq y) \le \mathbb P\big( h_{\hat \beta, \hat b}(x) \neq y), $$ (where the expectation is only w.r.t. $(x,y)$ not the training data), that is, $$\mathbb P\big( h_{Dis}(x) \neq y) \le \mathbb P\big( h_{Gen}(x) \neq y).$$ Q.E.D. (Note that there is no convergence in their Prop. 1, everything is defined and stated for the population, $\infty$-sample-size, case).

In short, for the mathematically inclined, $h_{Dis}$, by their definition is the minimizer of $h \mapsto \mathbb P(h(x) \neq y)$ over the class of functions $\mathcal H = \{h_{\beta, b} :\; \beta \in \mathbb R^d, b \in \mathbb R\}$ and $h_{Gen} \in \mathcal H$ again by definition. Hence, the inequality is an almost tautology.

For the second proposition, I would search using these keywords "generalization bounds for empirical risk minimization" or "lecture notes on statistical learning", etc.