2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

6
$\begingroup$

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

$\endgroup$

Your Answer

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

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