- Adam is fast, but tends to overfit
- SGD is slow but gives great results
- RMSProp sometimes works best
- SWA can easily improve quality
- AdaTune magically improves the learning rate

University of Michigan - Ann Arbor

Adam stands for adaptive moment estimation.
It combines gradient descent with momentum, and RMSProp. It brings the benefits from both sides - adaptive learning rate and faster convergence with momentum.

Adam (Deep Learning Optimization Algorithm)

- Stands for Root Mean Square Propagation
- RMSProp is an optimization algorithm closely related to AdaGrad, as both employ the square of the gradient to scale the update coefficients on a per-coordinate basis. However, RMSProp overcomes AdaGrad's tendency for radically diminishing learning rates by using a leaky (exponentially weighted) average of squared gradients rather than a cumulative sum.
- RMSProp also shares the leaky averaging mechanism with the momentum method, but applies it differently: whereas momentum uses leaky averaging to smooth the gradient direction, RMSProp uses the technique to adjust the coefficient-wise preconditioner that rescales the learning rate independently for each parameter.
- Because RMSProp does not automatically schedule the learning rate (unlike AdaGrad, whose learning rate decays implicitly through accumulation), the learning rate must be explicitly scheduled by the practitioner in practice.
- The decay coefficient $$\gamma$$ governs how long the gradient history is retained when adjusting the per-coordinate scale: a larger $$\gamma$$ produces a longer memory, while a smaller $$\gamma$$ makes the algorithm more responsive to recent gradients.

RMSprop (Deep Learning Optimization Algorithm)

If we choose the mini-batch size to be 1, then it gives the algorithm called Stochastic Gradient Descent or SGD.

In this case, on every iteration, you're taking gradient descent with just a single training example
$w = w - \alpha \nabla_w J(x^i, y^i; w)$

The most important property of SGD is that computation time per step does not grow with the number of examples. This makes SGD very efficient with large training sets.

The learning rate is a hyperparameter that must be adjusted. Unlike regular parameters of a model (weights like w and b), which are learned by the algorithm from the training set, hyperparameters are special parameters chosen by the algorithm designer that affect how the algorithm works.

Stochastic Gradient Descent Algorithm

https://www.youtube.com/watch?v=S27pHKBEp30

LSTM is dead. Long Live Transformers!

Keskar, N. S., & Socher, R. (2017). Improving generalization performance by switching from adam to sgd. arXiv preprint arXiv:1712.07628.

Improving Generalization Performance by Switching from Adam to SGD

```python
import numpy as np

class Adam():
  
    self.beta1 = 0.9
    self.beta2 = 0.99

    # Here is the M amd V matrices for the parameters and biases
    self.m_weights = np.zeros((input_dims, nodes))
    self.v_weights = np.zeros((input_dims, nodes))
    self.m_biases = np.zeros(nodes)
    self.v_biases = np.zeros(nodes)

    # need to track thecurrent time stamp
    self.curr_iter = 0

    def get_steps(self, grad_weights, grad_biases, learning_rate):

        eps = 1e-8

        # Just follows the formula and returns the update that have to be 
        # subtracted from the parametes and biases
      
        self.m_weights = self.beta1 * self.m_weights + (1 - self.beta1) * grad_weights
        self.v_weights = self.beta2 * self.v_weights + (1 - self.beta2) * np.power(grad_weights, 2)
        self.m_biases = self.beta1 * self.m_biases + (1 - self.beta1) * grad_biases
        self.v_biases = self.beta2 * self.v_biases + (1 - self.beta2) * np.power(grad_biases, 2)

        self.curr_iter += 1
        self.m_weights = self.m_weights / (1 - np.power(self.beta1, self.curr_iter))
        self.v_weights = self.v_weights / (1 - np.power(self.beta2, self.curr_iter))
        self.m_biases = self.m_biases / (1 - np.power(self.beta1, self.curr_iter))
        self.v_biases = self.v_biases / (1 - np.power(self.beta2, self.curr_iter))

        weights_step = np.multiply((learning_rate / (np.sqrt(self.v_weights) + eps)), self.m_weights)
        biases_step = np.multiply((learning_rate / (np.sqrt(self.v_biases) + eps)), self.m_biases)

        return weights_step, biases_step
```

Adam (Deep Learning Optimization Algorithm) Python Implementation

Adam vs. SGD vs. RMSProp vs. SWA vs. AdaTune

A key component of the Adam optimization algorithm is its use of exponential weighted moving averages, or leaky averaging, to estimate both the momentum and the second moment of the gradient. At each time step $$t$$, it maintains two state variables: $$\mathbf{v}_t \leftarrow \beta_1 \mathbf{v}_{t-1} + (1 - \beta_1) \mathbf{g}_t$$ and $$\mathbf{s}_t \leftarrow \beta_2 \mathbf{s}_{t-1} + (1 - \beta_2) \mathbf{g}_t^2$$. The terms $$\beta_1$$ and $$\beta_2$$ are nonnegative weighting parameters. Common default choices are $$\beta_1 = 0.9$$ and $$\beta_2 = 0.999$$, which ensures that the variance estimate $$\mathbf{s}_t$$ adapts much more slowly than the momentum term $$\mathbf{v}_t$$.

