<p>The first two equations are equivalent. The last equation can be equivalent if you scale <span class="math-container">$\alpha$</span> appropriately.</p>
<h2>Equation 1</h2>
<p>Consider the equation from the Stanford slide:</p>
<p><span class="math-container">$$
v_{t}=\rho v_{t-1}+\nabla f(x_{t-1}) 
\\ 
x_{t}=x_{t-1}-\alpha v_{t},
$$</span></p>
<p>Let's evaluate the first few <span class="math-container">$v_t$</span> so that we can arrive at a closed form solution:</p>
<p><span class="math-container">$v_0 = 0 \\
v_1 =  \rho v_0 + \nabla f(x_0) = \nabla f(x_0)\\
v_2 = \rho v_1 + \nabla f(x_1) = \rho \nabla f(x_0) + \nabla f(x_1)\\
v_3 = \rho v_2 + \nabla f(x_2) = \rho^2 \nabla f(x_0) + \rho \nabla f(x_1) + \nabla f(x_2)\\
\dots \\
v_t = \displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} \nabla f(x_i)
$</span></p>
<p>So the closed form update is:</p>
<p><span class="math-container">$$x_t = x_{t-1} - \alpha \displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} \nabla f(x_i)$$</span></p>
<h2>Equation 2</h2>
<p>Now consider the equation from the paper:
<span class="math-container">$$
v_{t}=\rho v_{t-1}+\alpha \nabla f(x_{t-1}) 
\\ 
x_{t}=x_{t-1}- v_{t},
$$</span></p>
<p>We again evaluate the first few <span class="math-container">$v_t$</span> to arrive at a closed form solution:</p>
<p><span class="math-container">$v_0 = 0 \\
v_1 =  \rho v_0 + \alpha \nabla f(x_0) = \alpha \nabla f(x_0)\\
v_2 = \rho v_1 + \alpha \nabla f(x_1) = \rho \alpha \nabla f(x_0) + \alpha \nabla f(x_1)\\
v_3 = \rho v_2 + \alpha \nabla f(x_2) = \rho^2 \alpha \nabla f(x_0) + \rho \alpha \nabla f(x_1) + \alpha \nabla f(x_2)\\
\dots \\
v_t = \displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} \alpha \nabla f(x_i)
$</span></p>
<p>So the closed from update is:</p>
<p><span class="math-container">$$x_t = x_{t-1} - \displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} \alpha \nabla f(x_i)$$</span></p>
<p>As you can see, this is equivalent to the previous closed form update. The only difference is if <span class="math-container">$\alpha$</span> is inside or outside the summation, but since it is a constant, it doesn't really matter anyways.</p>
<h2>Equation 3</h2>
<p>As for the last equation</p>
<p><span class="math-container">$$
v_{t}= \rho v_{t-1}+ (1- \rho) \nabla f(x_{t-1}) 
\\ 
x_{t}=x_{t-1}-\alpha v_{t}
$$</span>
Let's do the same thing:</p>
<p><span class="math-container">$v_0 = 0 \\
v_1 =  \rho v_0 + (1-\rho) \nabla f(x_0) = (1-\rho) \nabla f(x_0)\\
v_2 = \rho v_1 + (1-\rho) \nabla f(x_1) = \rho (1-\rho) \nabla f(x_0) + (1-\rho) \nabla f(x_1)\\
v_3 = \rho v_2 + (1-\rho) \nabla f(x_2) = \rho^2 (1-\rho) \nabla f(x_0) + \rho (1-\rho) \nabla f(x_1) + (1-\rho) \nabla f(x_2)\\
\dots \\
v_t = \displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} (1-\rho) \nabla f(x_i)
$</span></p>
<p>And so the closed form update is:</p>
<p><span class="math-container">$$x_t = x_{t-1} - \alpha \displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} (1-\rho) \nabla f(x_i)$$</span></p>
<p>This equation is equivalent to the other two as long as you scale <span class="math-container">$\alpha$</span> by a factor of <span class="math-container">$\displaystyle \frac{1}{1-\rho}$</span>.</p>

