The core intuition behind momentum is that averaging past gradients produces smoother, more effective updates. In a direction where the objective function has consistent curvature (such as the $$x_1$$ direction on an elongated quadratic), successive gradients are well-aligned, so their running average preserves a large step in that direction—accelerating progress toward the minimum. Conversely, in a direction where the gradient oscillates between positive and negative values on consecutive steps (such as the $$x_2$$ direction on the same elongated quadratic), the averaged gradient becomes small because the opposing contributions cancel each other out. This selective dampening of oscillations and amplification of consistent descent is what allows momentum to navigate ill-conditioned landscapes far more efficiently than plain gradient descent.

Intuition behind Gradient Descent with Momentum

These plots were generated with gradient descent; with gradient descent with momentum (β = 0.5) and gradient descent with momentum (β = 0.9). Which curve corresponds to which algorithm?

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)

The momentum method, an accelerated gradient method widely used in deep learning optimization, was originally proposed by Boris T. Polyak in $$1964$$.

Origin of the Momentum Method

When implementing the momentum method in optimization, the velocity vector $$\mathbf{v}_t$$ accumulates past gradients to update the parameters. At the beginning of the optimization process, specifically at time $$t=0$$, this velocity vector is conveniently initialized to zero, denoted as $$\mathbf{v}_0 = 0$$.

Velocity Initialization in Momentum Method

To mathematically analyze the convergence of the momentum method on a scalar quadratic function $$f(x) = \frac{\lambda}{2} x^2$$, the update equations for both the position $$x$$ and velocity $$v$$ can be formulated as a coupled system: $$\begin{bmatrix} v_{t+1} \ x_{t+1} \end{bmatrix} = \begin{bmatrix} \beta & \lambda \ -\eta \beta & (1 - \eta \lambda) \end{bmatrix} \begin{bmatrix} v_{t} \ x_{t} \end{bmatrix}$$. The convergence behavior is entirely governed by the eigenvalues of this $$2 	imes 2$$ transition matrix. Mathematical analysis of this matrix shows that the velocity converges when the hyperparameters satisfy $$0 < \eta \lambda < 2 + 2 \beta$$. This feasible range is substantially larger than the $$0 < \eta \lambda < 2$$ constraint required for standard gradient descent, mathematically confirming that large momentum coefficients ($$\beta$$) safely permit much larger learning rates without divergence.

Momentum Convergence on a Scalar Quadratic

On iteration $$t$$: Compute $$dW$$, $$db$$ on the current mini-batch

$$v_{dW} = \beta v_{dW} + (1-\beta)dW$$

$$v_{db} = \beta v_{db} + (1-\beta)db$$

$$W = W - \alpha v_{dW}, b = b - \alpha v_{db}$$

Note that now we have two parameters $$\alpha$$ and $$\beta$$.

Gradient Descent with Momentum Pseudocode

The basic idea of gradient descent with momentum is to compute an exponentially weighted average of your gradients, and then use that gradient to update your weights instead. It almost always works faster than the standard gradient descent algorithm.


University of Michigan - Ann Arbor

Claude

Exponentially weighted average is a technique frequently used for time-series data. By taking the average sum of previous data, you could smooth your data series and get an approximate trend of it. 

