3
$\begingroup$

I am studying logistic regression for binary classification.

The loss function used is cross-entropy. For a given input $x$, if our model outputs $\hat{y}$ instead of $y$, the loss is given by $$\text{L}_{\text{CE}}(y,\hat{y}) = -[y \log \hat{y} + (1 - y) (\log{1 - \hat{y}})]$$

Suppose there are $m$ such training examples, then the overall total loss function $\text{TL}_{\text{CE}}$ is given by

$$\text{TL}_{\text{CE}} = \dfrac{1}{m} \sum\limits_{i = 1}^{m} \text{L}_{\text{CE}} (y_i , \hat{y_i}) $$

It is said that the loss function is convex. That is, If I draw a graph between the loss values wrt the corresponding weights then the curve will be convex. The material from textbook did not give any explanation regarding the convex nature of the cross-entropy loss function. You can observe it from the following passage.

For logistic regression, this (cross-entropy) loss function is conveniently convex. A convex function has just one minimum; there are no local minima to get stuck in, so gradient descent starting from any point is guaranteed to find the minimum. (By contrast, the loss for multi-layer neural networks is non-convex, and gradient descent may get stuck in local minima for neural network training and never find the global optimum.)

How did they conclude conveniently that the loss function is convex? Is it by plotting or some other means?

$\endgroup$

3 Answers 3

3
$\begingroup$

The $L_{CE}$ that you provided is binary cross-entropy, the factor $y$ and $(1-y)$ is because $y$ is binary $({0,1})$, careful with the name next time. The cross-entropy loss should have form:

$$L_{CE}=-\displaystyle\sum_{i=1}^C y_i\log(\hat{y_i})$$

Where $C$ is the number of classes. Normally, the $y_i$ factor only is 1 when $i$ is the index of the correct class. Therefore, with each class, the function is just:

$$f(x)=-log(x)$$

Now, to prove this one is convex, we have multiple ways, but my favorite one is computing the derivative and second derivative.

$$\frac{\partial L}{\partial x}=-\frac{1}{x}\Rightarrow \frac{\partial^2 L}{\partial x^2}=\frac{1}{x^2}>0 \text{ for all }x\in(0,1]$$

This proves that $f(x) = -\log(x)$ is convex, given that, if the second derivative of a function is positive, then the function is convex (more info and an example here).

For the case of multiple samples, we also need to prove that the sum of a convex function is a convex function.

Based on the definition of convex function, a function $f:X\rightarrow \mathbb{R}$ will be convex if: $$f(tx_1+(1-t)x_2) \le tf(x_1) + (1-t)f(x_2)$$ where $0<t<1$ and $x_1,x_2\in X$.

Now, let's assume $h(x) = f(x) + g(x)$ where both $f$ and $g$ are convex. We have: $$f(tx_1+(1-t)x_2) \le tf(x_1) + (1-t)f(x_2)$$ $$g(tx_1+(1-t)x_2) \le tg(x_1) + (1-t)g(x_2)$$ $$\Rightarrow f(tx_1+(1-t)x_2) + g(tx_1+(1-t)x_2) \le tf(x_1) + (1-t)f(x_2) + tg(x_1) + (1-t)g(x_2)$$ $$\Rightarrow f(tx_1+(1-t)x_2) + g(tx_1+(1-t)x_2) \le t(f(x_1)+g(x_1)) + (1-t)(f(x_2)+g(x_2))$$ $$\Rightarrow h(tx_1+(1-t)x_2) \le th(x_1) + (1-t)h(x_2)$$ $\Rightarrow h$ is the convex function $\Rightarrow$ the summation of convex functions is a convex function.

$\endgroup$
0
1
$\begingroup$

If you find the Hessian matrix (the matrix of second order derivatives) for the binary cross entropy loss function, you'll see that it is positive semidefinite for any possible value of the parameters. This concludes that it is a convex function.

A side effect of it being convex is that it will have a single minimum as mentioned in the textbook you cited.

$\endgroup$
1
  • 1
    $\begingroup$ Maybe you could at least provide a link to a reference that shows this more in detail. For people also not very familiar with linear algebra, you could also explain a little bit more the relationship between the convexivity and being or not positive semi-definite (and what this latter even means). $\endgroup$
    – nbro
    Jun 21, 2021 at 22:19
1
$\begingroup$

I'm unable to comment on previous answers because I'm new to ai.stackexchange and don't have enough clout points. So I'm writing my comment as an answer instead.

Unless I'm missing something, I believe there are a couple errors in the answer given by @CuCaRot. First, the alternative formula he gave for $L_{CE}$ is partially incorrect because it should be $\log(1-\hat{y})$ in the case of class 0, and not $\log(\hat{y})$. Second, the original question was about the convexity of the log loss as a function of the weights w, and not as a function of $\hat{y}$; consequently the derivation used to prove convexity is flawed.

$\endgroup$
3
  • $\begingroup$ You can search for, and view, this text: "To make requests for clarification, or mere responses to other answers, you need to wait until you have the comment privilege." in the FAQ: "Why do I need 50 reputation to comment? What can I do instead?". --- See also: Converting answer to comment. $\endgroup$
    – Rob
    May 19 at 16:07
  • $\begingroup$ I understand the rationale behind needing the minimum 50 points to be able to comment, but I'm hoping someone will see and agree with my "comment" and convert it into a real comment, since I can't do it. $\endgroup$ May 19 at 19:29
  • $\begingroup$ you need to flag your comment and ask (custom reason); it seems important enough that the information should be provided, but it can't be an "answer" and you should expect it to be deleted. $\endgroup$
    – Rob
    May 19 at 20:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .