1
$\begingroup$

I am self-studying on optimization algorithm on https://d2l.ai/chapter_optimization/momentum.html and couldn't get my head around some derivation:

Instead of the standard gradient descent update equation:
$$\mathbf{x_t} \leftarrow \mathbf{x}_{t-1} - \eta_t \mathbf{g}_{t,t-1}$$ Momentum descent uses a "momentum gradient", $\mathbf{v_t}$, instead of the gradient, $\mathbf{g}_t$ : $$\begin{align}\mathbf{v_t}&\leftarrow\beta \mathbf{v_{t-1}+\mathbf{g}_{t,t-1}} \\ \mathbf{x}_t &\leftarrow \mathbf{x}_{t-1} - \eta \mathbf{v}_t \end{align}$$ where $0<\beta <1$ and $\mathbf{g}_{t,t-1}$ is the gradient at step size $t$ and $\mathbf{v_t}$ is updated recursively as follow:
$$\begin{align}\mathbf{v_t}&=\beta \mathbf{v}_{t-1}+\mathbf{g}_{t,t-1} \\ &=\beta^2 \mathbf{v}_{t-2}+\beta \mathbf{g}_{t-1,t-2}+\mathbf{g}_{t,t-1} \\ &\qquad\vdots \\ &=\sum_{\tau=0}^{t-1} \beta^\tau \mathbf{g}_{t-\tau,t-\tau-1}\end{align}$$

The text then continues by stating (11.6.1.4)

In the limit the terms add up to $\sum_{\tau=0}^\infty \beta^\tau = \frac{1}{1-\beta}$. In other words, rather than taking a step of size $\eta$ in gradient descent or SGD we take a step of size $\frac{\eta}{1-\beta}$ while at the same time, dealing with a potentially much better behaved descent direction.

I am at loss at how $\sum_{\tau=0}^{t-1} \beta^\tau \mathbf{g}_{t-\tau,t-\tau-1} \rightarrow \frac{1}{1-\beta}$ as $t\rightarrow \infty$. I try to reason it as follow:

Since $$\begin{align} \mathbf{x}_t &= \mathbf{x}_{t-2} -\eta\mathbf{v}_{t-1} -\eta\mathbf{v}_t\nonumber\\ &= \mathbf{x}_{t-3} - \eta\mathbf{v}_{t-2} -\eta\mathbf{v}_{t-1} - \eta\mathbf{v}_t\nonumber\\ &\hspace{25pt}\vdots\nonumber\\ &= \mathbf{x}_0 - \sum_{\tau=0}^{t}\eta\mathbf{v}_{t-\tau}\\ \mathbf{v}_t &= \beta^{t-1}\mathbf{g}_{1,0} + \beta^{t-2}\mathbf{g}_{2,1} + \cdots + \mathbf{g}_{t,t-1}\\ \mathbf{v}_{t-1} &= \beta^{t-2}\mathbf{g}_{1,0} + \beta^{t-3}\mathbf{g}_{2,1} + \cdots + \mathbf{g}_{t-1,t-2}\\ &\qquad \vdots\\ \mathbf{v}_1 &= \mathbf{g}_{1,0}\\ \newline \mathbf{v}_0 &= 0 \end{align} $$ Then, $$\begin{align} \mathbf{x}_t &= \mathbf{x}_0 - \eta\left\{\left(\beta^{t-1}+\beta^{t-2}+\cdots + 1\right)\mathbf{g}_{1,0} + \left(\beta^{t-2}+\beta^{t-3}+\cdots + 1\right)\mathbf{g}_{2,1}+\cdots+\beta\mathbf{g}_{t-1,t-2} + \mathbf{g}_{t,t-1}\right\}\nonumber\\ &= \mathbf{x}_0 - \eta\left\{\left(\sum_{\tau=0}^{t-1}\beta^{\tau}\right)\mathbf{g}_{1,0}+\left(\sum_{\tau=0}^{t-2}\beta^\tau\right)\mathbf{g}_{2,1}+\cdots+\beta\mathbf{g}_{t-1,t-2}+\mathbf{g}_{t,t-1}\right\} \end{align}$$

As $t\rightarrow\infty$ $$ \mathbf{x}_t = \mathbf{x}_0 - \eta\left\{\frac{1}{1-\beta}\mathbf{g}_{1,0} + \frac{1}{1-\beta}\mathbf{g}_{2,1} + \cdots + \underbrace{\beta\mathbf{g}_{t-1,t-2} + \mathbf{g}_{t,t-1}}_{\rightarrow 0\text{ as }t \rightarrow 0}\right\} $$

And this effectively becomes

$$ \mathbf{x}_t = \mathbf{x}_0 - \eta\left(\frac{1}{1-\beta}\right)\mathbf{g} $$

I'm not sure if this is what the text means? To be honest, I feel like I'm kinda forcing my reasoning on the equation. Can someone shed more light on my question? Thanks.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

It means that each gradient step affects the final position with weight $\eta\over{1-\beta}$ due to the velocity term. This can be seen in your final equations, where $\mathbf g_{1,0}, \mathbf g_{2,1}$ etc. are multiplied with $\eta\over{1-\beta}$. So, their effective step size is $\eta\over{1-\beta}$. In SGD, each term would have contributed to the final position with weight $\eta$, but the momentum expression modifies it.

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