Rate of convergence of gradient descent inference in likelihood maximization

Question

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!

Answer 1

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