Nadam

Author: Vinamr Jain (vj89) (ChemE 6800 Fall 2024)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

Nesterov-accelerated Adaptive Moment Estimation (Nadam) is an optimization algorithm introduced by Timothy Dozat in his 2016 paper, “Incorporating Nesterov Momentum into Adam” [1]. Nadam enhances the Adaptive Moment Estimation (Adam) optimizer by integrating Nesterov momentum, aiming to improve convergence speed and performance in training deep learning models. This algorithm has been applied across various domains, including computer vision and natural language processing, to optimize neural network training. Gradient descent optimization algorithms are fundamental tools in machine learning, often employed as black-box optimizers to minimize loss functions by iteratively adjusting model parameters. Gradient Descent updates parameters by following the negative gradient of the loss function to seek a minimum, but can be slow to converge, especially in regions with flat or elongated curvatures [2]. Several variants address these challenges. Momentum accelerates convergence by accumulating a decaying sum of past gradients, helping navigate ravines and reducing oscillations [1]. Nesterov’s Accelerated Gradient (NAG), also known as Nesterov momentum, improves upon Momentum by calculating the gradient at a projected future position, often resulting in faster convergence. RMSprop adapts learning rates for each parameter individually and normalizes gradients by a decaying average of recent magnitudes, effectively handling non-stationary objectives [3]. Adaptive Moment Estimation (Adam) [4] combines the benefits of Momentum and adaptive learning rates, computing individual adaptive rates based on first and second moments of gradients. However, Adam may sometimes converge to suboptimal solutions due to its adaptive learning rate mechanism [3] and can slow down before reaching global optima [2]. Nadam extends Adam by incorporating Nesterov momentum, evaluating the gradient at a projected future parameter position and improving convergence speed and accuracy.

Background

Gradient Descent is a first-order iterative optimization algorithm used to find a local minimum of a differentiable function. The parameter update rule at iteration $t$ is: $\theta _{t+1}=\theta _{t}-\eta \nabla _{\theta }J\left(\theta _{t}\right)$ Where $\theta _{t}$ denotes the parameters vector at iteration $t$, $\eta$ is the learning rate, and $\nabla _{\theta }J\left(\theta _{t}\right)$ is the gradient of the cost function $J$ with respect to $\theta$ at iteration $t$. Momentum accelerates Gradient Descent by accumulating an exponentially decaying moving average of past gradients. This accelerates gradient descent along stable gradient directions and slows it in oscillating directions [1].

$m_{t}=\gamma m_{t-1}+\eta \nabla _{\theta }J\left(\theta _{t}\right)$

$\theta _{t+1}=\theta _{t}-m_{t}$

Here in addition to the gradient component, there’s an additional term $m_{t}$, the momentum vector, and $\gamma$ is the momentum coefficient. Nesterov Momentum improves upon standard Momentum by calculating the gradient at the anticipated future position, leading to a more responsive update.

$m_{t}=\gamma m_{t-1}+\eta \nabla _{\theta }J\left(\theta _{t}-\gamma m_{t-1}\right)$

$\theta _{t+1}=\theta _{t}-m_{t}$

Alternatively, one can apply the current look-ahead momentum vector directly to update the current parameters:

$m_{t}=\gamma m_{t-1}+\eta \nabla _{\theta }J\left(\theta _{t}\right)$

$\theta _{t+1}=\theta _{t}-{(\gamma m}t\ +\ \eta {\ \nabla }\theta J\left(\theta _{t}\right)\ )$

AdaGrad (Adaptive Gradient Algorithm) adapts the learning rate for each parameter individually by scaling it inversely proportional to the square root of the sum of all historical squared values of the gradients. This method is particularly useful for dealing with sparse data [3].

$v_{t}=v_{t-1}+\left[\nabla _{\theta }J\left(\theta _{t}\right)\right]^{2}$

$\theta _{t+1}=\theta _{t}-\eta {\frac {\nabla _{\theta }J\left(\theta _{t}\right)}{{\sqrt {v_{t}}}+\epsilon }}$

