0
$\begingroup$

The logistic loss function is: $$\mathcal{L}=\frac{1}{n}\sum_{i=1}^n\log(1+\exp(-y_ix_i^T\theta))$$ in which $y_i\in\{-1,+1\},x\in \mathbb{R}^d$. How to show that $\mathcal{L}$ is strongly convex.

My thinkings: Can we get the $\nabla^2 \mathcal{L}(\theta)$ and show $\nabla^2 \mathcal{L}(\theta)-mI$ is PSD for some $m$?

$\endgroup$
  • $\begingroup$ Yes, you can compute the hessian wrt $\theta$ and it will be straightforward to see it is PSD. Computing it is a little bit of a hassle but does have a nice closed form expression $\endgroup$ – Casey Mar 15 at 12:33
  • $\begingroup$ The computation of the gradient and Hessian of logistic loss function is given here math.stackexchange.com/questions/3098910/… $\endgroup$ – user550103 Mar 16 at 8:37
2
$\begingroup$

It is not strongly convex. Take $n=d=1$. You are getting a function of the form $f(x)=\log(1+\exp( a x))$. Its second derivative is $$ f''(x) = \frac{a^2 \exp( a x) } { (1 + \exp(ax))^2} $$ Assuming $a > 0$, you have $\lim_{x \to -\infty} f''(x) = 0$. Thus, there is no positive constant which bounds $f''$ from below. A similar argument shows the same if $a < 0$.

$\endgroup$
  • $\begingroup$ You're absolutely right. And yet: I think it may be possible to prove strong convexity in the multidimensional case with certain conditions on $(y_i,x_i)$. I don't know this for sure. But this is certainly the case that's most interesting in machine learning applications. $\endgroup$ – Michael Grant Mar 18 at 15:36
  • $\begingroup$ @MichaelGrant intuitively, i do not believe so. Since each term of the log-loss behaves, approximately, like $\max(0, -y_i x_i^T \theta)$, and therefore any $\alpha \|x\|^2$ eventually 'curves up' faster. $\endgroup$ – Alex Shtof Mar 18 at 18:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.