Adam State Variables

After computing the bias-corrected state variables, the Adam optimization algorithm calculates its final parameter updates. First, it rescales the gradient to obtain $$\mathbf{g}_t' = \frac{\eta \hat{\mathbf{v}}_t}{\sqrt{\hat{\mathbf{s}}_t} + \epsilon}$$. While similar to RMSProp, this rescaling uses the debiased momentum $$\hat{\mathbf{v}}_t$$ rather than the raw gradient, and the $$\epsilon$$ parameter (typically $$10^{-6}$$ for numerical stability) is added outside the square root. Finally, the model parameters are updated using the explicit learning rate $$\eta$$, which controls the step length, via the simple rule $$\mathbf{x}_t \leftarrow \mathbf{x}_{t-1} - \mathbf{g}_t'$$.

Adam Optimizer Update Rule

```python
class RMSprop():
  
    # Object of this classes goes together with a layer parameters
    def __init__(self, input_dims, nodes):
  
      self.learning_rate = 0.01
      self.beta = 0.9

      # G matrx for parameters
      self.G_weights = np.zeros((input_dims, nodes))

      # G matrix for biases
      self.G_biases = np.zeros(nodes)


    # Function gets gradient of the weigths and biases
    # Returns the update that we need to substract from
    # the current weights and biases
    def get_steps(self, grad_weights, grad_biases):

      eps = 1e-8
      
      # updating G matrixes
      self.G_weights = self.beta * self.G_weights + (1 - self.beta) * np.power(grad_weights, 2)
      self.G_biases = self.beta * self.G_biases + (1 - self.beta) * np.power(grad_biases, 2)

      weights_step = np.multiply((self.learning_rate / np.sqrt(self.G_weights + eps)), grad_weights)
      biases_step = np.multiply((self.learning_rate / np.sqrt(self.G_biases + eps)), grad_biases)

      return weights_step, biases_step
```

RMSprop (Deep Learning Optimization Algorithm) Python implementation

On iteration t:
         Compute dW, db on the current mini-batch
                $S_{dW} = \beta S_{dW} + (1-\beta) dW^2$
                $S_{db} = \beta S_{db} + (1-\beta) db^2$
                $W := W - \alpha \frac{dW}{\sqrt{S_{dW}}}, b := b - \alpha \frac{db}{\sqrt{S_{db}}}$


RMSprop (Deep Learning Optimization Algorithm) Pseudocode

To visualize RMSProp's convergence behavior, the algorithm is applied to the two-dimensional quadratic function $$f(\mathbf{x}) = 0.1 x_1^2 + 2 x_2^2$$ with a learning rate of $$\eta = 0.4$$ and decay parameter $$\gamma = 0.9$$. The coordinate-wise implementation computes gradients $$g_1 = 0.2 x_1$$ and $$g_2 = 4 x_2$$, updates the leaky averages of squared gradients as $$s_i = \gamma s_i + (1 - \gamma) g_i^2$$, and adjusts each coordinate by $$x_i \leftarrow x_i - \frac{\eta}{\sqrt{s_i + \epsilon}} g_i$$. After $$20$$ epochs, the variables converge near the origin ($$x_1 \approx -0.0106$$, $$x_2 \approx 0$$). Unlike AdaGrad, which stalls in later iterations because the learning rate decreases too quickly, RMSProp maintains effective progress throughout training because $$\eta$$ is controlled independently from the state variable rescaling.

python
def rmsprop_2d(x1, x2, s1, s2):
    g1, g2, eps = 0.2 * x1, 4 * x2, 1e-6
    s1 = gamma * s1 + (1 - gamma) * g1 ** 2
    s2 = gamma * s2 + (1 - gamma) * g2 ** 2
    x1 -= eta / math.sqrt(s1 + eps) * g1
    x2 -= eta / math.sqrt(s2 + eps) * g2
    return x1, x2, s1, s2

eta, gamma = 0.4, 0.9


RMSProp Optimization Trajectory in 2D

A from-scratch implementation of the RMSProp optimizer for deep networks requires maintaining an auxiliary state variable for each parameter tensor, initialized to zeros with the same shape. During each update step, the state is updated as a leaky average of squared gradients: $$\mathbf{s} \leftarrow \gamma \mathbf{s} + (1 - \gamma) \mathbf{g}^2$$, where $$\gamma$$ is the decay factor and $$\mathbf{g}$$ is the current gradient. The parameter is then decremented by the learning rate times the gradient divided by the square root of the state plus a numerical stability constant ($$\epsilon = 10^{-6}$$). Finally, the parameter gradients are zeroed out.

In PyTorch, this can be implemented as follows:

python
def init_rmsprop_states(feature_dim):
    s_w = torch.zeros((feature_dim, 1))
    s_b = torch.zeros(1)
    return (s_w, s_b)

