11
$\begingroup$

I am looking to compute maximum likelihood estimators for $\mu$ and $\sigma^2$, given n i.i.d random variables drawn from a Gaussian distribution. I believe I know how to write the expressions for negative log likelihood (kindly see below), however before I take derivatives with respect to $\mu$ and $\sigma^2,$ I want to prove that the neg. log likelihood is a convex function in $\mu$ and $\sigma^2$.

This is where I'm stuck - I'm unable to prove that the Hessian is Positive Semidefinite.

The negative log-likelihood function, $$ l(\mu, \sigma^2) = \frac{n}{2}ln(2\pi) + \frac{n}{2}ln(\sigma^2) + \sum_{i=1}^n \frac{(xi - \mu)^2}{2\sigma^2}$$ Let $\alpha = \frac{1}{\sigma^2}$ (The book Convex Optimization by Boyd & Vandenberghe notes in Section 7.1 that this transformation should make the neg. log-likelihood convex in $\alpha$). We now get, $$ l(\mu, \alpha) = \frac{n}{2}ln(2\pi) - \frac{n}{2}ln(\alpha) + \sum_{i=1}^n \frac{(x_i - \mu)^2\alpha}{2}$$ $$ = \frac{n}{2}ln(2\pi) + \frac{1}{2}\sum_{i=1}^n\left(-ln(\alpha) + \frac{(x_i - \mu)^2\alpha}{2}\right)$$

Define, $$g_i(\mu, \alpha) = -ln(\alpha) + \frac{(x_i - \mu)^2\alpha}{2} $$

Now my approach is to show that $g_i(\mu, \alpha)$ is convex in $\mu$, $\alpha$ and use that to say that $l(\mu, \alpha)$ being a sum of convex $g_i$'s is also convex in $\mu$, $\alpha$. The Hessian for $g_i$ is:

$$ \nabla^2g_i = \begin{pmatrix} 2\alpha & -2(x_i - \mu)\\ -2(x_i - \mu) & \frac{1}{\alpha^2} \\ \end{pmatrix} $$

And the determinant of the Hessian is, $$ \lvert \nabla^2g_i \rvert = \frac{2}{\alpha} - 4(x_i - \mu)^2$$ This is where I'm stuck - I cannot show that this determinant is non-negative for all values of $\mu$ and $\alpha (>0)$. Kindly help figure out my conceptual or other errors.

Kindly note I've consulted the following similar queries: How to prove the global maximum log likelihood function of a normal distribution is concave

and Proving MLE for normal distribution

However both of them only show that the Hessian is non-negative at a point where $\mu$ and $\alpha$ equal their estimated values. The mistake I see is that the estimates were arrived in the first place by assuming the neg. log-likelihood is convex (i.e. by equating gradient to 0, which is the optimality criterion for a convex function).

Thanks

$\endgroup$
3
  • $\begingroup$ What is Prof. Stephen Boyd's book on Convex Optimization? Are there perhaps other authors? $\endgroup$
    – LinAlg
    Commented Jul 16, 2018 at 11:59
  • $\begingroup$ is the statement about convexity in $\alpha$, or about convexity in both $\alpha$ and $x$? $\endgroup$
    – LinAlg
    Commented Jul 16, 2018 at 12:04
  • 1
    $\begingroup$ @LinAlg I was looking for convexity in z = [mu, alpha], however looking at the expression for my Hessian, I can not show its determinant to be always non-negative, and therefore I can conclude that the Hessian is not positive semi-definite. Ahmad Bazzi below, has confirmed this in his answer, and I now do realize that to find MLE estimates, it is not required for l to be convex in both mu and alpha. Separately, I have now listed both the authors of the Convex Optimization book I alluded to in my original query. My bad. $\endgroup$ Commented Jul 16, 2018 at 14:07

2 Answers 2

11
$\begingroup$

So you get $$l(\mu,\alpha) =\frac{n}{2}\ln 2 \pi - \frac{n}{2} \ln \alpha+ \sum \frac{(x_i- \mu)^2\alpha}{2}$$ Convex in $\mu$

The second derivative w.r.t $\mu$ is $$\frac{\partial^2}{\partial \mu^2}l = n \alpha > 0$$ So we get convexity in $\mu$.

Convex in $\alpha$

The second derivative w.r.t $\alpha^2$ is $$\frac{\partial^2}{\partial \alpha^2}l = \frac{1}{\alpha^2} > 0$$ So we get convexity in $\alpha$.

What I think you meant is that you would want to prove that $l(\pmb{z})$ is convex in $\pmb{z}$, where $\pmb{z} = [\mu, \alpha]$ (jointly). Well, it is not convex in $\pmb{z}$ because the Hessian you wrote has negative values for values of $x_i,\mu,\alpha$: Choose a small $\frac{2}{\alpha}$ and a large $4(x_i - \mu)^2$, this leaves us with a negative determinant. Boyd does not tell you that $l(\mu,\alpha)$ is convex in $\mu,\alpha$. The statement convex in mean and variance means that it is convex in mean and it is convex in variance.

The link you shared here is something completely different. They want to show that the optimal values are concave (at least this is what they state).