$v_{t}$ is the accumulated sum of squared gradients up to time $t$, and $\epsilon$ is a small constant for numerical stability (e.g., $10^{-8}$). AdaGrad effectively scales down the learning rate for parameters associated with frequently occurring features, allowing for larger updates for infrequent features [1].

RMSprop (Root Mean Square Propagation) is an optimization algorithm that builds upon AdaGrad by modifying the way it accumulates squared gradients. While AdaGrad accumulates all past squared gradients, leading to a continually decreasing learning rate, RMSprop introduces a decay parameter to the accumulated squared gradients $v_{t}$. This parameterization prevents the learning rate from diminishing too quickly.

$v_{t}=\gamma v_{t-1}+\left(1-\gamma \right)\left[\nabla _{\theta }J\left(\theta _{t}\right)\right]^{2}$

$\theta _{t+1}=\theta _{t}-\eta {\frac {\nabla _{\theta }J\left(\theta _{t}\right)}{{\sqrt {v_{t}}}+\epsilon }}$

$\gamma$ is the decay rate (typically $\gamma =0.9$). By introducing the decay parameter in the $v_{t}$ term, RMSprop limits the influence of older gradients, ensuring that the algorithm adapts quickly to the most recent gradients.

Adam (Adaptive Moment Estimation) is an optimization algorithm that combines ideas from both Momentum and RMSprop. It extends RMSprop by not only adapting the learning rates per parameter but also incorporating momentum by using an exponentially decaying average of past gradients (first moment). Adam is designed to work well with sparse gradients and noisy problems, which are common in training deep neural networks.

$m_{t}=\beta _{1}m_{t-1}+\left(1-\beta _{1}\right)\nabla _{\theta }J\left(\theta _{t}\right)$

$v_{t}=\beta _{2}v_{t-1}+\left(1-\beta _{2}\right)\left[\nabla _{\theta }J\left(\theta _{t}\right)\right]^{2}$

$m_{t}$ is the first moment estimate (exponentially decaying average of past gradients), $v_{t}$ is the second moment estimate (exponentially decaying average of past squared gradients), and $\beta _{1}$ and $\beta _{2}$ are the exponential decay rates for the moment estimates (commonly $\beta _{1}=0.9,\beta _{2}=0.999$).

As $m_{t}$ and $v_{t}$ are initialized at zero vectors, they are biased towards zero, especially during the initial time steps and particularly when the decay rates are close to one (i.e., $\beta _{1},\beta _{2}\approx 1$). This bias can slow down the convergence of the algorithm because the moment estimates underestimate the true mean and variance of the gradients. To counteract these biases, the authors of Adam introduced bias-corrected moment estimates:

${\widehat {m_{t}}}={\frac {m_{t}}{1-\beta _{1}^{t}}}$

${\widehat {v_{t}}}={\frac {v_{t}}{1-\beta _{2}^{t}}}$

The denominators $1-\beta _{1}^{t}$ and $1-\beta _{2}^{t}$ approach 1 as $t$ increases, reducing the impact of the bias over time. The bias correction compensates for the initialization at zero, ensuring that the moment estimates are unbiased. The parameters are then updated using the bias-corrected moment estimates:

$\theta _{t+1}=\theta _{t}-\eta {\frac {\widehat {m_{t}}}{{\sqrt {\widehat {v_{t}}}}+\epsilon }}$

Algorithm

Nadam modifies the parameter update step of Adam by integrating the Nesterov accelerated gradient. In Adam, the update relies solely on the bias-corrected first moment estimate ${\widehat {m_{t}}}$. Nadam modifies the parameter update step of Adam by integrating the Nesterov accelerated gradient. In Adam, the update relies solely on the bias-corrected first moment estimate ${\widehat {m_{t}}}$. Nadam, however, adjusts this estimate by adding a term that accounts for the current gradient, effectively looking ahead to where the parameters are heading. This adjustment is similar to the Nesterov momentum in NAG, which computes the gradient at the approximate future position of the parameters. Firstly, consider the bias-corrected first moment ${\widehat {m_{t}}}$ using the definition of $m_{t}$ [3]

