# Limit of momentum update equation

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

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

• What is your specific question? Are you asking why that sum tends to that formula?
– nbro
Jan 10 at 16:28