Why does logistic regression with a logarithmic cost function converge to the optimal classification?

Why does logistic regression with a logarithmic cost function converge to the optimum for the classification problem (i.e. minimum number of mislabeled training samples)?

Put differently, why is the optimum for the probabilities $$h_\Theta(x) = P(y = 1|x;\Theta)$$ equivalent to the optimum for the classification problem?

My line of thought

For the terminology and formulas, see Andrew Ng coursera course on machine learning (relevant slides: https://github.com/vkosuri/CourseraMachineLearning/blob/master/home/week-3/lectures/pdf/Lecture6.pdf).

If we use the convex cost function $$J(\Theta) = -1/m * \Sigma_{i=1}^m ( y^{(i)} log h_\Theta(x^{(i)}) + (1 - y^{(i)}) log (1 - h_\Theta(x^{(i)})) )$$, we exponentially penalize higher differences between $$h_\Theta(x)$$ and $$y$$. Thus this logistic regression optimizes the parameters $$\Theta$$ for the probabilities $$h_\Theta(x) = P(y = 1|x;\Theta)$$.

But for the (in this example binary) classification problem, we use a threshold of $$P=0.5$$ to decide whether a sample is classified as positive or negative. So the classification problem does not care whether $$P=0.4$$ or $$P=0$$, however the cost function makes an exponential distinction. Thus I do not understand why logistic regression with a logarithmic cost function also converges to the optimum for the classification problem.

For example, $$\Theta$$ that yields many samples with $$h_\Theta(x)=0.4$$ and $$y=1$$, has lower cost (due to the exponential distinction) compared to $$\Theta'$$ that yields $$(0.6,1)$$ for most of those samples and $$(0.1,1)$$ for only few of those samples. So $$J(\Theta')$$ is higher, but $$\Theta'$$ classifies much better in terms of amount of false predictions over the training set.

Given one bad optimization step, logistic regression should not be able to converge to the optimal classification!?

• When you say "the optimum," it's not clear what you mean. It seems to have something to do with choosing a cutoff for predicted probabilities, but it's not clear how they're related. For example, when logistic regression is strongly convex, we know that the trained regression weights are optimal in the sense that they have a lower loss (lower $J(\Theta)$) than any other choice weights. In what sense are you suggesting that a logistic regression that uses probability cutoffs at 0.5 is optimal? What expression is maximized or minimized? – Sycorax Nov 9 '19 at 14:59
• I think your question might be answered by stats.stackexchange.com/questions/312780/… and the observation that logistic regression is not particularly concerned about accuracy. – Sycorax Nov 9 '19 at 15:05
• @ReinstateMonica: By cutoff you mean threshold to decide when to label positive vs. when to label negative? I think your comment is exactly what I am struggling with: how is optimizing for the probabilities identical with optimizing for the classification, i.e. number of false predictions on the training set. This is not stated explicitly in Andrew Ng's cited course, but implicitly. – DaveFar Nov 9 '19 at 15:08
• Yeah, cutoff is some $c$ s.t. you say "this observation is a positive" whenever $h_\Theta(x) > c$. But note that logistic regression doesn't actually coincide with optimizing accuracy for the exact reasons that you outline. Depending on the data, you might end up with all predictions, for positive and negative samples alike, well above 0.5, for instance. See: stats.stackexchange.com/questions/168929/… for some discussion. – Sycorax Nov 9 '19 at 15:37
• @ReinstateMonica: very helpful comments, thanks a lot. would you like to turn them into an answer? I think my question is not a duplicate of the links you mentioned, so I would rather accept your answer than delete my question. – DaveFar Nov 9 '19 at 19:30

Another way to think about it is that accuracy is discarding all the fine-grained detail in the predicted probabilities. Accuracy treats $$0.5+10^{-10}$$ and $$1.0-10^{-10}$$ as exactly the same, because both are larger than 0.5, even though the latter describes the probability of the event with much more confidence than the former. By contrast, the cross-entropy loss $$J$$ will penalize predictions which are far from the label, and the size of the penalty increases the "more incorrect" that prediction is.