Mathematical Foundations for Machine Learning

Gradient Descent Optimization

Published: 2026-07-11

Level: postgraduate

Audience: Postgraduate students in Machine Learning and related quantitative fields

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Gradient Descent and the Update Rule — covered in Lecture 11 (section 11.1)
Learning Rate and Adaptive Methods Preview — covered in Lecture 11 (section 11.5)
The Gradient — Direction of Steepest Increase — covered in Lecture 9 (section 9.3)
The Hessian Matrix and Loss Surface Curvature — covered in Lecture 10 (section 10.5) and Lecture 12 (section 12.7)
Challenges of Gradient Descent and Lagrange's Method — covered in Lecture 12 (sections 12.2 and 12.4)

Gradient Descent Optimization

Gradient descent is the engine behind nearly every machine learning model. This lecture starts with the plain algorithm and shows exactly where it breaks. A single learning rate cannot serve a loss surface that is steep in one direction and flat in another. From there it builds the fixes in order . Momentum adds memory to smooth the path, Adagrad and RMSProp give each parameter its own learning rate, and Adam combines both ideas. The lecture closes with constrained optimization and the Lagrangian method. Which folds hard rules into the objective so the same machinery still applies. Worked examples with real numbers run through every optimizer, and the exam guidance distills what to memorize.

13.1 Problems with Gradient Descent

13.1.1 Definition and Explanation

Hook.You are a blindfolded hiker standing on a mountain. Your only tool is a sensor under your boots that tells you which direction the ground slopes steepest. You take a step downhill, check again, take another step. Can you guarantee reaching the valley floor? If the mountain is a smooth bowl — yes. But real mountains have flat plateaus where your sensor reads zero. And knife-edge ravines where one bad step sends you flying across to the other wall. This is gradient descent in the real world.

Gradient descent is an iterative optimization algorithm. You start at some point on the loss surface. You take steps proportional to the negative of the gradient. The goal is to reach a minimum. But gradient descent has fundamental failure modes when the loss surface has certain shapes.

Intuition + Analogy.Picture a long, narrow canyon. The walls are steep cliffs. The canyon floor slopes gently toward the exit, but it is nearly flat. Now imagine three hikers, each taking a different fixed step size.

Hiker Atakes tiny, cautious steps. On the cliffs, she makes slow but steady progress downward. But once she reaches the flat canyon floor, her steps become so small that she barely moves. She stalls out, thinking she has arrived. She hasn't — the exit is still ahead.
Hiker Btakes moderate strides. On the cliffs, each stride sends her crashing into the opposite wall. She bounces from wall to wall — zigzagging — making slow, inefficient progress along the canyon.
Hiker Ctakes huge leaps. On the cliffs, she bounds wildly from one wall to the other and back again. The bouncing cancels out. She is stuck in place, trapped. If she leaps even harder, she flies out of the canyon entirely.

This is exactly what happens with gradient descent when the loss surface has different steepness in different directions. The canyon walls represent the steep dimension of the loss surface. The canyon floor represents the flat dimension. Each hiker's stride length represents the learning rate $α$ . No single fixed stride works for both the steep walls and the flat floor.

The analogy breaks at one point: real loss surfaces have hundreds or millions of dimensions. You cannot visualize them. But the math works the same way — each dimension can have its own steepness. And a single learning rate must serve them all.

Aloss functionmaps your model parameters to a single number — how wrong your model is. The shape of this loss surface determines whether gradient descent will succeed or fail. A well-behaved loss surface is smooth and bowl-shaped. You can start at any point, slide down, and reach the bottom. But real loss surfaces are rarely that nice.

The two root problems come from thecurvatureof the loss surface. The curvature describes how steep the surface is in different directions. If the surface is highly curved — steep in one direction and flat in another — gradient descent struggles. The companion document calls these problematic featurescliffs(where slope changes dramatically from flat to steep) andvalleys/ravines(long narrow depressions with steep sides and a gently sloping floor). With a single fixed learning rate, you either crawl forever on the flat parts or bounce uncontrollably on the steep parts.

13.1.2 Symbol Registry

Symbol	Meaning	Type
$W_{i}$	Weight vector at step $i$	vector in $R^{d}$
$α$	Learning rate — step size	scalar, typical range $(0, 1)$
$\nabla L (W_{i})$	Gradient of the loss at $W_{i}$	vector in $R^{d}$
$x, y$	Position coordinates on the loss surface	scalar
$f (x, y)$	Loss function value at $(x, y)$	scalar

13.1.3 Three Failure Modes

The gradient descent update rule.At each step

i

, you compute the gradient . The vector of partial derivatives pointing in the direction of steepest ascent — and move in the opposite direction.

$W_{i + 1} = W_{i} - α \nabla L (W_{i})$

where.

$W_{i} \in R^{d}$ is the weight vector (your current position on the loss surface),
$α > 0$ is the learning rate (how big each step is),
$\nabla L (W_{i})$ is the gradient of the loss function at $W_{i}$ .

The negative sign is crucial: $\nabla L (W_{i})$ points uphill (steepest ascent), so $- α \nabla L (W_{i})$ points downhill. The learning rate $α$ scales the step. If $α$ is wrong for the terrain, the algorithm fails.

Problem 1: Vanishing updates on flat regions.When you have a small learning rate, each step is tiny. You descend slowly. Once you enter a flat region, the gradient becomes nearly zero. Since the update is $W_{i + 1} = W_{i} - α \nabla L (W_{i})$ , when $\nabla L (W_{i}) \approx 0$ , we get $W_{i + 1} \approx W_{i}$ . You sit there, barely moving. The minimum is further ahead, but the algorithm thinks it has arrived because the gradient says "you are on flat ground." You never reach the true minimum — your steps have died out.

Problem 2: Zigzag oscillation.When you increase the learning rate to fix Problem 1, a new problem appears. In directions where the surface is steep. A large step in the $- \nabla L$ direction shoots you across to the other side of the valley. Then the gradient points back the other way. You shoot across again. This creates a zigzag pattern — you oscillate back and forth across the valley floor. You are still making progress along the valley, but very inefficiently. Most of each step's movement cancels the previous step's side-to-side motion.

Problem 3: Getting trapped in the valley.In extreme cases, the oscillation becomes balanced. You jump from one wall of the valley to the other and back again. The updates exactly cancel each other out. You are stuck, bouncing in place. The loss does not decrease. This happens when the learning rate is high enough to overshoot the valley bottom. But not high enough to escape the valley entirely.

Problem 3b (bonus): Overshooting the trajectory.If the learning rate is pushed even higher, you can leave the relevant region of the loss surface entirely. The updates become so large that you fly off in some direction, never to return to the valley. The algorithm diverges completely — the loss grows without bound instead of shrinking.

The fundamental tension.The same learning rate

α

must serve all dimensions of the parameter space. In a dimension with large curvature (steep), a large

α

causes oscillation. In a dimension with small curvature (flat), a small

α

causes stalling. There is no single

α

that works for both. This is the core problem that momentum, Adagrad, RMSProp, and Adam were each invented to solve.

13.1.4 Worked Visualization

Consider a specific loss function designed to illustrate all three failure modes.

$f (x, y) = \frac{0.01 x ^{2} + 1.5 y ^{2}}{30}$

Look at the coefficients. The $x^{2}$ term has coefficient 0.01. The $y^{2}$ term has coefficient 1.5. The ratio is $1.5/0.01 = 150$ . The surface is 150 times steeper in the $y$ -direction than in the $x$ -direction. The surface looks like a long, narrow valley . Steep walls on the sides (the $y$ -direction), a gently sloping floor along the bottom (the $x$ -direction).

Step 1 — Compute the gradient.Take partial derivatives.

$\frac{\partial f}{\partial x} = \frac{0.02 x}{30} = \frac{x}{1500}, \frac{\partial f}{\partial y} = \frac{3 y}{30} = \frac{y}{10}$

So the gradient vector is.

$\nabla f (x, y) = [\frac{x}{1500} \frac{y}{10}]$

Notice the ratio: $\frac{1}{10} / \frac{1}{1500} = 150$ . The gradient in $y$ is 150 times larger than the gradient in $x$ for the same distance from the origin. This is the asymmetry.

Step 2 — Run gradient descent with different learning rates.Start at $(x_{0}, y_{0}) = (5, 5)$ and apply $W_{i + 1} = W_{i} - α \nabla f (W_{i})$ .

$α = 0.001$ (too small).Each step is tiny: $Δ x \approx - 0.001 \cdot \frac{5}{1500} = - 0.0000033$ , $Δ y \approx - 0.001 \cdot \frac{5}{10} = - 0.0005$ . After hundreds of steps, you get close to $(0, 0)$ but slow to a crawl. The updates vanish before you truly reach the minimum.
$α = 0.18$ (moderately high).The $y$ -direction oscillates. At $y = 5$ , $Δ y = - 0.18 \cdot 0.5 = - 0.09$ . Next step, $y \approx 4.91$ . The gradient pulls back. The $x$ -direction moves at $Δ x = - 0.18 \cdot 5/1500 = - 0.0006$ per step — painfully slow. You zigzag along the valley. After many iterations, the gradient shrinks near the center and you may or may not reach the true minimum.
$α = 0.20$ (high).Severe oscillation. The $y$ -coordinate bounces between positive and negative values. The update magnitudes in $y$ are roughly $\pm 0.20 \cdot 0.5 = 0.10$ , but the gradient direction flips each step. The $y$ position bounces symmetrically. You are trapped.
$α = 0.23$ (too high).The step overshoots so far that the gradient at the new point is even larger than before. The magnitude grows with each step: $∣ y_{1} ∣ > ∣ y_{0} ∣$ , then $∣ y_{2} ∣ > ∣ y_{1} ∣$ . The algorithm diverges — you fly out of the valley entirely.

Sense-check.The true minimum is at $(0, 0)$ . For $α > 0.20$ , the $y$ -update magnitude exceeds the distance to the minimum, causing overshoot. For $α < 0.18$ , the $x$ -update is so slow you stall. Only a narrow band of $α$ values works, and even then, convergence is slow.

Assumptions & Scope.

Assumptions that make gradient descent work.

The loss surface issmooth(differentiable everywhere). If the function has kinks or discontinuities, the gradient is not defined.
The loss surface iswell-conditioned— the ratio of largest to smallest curvature (the condition number) is close to 1. When the condition number is large (like 150 in our example), gradient descent struggles.
The learning rate $α$ is chosen appropriately for the problem. There is no universal good value.

When gradient descent fails.

Ravines / ill-conditioned surfaces— exactly the scenario in this section. A single $α$ cannot handle both steep and flat directions.
Saddle points— points where the gradient is zero but it is not a minimum (like the center of a Pringles chip). Gradient descent stops here even though lower ground exists.
Local minima— the gradient is zero, so the algorithm stops. But a lower minimum exists elsewhere. Gradient descent has no way to know.
Non-differentiable functions— if the loss function has sharp edges (like ReLU at zero, or constraint boundaries), the gradient is undefined at those points.