$\endgroup$
4
  • 1
    $\begingroup$ Thanks Ahmad, this is quite helpful, I will mark this as the answer. Yes, I was looking to prove convexity in z. I realize that to find the MLE estimates, l need not be convex in z, and that I can first minimize over mu and then over alpha. Thanks for your help. (For anyone else interested, refer to "Optimizing over some variables", Section 4.1, in the book "Convex Optimization" by Boyd & Vandenberghe). $\endgroup$ Commented Jul 16, 2018 at 14:00
  • $\begingroup$ I'm glad you found it helpfuk @abhimanyutalwar .. If you found the answer helpful, you could upvote it as well ;) $\endgroup$ Commented Jul 16, 2018 at 14:17
  • $\begingroup$ @abhimanyutalwar first minimizing over mu and then over alpha will only be beneficial if the latter optimization problem is convex, which it probably is not; that means that your strategy is not simple to execute $\endgroup$
    – LinAlg
    Commented Jul 16, 2018 at 14:24
  • 1
    $\begingroup$ @LinAlg Agree that this doesn't work as a general strategy. However, in this case my original neg-log-likelihood function is convex in mu, and its infimum over mu is convex in alpha, so it worked. Ahmad, I would very much like to upvote!! However, as I'm a new user I do not have enough rep to do that :( $\endgroup$ Commented Jul 19, 2018 at 3:22
2
$\begingroup$

I think there is another very interesting view on the problem that involves the formula of the determinant of the negative log-likelihood hessian

$$\lvert \nabla^2g(\alpha, \mu) \rvert = \left| \nabla^2 \sum_{i=1}^n g_i(\alpha, \mu) \right| = \frac{2n^2}{\alpha} - 4 \left(\sum_{i=1}^n (x_i - \mu)\right)^2 \geq 0$$

Although it is easy to show that this equality does not hold for any $\alpha,\mu \in \mathbb{R}$ for given $x_i \in \mathbb{R}$, it allows to define the set

$$G = \left\{ \left(\alpha,\mu\right)\ \vert\ \lvert \nabla^2g(\alpha, \mu) \rvert \geq 0 \right\}.$$

Obviously, the negative log-likelihood function is convex on G. Also the MLE solution

\begin{align*} \mu^* &= \frac{1}{N} \sum_{i=1}^n x_i \\ \alpha^* &= \frac{N}{\sum_{i=1}^n (x_i - \mu^*)^2} \end{align*}

is itself contained in the the set G, since

\begin{align*} &\ \frac{2n^2}{\alpha^*} - 4 \left(\sum_{i=1}^n x_i - \mu^*\right)^2 \\ =&\ \frac{2n^2}{\alpha^*} - 4 \left(\sum_{i=1}^n \left( x_i - \frac{1}{n} \sum_{j=1}^n x_j\right)\right)^2 \\ =&\ \frac{2n^2}{\alpha^*} - 4 \left(\sum_{i=1}^n x_i - \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n x_j\right)^2 \\ =&\ \frac{2n^2}{\alpha^*} - 4 \left(\sum_{i=1}^n x_i - \sum_{j=1}^n x_j\right)^2 \\ =&\ \frac{2n^2}{\alpha^*} \end{align*}

and we know that the last quantity is strictly positive. Now a second interesting observation can be made by looking at the condition that defines the set G. As we can see, the term

\begin{align*} &\ 4 \left(\sum_{i=1}^n x_i - \mu\right)^2 \\ =&\ 4 \left(n \mu^* - n \mu\right)^2 \\ =&\ 4 n^2 \left(\mu^* - \mu\right)^2 \end{align*}

becomes larger with increasing distance between $\mu$ and $\mu*$. Consequently, the term

\begin{align*} &\ \frac{2n^2}{\alpha} \\ =&\ 2n^2 \sigma^2 \end{align*}

needs to increase as well, in order to ensure $\lvert \nabla^2g(\alpha, \mu) \rvert \geq 0$. The "problematic" points are those, where we have a bad "estimate" $\mu$ of the solution to the MLE and a comparatively small variance.

However, the set $G$ is not convex. If it would be, we could simply follow the gradient of the objective and get to the optimal solution. The non-convexity can be shown with the following example:

$$n=2, x_1 = 1, x_2 = 2, \mu_1 = 0.5, \alpha_1=0.5, \mu_2 = -1, \alpha_2 = 0.08.$$

With this it holds that

\begin{align*} &\lvert \nabla^2g(\alpha_1, \mu_1) \rvert = \frac{8}{0.5} - 4 \left((1 - 0.5) + (2 - 0.5)\right)^2 = 16 - 16 = 0 \geq 0 \\ &\lvert \nabla^2g(\alpha_2, \mu_2) \rvert = \frac{8}{0.08} - 4 \left((1 - (-1)) + (2 - (-1))\right)^2 = 100 - 100 = 0 \geq 0 \\ &\lvert \nabla^2g(0.4 \alpha_1 + 0.6 \alpha_2, 0.4 \mu_1 + 0.6 \mu_2) \rvert = \frac{8}{0.248} - 4 \left((1 - (-0.4)) + (2 - (-0.4))\right)^2 \approx -25.5 < 0. \end{align*}

However, there are generalized notions of convexity, such as geodesic convexity. Indeed, it can be shown that the MLE problem is geodesic convex in a certain Riemannian Manifold (see here).

$\endgroup$

You must log in to answer this question.

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