7
$\begingroup$

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 optimiser and Adam (adaptive momentum?) optimiser? Something should be added to the right side of the formula above?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.