Consider you have a series of data points $\theta_0,...,\theta_n$,
$$\left\{ \begin{array}{ll}v_t = \theta_t & t=0 \\
v_t = \beta v_{t-1} +(1-\beta)\theta_t & otherwise \end{array}\right.$$
If we expand the second formula,
$v_t  = \beta v_{t-1}+(1-\beta)\theta_t$ 
      $= (1-\beta)\theta_t+\beta(\beta v_{t-2}+(1-\beta)\theta_{t-1})$
      $= (1-\beta)\theta_t + (1-\beta)\beta\theta_{t-1}+ (1-\beta)\beta^2\theta_{t-2}+...$
To get a sense of how the weighted term changes as $\beta$ gets closer to 1,
$$(1 - \epsilon)^{1 / \epsilon}\approx \frac{1}{\epsilon} \Rightarrow \beta^{1/(1-\beta)}\approx \frac{1}{\epsilon}$$
If we denote $w_i$ be the weight we assign to $\theta_i$, then
                                         $w_{t-1/(1-\beta)}=\frac{1}{\epsilon}w_t$
Therefore, we are approximately average over $1/(1-\beta)$ days when calculating $v_t$.

Exponentially Weighted Average

When a neural network trains, it uses an algorithm to determine the optimal weights for the model, called an optimizer. 
There are several optimizer algorithms, such as:
- Gradient descent
- Mini-batch gradient descent
- Gradient descent with momentum
- RMSprop
- Adam optimization algorithm
- Nesterov momentum
- AdaGrad

Deep Learning Optimizer Algorithms

Assuming that the error function is $J(w)$ with one parameter $w$, to minimize the error, we can update the weight $w$ as follows.
$$w = w - \alpha * \frac{dJ(w)}{dw}$$
, where $\alpha$ is a learning rate, and $\frac{dJ(w)}{dw}$ is the derivative of $J(w)$ with respect to $w$.

If the error function has two or more parameters, for example, a weight $w$ and a bias $b$, we can update them one by one.
$$w = w - \alpha * \frac{\partial J(w,b)}{\partial w}$$
$$b = b - \alpha * \frac{\partial J(w,b)}{\partial b}$$
, where $\partial$ is a stylish cursive $d$, denoting the partial derivatives.

(Batch) Gradient Descent (Deep Learning Optimization Algorithm)

https://www.coursera.org/learn/deep-neural-network?specialization=deep-learning

Improving Deep Neural Networks: Hyperparameter tuning, Regularization and Optimization

A helpful website for understanding gradient descent:
https://towardsdatascience.com/gradient-descent-explained-9b953fc0d2c

Gradient Descent Reference

Dive into Deep Learning

Assume we have a data series of temperature (blue dots), we could use the formula shown in the parent node to get an approximate trend. 
When $\beta=0.9$,
                   $\frac{1}{1-\beta} = \frac{1}{1-0.9} = 10$
So we are averaging over about 10 days.
When $\beta=0.98$,
                   $\frac{1}{1-\beta} = \frac{1}{1-0.98} = 50$
So we are averaging over about 50 days. Thus we will get a smoother curve as shown below.

An Example of Exponentially Weighted Average

Gradient Descent with Momentum

- 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)

In an exponentially weighted average, when the time step $$t$$ is small, the estimation only considers a few data points. This can cause an initial bias towards smaller values, especially if the initial value is set to $$v_0 = 0$$. Bias correction adjusts these early estimates to provide a more accurate trend. The bias-corrected value $$v_t'$$ is calculated as:

$$v_t' = \frac{v_t}{1 - \beta^t}$$

where $$v_t$$ is the uncorrected exponentially weighted average and $$\beta$$ is the weighting parameter. For example, as shown in the accompanying diagram, without correction, the early temperature estimates (the purple curve) indicate artificially low values due to the influence of the zero initialization, whereas the bias-corrected estimates (the green curve) better approximate the true underlying trend.

Bias Correction in Exponentially Weighted Averages

Batch Gradient Descent requires the entire dataset to be processed to complete one step. Gradient Descent can require many steps in some cases which causes this procedure to be very slow and inefficient for large datasets.

Mini-Batch Gradient Descent solves this problem by taking small groups of random data points called mini-batches and using them to estimate each step.  The mini-batches are usually a size greater than 1 but less than N (dataset size). The smaller steps allow for a much faster algorithm.

Mini-Batch Gradient Descent

Here is a very helpful article on different types of optimizer algorithms
https://ruder.io/optimizing-gradient-descent/index.html

