Answers.Body: <p>I'm going to use slightly different notation, <span class="math-container">$\leftarrow$</span> for an assignment, <span class="math-container">$\alpha$</span> for learning rate, <span class="math-container">$\nabla_w J$</span> in place of <span class="math-container">$g$</span>* and implied multiplication as these are slightly more common. Also, using bold letters to represent vectors. In that notation, the update rule for basic gradient descent would be written as:</p>
  
  <p><span class="math-container">$$\mathbf{w} \leftarrow \mathbf{w} - \alpha \nabla_w J$$</span></p>
  
  <p>This cannot be extended to momentum and Adam update rules whilst keeping it as a single line and modifying the right hand side. That is because these variations of gradient descent maintain running statistics of previous gradient values, which have their own separate update rules. When implemented on a computer, these become additional terms, mainly vectors the same size as the weight vector being updated. These variables also require initialisation before use.</p>
  
  <h2>Momentum</h2>
  
  <p>Momentum maintains a "velocity" term which essentially tracks a recency-weighted average of gradients. However, the classic form of momentum given here does not normalise the resulting vector, and you often have to adjust the learning rate down when using it. Momentum has a parameter <span class="math-container">$\beta$</span> which should be between 0 and 1, and typically is set at <span class="math-container">$0.9$</span> or higher.</p>
  
  <p><em>Intitialisation</em></p>
  
  <p><span class="math-container">$$\mathbf{m} \leftarrow \mathbf{0}$$</span></p>
  
  <p><em>Update rules</em></p>
  
  <p><span class="math-container">$$\mathbf{m} \leftarrow \beta \mathbf{m} + \nabla_w J$$</span>
  <span class="math-container">$$\mathbf{w} \leftarrow \mathbf{w} - \alpha \mathbf{m}$$</span></p>
  
  <p>There are some variants of these update rules in practice. An important one is Nesterov momentum.</p>
  
  <h2>Adam</h2>
  
  <p>The Adam optimiser maintains a momentum term, plus a scaling term, and also corrects these terms for initial bias. Adam has three parameters <span class="math-container">$\beta_m$</span> for momentum (typically 0.99), <span class="math-container">$\beta_v$</span> for scaling (typically 0.999) and <span class="math-container">$\epsilon$</span> to avoid divide by zero and numerical stability issues (typically <span class="math-container">$10^{-6}$</span>). </p>
  
  <p><em>Initialisation</em></p>
  
  <p><span class="math-container">$$\rho_m \leftarrow 1$$</span>
  <span class="math-container">$$\rho_v \leftarrow 1$$</span>
  <span class="math-container">$$\mathbf{m} \leftarrow \mathbf{0}$$</span>
  <span class="math-container">$$\mathbf{v} \leftarrow \mathbf{0}$$</span></p>
  
  <p><em>Update rules</em></p>
  
  <p><span class="math-container">$$\rho_m \leftarrow \beta_m \rho_m$$</span>
  <span class="math-container">$$\rho_v \leftarrow \beta_v \rho_v$$</span>
  <span class="math-container">$$\mathbf{m} \leftarrow \beta_m \mathbf{m} + (1-\beta_m) \nabla_w J$$</span>
  <span class="math-container">$$\mathbf{v} \leftarrow \beta_v \mathbf{v} + (1-\beta_v) (\nabla_w J \odot \nabla_w J)$$</span>
  <span class="math-container">$$\mathbf{w} \leftarrow \mathbf{w}- \alpha(\frac{\mathbf{m}}{\sqrt{\mathbf{v}}+\epsilon} \frac{\sqrt{1-\rho_v}}{1-\rho_m})$$</span></p>
  
  <p>The symbol <span class="math-container">$\odot$</span> stands for element-wise multiplication. Here that essentially means to square each term of the gradient to calculate terms in <span class="math-container">$\mathbf{v}$</span>. The square root and division of <span class="math-container">$\mathbf{m}$</span> by <span class="math-container">$\sqrt{\mathbf{v}}+\epsilon$</span> in the last update step are also handled element-wise.</p>
  
  <p>The variant I show here has an "optimisation" to the bias correction so that you don't need to calculate high powers of either of the parameters. You may see variants that don't have <span class="math-container">$\rho_m$</span> and <span class="math-container">$\rho_v$</span> (or equivalents), but instead use <span class="math-container">$\beta_{m}^t$</span> or <span class="math-container">$\beta_{v}^t$</span> directly, which is exactly what <span class="math-container">$\rho_m$</span> and <span class="math-container">$\rho_v$</span> represent.</p>
  
  <hr>
  
  <p>* <span class="math-container">$\nabla_w J$</span> is the gradient of <span class="math-container">$J$</span> with respect to <span class="math-container">$\mathbf{w}$</span>. By writing it this way, it also describes the goal of the update explicitly within the notation i.e. to minimise a function that is parameterised by <span class="math-container">$\mathbf{w}$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-13T09:30:08.487Z
