# Proving that momentum gradient descent converges for function $f(x) = x^2$

It is well-known that using vanilla gradient descent on $$f(x) = x^2$$ can lead to ping-ponging and non-convergence. I would like to show that convergence can occur for momentum gradient descent.

We have function $$f(x) = x^2$$ and learning rate $$\eta > 1$$. Then,

\begin{aligned} x_{n+1} &= x_n - \eta g_n \\ g_n &= (1-\gamma)g_{n-1} + \gamma \nabla f(x_n) \end{aligned}

with initial condition $$g_{-1} = 0$$. I would like to show that for any $$\eta > 1$$, there is a $$\gamma > 0$$ such that $$f(x_n) \to 0$$. What I did was find that

$$x_{t+1} = x_t - \eta\big[(1-\gamma)g_{t-1} + \gamma\nabla f(x_t)\big] = x_t(2-\gamma - 2\eta\gamma) - x_{t-1}(1-\gamma)$$

using the facts that $$\nabla f(x) = 2x$$ and $$x_t - x_{t-1} = -2\eta g_{t-1}$$. Then I picked $$\gamma = \frac12\eta$$, which led me to

$$x_{t+1} = \left(1 - \frac{1}{2\eta} \right) (x_t - x_{t-1})$$

and to the recurrence relation

$$x_{t+1} = \alpha(x_t - x_{t-1})$$

where $$\alpha < 1$$ and $$\alpha = 1 - \frac12\eta$$. Using this recurrence relation, how can one show that $$f(x_t) \to 0$$?

I plotted this in Python and it does seem to converge well enough, but I can't show it analytically. Should I be choosing a different value of $$\gamma$$ instead?

$$\begin{bmatrix} x_{k+1} \\ x_k \end{bmatrix} = \begin{bmatrix} \alpha & - \alpha \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x_k \\ x_{k-1} \end{bmatrix}$$
Now find for which values of $$\alpha$$ the matrix's eigenvalues are strictly inside the unit circle.