We want to prove that the error/objective function of logistic regression :

is convex.

**Proof:**

Before beginning the proof, i would first like to make you review/recollect a few definitions/rules/facts/results related to convex functions:

**Definition of a convex function:**A function f(x) is said to be convex if the following inequality holds true:

**First-order condition of convexity:**A function f(x) which is differentiable is convex if the following inequality condition holds true:

Intuitively, this condition says that the tangent/first-order-taylor-series approximation of f(x) is globally an under-estimator.

**Second-order condition of convexity:**A function f(x) which is twice-differentiable is convex if and only if its hessian matrix (matrix of second-order partial derivatives) is positive semi-definite, i.e.

**Sum/Linear-combination of two or more convex functions is also convex:**Let f(x) and g(x) be two convex functions. Then any linear combination of these two functions

is also a convex function (this can be easily proved using the definition of the convex function).

Now notice that if we can prove that the two functions

are convex, then our objective function

must also be convex since any linear combination of two or more convex functions is also convex.

Let us now try to prove that

is a convex function of theta. In order to do this, we will use the __second-order condition of convexity__ described above. Let us first compute the hessian matrix:

Now below is the proof that this hessian matrix is positive semi-definite:

Let us now try to prove that

is a convex function of theta. In order to do this, we will again use the__ second-order condition of convexity__ described above. Let us first compute its hessian matrix:

Above, we have proved that both

are convex functions. And, the error/objective function of logistic regression

is essentially a linear-combination of several such convex functions. Now, since a linear combination of two or more convex functions is convex, we conclude that the objective function of logistic regression is convex.

Hence proved …

Following the same line of approach/argument it can be easily proven that the objective function of logistic regression is convex even if regularization is used.

Just to correct a little mistake: only a positive linear combination of convex functions is guaranteed to be convex again. However, in the logistic regression case y_i are positive, so it works indeed.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteI think for equation(2) you lost a z in the left part.

ReplyDeleteThanks for post:

ReplyDeleteship hỏa tốc sang Nepal

ship nhanh đi Nepal

ship nhanh tới Nepal

vận chuyển bưu phẩm đi Nepal

ship tốc độ đi Nepal

www.caycotacdunggi.info

Awesome post, thank you.

ReplyDeleteAgree with above that (2) missing a z on L.H.S.

I think in Eq.(2) you should write grad_{\theta} and not w.r.t. x.

ReplyDeleteThis is of course just a typo.

Nice post btw.!

I think things like this are really interesting. I absolutely love to find unique places like this. It really looks super creepy though!! Best Machine Learning institute in Chennai | Best Machine learning training | best machine learning training certification

ReplyDeleteVery interesting blog.Thanks for sharing this much valuable information.Keep Rocking.

ReplyDeleterpa training institute in chennai | rpa course fee in chennai | trending technologies list 2018