CC BY-SA 4.0
2020-12-31T07:58:32.947Z
Great, this is exactly what I want to hear. Thank you for a very detailed answer
CuCaRot
CC BY-SA 4.0
2024-08-24T11:56:58.627Z
@user3667125 So the sum of weights $\displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} (1-\rho)$ doesn't sum to 1 unless $t \to \infty$ (convergence of geometric series)?
Antonios Sarikas
CC BY-SA 4.0
2020-12-31T06:33:00.633Z
2020-12-31T06:33:00.633Z
user3667125
<p>I know this question may be so silly, but I can not prove it.</p>
<p>In <a href="http://cs231n.stanford.edu/slides/2020/lecture_8.pdf#page=17" rel="nofollow noreferrer">Stanford slide</a> (page 17), they define the formula of SGD with momentum like this:</p>
<p><span class="math-container">$$
v_{t}=\rho v_{t-1}+\nabla f(x_{t-1}) 
\\ 
x_{t}=x_{t-1}-\alpha v_{t},
$$</span></p>
<p>where:</p>
<ul>
<li><span class="math-container">$v_{t+1}$</span> is the momentum value</li>
<li><span class="math-container">$\rho$</span> is a friction, let say it's equal 0.9</li>
<li><span class="math-container">$\nabla f(x_{t-1})$</span> is the gradient of the objective function at iteration <span class="math-container">$t-1$</span></li>
<li><span class="math-container">$x_t$</span> are the parameters</li>
<li><span class="math-container">$\alpha$</span> is the learning rate</li>
</ul>
<p>However, in <a href="https://arxiv.org/pdf/1609.04747.pdf" rel="nofollow noreferrer">this paper</a> and many other documents, they define the equation like this:</p>
<p><span class="math-container">$$
v_{t}=\rho v_{t-1}+\alpha \nabla f(x_{t-1}) 
\\ 
x_{t}=x_{t-1}- v_{t},
$$</span></p>
<p>where <span class="math-container">$\rho$</span> and <span class="math-container">$\alpha$</span> still have the same value as in the previous formula.</p>
<p>I think it should be</p>
<p><span class="math-container">$$v_{t}=\alpha \rho v_{t-1}+\alpha \nabla f(x_{t-1})$$</span></p>
<p>if we want to multiply the learning rate inside the equation.</p>
<p>In some other document (<a href="https://towardsdatascience.com/stochastic-gradient-descent-with-momentum-a84097641a5d" rel="nofollow noreferrer">this</a>) or normal form of momentum, they define like this:</p>
<p><span class="math-container">$$
v_{t}= \rho v_{t-1}+ (1- \rho) \nabla f(x_{t-1}) 
\\ 
x_{t}=x_{t-1}-\alpha v_{t}
$$</span></p>
<p>I can not understand how can they prove those equations are similar. Can someone help me?</p>

CC BY-SA 4.0
2020-12-31T08:03:36.280Z
@DuttaA I am not sure I understand you correctly, but stochastic gradient descent is one of the basic methods in convex optimization, right? And I don't understand the part "NNs are very bad functions", can you explain more about it?
CuCaRot
CC BY-SA 4.0
2021-01-01T09:32:05.603Z
I see, I understand that maybe you feel annoyed by those unclear assumptions. However, as an amateur, I know that NNs is not CO problem, but the performance of SGD (with or without momentum) is really good to optimize the parameters, so I just want to understand the similarity between those equations (for later or maybe the interview). Anyway, happy new year!
CuCaRot
<deep-learning><comparison><optimization><stochastic-gradient-descent><momentum>
How are these equations of SGD with momentum equivalent?
CuCaRot
# How are these equations of SGD with momentum equivalent?

(Asked by: username_0 on 2020-12-13)

I know this question may be so silly, but I can not prove it.