${\widehat {m_{t}}}={\frac {m_{t}}{1-\beta _{1}^{t}}}={\frac {\beta _{1}m_{t-1}+\left(1-\beta _{1}\right)g_{t}}{1-\beta _{1}^{t}}}$

Where $g_{t}=\nabla _{\theta }J\left(\theta _{t}\right)$. The update rule of Adam can be rewritten as

$\theta _{t+1}=\theta _{t}-{\frac {\eta }{\left({\sqrt {\widehat {v_{t}}}}+\epsilon \right)}}\left[{\frac {\beta _{1}m_{t-1}}{\left(1-\beta _{1}^{t}\right)}}+{\frac {\left(1-\beta _{1}\right)g_{t}}{\left(1-\beta _{1}^{t}\right)}}\right]$

Recognizing that ${\frac {\beta _{1}m_{t-1}}{1-\beta _{1}^{t}}}$ is the bias-corrected estimate of the momentum vector from the previous time step, let’s denote:

${\widehat {m_{t-1}}}={\frac {m_{t-1}}{1-\beta _{1}^{t-1}}}$

However, since $\beta _{1}^{t-1}$ is close to $\beta _{1}^{t}$ for large $t$, it can be approximated as:

${\frac {\beta _{1}m_{t-1}}{1-\beta _{1}^{t}}}\approx \beta _{1}{\widehat {m_{t-1}}}$ Thus, the update rule becomes:

$\theta _{t+1}=\theta _{t}-\eta {\frac {\beta _{1}{\widehat {m_{t-1}}}+{\frac {\left(1-\beta _{1}\right)g_{t}}{1-\beta _{1}^{t}}}}{{\sqrt {\widehat {v_{t}}}}+\epsilon }}$

This form resembles the momentum term in Nesterov Accelerated Gradient (NAG). To incorporate Nesterov momentum into Adam, the previous bias-corrected momentum estimate ${\widehat {m_{t-1}}}$ is replaced with the current estimate ${\widehat {m_{t}}}$. This aligns with the NAG approach of using the look-ahead momentum vector for updating parameters.

The Nadam update rule becomes:

$\theta _{t+1}=\theta _{t}-\eta {\frac {\beta _{1}{\widehat {m_{t}}}+{\frac {\left(1-\beta _{1}\right)g_{t}}{1-\beta _{1}^{t}}}}{{\sqrt {\widehat {v_{t}}}}+\epsilon }}$

By combining the bias-corrected first moment estimate ${\widehat {m_{t}}}$ and the current gradient $g_{t}$, weighted appropriately, Nadam aims to improve the responsiveness of the optimizer to recent gradient information, potentially enhancing convergence speed.

The pseudocode for Nadam is as follows:

Algorithm Nadam Optimization Input: Initial parameters $\theta _{0}$, learning rate $\eta$, decay rates $\beta _{1}$, $\beta _{2}$, small constant $\epsilon$

Initialize $m_{0}\gets 0,v_{0}\gets 0,t\gets 0$

While not converged do

$t\ \gets t\ +\ 1$

Compute gradient: $g_{t}=\nabla _{\theta }J\left(\theta _{t-1}\right)$

Update biased first moment: $m_{t}\gets \beta _{1}\cdot m_{t-1}+\left(1-\beta _{1}\right)\cdot g_{t}$

Update biased second moment: $v_{t}\gets \beta _{2}\cdot v_{t-1}+\left(1-\beta _{2}\right)\cdot g_{t}^{2}$

Bias correction: ${\widehat {m_{t}}}\gets {\frac {m_{t}}{1-\beta _{1}^{t}}},{\widehat {v_{t}}}\gets {\frac {v_{t}}{1-\beta _{2}^{t}}}$