Answers.LastActivityDate: 2020-01-13T09:43:45.517Z
Answers.LastEditDate: 2020-01-13T09:43:45.517Z
Answers.UserDisplayName: Neil Slater
Body: <p>In the gradient descent algorithm, the formula to update the weight <span class="math-container">$w$</span>, which has <span class="math-container">$g$</span> as the partial gradient of the loss function with respect to it, is:</p>
  <p><span class="math-container">$$w\ -= r \times g$$</span></p>
  <p>where <span class="math-container">$r$</span> is the learning rate.</p>
  <p>What should be the formula for momentum optimizer and Adam (adaptive momentum?) optimizer? Something should be added to the right side of the formula above?</p>
  
Tags: <machine-learning><gradient-descent><momentum><adam><optimizers>
Title: What is the formula for the momentum and Adam optimisers?
UserDisplayName: Dan D.
ThreadText: # What is the formula for the momentum and Adam optimisers?
  
  (Asked by: username_0 on 2020-01-13)
  
  In the gradient descent algorithm, the formula to update the weight $w$, which has $g$ as the partial gradient of the loss function with respect to it, is:
  
  $$w\ -= r \times g$$
  
  where $r$ is the learning rate.
  
  What should be the formula for momentum optimizer and Adam (adaptive momentum?) optimizer? Something should be added to the right side of the formula above?
  
  **Tags:** machine-learning, gradient-descent, momentum, adam, optimizers
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-01-13. Score: 9 | Accepted answer
  
  I'm going to use slightly different notation, $\leftarrow$ for an assignment, $\alpha$ for learning rate, $\nabla\_w J$ in place of $g$\* and implied multiplication as these are slightly more common. Also, using bold letters to represent vectors. In that notation, the update rule for basic gradient descent would be written as:
  
  $$\mathbf{w} \leftarrow \mathbf{w} - \alpha \nabla\_w J$$
  
  This cannot be extended to momentum and Adam update rules whilst keeping it as a single line and modifying the right hand side. That is because these variations of gradient descent maintain running statistics of previous gradient values, which have their own separate update rules. When implemented on a computer, these become additional terms, mainly vectors the same size as the weight vector being updated. These variables also require initialisation before use.
  
  ## Momentum
  
  Momentum maintains a "velocity" term which essentially tracks a recency-weighted average of gradients. However, the classic form of momentum given here does not normalise the resulting vector, and you often have to adjust the learning rate down when using it. Momentum has a parameter $\beta$ which should be between 0 and 1, and typically is set at $0.9$ or higher.
  
  *Intitialisation*
  
  $$\mathbf{m} \leftarrow \mathbf{0}$$
  
  *Update rules*
  
  $$\mathbf{m} \leftarrow \beta \mathbf{m} + \nabla\_w J$$
  $$\mathbf{w} \leftarrow \mathbf{w} - \alpha \mathbf{m}$$
  
  There are some variants of these update rules in practice. An important one is Nesterov momentum.
  
  ## Adam
  
  The Adam optimiser maintains a momentum term, plus a scaling term, and also corrects these terms for initial bias. Adam has three parameters $\beta\_m$ for momentum (typically 0.99), $\beta\_v$ for scaling (typically 0.999) and $\epsilon$ to avoid divide by zero and numerical stability issues (typically $10^{-6}$).
  
  *Initialisation*
  
  $$\rho\_m \leftarrow 1$$
  $$\rho\_v \leftarrow 1$$
  $$\mathbf{m} \leftarrow \mathbf{0}$$
  $$\mathbf{v} \leftarrow \mathbf{0}$$
  
  *Update rules*
  
  $$\rho\_m \leftarrow \beta\_m \rho\_m$$
  $$\rho\_v \leftarrow \beta\_v \rho\_v$$
  $$\mathbf{m} \leftarrow \beta\_m \mathbf{m} + (1-\beta\_m) \nabla\_w J$$
  $$\mathbf{v} \leftarrow \beta\_v \mathbf{v} + (1-\beta\_v) (\nabla\_w J \odot \nabla\_w J)$$
  $$\mathbf{w} \leftarrow \mathbf{w}- \alpha(\frac{\mathbf{m}}{\sqrt{\mathbf{v}}+\epsilon} \frac{\sqrt{1-\rho\_v}}{1-\rho\_m})$$
  
  The symbol $\odot$ stands for element-wise multiplication. Here that essentially means to square each term of the gradient to calculate terms in $\mathbf{v}$. The square root and division of $\mathbf{m}$ by $\sqrt{\mathbf{v}}+\epsilon$ in the last update step are also handled element-wise.
  
  The variant I show here has an "optimisation" to the bias correction so that you don't need to calculate high powers of either of the parameters. You may see variants that don't have $\rho\_m$ and $\rho\_v$ (or equivalents), but instead use $\beta\_{m}^t$ or $\beta\_{v}^t$ directly, which is exactly what $\rho\_m$ and $\rho\_v$ represent.
  
  ---
  
  \* $\nabla\_w J$ is the gradient of $J$ with respect to $\mathbf{w}$. By writing it this way, it also describes the goal of the update explicitly within the notation i.e. to minimise a function that is parameterised by $\mathbf{w}$.
  
  
  ---
  
  