3
$\begingroup$

I am reading this classic paper on convergence properties of EM for Gaussian Mixture Models. In section 5, the authors compare EM with a gradient based inference approach.

The gradient approach requires step-size $\eta$ for parameter update at each iteration $k$ i.e. updation of paramters from $\Theta^k$ to $\Theta^{k+1}$.

The authors claim that for local convergence, one can use Taylor series expansion of the likelihood around the true parameter $\Theta^*$ and claim that the following condition needs to hold true:

$$\left\|\Theta^{(k+1)}-\Theta^{*}\right\| \leq\left\|I+\eta H\left(\Theta^{*}\right)\right\|\left\|\Theta^{(k)}-\Theta^{*}\right\|$$

Here $H$ is the Hessian of the likelihood. I am trying to derive this condition.

Here is my attempt:

Let $L$ be the likelihood. Expanding $L$ around the true parameter $\Theta^*$ gives

$$L(\Theta^k) \approx L(\Theta^*) + \nabla L(\Theta^* - \Theta^k) + 0.5(\Theta^* - \Theta^k)^{T}H(\Theta^* - \Theta^k) $$

Similarly, I expand $L$ for $\Theta^{k+1}$. $$L(\Theta^{k+1}) \approx L(\Theta^*) + \nabla L(\Theta^* - \Theta^{k+1}) + 0.5(\Theta^* - \Theta^{k+1})^{T}H(\Theta^* - \Theta^{k+1}) $$

Also, at $\Theta^*$, the gradient $\nabla L = 0$. Subtracting the above two equations, using the condition to ensure montonocity of $L$ at each iteration, I have

$$ (\Theta^* - \Theta^k)^{T}H(\Theta^* - \Theta^k) - (\Theta^* - \Theta^{k+1})^{T}H(\Theta^* - \Theta^{k+1}) < 0 $$

I am unable to simplify further. Is this the right approach? Thank you in advance!

$\endgroup$

1 Answer 1

1
$\begingroup$

That expression does not guarantee convergence, in fact it is just application of Cauchy-Schwartz inequality. Let's see.

First, we use a second order approximation of our cost function $L:\mathbb{R}^n\rightarrow \mathbb{R}$(negative log-likelihood in your case) around the optimum $\Theta^{*}$, taking into account that $\frac{\partial L(\Theta)}{\partial\Theta}\Big|_{\Theta^*}=\vec{0}$:

$$ L(\Theta^*+\Delta \Theta) \approx L(\Theta^*) + \frac{1}{2} \Delta \Theta^T \frac{\partial^2 L(\Theta)}{\partial^2\Theta}\Big|_{\Theta^*}\Delta \Theta $$

Now, we compute an approximation of the gradient around the optimum:

$$ \frac{\partial L(\Theta)}{\partial \Delta \Theta} \approx \frac{\partial^2 L(\Theta)}{\partial^2\Theta}\Big|_{\Theta^*}(\Theta-\Theta^*) = H(\Theta-\Theta^*) $$

Which is used in the gradient descent method as follows:

$$ \Theta^{k+1} = \Theta^k - \eta \frac{\partial L(\Theta)}{\partial \Theta} \approx \Theta^k - \eta H(\Theta-\Theta^*) $$

Which leads to: $$ \Theta^{k+1} - \Theta^* \approx (I - \eta H)(\Theta-\Theta^*) $$

Now, taking norms and applying Cauchy–Schwarz inequality: $$ \Vert\Theta^{k+1} - \Theta^*\Vert \approx \Vert(I - \eta H)(\Theta-\Theta^*)\Vert \leq \Vert I - \eta H \Vert \Vert \Theta-\Theta^* \Vert \leq \lambda_M \Vert \Theta-\Theta^* \Vert $$

Where $\lambda_M$ is the greatest eigenvalue of $I - \eta H$. This expression is true independently of convergence. To guarantee convergence, this condition is necessary: $$ \Vert\Theta^{k+1} - \Theta^*\Vert \leq \Vert\Theta^{k} - \Theta^*\Vert $$

Putting together both inequalities, it arise that convergence condition is: $$\Vert I - \eta H \Vert <\lambda_M <1$$

$\endgroup$
1
  • $\begingroup$ Thanks for the detailed answer! If I understand correctly, the key idea in this approach is to approximate the gradient around the optimum using the Hessian and study the appropriate step size, convergence rate, etc. I have never come across this approach. Is this a widely used approach? Can you please point me towards some references ? $\endgroup$ Aug 29, 2019 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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