An overview of gradient descent optimization algorithms

Learning rate decay is the gradual reduction of the learning rate as a function of time to speed up the learning algorithm. Decaying the learning rate as the gradient descent approaches completion reduces noise and facilitates a tighter convergence to a target.

Learning Rate Decay

Gradient descent is a fundamental optimization algorithm that leverages gradients to minimize a model's loss function. Because the gradient of a function points in the direction of steepest ascent, moving the model's parameters in the opposite direction iteratively lowers the loss. Each step of such gradient-based optimization algorithms requires calculating the exact gradient of the loss with respect to the parameters.

Gradient Descent

In the momentum method we basically first moved our weight in the direction of the current gradient and then moved in the direction  of momentum (weighted sum of all previous steps). Now in the new method we first move in the direction of the momentum and then calculate the gradient at the new point. Using this gradient we move in the direction of the new gradient. 

The update rules are as follows:
$$v \leftarrow \alpha v - \epsilon \nabla_{\theta} [\frac{1}{m} \sum^{m}_{i=1} L(f(x^{(i)};\theta + \alpha v), y^{(i)})]$$
$$\theta \leftarrow \theta + v$$

Nesterov momentum (Deep Learning Optimization Algorithm)

- **Local optima**: it's actually unlikely to get stuck in local optima.
- **Cliffs**: on the face of an extremely steep cliﬀ structure, the
gradient update step can move the parameters extremely far
- **Inexact Gradients**: sometimes approximation is needed for gradients
- **Plateaus**: low cost function slope (close to flat) makes learning slow.

Challenges with Deep Learning Optimizer Algorithms

Adam stands for: adaptive moment estimation. Briefly, this method combines momentum and RMSprop (root mean squared prop).
Like momentum alone, RMSprop smooths the gradient, (it takes RMSProp and applies momentum to the rescaled gradients). This alternative approach is best explained mathematically:

Adam introduces four hyperparameters:
- learning rate alpha
- beta from momentum (usually 0.9)
- beta2 from RMSprop (usually 0.999)
- epsilon (usually 1e-8)

As mentioned above, you usually do not need to tune beta, beta2, and epsilon as the values listed above will generally work well. Only the learning rate is left to tune in order to accelerate training.


Adam combines the advantages of AdaGrad and RMSProp these two optimization algorithms. It comprehensively considers the first moment estimation of the gradient (First Moment Estimation, the mean value of the gradient) and the second moment estimation (Second Moment Estimation, the uncentered variance of the gradient), and calculates the update step size.

Adam optimization algorithm


Adam is different to classical stochastic gradient descent (SGD). SGD maintains a single learning rate (alpha) for all weight updates and the learning rate does not change during training. Adam combines the advantages of AdaGrad and RMSProp. It not only adapts the parameter learning rates based on the average first moment (the mean) as in RMAProp, but also makes use of the average of the second moments of the gradients (the uncentered variance).

Difference between Adam and SGD

The Adagrad optimization algorithm addresses the difficulty of tuning learning rates for sparse features by replacing simple feature occurrence counters with an aggregate of the squares of previously observed gradients. Specifically, it uses $$s(i, t+1) = s(i, t) + \left(\partial_i f(\mathbf{x})\right)^2$$ to adjust the learning rate. This automatically scales down the step size significantly for coordinates that frequently have large gradients, while applying a gentler treatment to coordinates with small gradients, thereby eliminating the need to manually decide when a gradient is considered large enough.

Adagrad

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

The gradient $\nabla_x f(x)$ of a scalar function $f(x_1, x_2, x_3, ..., x_n)$ is defined as the unique vector field whose dot product with any vector $v$ at each point $x$ is the directional derivative of $f$ along $v$. That is,
$ \nabla_x f(x) \cdot  v = \nabla_v f(x) $

The directional derivative in direction $v$ (a unit vector) is the slope of the function $f$ in direction $v$, namely the rate of increase of $f$ per unit of distance moved in the direction given by $v$. 

