0
$\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$
1
  • $\begingroup$ What is your specific question? Are you asking why that sum tends to that formula? $\endgroup$
    – nbro
    Jan 10 at 16:28

0

You must log in to answer this question.

Browse other questions tagged .