def rmsprop(params, states, hyperparams):
    gamma, eps = hyperparams['gamma'], 1e-6
    for p, s in zip(params, states):
        with torch.no_grad():
            s[:] = gamma * s + (1 - gamma) * torch.square(p.grad)
            p[:] -= hyperparams['lr'] * p.grad / torch.sqrt(s + eps)
        p.grad.data.zero_()


RMSProp Optimizer From-Scratch Implementation

When the weighting term $$\gamma$$ is set to $$0.9$$, the state variable $$\mathbf{s}$$ in RMSProp effectively aggregates information over the past $$\frac{1}{1 - \gamma} = \frac{1}{1 - 0.9} = 10$$ observations of the squared gradient. This applies the general exponentially weighted average principle—where a decay factor $$\beta$$ yields an effective window of $$\frac{1}{1 - \beta}$$—specifically to RMSProp's squared gradient state variable. The quantity $$\frac{1}{1 - \gamma}$$ defines the effective observation window: a larger $$\gamma$$ produces a longer memory (smoother average), while a smaller $$\gamma$$ makes the algorithm more responsive to recent gradients.

Effective Observation Window of RMSProp

The RMSProp update rule maintains a state variable $$G^{t}$$ that tracks the exponentially weighted average of squared gradients, and uses it to adaptively scale the learning rate:

$$G^{t} = \beta G^{t-1} + (1 - \beta) (
abla J(W^{t}))^2$$

$$W^{t} = W^{t-1} - \frac{\alpha}{\sqrt{G^{t} + \epsilon}} 
abla J(W^{t})$$

The same principle applies to the bias parameters.

- $$G^{t}$$: helper matrix for the algorithm
- $$\beta$$: the decay factor controlling how quickly the running average forgets old observations (typically around $$0.9$$)
- $$W^{t}$$: the model parameters
- $$\alpha$$: the initial learning rate (typically around $$0.01$$)
- $$\epsilon$$: a small constant to prevent division by zero (typically around $$10^{-6}$$ or $$10^{-8}$$)

RMSprop (Deep Learning Optimization Algorithm) Mathematical Implementations

Adadelta is an optimization algorithm that has no explicit learning rate parameter. Instead, it uses the rate of change in the parameters themselves to dynamically adapt the learning rate. To accomplish this, the algorithm utilizes two specific state variables: $$\mathbf{s}_t$$ to track a leaky average of the second moment of the gradient, and $$\Delta\mathbf{x}_t$$ to track a leaky average of the second moment of the model's parameter changes. The algorithm retains standard naming conventions for these variables to maintain consistency with similar optimization methods like momentum, AdaGrad, and RMSProp.

Adadelta

For a finite sample size $$n$$, the empirical data distribution is modeled as a discrete probability distribution $$p(x, y) = \frac{1}{n} \sum_{i=1}^n \delta_{x_i}(x) \delta_{y_i}(y)$$, where $$\delta$$ denotes the Dirac delta function. This discrete distribution theoretically justifies performing stochastic gradient descent over a finite dataset by drawing independent samples $$(x_i, y_i)$$ from it.

Finite Sample Distribution for Stochastic Gradient Descent

Optimality guarantees for stochastic gradient descent are generally unavailable when dealing with nonconvex objectives. In such cases, the number of local minima that would require checking to confirm a global optimum could be exponentially large, making theoretical guarantees intractable.

Lack of Optimality Guarantees in Nonconvex Optimization

A minimal from-scratch implementation of the stochastic gradient descent optimizer defines a function sgd(params, states, hyperparams) that accepts three arguments: a list of model parameters, optimizer states (unused for vanilla SGD), and a dictionary of hyperparameters. For each parameter tensor, the function subtracts the product of the learning rate and the parameter's gradient using an in-place operation, then zeroes the gradient. In PyTorch:

python
def sgd(params, states, hyperparams):
    for p in params:
        p.data.sub_(hyperparams['lr'] * p.grad)
        p.grad.data.zero_()


This function signature—taking params, states, and hyperparams—is deliberately general so that more advanced optimizers introduced later (e.g., momentum, Adam) can share the same calling convention by making use of the states argument for maintaining auxiliary variables.

SGD Optimizer From-Scratch Implementation

Batch gradient descent (batch size = $$N$$) produces low-noise gradient estimates and takes large, reliable steps toward the minimum. However, it may require considerable time per iteration and significant additional memory.

Stochastic gradient descent (batch size = $$1$$) is memory-efficient and well-suited for large datasets. However, it is extremely noisy because individual training examples may point in poor directions. SGD tends to oscillate and wander around the region of the minimum rather than converging directly to it.

Minibatch gradient descent (batch size between $$1$$ and $$N$$) offers a practical compromise. Although it does not guarantee monotonic progress toward the minimum, it tends to head more consistently in the right direction.

Experimentally, while SGD converges faster than batch GD in terms of the number of examples processed, it consumes more wall-clock time because computing the gradient example by example is computationally less efficient. Minibatch SGD balances convergence speed and computation efficiency: for instance, a batch size of $$100$$ can even outperform full-batch GD in runtime.

Learn Before

Related