To minimize $f$, we would like to ﬁnd the direction in which $f$ decreases the fastest. We can do this using the directional derivative:
$\min_{v, v^Tv = 1} \nabla_x f(x) \cdot  v= \min_{v, v^Tv = 1} ||\nabla_x f(x)||_2 ||v||_2 \cos \theta$
where θ is the angle between $v$ and the gradient. Substituting in $||v||_2= 1$ and ignoring factors that do not depend on $v$, this simpliﬁes to $\min_{v}cos θ$.

This is minimized when $v$ points in the opposite direction as the gradient. In otherwords, the gradient points directly uphill, and the negative gradient points directly down hill. We can decrease $f$ by moving in the direction of the negative gradient.

Hence we have $x' = x-\alpha \frac{df(x)}{dx}$ where $\alpha$ is the learning rate, a positive scalar determining the size of the step.

Derivation of the Gradient Descent Formula

Epoch is every iteration of gradient descent through the entire training set.

Epoch in Gradient Descent

For logistic regression, the gradient is given by ∂∂θjJ(θ)=1m∑mi=1(hθ(x(i))−y(i))x(i)j. Which of these is a correct gradient descent update for logistic regression with a learning rate of α?

Does adding polynomial features (e.g., instead using $h\theta(x)=g(\theta0+\theta1x1+\theta2x2+\theta3x21+\theta4x1x2+\theta5x22) )$ could increase how well we can fit the training data?

Suppose you have the following training set, and fit a logistic regression classifier $h\theta(x)=g(\theta0+\theta1x1+\theta2x2)$.

Backpropagation is a systematic computational procedure for applying the chain rule to calculate gradients automatically. It operates by traversing a computational graph in a backwards direction—from the output loss back to the input parameters—multiplying matrices of partial derivatives at each step to determine how parameters affect the final output.

Backpropagation

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.

Batch vs Stochastic vs Mini-Batch Gradient Descent

If we only have two features, $$x_1$$ and $$x_2$$, in order to minimize the loss function, we can apply gradient descent to update $$w_1$$, $$w_2$$, and $$b$$. To compute the derivatives of $$\mathcal{L}(a, y)$$ with respect to $$w_1$$, $$w_2$$, and $$b$$, we need to compute the derivatives of $$\mathcal{L}(a, y)$$ with respect to $$a$$ and $$z$$ first. $$\mathcal{L}(a, y) = -(y \log(a) + (1 - y) \log(1 - a)) \Rightarrow$$ $$\frac{d\mathcal{L}(a, y)}{da} = -\frac{y}{a}+\frac{1-y}{1-a}$$ $$a = \sigma(z) = \frac{1}{1 + e^{-z}} \Rightarrow \frac{da}{dz} = a(1-a) \Rightarrow$$ $$\begin{aligned} \frac{d\mathcal{L}(a, y)}{dz} & = \frac{d\mathcal{L}(a, y)}{da}\frac{da}{dz} \\ & = \left(-\frac{y}{a}+\frac{1-y}{1-a}\right)(a(1-a)) = a-y \end{aligned}$$ $$\begin{aligned} \frac{d\mathcal{L}(a, y)}{dw_1} & = \frac{d\mathcal{L}(a, y)}{dz}\frac{dz}{dw_1} = (a-y)x_1 \end{aligned}$$ $$\begin{aligned} \frac{d\mathcal{L}(a, y)}{dw_2} & = \frac{d\mathcal{L}(a, y)}{dz}\frac{dz}{dw_2} = (a-y)x_2 \end{aligned}$$ $$\begin{aligned} \frac{d\mathcal{L}(a, y)}{db} & = \frac{d\mathcal{L}(a, y)}{dz}\frac{dz}{db} = (a-y) \cdot 1 = a-y \end{aligned}$$

Learn Before

Related

Learn After