What this section does NOT cover.Momentum, adaptive learning rates, second-order methods (Newton's method), stochastic gradient descent, or constrained optimization. Each of these is designed to fix specific failure modes of plain gradient descent.

13.1.5 Visual Intuition

Imagine a 3D plot with $x$ and $y$ on the horizontal plane and $f (x, y)$ on the vertical axis. The surface is shaped like a long canyon running diagonally. The $y$ -axis direction has steep, nearly vertical walls. The $x$ -axis direction is a gentle slope, almost a flat plain.

Draw contour lines (lines of constant $f$ ) on the $x$ - $y$ plane. Near the origin, the contours are tightly packed in the $y$ -direction (steep) and widely spaced in the $x$ -direction (flat). The tight spacing means the gradient is large; the wide spacing means the gradient is small.

Now trace the path of gradient descent with $α = 0.18$ . The trajectory bounces from one side of the canyon to the other, making slow diagonal progress. Each bounce wastes movement crossing the canyon rather than moving along it. With $α = 0.001$ , the trajectory barely moves once it hits the flat center — it looks like it stopped. With $α = 0.23$ , the trajectory spirals outward and off the page.

Takeaway.The shape of the loss surface — not just the algorithm — determines whether gradient descent succeeds. A surface with a high condition number (like 150) makes plain gradient descent impractical.

13.1.6 Student Questions and Answers

Q.I understood the low learning rate case — you get stuck at a local minimum or valley. And the high learning rate case — you oscillate and sometimes overshoot. What is the third problem?

A.There are two distinct problems within the high-learning-rate regime. One is zigzag oscillation — you go from one side of the loss surface to the other, then back, making slow progress. The other is being trapped in that oscillation . You just keep bouncing between the two walls and never descend further because the updates cancel out. And there is a third scenario: if the rate is far too high, you overshoot the trajectory entirely and diverge. In terms of root cause, there are only two: $α$ too small (stalling) or $α$ too large (oscillation/trapping/divergence). The large- $α$ case splits into sub-problems depending on severity.

Pitfalls.

Confusing "flat region" with "minimum."Both have $\nabla L \approx 0$ . Gradient descent cannot tell them apart. If your loss stops decreasing, you need to check whether you are at a true minimum or just stuck on a plateau. Plot the loss curve and verify it has flattened near zero — not just stopped changing.
Treating the learning rate as a one-time choice.The right $α$ depends on the shape of the loss surface, which you do not know in advance. You must experiment. Start with $α = 0.01$ or $0.001$ , observe the loss curve, and adjust. Tools like grid search or Bayesian optimization can help, but they are computationally expensive.
Assuming all dimensions behave the same.They do not. The condition number of the Hessian (the matrix of second derivatives) tells you the ratio of steepest to flattest direction. If it is large (e.g., > 100), plain gradient descent will be slow no matter what $α$ you pick. You need momentum or adaptive methods.
Forgetting to normalize features.If your input features have different scales (e.g., one feature ranges 0–1 and another ranges 0–1000). The loss surface becomes a ravine just like our example. Normalizing features to zero mean and unit variance before training removes this artificial curvature and helps gradient descent enormously.
Checking only the final loss.Watch thetrajectory— the loss at each step. If it oscillates (goes up-down-up-down), your $α$ is too high. If it drops monotonically but incredibly slowly, your $α$ is too low. If it shoots up and never comes down, you have diverged.

Recap + Bridge.Plain gradient descent fails when the loss surface varies in steepness across dimensions. Because one fixed learning rate cannot serve both steep and flat directions. Small

α

stalls; large

α

oscillates. The next section introduces momentum . A modification that adds "memory" of past steps to smooth out the oscillation and carry you through flat regions. Momentum is the first of several fixes to the fundamental problems exposed here.

13.1.7 Real-World and Domain Connection

The failure modes of gradient descent are not academic curiosities. In deep learning, loss surfaces of neural networks are highly non-convex and ill-conditioned. Researchers have found that the Hessian of a trained neural network often has a few very large eigenvalues. And many near-zero ones . Exactly the ravine geometry we studied. This is why plain gradient descent is almost never used in modern deep learning. Every major framework (PyTorch, TensorFlow, JAX) defaults to momentum, Adam, or another adaptive variant. Understanding why plain gradient descent fails is the prerequisite to understanding why every subsequent optimizer exists. In production machine learning systems at companies like Google and Meta. The choice of optimizer and learning rate schedule can be the difference between a model that trains in hours versus one that never converges.

13.2 Momentum-Based Gradient Descent

13.2.1 Physical Intuition — The Heavy Ball

Hook.Rolling a marble down a bowl is easy. It finds the bottom and settles. But rolling a marble down our canyon from Section 13.1 — with steep walls and a flat floor — is hard. A marble with no weight gets stuck on the flat floor. A heavy marble, though, has momentum. It remembers where it was going. When it hits the flat spot, it keeps rolling. When it crosses the canyon, it settles into a path along the floor instead of bouncing wall-to-wall. How do we give gradient descent the physics of a heavy ball?

Standard gradient descent has no memory. Each step depends only on the current gradient. It does not "remember" that the previous step was large and in a certain direction. Momentum adds this memory.

Intuition + Analogy.Imagine pushing a heavy shopping cart down a sidewalk. You push it forward (gravity — the gradient). As it rolls, it gains speed. When you reach a flat stretch, you stop pushing, but the cart does not stop instantly. Its momentum carries it forward. If the sidewalk has side-to-side bumps, the cart's weight keeps it from jerking left and right . The forward momentum is stronger than the sideways bumps.

Now map this to optimization.

Thecart's positionat time $t$ is your parameter vector $W_{t}$ .
Thepush you giveat each step is the gradient $\nabla L (W_{t})$ — it points downhill.
Thecart's velocityis $v_{t}$ — how fast and in which direction it is currently rolling.
Thecart's weight(inertia) is controlled by $β$ — a friction parameter. A heavy cart ( $β$ close to 1) keeps rolling for a long time. A light cart ( $β$ close to 0) stops quickly and behaves like plain gradient descent.

In the canyon, the gradient tries to push you across the valley walls (side-to-side). But the momentum from rolling along the valley floor (forward) resists. Over time, the side-to-side pushes cancel each other out (positive then negative then positive), while the forward momentum accumulates. The cart finds a smooth path along the canyon floor.

The analogy breaks at one point: in physics, momentum is mass times velocity ( $p = m v$ ). Here, we do not have a mass parameter. Instead, $β$ acts like a friction/damping coefficient controlling how much past velocity survives into the next step. Think of $β$ as "how heavy the ball is" — higher $β$ means heavier, more momentum.

In physics, momentum is mass times velocity. A heavy ball rolling downhill gains velocity. When it reaches the bottom, that velocity carries it forward. It might overshoot slightly, then roll back, then overshoot less, then settle. The oscillations dampen out because friction is working against the velocity.

Standard gradient descent has no memory. Each step depends only on the current gradient. It does not "remember" that the previous step was large and in a certain direction. Momentum adds this memory. It says: "I was moving fast in this direction previously. Let me keep some of that speed, plus respond to the current gradient."

13.2.2 Symbol Registry

Symbol	Meaning	Type	Typical value
$W_{t}$	Weight vector at step $t$	vector in $R^{d}$	.
$v_{t}$	Velocity at step $t$	vector in $R^{d}$	.
$\nabla L (W_{t})$	Gradient of the loss at $W_{t}$	vector in $R^{d}$	.
$α$	Learning rate — step size	scalar	0.001–0.1
$β$	Friction parameter — scales old velocity	scalar $\in [0, 1)$	0.8–0.9

13.2.3 Mathematical Formulation

Momentum-based gradient descent uses two equations. The first builds the velocity (a smoothed version of the gradient history). The second updates the weights using the velocity instead of the raw gradient.

Velocity update — the memory equation.

$v_{t + 1} = β v_{t} + (1 - β) \nabla L (W_{t})$

This says: the new velocity $v_{t + 1}$ is a blend of the old velocity $v_{t}$ (weighted by $β$ ). And the current gradient $\nabla L (W_{t})$ (weighted by $1 - β$ ).

If $β = 0.9$ , you keep 90% of the old velocity and add only 10% of the current gradient. The velocity decays slowly — it has a long memory. Past gradients from many steps ago still influence the current velocity.
If $β = 0.5$ , you keep only 50% of the old velocity. The memory is short — only very recent gradients matter.
If $β = 0$ , $v_{t + 1} = \nabla L (W_{t})$ . The velocity is just the raw gradient. This reduces to plain gradient descent (see below).

Weight update — using the velocity.

$W_{t + 1} = W_{t} - α v_{t + 1}$

This is the key difference from standard gradient descent. Instead of stepping in the direction of $- \nabla L (W_{t})$ , you step in the direction of $- v_{t + 1}$ — the smoothed gradient history. The velocity $v_{t + 1}$ already incorporates past gradient information through the $β v_{t}$ term.

What happens at the first step.At $t = 0$ , there is no previous velocity. You set $v_{0} = 0$ . The very first velocity is then $v_{1} = (1 - β) \nabla L (W_{0})$ . This makes the first momentum step identical indirectionto a gradient descent step, butscaledby $(1 - β)$ . If $β = 0.8$ , the first step is only 20% as large as a pure gradient descent step with the same $α$ . This is why momentum often needs a slightly higher learning rate than plain gradient descent — the early steps are diminished.

Why the velocity dampens oscillation.Consider the canyon from Section 13.1. When you are on the left wall, the gradient points right (toward the right wall). The velocity, however, was built up from sliding down the left wall . It also points right, but its magnitude is driven by the steep wall slope. When you cross the center and land on the right wall, the gradient now points left. But the velocity — which is 90% old velocity — still points right (from the previous step). The two oppose each other. The velocity wins because $β = 0.9$ gives it 9× more weight than the new gradient. Instead of bouncing back immediately, you slide along the valley floor.

Think of two forces: the gradient pulls you across the valley (side-to-side). The velocity pulls you along the valley (forward). Over many steps, the side-to-side gradient pulls cancel out (positive, negative, positive...), while the forward velocity accumulates. The net result is smooth forward progress.

When $β = 0$ .If you set $β = 0$ .

$v_{t + 1} = 0 \cdot v_{t} + (1 - 0) \cdot \nabla L (W_{t}) = \nabla L (W_{t})$

$W_{t + 1} = W_{t} - α \cdot v_{t + 1} = W_{t} - α \cdot \nabla L (W_{t})$

This is exactly standard gradient descent. Momentum with $β = 0$ reduces to plain gradient descent. So momentum is a generalization — gradient descent is the special case with no memory. As $β$ increases, you get more and more momentum.

Why you cannot use velocity alone (without gradient).The gradient provides the local terrain information — which way is downhill right here, right now. The velocity provides history — where you were going before. Without the gradient, the velocity would never change direction, even if you passed the minimum and started going uphill. The gradient acts as a steering wheel. The velocity acts as the engine. You need both. The equation $v_{t + 1} = β v_{t} + (1 - β) \nabla L (W_{t})$ blends them: the $β v_{t}$ term is the engine (momentum), the $(1 - β) \nabla L$ term is the steering wheel (gradient).

Notation note — alternative formulations.The companion document for this lecture uses a different (but equivalent) form.

$x_{t + 1} = x_{t} - α \nabla f (x_{t}) + β (x_{t} - x_{t - 1})$

In this version, the momentum term $β (x_{t} - x_{t - 1})$ is theactual previous displacement(the vector from the old position to the current position), not a separate velocity variable. This is sometimes called the "heavy ball" form after Polyak (1964). Both forms encode the same idea: the update includes a fraction of the previous step. The two-equation velocity form used in this lecture is the standard implementation in PyTorch, TensorFlow. And JAX because it requires storing only the velocity vector $v_{t}$ rather than both $W_{t}$ and $W_{t - 1}$ . The equivalence: if you define $v_{t + 1} = W_{t} - W_{t + 1}$ (up to scaling by $α$ ), the two forms match.

13.2.4 Worked Example — Momentum Step Calculation

Consider the same loss function from Section 13.1.

$f (x, y) = \frac{0.01 x ^{2} + 1.5 y ^{2}}{30}$

with gradient.

$\nabla f (x, y) = [\frac{0.02 x}{30} \frac{3 y}{30}] = [\frac{x}{1500} \frac{y}{10}]$

Start at $W_{0} = (x_{0}, y_{0}) = (180.9, 76.3)$ . Use momentum with $β = 0.8$ and $α = 0.01$ .

Step 1 — Compute the gradient at $W_{0}$ .

$\nabla f (W_{0}) = [\frac{180.9}{1500} \frac{76.3}{10}] = [0.1206 7.63]$

Notice the $y$ -component is about 63× larger than the $x$ -component. The surface is much steeper in $y$ .

Step 2 — Compute the first velocity.With $β = 0.8$ and $v_{0} = 0$ .

$v_{1} = β v_{0} + (1 - β) \nabla f (W_{0}) = 0.8 \cdot [00] + 0.2 \cdot [0.1206 7.63] = [0.02412 1.526]$

The first velocity is exactly 20% of the gradient. The $y$ -component (1.526) dominates — as expected, since the surface is much steeper in the $y$ -direction.

Step 3 — Weight update.

$W_{1} = W_{0} - α \cdot v_{1} = [180.9 76.3] - 0.01 \cdot [0.02412 1.526] = [180.9 - 0.000241 76.3 - 0.01526] = [180.8998 76.2847]$

The $x$ -coordinate barely moves (drop of 0.0002). The $y$ -coordinate drops by 0.015. Both changes are small because $α = 0.01$ and the first step is further reduced by the $(1 - β) = 0.2$ factor.

Step 4 — Second gradient.At $W_{1} = (180.8998, 76.2847)$ .

$\nabla f (W_{1}) = [\frac{180.8998}{1500} \frac{76.2847}{10}] = [0.1206 7.6285]$

Step 5 — Second velocity.

$v_{2} = β v_{1} + (1 - β) \nabla f (W_{1}) = 0.8 \cdot [0.02412 1.526] + 0.2 \cdot [0.1206 7.6285]$

$= [0.01930 1.2208] + [0.02412 1.5257] = [0.04342 2.7465]$

Notice what happened: the old velocity contributed $[0.01930, 1.2208]$ and the new gradient contributed $[0.02412, 1.5257]$ . They add constructively in this step because both point in the same direction (downhill). The velocity is growing — the ball is accelerating.

Step 6 — Second weight update.

$W_{2} = W_{1} - α \cdot v_{2} = [180.8998 76.2847] - 0.01 \cdot [0.04342 2.7465] = [180.8994 76.2572]$

What happens at the valley bottom.When the ball crosses the center and the gradient reverses, the new gradient and old velocity oppose each other. Say at some future step $k$ , $v_{k} = [0.05, - 3.0]$ (moving strongly in the negative $y$ direction). But the gradient is $\nabla f = [0.001, 5.0]$ (pointing strongly positive $y$ ). Then.

$v_{k + 1} = 0.8 \cdot [0.05 - 3.0] + 0.2 \cdot [0.001 5.0] = [0.04 - 2.4] + [0.0002 1.0] = [0.0402 - 1.4]$

The velocity in $y$ went from $- 3.0$ to $- 1.4$ — it is beingdampenedbut not reversed. The gradient wanted to push it positive, but the momentum (weighted at 0.8) overpowers it. This is how momentum avoids the zigzag. It keeps moving in the accumulated direction instead of jerking back with every gradient sign change.

Sense-check.The true minimum is at $(0, 0)$ . After 6 steps, we are at approximately $(180.9, 76.3)$ — still far away. But the velocity is building. In flat regions where the gradient becomes small, the velocity persists ( $β v_{t}$ term dominates), so the ball keeps rolling. This is the key advantage over plain gradient descent, which would stall as soon as the gradient shrinks.

13.2.5 Student Questions and Answers

Q.If the velocity part is so important, why do we need the gradient at all? Why not just use only the velocity to update the weights?

A.You need the gradient to know the curvature. Velocity alone cannot tell you where the steepness is or in which direction. The gradient provides local surface information — is this spot steep or flat? Is the slope in this direction or that? Without the gradient, the velocity would not know how to adjust to the terrain. Look at the equation: $v_{t + 1} = β v_{t} + (1 - β) \nabla L (W_{t})$ . Both terms matter. The $β v_{t}$ term gives you momentum — it pushes you in the direction you were already going. The $(1 - β) \nabla L$ term gives you steering — it nudges you toward the locally steepest descent. Without the gradient, you would be steering blind. If the velocity carried you past the minimum and onto an uphill slope, only the gradient can signal "turn around."

Q.Can we have independent learning rates for different directions? One learning rate for each parameter?

A.Yes. This is exactly what adaptive learning rate methods do. Algorithms like Adagrad, RMSProp, and Adam adapt the learning rate differently for different parameters. They reduce the learning rate for directions where the gradient has historically been large (steep dimensions — to prevent oscillation). They keep it higher for directions where the gradient has been small (flat dimensions — to make progress). The only way to find the right learning rates is trial and error. You cannot know in advance how many local minima exist or how many flat valleys lie in a high-dimensional loss surface. You try multiple combinations, observe which reduce the training error, and select the best. Tools like GridSearchCV and Bayesian optimization can automate this search.

Q.Doesn't gradient descent already have a direction and a scalar? The gradient shows the direction and the velocity gives a push in that direction. How do these interact?

A.The velocity term already includes the gradient — look at $v_{t + 1} = β v_{t} + (1 - β) \nabla L (W_{t})$ . The velocity itself is built from past gradients. So when you compute $W_{t + 1} = W_{t} - α v_{t + 1}$ , you are already using gradient information through the velocity. Think of it this way: the $β v_{t}$ term contains a long-running average of all past gradients. The $(1 - β) \nabla L (W_{t})$ term adds the current gradient to this average. The velocity is the smoothed gradient history. The update direction comes from that smoothed history rather than the raw instantaneous gradient. When the current gradient is large, multiplying it by $1 - β$ (e.g., 0.1) reduces its immediate effect — it cannot jerk the trajectory. When the current gradient is small, the velocity term — carrying momentum from earlier, larger gradients — still carries weight. This is why momentum keeps moving through flat regions.

Q.There are two different formulas in different sources — one says the weight update adds the velocity, another uses a different form. Which is correct?

A.Both are correct — they are equivalent forms of the same idea. The canonical implementation form (used in PyTorch, TensorFlow, and JAX) uses two equations.

$v_{t + 1} = β v_{t} + (1 - β) \nabla L (W_{t})$ — build velocity
$W_{t + 1} = W_{t} - α v_{t + 1}$ — update weights

The alternative form (Polyak's heavy ball, also shown in the companion document for this lecture) writes it as a single equation.

$W_{t + 1} = W_{t} - α \nabla L (W_{t}) + β (W_{t} - W_{t - 1})$

Here, $β (W_{t} - W_{t - 1})$ is the actual displacement from the previous step . The momentum term is the previous update itself rather than a separate velocity variable. Under a change of variables, the two forms are equivalent. The professor's version (the two-equation form) is the one you should use on the exam and in code. Because it is the standard in all major deep learning frameworks. The learning rate $α$ is essential in both forms — it scales the step before subtracting from the weights.

Pitfalls.

Setting $β$ too high ( $> 0.99$ ).The velocity has such a long memory that it barely responds to changes in the gradient. If the minimum is behind you, momentum keeps pushing you forward for hundreds of steps before turning around. This wastes computation and can overshoot badly.
Setting $β$ too low ( $< 0.5$ ).The velocity decays too quickly. You get very little benefit from momentum — it behaves almost like plain gradient descent. The standard value $β = 0.9$ is a good default.
Forgetting the $(1 - β)$ scaling on the first step.With $v_{0} = 0$ , the first velocity is $v_{1} = (1 - β) \nabla L (W_{0})$ . If $β = 0.9$ , the first step is only 10% of what plain gradient descent would take with the same $α$ . You may need to compensate with a slightly larger $α$ or use a warm-up schedule.
Using momentum on a well-conditioned problem.If your loss surface is already a nice bowl (condition number close to 1), momentum adds little benefit and may cause overshooting. Plain gradient descent works fine. Momentum is a fix for ill-conditioned problems — do not apply fixes you do not need.
Confusing $β$ with $α$ . $α$ controls the overall step size. $β$ controls memory length. They interact: with high $β$ , you can use a smaller $α$ because the velocity accumulates over time. With low $β$ , you need a larger $α$ to make progress. Tune them together, not independently.

Recap + Bridge.Momentum adds a velocity term that remembers past gradients, smoothing out the trajectory. The velocity equation

v_{t + 1} = β v_{t} + (1 - β) \nabla L (W_{t})

blends old memory (

β

) with new gradient (

1 - β

). This dampens oscillation across steep valleys and carries you through flat plateaus. But momentum still uses one global learning rate

α

for all parameters. The next three sections introduce adaptive methods that give each parameter its own learning rate . Fixing the remaining problem that different dimensions need different step sizes.

Notation note — alternative forms.The standard form of the momentum equations in deep learning frameworks matches the professor's version above with the

(1 - β)

scaling on the gradient term. The companion document shows the alternative Polyak heavy-ball form

x_{t + 1} = x_{t} - α \nabla f (x_{t}) + β (x_{t} - x_{t - 1})

. Both are valid and encode the same physical intuition.

13.2.6 Real-World and Domain Connection

Momentum with $β = 0.9$ is the default optimizer in PyTorch's SGD implementation. And appeared as the standard training algorithm for ImageNet-winning architectures like AlexNet and VGG. When training ResNet-50 on ImageNet. The standard recipe uses SGD with momentum $β = 0.9$ . And a learning rate schedule that drops by a factor of 10 at specific epochs. This recipe has been so successful that "SGD + momentum" became the baseline against which all new optimizers are compared. Even today, when Adam is more popular for many tasks. SGD with momentum remains the preferred choice for state-of-the-art image classification models because it often generalizes better . Momentum finds flatter minima that transfer better to test data. In the 2018 paper "Three Mechanisms of Weight Decay," researchers showed that combining momentum with weight decay. And a learning rate schedule produced better vision models than Adam on several benchmarks.

13.2.7 Industry Applications

Most deep learning frameworks — PyTorch, TensorFlow, JAX — implement momentum-based gradient descent as the default or a primary option. The friction parameter $β$ is almost universally set to 0.9 in implementations across these tools. This is not arbitrary . 0.9 has been found empirically to give the best dampening behavior across a wide range of architectures and datasets.

In NLP, when you convert words to high-dimensional vectors (word embeddings), some words appear very frequently and others rarely. You do not want the frequent words to dominate gradient updates. Adaptive methods address this by effectively assigning different learning rates to different parameters based on how often they appear. For a very frequent word like "the", the learning rate might be small (0.003) because its gradient has been seen many times. For a rare word, the learning rate stays higher (0.03) because there is less accumulated gradient history.

13.3 Adagrad — Adaptive Gradient

13.3.1 Definition and Intuition

Hook.Momentum fixed the zigzag by smoothing the direction. But it left one problem untouched: every parameter still gets the same learning rate

α

. In our canyon, the

y

-direction is 150× steeper than the

x

-direction. The step that is right for

x

is wrong for

y

. What if each parameter could have its own learning rate . A small one for steep directions and a large one for flat directions? That is Adagrad.

Adagrad stands foradaptive gradient. Unlike momentum, which tackles the oscillation problem by adding velocity. Adagrad tackles it by adaptively changing the learning rate itself — differently for each parameter.

Intuition + Analogy.Imagine each parameter is a road with a toll booth. Every time a gradient update passes through (a car drives by), the toll increases. If a road sees heavy traffic (large gradients), its toll becomes very expensive. And future cars slow down — they take smaller steps. If a road sees light traffic (small gradients), its toll stays cheap, and cars keep moving fast.

Now map this to the canyon.

The $y$ -direction is a busy highway. Gradients are large. Every step adds to the toll. After a few steps, the toll is high → the effective learning rate in $y$ becomes small → no more oscillation.
The $x$ -direction is a quiet back road. Gradients are tiny. The toll barely increases → the effective learning rate in $x$ stays close to the original $α$ . You keep making progress along the flat canyon floor.

This is adaptive cruise control for optimization. The system automatically slows you down where you are already going fast (steep directions). And speeds you up where you are crawling (flat directions).

The analogy breaks at one point: in a real toll booth, the toll resets periodically. In Adagrad, it never resets — it only increases. This is the algorithm's main weakness, which RMSProp was designed to fix.

The core idea: parameters that have received large gradients in the past should get smaller updates in the future. Parameters that have received small gradients should get larger updates. This is the opposite of what standard gradient descent does. With a fixed learning rate, large gradients produce large steps, which cause oscillation. Small gradients produce small steps, which cause stalling.

The mechanism: you accumulate a history of squared gradients. When the sum of past squared gradients is large. You divide the learning rate by a large number, making the effective step smaller. When the sum is small, the effective step stays large.

13.3.2 Symbol Registry

Symbol	Meaning	Type
$A_{i}$	Accumulated squared gradient at step $i$	scalar (per parameter) or vector
$\nabla L (W_{i})$	Gradient of the loss at step $i$	vector in $R^{d}$
$α$	Global learning rate	scalar
$W_{i}$	Weight at step $i$	vector in $R^{d}$

13.3.3 Mathematical Formulation

Adagrad has two steps per iteration. First, accumulate the squared gradient. Second, use it to scale down the learning rate.

Step 1 — Accumulate the squared gradient.

$A_{i} = A_{i - 1} + (\nabla L (W_{i}))^{2}$

This says: take the previous accumulated sum of squared gradients and add thesquareof the current gradient. The square eliminates the sign — both positive and negative gradients add to the sum. If gradients have historically been large, $A_{i}$ grows quickly. If gradients have been small, $A_{i}$ grows slowly.

In practice, implementations add a tiny constant $ϵ$ (e.g.. $1 0^{- 8}$ ) to the denominator to avoid division by zero on the first step when $A_{0} = 0$ . The full form is $\frac{α}{A _{i} + ϵ}$ .

Step 2 — Update the weight with adaptive learning rate.

$W_{i + 1} = W_{i} - \frac{α}{A _{i}} \nabla L (W_{i})$

The global learning rate $α$ is divided by $A_{i}$ . This is the adaptive part.

When $A_{i}$ is large (this parameter has seen many large gradients) → $\frac{α}{A _{i}}$ is small → you take a cautious step. This prevents oscillation in steep directions.
When $A_{i}$ is small (this parameter has seen only small gradients) . $\frac{α}{A _{i}}$ stays close to $α$ → you take a normal-sized step. This helps you make progress through flat directions.

Walkthrough on the canyon example.In our loss function $f (x, y) = \frac{0.01 x ^{2} + 1.5 y ^{2}}{30}$ .

The $y$ -direction gradient is $\frac{y}{10}$ . Starting at $y = 76.3$ , the gradient is 7.63. Its square is 58.2. After one step, $A_{1, y} = 58.2$ . After two steps, $A_{2, y} \approx 116$ . The denominator $A_{2, y} \approx 10.8$ . The effective learning rate for $y$ is $\frac{α}{10.8}$ — already reduced by a factor of 10.
The $x$ -direction gradient is $\frac{x}{1500}$ . Starting at $x = 180.9$ , the gradient is 0.12. Its square is 0.014. After one step, $A_{1, x} = 0.014$ . After two steps, $A_{2, x} \approx 0.029$ . The denominator $A_{2, x} \approx 0.17$ . The effective learning rate for $x$ is $\frac{α}{0.17}$ — essentially unchanged.

In the visualization, Adagrad reaches the minimum first among all methods tested. The steep $y$ -direction's effective learning rate drops quickly, dampening oscillation. The flat $x$ -direction's effective learning rate stays high, speeding up valley progress.

The critical weakness. $A_{i}$ never decreases. It only grows with each step — every new gradient, squared, gets added. Over a very long training run, $A_{i}$ can become enormous. The effective learning rate $\frac{α}{A _{i}}$ approaches zero. Training grinds to a halt even though you have not converged. This monotonic decay is why Adagrad is rarely used for long training runs. RMSProp and Adam were designed to fix this.

13.3.4 Student Questions and Answers

Q.What should the initial value of

A_{i}

be? Is there a standard assumption?

A. $A_{i}$ is not a tunable hyperparameter like $α$ or $β$ . It is the accumulated history of squared gradients. You start with $A_{0} = 0$ (or a small positive number like $ϵ = 1 0^{- 8}$ to avoid division by zero on the first update). Every step, you add the square of the current gradient. So $A_{i} = (\nabla L (W_{1}))^{2} + (\nabla L (W_{2}))^{2} + \dots + (\nabla L (W_{i}))^{2}$ . It grows automatically from the data — there is no hyperparameter to tune for $A_{i}$ itself. It is purely a running sum derived from the gradients you compute during training.

Q.Does Adagrad reduce the learning rate so much that the number of steps increases? Is that a disadvantage?

A.Yes and yes. The effective learning rate decreases over time because $A_{i}$ accumulates. Each step becomes progressively smaller. You may need more iterations to converge than with a constant learning rate. This monotonic decay is the known weakness of Adagrad. In very long training runs (e.g., training a large neural network for hundreds of epochs). The effective learning rate can effectively reach zero before convergence, and the model stops learning. RMSProp and Adam fix this by replacing the cumulative sum with a weighted moving average of squared gradients . An average that can godownwhen recent gradients are small, preventing the learning rate from vanishing.

Pitfalls.

Forgetting that $A_{i}$ grows forever.Adagrad is great for convex problems or short training runs. For deep neural networks trained over many epochs, the learning rate decays to near zero and training stalls. Use RMSProp or Adam for long training runs.
Using too small a global $α$ .Since each parameter's effective rate is already divided by $A_{i}$ . Starting with a tiny $α$ means even the flat directions get near-zero updates. A common starting value for Adagrad is $α = 0.01$ (higher than you might use for plain gradient descent).
Not adding $ϵ$ in the denominator.On the first step, $A_{0} = 0$ , so you would divide by zero. Always use $\frac{α}{A _{i} + ϵ}$ with $ϵ = 1 0^{- 8}$ in code. The professor's slides omit $ϵ$ for clarity, but every implementation includes it.
Expecting Adagrad to work well on non-stationary problems.If the gradient distribution changes during training (e.g., different mini-batches have very different gradient magnitudes), the ever-growing $A_{i}$ cannot adapt. RMSProp handles this better because its moving average can forget old gradients.

Recap + Bridge.Adagrad gives each parameter its own effective learning rate by dividing the global

α

A_{i}

. Where

A_{i}

is the sum of past squared gradients. Steep directions accumulate large

A_{i}

and get small steps; flat directions keep small

A_{i}

and get normal steps. The weakness:

A_{i}

only grows, so the learning rate monotonically decays. RMSProp fixes this by replacing the cumulative sum with a weighted moving average that can forget old gradients. And adapt to changing conditions.

13.3.5 Real-World and Domain Connection

Adagrad was introduced by Duchi, Hazan. And Singer in 2011 and was one of the first adaptive learning rate methods to gain widespread adoption. It proved particularly effective for sparse data — problems where most features are zero most of the time. In natural language processing, word frequency follows a Zipfian distribution: "the" appears millions of times, while "hippopotamus" appears maybe once. With a fixed learning rate, common words dominate the gradient signal. Adagrad automatically reduces the effective learning rate for frequently occurring features. (which accumulate large $A_{i}$ ) and keeps it high for rare features (which accumulate little). This made Adagrad the go-to optimizer for word embedding models like word2vec and GloVe in the early 2010s. Google's original word2vec paper used Adagrad for training. Today, Adagrad has largely been superseded by Adam for most applications. But the idea of per-parameter adaptive learning rates — which Adagrad pioneered — is the foundation of every modern optimizer.

13.4 RMSProp

13.4.1 Definition and Intuition

Hook.Adagrad's toll booth has a fatal flaw: the toll only goes up, never down. After thousands of cars, every road becomes too expensive, and all traffic stops. What if the toll booth were smart . Raising the price when traffic is heavy, but lowering it when the road goes quiet? That is RMSProp.

RMSProp — Root Mean Square Propagation — fixes the main weakness of Adagrad. Instead of accumulating all past squared gradients in a sum that only grows, RMSProp uses an exponentially weighted moving average. This average can adapt — it rises when recent gradients are large and falls when they are small.

Intuition + Analogy.Expand the toll booth analogy from Adagrad. The smart toll booth cares more aboutrecenttraffic than traffic from hours ago. It blends the old toll price with the price of the most recent car, weighted by

ρ

If $ρ = 0.9$ (the typical value). Then 90% of today's toll price comes from the old price and 10% from the most recent car. Old traffic slowly fades from memory.
If a road was busy an hour ago but is quiet now, the toll pricedecreasesover time as old, expensive cars are forgotten. Traffic can speed up again.
If a road suddenly gets busy, the toll price rises quickly to slow things down.

Compare with Adagrad's toll booth: every car ever is remembered with equal weight. An hour of heavy traffic at 9 AM permanently raises the price. Even at 3 PM when no one is on the road. RMSProp is smarter — it adapts to changing conditions.

The analogy breaks at one point: $ρ$ is not truly a "memory length" in terms of absolute time steps. With $ρ = 0.9$ , a gradient from 10 steps ago contributes $0. 9^{10} \approx 0.35$ of its original weight. It is still present, just diminished. The effective memory horizon is roughly $\frac{1}{1 - ρ}$ steps — for $ρ = 0.9$ , that is about 10 steps.

13.4.2 Mathematical Formulation

Symbol Registry — RMSProp

Symbol	Meaning	Type	Typical value
$A_{i}$	Running average of squared gradients	scalar/vector	.
$ρ$	Decay rate for the running average	scalar $\in [0, 1)$	0.9
$\nabla L (W_{i})$	Gradient of the loss at step $i$	vector	.
$α$	Global learning rate	scalar	.

RMSProp changes only one thing from Adagrad: how $A_{i}$ is computed. The weight update formula is identical.

The running average update (the only difference from Adagrad).

$A_{i} = ρ A_{i - 1} + (1 - ρ) (\nabla L (W_{i}))^{2}$

This is a weighted moving average.

$ρ A_{i - 1}$ keeps a fraction $ρ$ of the old running average.
$(1 - ρ) (\nabla L (W_{i}))^{2}$ adds a fraction $(1 - ρ)$ of the current squared gradient.
$ρ$ controls the memory length. $ρ = 0.9$ → long memory (past gradients decay slowly). $ρ = 0.5$ → short memory (only very recent gradients matter).

Contrast with Adagrad's $A_{i} = A_{i - 1} + (\nabla L (W_{i}))^{2}$ , where old and new gradients are added with equal weight, and the sum only grows.

The weight update (same form as Adagrad).

$W_{i + 1} = W_{i} - \frac{α}{A _{i}} \nabla L (W_{i})$

The only difference from Adagrad is the definition of $A_{i}$ . Because RMSProp's $A_{i}$ is a weighted average (not a cumulative sum), it can go both up AND down.

If recent gradients are large → $A_{i}$ grows → effective learning rate $\frac{α}{A _{i}}$ shrinks → oscillation is dampened.
If recent gradients become small → $A_{i}$ shrinks (old large gradients decay out of memory) . Effective learning rate rises again → progress resumes in flat regions.

This prevents the vanishing learning rate problem. The learning rate adapts to thecurrentgradient landscape, not the entire history since step zero.

How the decay works numerically.With $ρ = 0.9$ .

A squared gradient contributes $0.1$ of its value to $A_{i}$ at the current step.
After 1 step, it contributes $0.1 \times 0.9 = 0.09$ .
After $k$ steps, it contributes $0.1 \times 0. 9^{k}$ .
After about 23 steps ( $0. 9^{23} \approx 0.09$ ), the contribution falls below 1% of the original. The effective memory window is roughly $\frac{1}{1 - 0.9} = 10$ steps (the time constant of the exponential decay).

Why the name "Root Mean Square Propagation."The denominator $A_{i}$ is essentially theroot mean square(RMS) of recent gradients. The running average $A_{i}$ approximates the mean of squared gradients. Its square root gives the RMS. The algorithm propagates the RMS of past gradients to scale the current gradient — hence "Root Mean Square Propagation."

Worked Example — Comparing Adagrad vs RMSProp on one parameter.Consider a single parameter $w$ with the following gradient values over 5 steps.

$g_{1} = 5.0, g_{2} = 0.1, g_{3} = 0.1, g_{4} = 0.1, g_{5} = 5.0$

Use $α = 0.1$ . Start with $A_{0} = 0$ . Assume $ρ = 0.9$ for RMSProp.

Adagrad.

Step 1: $A_{1} = 0 + 5^{2} = 25$ . Effective LR = $0.1/5 = 0.02$ . Update: $w_{1} = w_{0} - 0.02 \cdot 5 = w_{0} - 0.1$ .
Step 2: $A_{2} = 25 + 0.01 = 25.01$ . Effective LR = $0.1/5.001 = 0.02$ . Update: $w_{2} = w_{1} - 0.02 \cdot 0.1 = w_{1} - 0.002$ .
Step 3: $A_{3} = 25.01 + 0.01 = 25.02$ . Effective LR ≈ 0.02. Update: $w_{3} = w_{2} - 0.0002$ .
Step 4: same tiny updates.
Step 5: $A_{5} = 25.03 + 25 = 50.03$ . Effective LR = $0.1/7.07 = 0.014$ . Update: $w_{5} = w_{4} - 0.014 \cdot 5 = w_{4} - 0.07$ .

After step 5, the effective learning rate isstill smallbecause step 1's big gradient permanently inflated $A_{i}$ .

RMSProp.

Step 1: $A_{1} = 0.9 \cdot 0 + 0.1 \cdot 25 = 2.5$ . Effective LR = $0.1/1.581 = 0.063$ . Update: $w_{1} = w_{0} - 0.063 \cdot 5 = w_{0} - 0.315$ .
Step 2: $A_{2} = 0.9 \cdot 2.5 + 0.1 \cdot 0.01 = 2.251$ . Effective LR = $0.1/1.500 = 0.067$ . Update: $w_{2} = w_{1} - 0.067 \cdot 0.1 = w_{1} - 0.007$ .
Step 3: $A_{3} = 0.9 \cdot 2.251 + 0.1 \cdot 0.01 = 2.027$ . Effective LR = $0.1/1.424 = 0.070$ .
Step 4: $A_{4} = 0.9 \cdot 2.027 + 0.1 \cdot 0.01 = 1.825$ . Effective LR = $0.1/1.351 = 0.074$ .
Step 5: $A_{5} = 0.9 \cdot 1.825 + 0.1 \cdot 25 = 1.643 + 2.5 = 4.143$ . Effective LR = $0.1/2.035 = 0.049$ . Update: $w_{5} = w_{4} - 0.049 \cdot 5 = w_{4} - 0.245$ .

Key observation.In steps 2–4 (small gradients), RMSProp's $A_{i}$ decreasedfrom 2.5 to 1.825, allowing the effective learning rate toincreasefrom 0.063 to 0.074. Adagrad's $A_{i}$ only grew, keeping the effective LR stuck. Then at step 5 (large gradient), RMSProp's $A_{i}$ rose again to 4.143, dampening the step.

Sense-check.After many small gradients, RMSProp recovers and takes larger steps again. Adagrad never recovers. This is why RMSProp is preferred for non-stationary or long-running optimization problems.

Assumptions & Scope.

Assumptions.

The gradient distribution may change over time (non-stationary). RMSProp handles this; Adagrad does not.
A single decay rate $ρ$ works for the entire training run. In practice, $ρ = 0.9$ is almost always a good default.

When RMSProp is the right choice.

Long training runs where Adagrad's learning rate would decay to zero.
Problems where gradient magnitudes vary over time (e.g., different mini-batches have different statistics, or you are using a curriculum learning strategy).
Online learning settings where the data distribution shifts (concept drift).

When RMSProp might not help.

If the problem is well-conditioned, adaptive methods add unnecessary overhead. Plain SGD or SGD with momentum may work just as well and generalize better.
If $ρ$ is set too close to 1 (e.g., 0.999). The running average behaves like Adagrad's cumulative sum — it barely forgets anything. Setting it too close to 0 (e.g., 0.5) makes the average too jumpy — it reacts excessively to every gradient fluctuation.

Pitfalls.

Confusing $ρ$ (RMSProp) with $β$ (momentum).Both are decay parameters around 0.9, but they serve different purposes. $β$ controls velocity memory (direction smoothing). $ρ$ controls the running average of squared gradients (learning rate adaptation). In Adam, both appear together, so keep them distinct.
Setting $ρ$ too high ( $> 0.99$ ).The running average barely changes. Old large gradients dominate for hundreds of steps. RMSProp loses its adaptivity and behaves like Adagrad.
Setting $ρ$ too low ( $< 0.7$ ).The running average is too volatile. It jumps around with every gradient, and the effective learning rate fluctuates wildly. Training becomes unstable.
Forgetting the $ϵ$ in the denominator.As with Adagrad, always use $\frac{α}{A _{i} + ϵ}$ with $ϵ \approx 1 0^{- 8}$ to avoid division by zero on early steps. The professor's slides may omit it, but every implementation includes it.

Recap + Bridge.RMSProp replaces Adagrad's cumulative sum with a weighted moving average of squared gradients:

A_{i} = ρ A_{i - 1} + (1 - ρ) (\nabla L)^{2}

. The running average can adapt up or down, preventing the learning rate from vanishing. RMSProp handles changing gradient distributions; Adagrad does not. The next section introduces Adam, which combines RMSProp's adaptive learning rates with momentum's velocity — getting the best of both worlds.

13.4.3 Real-World and Domain Connection

RMSProp was introduced by Geoffrey Hinton in a 2012 Coursera lecture (never formally published as a paper . It originated from a slide in his online course. Which is an unusual origin for one of the most-used optimization algorithms in deep learning). RMSProp became immediately popular because it solved a practical problem: training recurrent neural networks (RNNs) on long sequences. RNNs have very non-stationary gradient distributions — gradients explode early in training and vanish later. Adagrad's monotonically decaying learning rate was disastrous for RNNs because it killed learning in later epochs. RMSProp's adaptive running average allowed the learning rate to recover when gradients became small. Making it the default optimizer for sequence models in the mid-2010s. Today, RMSProp is less commonly used as a standalone optimizer but lives on as the $v_{t}$ component inside Adam . Every Adam update implicitly uses RMSProp's mechanism.

13.5 Adam — Adaptive Moment Estimation

13.5.1 Overview and Context

Hook.You have seen two separate ideas. Momentum smooths thedirectionof your steps by remembering past gradients. RMSProp scales thesizeof your steps by adapting the learning rate per parameter. Can you use both at once — smooth direction AND adaptive step size? That combination is Adam. It is the most widely used optimizer in deep learning today.

Adam combines the ideas of momentum and RMSProp into a single algorithm. It maintains two running averages: one for the gradient (like momentum's velocity) and one for the squared gradient (like RMSProp's $A_{i}$ ). It also includes bias correction terms for the early steps. When the running averages start from zero and need time to "warm up."

Intuition + Analogy.Think of Adam as a complete traffic management system for your city.

Momentumis thetraffic directorwho looks at the general flow of cars and guides them along the smoothest, most consistent routes. It prevents jerky side-to-side movements.
RMSPropis thesmart toll booththat adjusts prices per road based on recent traffic. It slows down busy highways and speeds up quiet back streets.
Adamis both at once. A traffic director who also controls toll prices. Cars flow smoothly (momentum) at the right speed for each road (adaptive learning rate).

The "Adaptive Moment Estimation" name comes from the two running averages.

Thefirst moment(mean) of the gradient — the momentum term $m_{t}$ .
Thesecond moment(uncentered variance) of the gradient — the RMSProp term $v_{t}$ .

In statistics, the first moment of a distribution is its mean; the second moment is related to its variance. Adam estimates both moments adaptively as training proceeds.

The full Adam algorithmuses four equations.

1. Gradient computation.

$g_{t} = \nabla L (W_{t})$

2. First moment estimate (momentum — direction smoothing).

$m_{t} = β_{1} m_{t - 1} + (1 - β_{1}) g_{t}$

This is the momentum term. $β_{1}$ (typically 0.9) controls how much old gradient direction is remembered. $m_{t}$ is a running average of the gradient — it smooths out the trajectory.

3. Second moment estimate (RMSProp — step size adaptation).

$v_{t} = β_{2} v_{t - 1} + (1 - β_{2}) g_{t}^{2}$

This is the RMSProp term. $β_{2}$ (typically 0.999) controls the memory of squared gradients. $v_{t}$ scales the learning rate per parameter.

4. Weight update.

$W_{t + 1} = W_{t} - \frac{α}{v _{t} + ϵ} m_{t}$

The update uses thesmoothed direction $m_{t}$ (from momentum) and divides by theadaptive scale $v_{t}$ (from RMSProp). The result: smooth, well-paced steps in every dimension.

Bias correction (not covered in this lecture but standard in implementations).Because $m_{0} = 0$ and $v_{0} = 0$ , the early estimates are biased toward zero. Adam corrects this by dividing by $(1 - β_{1}^{t})$ and $(1 - β_{2}^{t})$ respectively. Full coverage in the next session.

In the visualization with the loss function $f (x, y) = \frac{0.01 x ^{2} + 1.5 y ^{2}}{30}$ , Adam's trajectory is similar to Adagrad's and RMSProp's. It adapts the effective learning rate per dimension and reaches the minimum efficiently. The momentum term helps smooth the path, reducing residual oscillation that might remain with pure RMSProp.

Comparison — Gradient Descent vs Momentum vs Adagrad vs RMSProp vs Adam

Feature	GD	Momentum	Adagrad	RMSProp	Adam
Per-parameter LR	No	No	Yes	Yes	Yes
Direction smoothing	No	Yes	No	No	Yes
LR can increase	N/A	N/A	No (only decreases)	Yes	Yes
Handles sparse gradients	Poor	Poor	Good	Good	Good
Long-training stability	Poor	Medium	Poor (LR vanishes)	Good	Good
Number of hyperparameters	1 ( $α$ )	2 ( $α, β$ )	1 ( $α$ )	2 ( $α, ρ$ )	3 ( $α, β_{1}, β_{2}$ )
Default settings	$α = 0.01$	$α = 0.01, β = 0.9$	$α = 0.01$	$α = 0.001, ρ = 0.9$	$α = 0.001, β_{1} = 0.9, β_{2} = 0.999$

When to pick which.

Start withAdamfor most deep learning problems. It is the most robust default.
If Adam's validation performance plateaus, trySGD + momentum— it sometimes generalizes better for vision tasks.
For very simple problems (linear regression, logistic regression on small data), plainGDwith a well-tuned $α$ is fine.

Pitfalls.

Using Adam without understanding what $β_{1}$ and $β_{2}$ do. $β_{1} = 0.9$ controls momentum memory. $β_{2} = 0.999$ controls adaptive learning rate memory. The asymmetry ( $β_{2}$ much closer to 1) is deliberate. Squared gradients need a longer memory to produce stable estimates of the second moment.
Treating Adam as always better.Adam converges faster in training, but SGD + momentum sometimes finds solutions thatgeneralizebetter (lower test error). Adam can converge to sharper minima that do not transfer well. For vision benchmarks like ImageNet, SGD + momentum often beats Adam on final test accuracy.
Ignoring bias correction when implementing from scratch.If you implement Adam without the $(1 - β^{t})$ correction terms, the first few steps will be severely scaled down because $m_{0} = v_{0} = 0$ . This is why frameworks like PyTorch and TensorFlow include bias correction by default.
Tuning Adam's $α$ too high.Because Adam adapts per-parameter, the effective learning rate can be larger than you think. The recommended default is $α = 0.001$ , which is an order of magnitude smaller than typical values for plain SGD ( $α = 0.01$ ).
Using Adam where second-order methods are better.For small, well-conditioned convex problems, Newton's method or L-BFGS may converge in far fewer iterations. Adam is designed for stochastic, high-dimensional, non-convex problems — it is overkill for a 5-parameter linear regression.

Recap + Bridge.Adam combines momentum (direction smoothing via

m_{t}

) and RMSProp (per-parameter adaptive learning rate via

v_{t}

). It uses two decay rates:

β_{1} = 0.9

for the first moment and

β_{2} = 0.999

for the second moment. Adam is the default optimizer for most deep learning applications. All methods so far have beenunconstrained— the parameters could go anywhere. The next section introducesconstrained optimization, where parameters must satisfy rules, and the Lagrangian method for handling them.

13.5.2 Real-World and Domain Connection

Adam was introduced by Kingma and Ba in their 2014 paper "Adam. A Method for Stochastic Optimization," which has been cited over 150,000 times . Making it one of the most cited papers in computer science history. Adam is the default optimizer in nearly every deep learning framework and library. The Transformer architecture (the foundation of GPT, BERT, and all modern LLMs) was originally trained with Adam using $β_{1} = 0.9$ , $β_{2} = 0.98$ , and $ϵ = 1 0^{- 9}$ . The GPT-3 paper used Adam with $β_{1} = 0.9$ , $β_{2} = 0.95$ , and a learning rate of $6 \times 1 0^{- 5}$ with batch size 3.2M tokens. Vision Transformers (ViT), diffusion models (Stable Diffusion). And most generative models use Adam or AdamW (Adam with decoupled weight decay) as their optimizer. The specific hyperparameters vary by domain — vision models often use $β_{1} = 0.9, β_{2} = 0.999$ . While language models often reduce $β_{2}$ to 0.95 or 0.98 for better stability with very large batch sizes.

13.6 Constrained Optimization and Lagrangian

13.6.1 Definition and Motivation

Hook.Every optimizer we have studied so far lets the parameters wander anywhere — there are no fences, no rules, no forbidden zones. But real-world parameters always have limits. A probability must stay in

[0, 1]

. A portfolio cannot spend more than your budget. A factory cannot use negative hours of labor. What happens when gradient descent hits a constraint? It stops dead — the gradient is undefined at the boundary. How do you optimize when the parameter space has walls?

All optimization so far has beenunconstrained— you minimize a loss function with no restrictions on the parameter values. But many real problems have constraints. You might need to keep weights within a certain range, or ensure they satisfy an equation, or stay within a budget. This isconstrained optimization.

The problem: constraints create sharp edges on the feasible region. The loss surface might be smooth, but the boundaries — where constraints cut off the surface — are not. Gradient descent fails at edges. The gradient is undefined there. Even with momentum, the ball cannot roll past a sharp edge. It gets stuck.

Intuition + Analogy.You are walking in a park. The park is beautiful (that is the objective function

f (x)

— you want to find the best spot). But there is a fence around a restricted area (that is the constraint

g (x) \leq 0

— you cannot cross it). If you cross the fence, a park ranger fines you. The amount of the fine is

λ

— the Lagrange multiplier.

Now consider three scenarios.

You are well inside the park, far from the fence. No fine. $λ = 0$ . The constraint does not matter.
You are standing right at the fence. The ranger says: "I will fine you $λ$ rupees for every meter you cross." $λ$ has a real meaning now — it is the price of the constraint.
You cross the fence. The ranger sets an infinite fine: $λ \to \infty$ . The penalty is so high you are forced back inside.

This is the Lagrangian method: you add the fine (constraint × multiplier) to your objective, and then solve theunconstrainedproblem of minimizing (objective + fines). The fines enforce the constraints automatically — you never actually cross the fence because crossing makes the total cost explode.

The fence analogy comes from the companion document for this lecture. Which uses a Park Ranger (setting fines) and a Climber (choosing the location) to explain the primal-dual relationship. The professor's version uses a simpler fence-and-fine narrative.

The solution: convert the constrained problem into an unconstrained one by folding the constraints into the objective function with penalty terms. This is the Lagrangian method.

13.6.2 Symbol Registry

Symbol	Meaning	Type
$f (x)$	Objective function to minimize or maximize	scalar function, $x \in R^{d}$
$g_{i} (x)$	Constraint function $i$	scalar function
$λ_{i}$	Lagrange multiplier (penalty parameter) for constraint $i$	scalar
$L (x, λ)$	Lagrangian — combined objective with constraints	scalar function
$x$	Decision variables (e.g., model parameters)	vector in $R^{d}$

13.6.3 The Lagrangian Function

The Lagrangian construction.You start with an objective function $f (x)$ to minimize. You have constraints $g_{i} (x) \leq 0$ (inequality constraints) or $h_{j} (x) = 0$ (equality constraints). The Lagrangian folds each constraint into the objective with a multiplier.

$L (x, λ) = f (x) + i \sum λ_{i} g_{i} (x)$

where.

$f (x)$ is the original objective (what you want to minimize or maximize).
Each $g_{i} (x)$ is a constraint function, written so that $g_{i} (x) \leq 0$ means "satisfying the constraint."
Each $λ_{i} \geq 0$ is a Lagrange multiplier — the penalty for violating constraint $i$ .
$L (x, λ)$ is the Lagrangian — a new, unconstrained function.

How to read the formula.The Lagrangian is the original objectivepluspenalty terms. If you satisfy constraint $i$ (so $g_{i} (x) \leq 0$ ), the penalty term $λ_{i} g_{i} (x)$ is negative or zero . It reduces the Lagrangian or leaves it unchanged. If you violate the constraint ( $g_{i} (x) > 0$ ), the penalty is positive and increases the Lagrangian. The optimizer is punished for crossing constraints.

Why this works.The original constrained problem.

$x min f (x) subject to g_{i} (x) \leq 0$

can be rewritten as the min-max problem.

$x min λ \geq 0 max L (x, λ)$

Here is why.

If you pick an $x$ that violates $g_{i} (x) > 0$ , the inner max sets $λ_{i} \to \infty$ , making $L \to \infty$ . Such $x$ are eliminated — they are infinitely expensive.
If you pick an $x$ that satisfies all constraints ( $g_{i} (x) \leq 0$ ). The inner max sets $λ_{i} = 0$ for inactive constraints (since making $λ_{i}$ positive would add a negative term. Reducing the Lagrangian — which the "max" would avoid). The Lagrangian reduces to $f (x)$ .

So the min-max over the Lagrangian is equivalent to the original constrained problem. This is the foundation of Lagrange duality, which will be explored in the next session.

Think of it with the fence analogy from earlier. You are walking in a park. There is a fence — you are not allowed to cross it. If you try to cross, you pay a fine. The fine is the $λ g (x)$ term. The park experience is $f (x)$ . The combined function — park experience plus any fines — is the Lagrangian.

When you solve the unconstrained problem of minimizing the Lagrangian, you are still trying to stay within the constraints. Crossing them incurs a penalty that increases the Lagrangian value. The penalty parameters $λ_{i}$ control how harshly violations are punished.

13.6.4 Worked Example — Bounded 2D Surface

Consider the problem.

$Minimize f (x, y) = 2 (x^{2} + y^{2})$

subject to.

$x + y \leq 2, x + y \geq 1$

Step 1 — Understand the geometry.The constraints define a diagonal strip in the $x$ - $y$ plane.

The line $x + y = 2$ is the upper boundary (northeast).
The line $x + y = 1$ is the lower boundary (southwest).
The feasible region is everything between these two parallel lines — an infinite diagonal band.

The objective $f (x, y) = 2 (x^{2} + y^{2})$ is a paraboloid bowl centered at the origin $(0, 0)$ . As you move away from the origin, the function value grows quadratically. To minimize it under the constraints, you want the pointinside the stripthat isclosest to the origin.

Step 2 — Find the unconstrained minimum.The unconstrained minimum of $f (x, y) = 2 (x^{2} + y^{2})$ is at $(0, 0)$ , where $f = 0$ . But check the constraints: at $(0, 0)$ , $x + y = 0$ . Is $0$ between 1 and 2? No — $0 < 1$ . So the unconstrained minimum isnotin the feasible region. The constraint $x + y \geq 1$ is violated.

Step 3 — Find the constrained minimum by reasoning.The origin is the global minimum. The constraint $x + y \geq 1$ means the origin is excluded. The closest point in the strip to the origin must lie on thelowerboundary $x + y = 1$ (since moving from the origin toward the strip, you first hit the lower boundary). Among all points on the line $x + y = 1$ , the one closest to the origin is the perpendicular projection.

The line $x + y = 1$ has normal vector $(1, 1)$ . The closest point to the origin is where the position vector is parallel to the normal: $(x, y) = t (1, 1)$ for some $t$ . Substituting into $x + y = 1$ : $t + t = 1$ , so $t = 0.5$ . The optimal point is $(0.5, 0.5)$ .

Step 4 — Verify.At $(0.5, 0.5)$ : $f = 2 (0.25 + 0.25) = 1.0$ . Check any other point on the boundary, e.g., $(1, 0)$ : $f = 2 (1 + 0) = 2 > 1$ . Check $(0.8, 0.2)$ : also on the boundary and $f = 2 (0.64 + 0.04) = 1.36 > 1$ . The point $(0.5, 0.5)$ is indeed the minimum.

Step 5 — Why gradient descent fails here.The feasible region is a strip. At the optimal point $(0.5, 0.5)$ on the boundary $x + y = 1$ , the gradient of $f$ is.

$\nabla f (0.5, 0.5) = [4 x 4 y] = [22]$

This gradient points northeast (away from the origin). If you take a gradient descent step from the boundary, you would move southwest . Back toward the origin, which is outside the feasible region. You would immediately violate the constraint. If you stop at the boundary, you are stuck . The true minimum of $f$ inside the feasible region is on the boundary. But gradient descent cannot "slide along" the boundary because the gradient points across it.

Step 6 — The Lagrangian solution.Rewrite the constraints in standard form ( $g (x) \leq 0$ ).

$x + y \leq 2$ → $g_{1} (x, y) = x + y - 2 \leq 0$
$x + y \geq 1$ → $- x - y + 1 \leq 0$ → $g_{2} (x, y) = 1 - x - y \leq 0$

Construct the Lagrangian.

$L (x, y, λ_{1}, λ_{2}) = 2 (x^{2} + y^{2}) + λ_{1} (x + y - 2) + λ_{2} (1 - x - y)$

with $λ_{1} \geq 0, λ_{2} \geq 0$ .

Now solve the unconstrained problem $min_{x, y} L$ by taking partial derivatives.

$\frac{\partial L}{\partial x} = 4 x + λ_{1} - λ_{2} = 0$

$\frac{\partial L}{\partial y} = 4 y + λ_{1} - λ_{2} = 0$

From the first equation: $x = \frac{λ _{2} - λ _{1}}{4}$ . From the second: $y = \frac{λ _{2} - λ _{1}}{4}$ . So $x = y$ .

Only one constraint can be active at the optimum (you cannot be on both boundaries simultaneously since the lines are parallel). Since the origin is below the lower boundary, the lower constraint $x + y \geq 1$ is active: $λ_{2} > 0, λ_{1} = 0$ .

With $x = y$ and $x + y = 1$ : $2 x = 1$ , so $x = y = 0.5$ . Then $4 (0.5) - λ_{2} = 0$ , so $λ_{2} = 2$ .

Final answer: $(x^{*}, y^{*}) = (0.5, 0.5)$ with $f^{*} = 1.0$ and $λ_{2}^{*} = 2$ .The multiplier $λ_{2} = 2$ tells you themarginal costof the constraint: if you relax the constraint from $x + y \geq 1$ to $x + y \geq 0.99$ , the optimal objective value improves by approximately $2 \times 0.01 = 0.02$ .

Sense-check.The Lagrangian gives the same answer as geometric reasoning. The multiplier $λ_{2} = 2$ means the constraint is binding and costly — loosening it would improve the objective.

Scope — when constraints matter and when they do not.

Active vs inactive constraints.If the unconstrained minimum already satisfies a constraint, that constraint isinactive— its multiplier $λ = 0$ . The constraint does not affect the solution. If the unconstrained minimum liesoutsidethe feasible region, the constraint isactive— $λ > 0$ — and the optimum lies on the constraint boundary.

Equality vs inequality constraints.

$h (x) = 0$ (equality): The multiplier $λ$ can be any real number (positive or negative). The optimum always lies on the boundary.
$g (x) \leq 0$ (inequality): $λ \geq 0$ . The optimum may be in the interior ( $λ = 0$ ) or on the boundary ( $λ > 0$ ).

When the Lagrangian method fails.

Non-differentiable constraints: if $g (x)$ is not smooth, the Lagrangian's derivatives are undefined.
Non-convex feasible regions: if the feasible set has holes or disconnected components. The Lagrangian may find a local minimum that is not global.
Integer constraints ( $x \in {0, 1}$ ): the Lagrangian method works for continuous variables. Discrete variables need integer programming, which is a different class of algorithms entirely.

13.6.5 Visual Intuition

Draw the $x$ - $y$ plane. Mark the origin $(0, 0)$ . Draw two parallel diagonal lines: $x + y = 1$ (southwest) and $x + y = 2$ (northeast). Shade the region between them — this is the feasible strip.

Now draw concentric circles centered at the origin, each representing a level set of $f (x, y) = 2 (x^{2} + y^{2}) = c$ . The circles grow in radius as $c$ increases. The smallest circle thattouchesthe shaded strip is the one that grazes the lower boundary $x + y = 1$ . The point of tangency is $(0.5, 0.5)$ , where the circle is tangent to the constraint line.

At this point, the gradient of $f$ (pointing radially outward from the origin) is perpendicular to the level curve. The gradient of the constraint $x + y = 1$ is $(1, 1)$ , which points perpendicular to the constraint line. At the optimum, these two gradients areparallel: $\nabla f = - λ \nabla g$ . This is the key geometric condition: at the optimal point under a binding constraint. The gradient of the objective is parallel to the gradient of the constraint. The multiplier $λ$ is the scaling factor.

Takeaway.The constrained optimum occurs where the level sets of the objective just touch the constraint boundary — the gradients align.

13.6.6 Student Questions and Answers

Q.Does the Lagrangian always produce a smooth function? How do we know the penalty parameters

λ_{i}

are correct?

A.The Lagrangian itself is smooth . It is a sum of differentiable functions (the original objective plus the constraint terms, each multiplied by a constant). The penalty parameters $λ_{i}$ are not known in advance. They emerge as part of the solution. Solving the Lagrangian involves finding both the optimal $x$ and the optimal $λ_{i}$ simultaneously . You solve the system of equations $\nabla_{x} L = 0$ together with thecomplementary slacknessconditions ( $λ_{i} g_{i} (x) = 0$ for each $i$ ). This leads to the min-max formulation and the Karush-Kuhn-Tucker (KKT) conditions, which will be explored in the next session. The KKT conditions are the necessary conditions for optimality in constrained optimization . They generalize the idea that "the gradient must be zero at the optimum" to problems with constraints.

Pitfalls.

Forgetting to check constraint signs.When converting to $g (x) \leq 0$ form, the sign matters. $x + y \geq 1$ becomes $- x - y + 1 \leq 0$ , NOT $x + y - 1 \leq 0$ . Getting the sign wrong flips the multiplier's sign and leads to nonsensical solutions.
Treating all constraints the same.Equality constraints ( $h (x) = 0$ ) have unrestricted $λ$ (can be positive or negative). Inequality constraints ( $g (x) \leq 0$ ) require $λ \geq 0$ . If you get this wrong, the KKT conditions will not hold.
Assuming the unconstrained optimum is always feasible.Always check: does the unconstrained solution satisfy all constraints? If yes, you are done — the constraints are inactive. If no, at least one constraint is binding.
Confusing the Lagrangian with regularization.Both add penalty terms to the objective. But regularization penalizeslarge parameter valuesto prevent overfitting. The Lagrangian penalizesconstraint violations. The goals are different: regularization simplifies the model, Lagrangian enforces hard rules.
Expecting a closed-form solution.Most real constrained optimization problems have no analytical solution. The Lagrangian formulation converts the problem into an unconstrained form that can be solvednumericallywith gradient-based methods. The fact that you wrote the Lagrangian does not mean you can solve it by hand . But you can now apply Adam or momentum to it.

13.6.7 Conceptual Connections

Recap + Bridge.Constrained optimization adds rules to the optimization problem: minimize

f (x)

subject to

g (x) \leq 0

. The Lagrangian

L (x, λ) = f (x) + \sum λ_{i} g_{i} (x)

folds the constraints into the objective with penalty multipliers

λ_{i}

. The resulting min-max problem

min_{x} max_{λ \geq 0} L (x, λ)

is equivalent to the original constrained problem. This connects to Lagrange duality, KKT conditions, and the min-max structure of game theory — topics covered in the next session.

The movieA Beautiful Minddramatizes the story of John Nash, whose Nobel-prize winning work on game theory connects to min-max theory. In constrained optimization, the Lagrangian formulation leads to a min-max problem. You minimize the Lagrangian with respect to $x$ . You maximize it with respect to $λ$ . This duality — min in one variable, max in another . Mirrors the conceptual structure of Nash equilibrium (players simultaneously minimizing their own costs while opponents maximize them). The mathematical elegance of this connection makes constrained optimization one of the most rewarding topics in the course.

13.6.8 Real-World and Domain Connection

Constrained optimization powers mission-critical scheduling at major cloud providers. When Oracle or Microsoft schedules upgrades for thousands of enterprise customer systems, each customer has a unique set of constraints. Maintenance windows ("do not touch my servers between 9 AM and 5 PM"). Dependency chains ("upgrade the database before the application server"). Regulatory requirements ("data must stay in the EU"), and service-level agreements ("99.99% uptime during business hours"). The objective is to minimize total disruption — measured in downtime-minutes or revenue impact — subject to all these constraints. This is a massive constrained optimization problem with millions of variables. Cloud providers increasingly use AI agents for this: each agent represents a customer's requirements and negotiates with a central scheduler. The Lagrangian framework underlies the mathematical modeling of these systems. Even if the actual solving is done by specialized constraint solvers or reinforcement learning agents.

Beyond cloud scheduling, constrained optimization appears in portfolio optimization (maximize return subject to risk budget). Structural engineering (minimize weight subject to load-bearing constraints). Supply chain logistics (minimize shipping cost subject to delivery windows). And power grid management (minimize generation cost subject to demand and transmission limits). The Lagrangian method and KKT conditions are the mathematical language used across all these domains.

Exam Guidance Summary

Exam note — Mark distribution.Post-mid-semester content carries approximately 70% of the comprehensive exam weight. Pre-mid-semester content carries approximately 30%. If there are 8 problems on the exam, expect 5–6 from post-mid-sem and 2 from pre-mid-sem.

High-probability question types.

Expect one6-mark questionon any of the adaptive optimization algorithms — most likely Adagrad or RMSProp. You may be asked to write down two steps of the algorithm with numerical values (like the worked examples in sections 13.1 and 13.2). Momentum may also appear as a computational problem.
Constrained optimizationand the Lagrangian formulation are recurring exam topics. Be comfortable converting a constrained problem (with both equality and inequality constraints) into the Lagrangian form. Know how to handle the sign of each constraint when converting to $g (x) \leq 0$ form. The min-max interpretation $min_{x} max_{λ \geq 0} L (x, λ)$ is important.

Pre-mid-sem dependency.

Principal Component Analysis (PCA), covered in the companion document for this lecture block, relies on eigenvalues and eigenvectors. You must understand matrix structure, eigenvalues, and eigendecomposition from the pre-mid-sem material to grasp PCA. Do not skip the pre-mid-sem portion entirely — the 30% provides the mathematical foundations for the 70%. Specifically review: definitions of eigenvalues and eigenvectors, the characteristic equation $det (A - λ I) = 0$ , and the covariance matrix.

Exam note — Study strategy for adaptive methods.Focus on understandingwhyeach algorithm was invented — what problem of gradient descent it solves.

Adagrad.monotonic learning-rate decay per parameter using cumulative sum of squared gradients. Fixes the "one learning rate for all dimensions" problem.
RMSProp.replaces cumulative sum with weighted moving average of squared gradients. Fixes Adagrad's vanishing learning rate.
Adam.combines momentum (direction smoothing) with RMSProp (adaptive step size) plus bias correction. Fixes both oscillation and per-parameter scaling.

The formulas flow naturally from the motivation. If you understand the problem each algorithm solves, you can reconstruct the equations.

Exam note — Presentation matters.

Show your computations in a clear, step-by-step format.

Write the formula first.
Substitute the numbers.
Show the result.
Write your assumptions explicitly.

A well-organized answer with neatly labeled steps is easier to grade and earns more partial credit. For example, when asked to compute two steps of Adagrad.

          Step 1: Compute gradient at W_0. ∇L(W_0) = ... Step 2: Update A_1 = A_0 + (∇L(W_0))² = ... Step 3: Update W_1 = W_0 − (α/√A_1) ∇L(W_0) = ... Step 4: Compute gradient at W_1. ∇L(W_1) = ... Step 5: Update A_2 = A_1 + (∇L(W_1))² = ... Step 6: Update W_2 = W_1 − (α/√A_2) ∇L(W_1) = ...

Trial and error in practice.

When tuning gradient descent in real projects, people often start with one fixed learning rate (0.1 or 0.01). Observe the training error curve, and iteratively adjust. A loss curve that oscillates means $α$ is too high. A loss curve that drops slowly and plateaus means $α$ is too low. A loss curve that shoots upward means divergence — reduce $α$ significantly.

Tools like scikit-learn'sGridSearchCVautomate hyperparameter search by trying a predefined list of learning rates and selecting the best via cross-validation. You supply a grid like $α \in {0.001, 0.003, 0.01, 0.03, 0.1}$ and the grid search trains a model for every combination. Returning the one with the lowest validation error. This is simple but computationally expensive — training $k$ models for $k$ candidate hyperparameters.

Bayesian optimization is a more sophisticated alternative. It builds a probabilistic model (usually a Gaussian process) of the validation loss as a function of hyperparameters. It chooses each new candidate by balancingexploration(trying regions with high uncertainty) againstexploitation(trying regions near known good values). Bayesian optimization typically finds good hyperparameters in far fewer trials than grid search. It is the preferred approach when each training run is expensive (e.g., training a large neural network on a GPU cluster).

Both methods are available in scikit-learn and specialized libraries like Optuna and Hyperopt. For exam purposes, you do not need to implement these — just know what they do and when to use which.

Exam note — Key formulas to memorize.

Algorithm	Key Equation(s)
Gradient Descent	$W_{i + 1} = W_{i} - α \nabla L (W_{i})$
Momentum	$v_{t + 1} = β v_{t} + (1 - β) \nabla L (W_{t})$ $W_{t + 1} = W_{t} - α v_{t + 1}$
Adagrad	$A_{i} = A_{i - 1} + (\nabla L (W_{i}))^{2}$ $W_{i + 1} = W_{i} - \frac{α}{A _{i}} \nabla L (W_{i})$
RMSProp	$A_{i} = ρ A_{i - 1} + (1 - ρ) (\nabla L (W_{i}))^{2}$ (same weight update as Adagrad)
Lagrangian	$L (x, λ) = f (x) + \sum_{i} λ_{i} g_{i} (x)$ ( $λ_{i} \geq 0$ for $g_{i} (x) \leq 0$ )

Key Industry Applications

Momentum ( $β = 0.9$ )

The combination of SGD with momentum and $β = 0.9$ is nearly universal as the default optimizer in PyTorch, TensorFlow, and JAX. The friction parameter 0.9 is the empirically optimal value across most architectures, found through decades of experimentation. Notable models trained with SGD + momentum include.

AlexNet(2012): the breakthrough deep CNN for ImageNet, trained with momentum $β = 0.9$ and learning rate $α = 0.01$ .
ResNet(2015): the residual network architecture that won ImageNet, trained with SGD + momentum $β = 0.9$ and a step-wise learning rate decay schedule.
VGG(2014): deep convolutional networks for visual recognition, all variants trained with momentum $β = 0.9$ .

Interestingly, for state-of-the-art image classification, SGD + momentum still often beats Adam on final test accuracy . Momentum finds flatter minima that generalize better. The 2018 paper "Three Mechanisms of Weight Decay" (Loshchilov & Hutter) showed that decoupling weight decay from the optimizer (AdamW) can close this generalization gap.

Adam (Adaptive Moment Estimation)

Adam, introduced by Kingma & Ba (2014), is among the most widely used optimization algorithms in deep learning. It handles sparse gradients well, making it popular in NLP where word frequency distributions are highly skewed (Zipf's law). Key applications.

Transformers and LLMs.Every major language model from BERT to GPT-4 was trained with Adam or AdamW. The original Transformer paper used Adam with $β_{1} = 0.9, β_{2} = 0.98, ϵ = 1 0^{- 9}$ .
Generative models.Stable Diffusion, DALL-E, and other diffusion models use Adam/AdamW with $β_{1} = 0.9$ and $β_{2} = 0.999$ .
Reinforcement learning.Proximal Policy Optimization (PPO) and other RL algorithms often use Adam for policy gradient updates.

The standard hyperparameters ( $α = 0.001, β_{1} = 0.9, β_{2} = 0.999$ ) work well for most problems. Which is why Adam is the recommended "start here" optimizer in every deep learning framework's documentation.

Adaptive Learning Rates in NLP

Word embedding training (word2vec, GloVe, fastText) benefits from per-parameter learning rates because word frequency follows power-law distributions. The word "the" appears in roughly 7% of all English text, while "hippopotamus" may appear once per billion words. With a fixed learning rate.

Frequent words dominate the gradient signal, receiving abnormally large cumulative updates.
Rare words barely update at all, remaining near their random initialization.

Adaptive methods solve this: frequent words accumulate large gradient histories ( $A_{i}$ grows), reducing their effective learning rate to a trickle ( $\sim 0.003$ ). Rare words maintain their original learning rate ( $\sim 0.03$ ), allowing them to learn meaningful representations from their few occurrences. Google's original word2vec paper used Adagrad for precisely this reason. Modern embedding models use Adam for the same benefit with better long-training stability.

Constrained Optimization in Cloud Computing

Oracle, Microsoft, AWS, and Google Cloud schedule upgrades and maintenance for thousands of enterprise customers using constrained optimization. The problem structure.

Objective.Minimize total disruption (downtime-minutes × customer-importance-weight).
Constraints.Each customer's availability windows, dependency chains (service A must be upgraded before service B). Regulatory compliance (data sovereignty, GDPR), and SLA guarantees (e.g., 99.99% uptime).
Scale.Thousands of customers, millions of constraint variables.

This class of problem is increasingly delegated to AI agents — autonomous systems that negotiate schedules. Detect and resolve conflicts, and adapt when constraints change (e.g., a customer extends their maintenance window). The Lagrangian framework underlies the mathematical modeling, even when the actual solving uses mixed-integer programming solvers or reinforcement learning.

GridSearchCV (scikit-learn)

A brute-force hyperparameter tuning tool in scikit-learn. You supply a grid of values for each hyperparameter — e.g., $α \in {0.001, 0.003, 0.01, 0.03, 0.1}$ and $β \in {0.8, 0.85, 0.9, 0.95}$ . The tool trains a model for every combination (4 × 5 = 20 combinations), evaluates each via cross-validation, and returns the best. Simple and guaranteed to find the best among the candidates, but computationally expensive — cost grows exponentially with the number of hyperparameters. For 5 hyperparameters with 5 values each, you need $5^{5} = 3125$ training runs. In practice, grid search is feasible for 1–3 hyperparameters with 3–5 values each. For larger searches, use random search (sample randomly from the grid) or Bayesian optimization.

Bayesian Optimization

A smarter alternative to grid search. Instead of trying every combination. Bayesian optimization builds a probabilistic surrogate model (typically a Gaussian Process) that predicts the validation loss for any hyperparameter setting. Along with an uncertainty estimate. It uses anacquisition functionto choose the next hyperparameter to try.

Exploration.Try points where the model is uncertain (high variance) — you might discover a great region you have not explored.
Exploitation.Try points near known good values (low predicted loss) — you refine the best solution you have found.

The acquisition function (commonly Expected Improvement or Upper Confidence Bound) balances these two. Each new training run updates the surrogate model, and the cycle repeats. Bayesian optimization typically finds good hyperparameters in 10–50 trials, versus hundreds or thousands for grid search. It is the preferred approach when each training run is expensive (hours on a GPU cluster). Libraries: scikit-optimize, Optuna, Hyperopt, BoTorch (Meta's Bayesian optimization library for PyTorch).

Agents and Autonomous Optimization

The next generation of ML engineering involves configuring and managing AI agents that perform optimization autonomously . Selecting architectures, tuning hyperparameters, scheduling training runs, and deploying models without human intervention. Understanding the mathematical foundations — gradient descent, momentum, adaptive methods. Constrained optimization — is essential for designing, debugging, and improving these agent systems. When an agent's training fails to converge, you need to know whether the problem is the optimizer (try Adam instead of SGD). The learning rate (too high → oscillation; too low → stalling), the constraints (check feasibility), or the architecture (gradient vanishing/exploding). The concepts in this lecture are the diagnostic toolkit for every ML practitioner.

Prerequisite Knowledge

Previously Covered in This Subject

13.1 Problems with Gradient Descent

13.1.1 Definition and Explanation

13.1.2 Symbol Registry

13.1.3 Three Failure Modes

13.1.4 Worked Visualization

13.1.5 Visual Intuition

13.1.6 Student Questions and Answers

13.1.7 Real-World and Domain Connection

13.2 Momentum-Based Gradient Descent

13.2.1 Physical Intuition — The Heavy Ball

13.2.2 Symbol Registry

13.2.3 Mathematical Formulation

13.2.4 Worked Example — Momentum Step Calculation

13.2.5 Student Questions and Answers

13.2.6 Real-World and Domain Connection

13.2.7 Industry Applications

13.3 Adagrad — Adaptive Gradient

13.3.1 Definition and Intuition

13.3.2 Symbol Registry

13.3.3 Mathematical Formulation

13.3.4 Student Questions and Answers

13.3.5 Real-World and Domain Connection

13.4 RMSProp

13.4.1 Definition and Intuition

13.4.2 Mathematical Formulation

13.4.3 Real-World and Domain Connection

13.5 Adam — Adaptive Moment Estimation

13.5.1 Overview and Context

13.5.2 Real-World and Domain Connection

13.6 Constrained Optimization and Lagrangian

13.6.1 Definition and Motivation

13.6.2 Symbol Registry

13.6.3 The Lagrangian Function

13.6.4 Worked Example — Bounded 2D Surface

13.6.5 Visual Intuition

13.6.6 Student Questions and Answers

13.6.7 Conceptual Connections

13.6.8 Real-World and Domain Connection

Exam Guidance Summary

Key Industry Applications

Momentum (β=0.9)

Adam (Adaptive Moment Estimation)

Adaptive Learning Rates in NLP

Constrained Optimization in Cloud Computing

GridSearchCV (scikit-learn)

Bayesian Optimization

Agents and Autonomous Optimization

MFML Lecture 13 notes · Gradient Descent Optimization

Sections Breakdown

Exam Revision Notes

Problems with Plain Gradient Descent

Momentum-Based Gradient Descent

Adagrad \u2014 Adaptive Gradient

RMSProp

Adam \u2014 Adaptive Moment Estimation

Constrained Optimization and the Lagrangian

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

Momentum ( $β = 0.9$ )