Nesterov adjustment: $m'_{t}\gets \beta _{1}\cdot {\widehat {m_{t}}}+{\frac {\left(1-\beta _{1}\right)\cdot g_{t}}{1-\beta _{1}^{t}}}$

Update parameters: $\theta _{t}\gets \theta _{t-1}-\eta \cdot {\frac {m'_{t}}{{\sqrt {\widehat {v_{t}}}}+\epsilon }}$

Output: Optimized parameters $\theta _{t}$

Numerical Examples

This section provides numerical examples to illustrate how the Nadam algorithm operates. We choose a simple quadratic function to make the calculations straightforward and easy to follow, and then we demonstrate the numerical calculations for a linear regression task.

Minimizing a Quadratic Function

Consider the cost function: $J\left(\theta \right)={\frac {1}{2}}\theta ^{2}$which has its global minimum at $\theta =0$. The aim is to minimize this function using the Nadam optimizer, starting from an initial parameter value of $\theta _{0}=5$.

The hyperparameters are set as follows: learning rate $\eta =0.1$, exponential decay rates $\beta _{1},\beta _{2}=0.9$, numerical stability constant $\epsilon ={10}^{-8}$, and initialize the first and second moment estimates and the time step as $m_{0}=0,v_{0}=0,t=0$.

Iteration 1

1. Time Step Update:

$t\ \gets t\ +\ 1\ =\ 1$

2. Compute Gradient at Current Parameter:

$g_{1}=\nabla _{\theta }J\left(\theta _{0}\right)=\theta _{0}=5$

3. Update Biased First Moment Estimate:

$m_{1}=\beta _{1}m_{0}+\left(1-\beta _{1}\right)g_{1}=0.9\times 0+0.1\times 5=0.5$

4. Update Biased Second Moment Estimate:

$v_{1}=\beta _{2}v_{0}+\left(1-\beta _{2}\right)g_{1}^{2}=0.999\times 0+0.001\times 25=0.025$

5. Compute Bias-Corrected Estimates:

${\widehat {m_{1}}}={\frac {m_{1}}{1-\beta _{1}^{t}}}={\frac {0.5}{1-{0.9}^{1}}}={\frac {0.5}{0.1}}=5$

${\widehat {v_{1}}}={\frac {v_{1}}{1-\beta _{2}^{t}}}={\frac {0.025}{1-{0.999}^{1}}}={\frac {0.025}{0.001}}=25$

6. Nesterov Adjustment for First Moment:

$m\prime _{1}=\beta _{1}{\widehat {m_{1}}}+{\frac {\left(1-\beta _{1}\right)g_{1}}{1-\beta _{1}^{t}}}=0.9\times 5+{\frac {0.1\times 5}{0.1}}=4.5+5=9.5$

7. Parameter Update:

$\theta _{1}=\theta _{0}-\eta {\frac {m\prime _{1}}{{\sqrt {\widehat {v_{1}}}}+\epsilon }}=5-0.1\times {\frac {9.5}{{\sqrt {25}}+{10}^{-8}}}=5-0.1\times {\frac {9.5}{5}}=5-0.1\times 1.9=5-0.19=4.81$

Iteration 2

1. Time Step Update:

$t\ \gets t\ +\ 1\ =\ 2$

2. Compute Gradient at Current Parameter:

$g_{2}=\nabla _{\theta }J\left(\theta _{1}\right)=\theta _{1}=4.81$

3. Update Biased First Moment Estimate:

$m_{2}=\beta _{1}m_{1}+\left(1-\beta _{1}\right)g_{2}=0.9\times 0.5+0.1\times 4.81=0.45+0.481=0.931$

4. Update Biased Second Moment Estimate:

$v_{2}=\beta _{2}v_{1}+\left(1-\beta _{2}\right)g_{2}^{2}=0.999\times 0.025+0.001\times \left(4.81\right)^{2}=0.024975+0.001\times 23.1361=0.024975+0.0231361=0.0481111$

5. Compute Bias-Corrected Estimates:

${\widehat {m_{2}}}={\frac {m_{2}}{1-\beta _{1}^{t}}}={\frac {0.931}{1-{0.9}^{2}}}={\frac {0.931}{1-0.81}}={\frac {0.931}{0.19}}\approx 4.9005$

${\widehat {v_{2}}}={\frac {v_{2}}{1-\beta _{2}^{t}}}={\frac {0.0481111}{1-{0.999}^{2}}}={\frac {0.0481111}{1-0.998001}}={\frac {0.0481111}{0.001999}}\approx 24.0696$

6. Nesterov Adjustment for First Moment:

$m\prime _{2}=\beta _{1}{\widehat {m_{2}}}+{\frac {\left(1-\beta _{1}\right)g_{2}}{1-\beta _{1}^{t}}}=0.9\times 4.9005+{\frac {0.1\times 4.81}{0.19}}=4.41045+{\frac {0.481}{0.19}}\approx 4.41045+2.5316=6.9421$

7. Parameter Update:

$\theta _{2}=\theta _{1}-\eta {\frac {m\prime _{2}}{{\sqrt {\widehat {v_{2}}}}+\epsilon }}=4.81-0.1\times {\frac {6.9421}{{\sqrt {24.0696}}+{10}^{-8}}}=4.81-0.1\times {\frac {6.9421}{4.9061}}=4.81-0.1\times 1.4142=4.81-0.14142=4.6686$

Iteration 3

1. Time Step Update:

$t\ \gets t\ +\ 1\ =\ 3$

2. Compute Gradient at Current Parameter:

$g_{3}=\nabla _{\theta }J\left(\theta _{2}\right)=\theta _{2}=4.6686$

3. Update Biased First Moment Estimate:

$m_{3}=\beta _{1}m_{2}+\left(1-\beta _{1}\right)g_{3}=0.9\times 0.931+0.1\times 4.6686=0.8379+0.46686=1.30476$

4. Update Biased Second Moment Estimate:

$v_{3}=\beta _{2}v_{2}+\left(1-\beta _{2}\right)g_{3}^{2}=0.999\times 0.0481111+0.001\times \left(4.6686\right)^{2}=0.048063+0.001\times 21.7899=0.048063+0.0217899=0.0698529$

5. Compute Bias-Corrected Estimates:

${\widehat {m_{3}}}={\frac {m_{3}}{1-\beta _{1}^{t}}}={\frac {1.30476}{1-{0.9}^{3}}}={\frac {1.30476}{1-0.729}}={\frac {1.30476}{0.271}}\approx 4.8134$

${\widehat {v_{3}}}={\frac {v_{3}}{1-\beta _{2}^{t}}}={\frac {0.0698529}{1-{0.999}^{3}}}={\frac {0.0698529}{1-0.997002999}}={\frac {0.0698529}{0.002997001}}\approx 23.3132$

6. Nesterov Adjustment for First Moment:

$m\prime _{3}=\beta _{1}{\widehat {m_{3}}}+{\frac {\left(1-\beta _{1}\right)g_{3}}{1-\beta _{1}^{t}}}=0.9\times 4.8134+{\frac {0.1\times 4.6686}{0.271}}=4.3321+{\frac {0.46686}{0.271}}\approx 4.3321+1.7227=6.0548$

7. Parameter Update:

$\theta _{3}=\theta _{2}-\eta {\frac {m\prime _{3}}{{\sqrt {\widehat {v_{3}}}}+\epsilon }}=4.6686-0.1\times {\frac {6.0548}{{\sqrt {23.3132}}+{10}^{-8}}}=4.6686-0.1\times {\frac {6.0548}{4.8284}}=4.6686-0.1\times 1.2547=4.6686-0.12547=4.5431$

After three iterations, the parameter values have been updated as follows:

$\theta _{1}=4.81$

$\theta _{2}=4.6686$

$\theta _{3}=4.5431$

The parameter $\theta$ is gradually moving towards the global minimum at $\theta =0$, demonstrating how the Nadam optimizer adjusts the parameters efficiently.