Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T07:58:32.947Z
Answers.Text: Great, this is exactly what I want to hear. Thank you for a very detailed answer
Answers.UserDisplayName: CuCaRot
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-24T11:56:58.627Z
Answers.Text: @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)?
Answers.UserDisplayName: Antonios Sarikas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-31T06:33:00.633Z
Answers.LastActivityDate: 2020-12-31T06:33:00.633Z
Answers.UserDisplayName: user3667125
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-31T08:03:36.280Z
Comments.Text: @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?
Comments.UserDisplayName: CuCaRot
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-01T09:32:05.603Z
Comments.Text: 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!
Comments.UserDisplayName: CuCaRot
Tags: <deep-learning><comparison><optimization><stochastic-gradient-descent><momentum>
Title: How are these equations of SGD with momentum equivalent?
UserDisplayName: CuCaRot
ThreadText: # 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**: @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)?  
  
  ---
  
  