# Rate of convergence of gradient descent inference in likelihood maximization

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!

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$$

• 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 ? Aug 29, 2019 at 17:33