In [Stanford slide](http://cs231n.stanford.edu/slides/2020/lecture_8.pdf#page=17) (page 17), they define the formula of SGD with momentum like this:

$$
v\_{t}=\rho v\_{t-1}+\nabla f(x\_{t-1})
\\
x\_{t}=x\_{t-1}-\alpha v\_{t},
$$

where:

* $v\_{t+1}$ is the momentum value
* $\rho$ is a friction, let say it's equal 0.9
* $\nabla f(x\_{t-1})$ is the gradient of the objective function at iteration $t-1$
* $x\_t$ are the parameters
* $\alpha$ is the learning rate

However, in [this paper](https://arxiv.org/pdf/1609.04747.pdf) and many other documents, they define the equation like this:

$$
v\_{t}=\rho v\_{t-1}+\alpha \nabla f(x\_{t-1})
\\
x\_{t}=x\_{t-1}- v\_{t},
$$

where $\rho$ and $\alpha$ still have the same value as in the previous formula.

I think it should be

$$v\_{t}=\alpha \rho v\_{t-1}+\alpha \nabla f(x\_{t-1})$$

if we want to multiply the learning rate inside the equation.

In some other document ([this](https://towardsdatascience.com/stochastic-gradient-descent-with-momentum-a84097641a5d)) or normal form of momentum, they define like this:

$$
v\_{t}= \rho v\_{t-1}+ (1- \rho) \nabla f(x\_{t-1})
\\
x\_{t}=x\_{t-1}-\alpha v\_{t}
$$

I can not understand how can they prove those equations are similar. Can someone help me?

**Tags:** deep-learning, comparison, optimization, stochastic-gradient-descent, momentum

> **Comments:**
> **username_0**: @DuttaA I am not sure I understand you correctly, but stochastic gradient descent is one of the basic methods in convex optimization, right? And I don't understand the part "NNs are very bad functions", can you explain more about it?  
> **username_0**: I see, I understand that maybe you feel annoyed by those unclear assumptions. However, as an amateur, I know that NNs is not CO problem, but the performance of SGD (with or without momentum) is really good to optimize the parameters, so I just want to understand the similarity between those equations (for later or maybe the interview). Anyway, happy new year!  

---

## 1 answers

### Answer by username_1 on 2020-12-31. Score: 4 | Accepted answer

The first two equations are equivalent. The last equation can be equivalent if you scale $\alpha$ appropriately.

## Equation 1

Consider the equation from the Stanford slide:

$$
v\_{t}=\rho v\_{t-1}+\nabla f(x\_{t-1})
\\
x\_{t}=x\_{t-1}-\alpha v\_{t},
$$

Let's evaluate the first few $v\_t$ so that we can arrive at a closed form solution:

$v\_0 = 0 \\
v\_1 = \rho v\_0 + \nabla f(x\_0) = \nabla f(x\_0)\\
v\_2 = \rho v\_1 + \nabla f(x\_1) = \rho \nabla f(x\_0) + \nabla f(x\_1)\\
v\_3 = \rho v\_2 + \nabla f(x\_2) = \rho^2 \nabla f(x\_0) + \rho \nabla f(x\_1) + \nabla f(x\_2)\\
\dots \\
v\_t = \displaystyle \sum\_{i=0}^{t-1} \rho^{t-1-i} \nabla f(x\_i)
$

So the closed form update is:

$$x\_t = x\_{t-1} - \alpha \displaystyle \sum\_{i=0}^{t-1} \rho^{t-1-i} \nabla f(x\_i)$$

## Equation 2

Now consider the equation from the paper:
$$
v\_{t}=\rho v\_{t-1}+\alpha \nabla f(x\_{t-1})
\\
x\_{t}=x\_{t-1}- v\_{t},
$$

We again evaluate the first few $v\_t$ to arrive at a closed form solution:

$v\_0 = 0 \\
v\_1 = \rho v\_0 + \alpha \nabla f(x\_0) = \alpha \nabla f(x\_0)\\
v\_2 = \rho v\_1 + \alpha \nabla f(x\_1) = \rho \alpha \nabla f(x\_0) + \alpha \nabla f(x\_1)\\
v\_3 = \rho v\_2 + \alpha \nabla f(x\_2) = \rho^2 \alpha \nabla f(x\_0) + \rho \alpha \nabla f(x\_1) + \alpha \nabla f(x\_2)\\
\dots \\
v\_t = \displaystyle \sum\_{i=0}^{t-1} \rho^{t-1-i} \alpha \nabla f(x\_i)
$

So the closed from update is:

$$x\_t = x\_{t-1} - \displaystyle \sum\_{i=0}^{t-1} \rho^{t-1-i} \alpha \nabla f(x\_i)$$

As you can see, this is equivalent to the previous closed form update. The only difference is if $\alpha$ is inside or outside the summation, but since it is a constant, it doesn't really matter anyways.

## Equation 3

As for the last equation

$$
v\_{t}= \rho v\_{t-1}+ (1- \rho) \nabla f(x\_{t-1})
\\
x\_{t}=x\_{t-1}-\alpha v\_{t}
$$
Let's do the same thing:

$v\_0 = 0 \\
v\_1 = \rho v\_0 + (1-\rho) \nabla f(x\_0) = (1-\rho) \nabla f(x\_0)\\
v\_2 = \rho v\_1 + (1-\rho) \nabla f(x\_1) = \rho (1-\rho) \nabla f(x\_0) + (1-\rho) \nabla f(x\_1)\\
v\_3 = \rho v\_2 + (1-\rho) \nabla f(x\_2) = \rho^2 (1-\rho) \nabla f(x\_0) + \rho (1-\rho) \nabla f(x\_1) + (1-\rho) \nabla f(x\_2)\\
\dots \\
v\_t = \displaystyle \sum\_{i=0}^{t-1} \rho^{t-1-i} (1-\rho) \nabla f(x\_i)
$

And so the closed form update is:

$$x\_t = x\_{t-1} - \alpha \displaystyle \sum\_{i=0}^{t-1} \rho^{t-1-i} (1-\rho) \nabla f(x\_i)$$

This equation is equivalent to the other two as long as you scale $\alpha$ by a factor of $\displaystyle \frac{1}{1-\rho}$.

> **Comments:**
> **username_0**: Great, this is exactly what I want to hear. Thank you for a very detailed answer  
> **username_2**: @username_1 So the sum of weights $\displaystyle \sum_{i=0}^{t-1} \rho^{t-1-i} (1-\rho)$ doesn't sum to 1 unless $t \to \infty$ (convergence of geometric series)?  

---

