Mathematical Foundations for Machine Learning

Gradient Descent

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

The Gradient — Direction of Steepest Increase— covered in Lecture 9 (section 9.3)
Maxima, Minima, and Saddle Points— covered in Lecture 9 (section 9.8)
The Hessian Matrix— covered in Lecture 10 (section 10.5)
Classifying Critical Points Using the Hessian— covered in Lecture 10 (section 10.6)
Two-Variable Taylor Series and the Gradient— covered in Lecture 10 (section 10.4)

Gradient Descent

Gradient descent is the workhorse of modern machine learning. Every time a neural network learns, every time a linear model fits data. Gradient descent is underneath, quietly taking one downhill step after another. This lecture builds the idea from first principles: where the update rule comes from, why it works. It fails, and how its variants (batch, mini-batch, stochastic) trade speed for stability. You will also see how gradient descent connects to linear regression, convexity, learning rate tuning. The practical considerations that matter when you push the algorithm to scale.

11.1 Continuous Optimization and Gradient Descent

11.1.1 Definition and Context

Gradient descent is a core algorithm in continuous optimization. Continuous optimization deals with finding the minimum of functions over continuous variables. A subclass of continuous optimization is convex optimization — where the function's shape is bowl-like. Before diving into gradient descent itself, you need to understand the difference between constrained and unconstrained optimization. Constrained optimization places restrictions on the variables you can choose. Unconstrained leaves them free. Gradient descent is an unconstrained method.

Why should you care?Suppose you have a function with a thousand knobs to turn, and you want the combination that gives the smallest output. You cannot try every combination — there are too many. You cannot solve for the answer directly — the function is too messy. You need a strategy that starts somewhere random and walks downhill, one step at a time. That strategy is gradient descent.

At its heart, gradient descent tries to answer one question: from where you are standing, which direction takes you downhill fastest?

Intuition — the foggy mountain hiker.You are standing in the dark on a foggy mountain at night. You cannot see more than 10 meters ahead. But you know there is a village at the bottom of the valley. What do you do? You tap the ground in a full 360-degree circle around you. You feel which direction the ground rises most sharply. Then you take a 180-degree turn and walk the opposite way. That is gradient descent — find the steepestincrease, go the opposite direction.

Here is the mapping: you are the current position $X_{n}$ . The steepness you feel is the gradient $\nabla f (X_{n})$ . The opposite direction is the minus sign. The length of your step is the learning rate $α$ . Where the analogy breaks: you feel the slope with perfect precision (zero noise). You take exactly one step before feeling again — no momentum, no memory.

The algorithm doesnotguarantee you will find the global minimum. It only guarantees that it will descend — that each step lowers the function value relative to where you were. The guarantee holds regardless of the surface shape.

But the surface shape still matters. On a convex surface (a bowl with a single deepest point), gradient descent will always find that global minimum. On a non-convex surface, many dips, ridges, and valleys exist. The algorithm can get stuck in alocal minimum— a depression lower than its neighbors but not the global lowest point.

11.1.2 The Gradient Descent Update Rule

The update rule.Given a current position

X_{n}

, a function

f

, a learning rate

α > 0

, and the gradient

\nabla f (X_{n})

$X_{n + 1} = X_{n} - α \nabla f (X_{n})$

Every symbol:

$X_{n}$ — where you are right now (a point, could be a scalar or vector)
$X_{n + 1}$ — where you go next
$α$ (alpha) — thelearning rateorstep size, a small positive number, typically in $(0, 1]$
$\nabla f (X_{n})$ — thegradientof $f$ at $X_{n}$ . In one dimension this is just the derivative $f^{'} (X_{n})$ . In higher dimensions it is the vector of partial derivatives — one slope per direction.

Why the minus sign? You first look at where the function increases. Then you turn 180 degrees away from it. If the gradient is a vector pointing uphill, the negative of that vector points downhill.

A simple two-dimensional picture makes this clear. Suppose you are standing on one side of a valley. The slope at your feet is negative — the ground tilts down toward the valley floor. With a negative slope, the update $X_{n} - α \cdot (negative)$ becomes $X_{n} + something positive$ . You move to the right, toward the minimum. If you are standing on the other side of the same valley, the slope is positive. The update becomes $X_{n} - something positive$ . You move to the left, again toward the minimum. The minus sign always points toward the valley floor, regardless of which side you start on.

11.1.3 Symbol Registry

$X_{n}$ — current position (point at iteration $n$ ) — scalar or vector, depending on dimension
$X_{n + 1}$ — next position (point at iteration $n + 1$ )
$α$ — learning rate or step size — small positive scalar, typically in $(0, 1]$
$\nabla f (X_{n})$ — gradient of the function $f$ evaluated at $X_{n}$ — same dimensionality as $X_{n}$
$f$ — the function being minimized (often a loss function)
$δ X$ — the step taken, defined as $δ X = X_{n + 1} - X_{n}$

11.1.4 Derivation from Taylor Series

Gradient descent is not an ad-hoc rule. It falls directly out of the Taylor series expansion.

Step 1 — The Taylor approximation.Stand at

X_{n}

and take a small step

δ X

. The first-order Taylor expansion tells you the new function value:

$f (X_{n} + δ X) \approx f (X_{n}) + δ X \cdot f^{'} (X_{n})$

The function's new value is roughly your current value plus the step times the slope at your current point.

Step 2 — The descent goal.You want every step to go downhill:

$f (X_{n + 1}) < f (X_{n})$

Define $δ X = X_{n + 1} - X_{n}$ and substitute the Taylor expansion:

$f (X_{n}) + δ X \cdot f^{'} (X_{n}) < f (X_{n})$

Cancel $f (X_{n})$ from both sides:

$δ X \cdot f^{'} (X_{n}) < 0$

Step 3 — The key condition.This is the descent inequality: the product of your step $δ X$ and the slope $f^{'} (X_{n})$ must be negative. If the slope is positive (you are on the right side of the valley), $δ X$ must be negative — you step left. If the slope is negative (left side), $δ X$ must be positive — you step right.

Step 4 — A guaranteed choice.Choose $δ X = - α f^{'} (X_{n})$ with $α > 0$ :

$(- α f^{'} (X_{n})) \cdot f^{'} (X_{n}) = - α (f^{'} (X_{n}))^{2}$

A square is never negative. Multiplied by $- α$ , the product is never positive. The descent condition holds for any choice of $α > 0$ . This is why the minus sign is necessary. Sufficient — it is the only choice of the form $δ X = - α f^{'} (X_{n})$ that guarantees $δ X \cdot f^{'} (X_{n}) < 0$ regardless of the sign of $f^{'} (X_{n})$ .

Step 5 — Recover the update rule.Recall $δ X = X_{n + 1} - X_{n}$ :

$X_{n + 1} - X_{n} X_{n + 1} = - α f^{'} (X_{n}) = X_{n} - α f^{'} (X_{n})$

Step 6 — Multi-dimensional generalization.Replace the scalar derivative $f^{'} (X_{n})$ with the gradient vector $\nabla f (X_{n})$ . The update becomes $X_{n + 1} = X_{n} - α \nabla f (X_{n})$ .

The entire derivation depends on a single assumption: $δ X = - α f^{'} (X_{n})$ . That choice guarantees every step lowers the function value, to the precision of the first-order Taylor approximation.

11.1.5 The Steepest Direction — Why the Gradient

In multiple dimensions, you can step in many directions. Why is the gradient direction always the best choice?

Take a point where you stand and imagine all possible unit direction vectors $u$ radiating outward. You want the direction that aligns most closely with the direction straight toward the minimum — call it $m$ .

The dot product measures alignment:

$m \cdot u = ∥ m ∥ ∥ u ∥ cos θ$

This is maximized when $cos θ = 1$ , meaning $θ = 0$ . The vectors point in exactly the same direction. That direction is the gradient direction (up to sign). No other direction gives a larger dot product with the path toward the minimum.

This is why gradients produce the steepest descent: they are the direction that maximizes alignment with where you need to go. In the foggy-mountain hiker language: the gradient points to the steepestuphill. The negative gradient points to the steepestdownhill.

11.1.6 Worked Example — Gradient Descent on a Simple Parabola

Minimize $f (x) = x^{2}$ starting from $x_{0} = 3$ with $α = 0.3$ .

The derivative is $f^{'} (x) = 2 x$ .

Iteration 1:

$x_{1} = x_{0} - α f^{'} (x_{0}) = 3 - 0.3 \cdot (2 \cdot 3) = 3 - 0.3 \cdot 6 = 3 - 1.8 = 1.2$

Iteration 2:

$x_{2} = 1.2 - 0.3 \cdot (2 \cdot 1.2) = 1.2 - 0.3 \cdot 2.4 = 1.2 - 0.72 = 0.48$

Iteration 3:

$x_{3} = 0.48 - 0.3 \cdot (2 \cdot 0.48) = 0.48 - 0.3 \cdot 0.96 = 0.48 - 0.288 = 0.192$

Iteration 4:

$x_{4} = 0.192 - 0.3 \cdot (2 \cdot 0.192) = 0.192 - 0.3 \cdot 0.384 = 0.192 - 0.1152 = 0.0768$

Iteration 5:

$x_{5} = 0.0768 - 0.3 \cdot (2 \cdot 0.0768) = 0.0768 - 0.04608 = 0.03072$

Sense-check:The true minimum is at $x = 0$ . Starting from $x = 3$ , after 5 steps we reached $x \approx 0.031$ . Each step got smaller because the gradient $(2 x)$ shrinks as we approach the minimum. If we kept going, $x$ would decay toward zero geometrically.

11.1.7 Assumptions and Scope

Scope — when the gradient descent update rule applies.

Assumption 1: Differentiability.The function must be differentiable at every point you evaluate the gradient. If $f$ has a sharp corner or a discontinuity, the gradient does not exist there, and the update rule is undefined.

Assumption 2: Small enough $α$ .The Taylor approximation underpinning the derivation is only accurate for small $δ X$ . If $α$ is too large, the step overshoots the region where the first-order approximation is good. The descent guarantee evaporates — the function value can actually increase.

Assumption 3: First-order method.Gradient descent uses only first-derivative information. It is blind to curvature. On a narrow, winding valley, it will zigzag inefficiently. On a function with a saddle point. It can stall even though the point is not a minimum (the gradient is zero at saddle points too).

What breaks these?On a non-differentiable function (like the absolute value at the origin), subgradient methods are needed. For a poorly conditioned function (elongated contours), the simple gradient direction is inefficient — momentum or second-order methods (Newton's method) help. For a function with saddle points, you need momentum or random perturbations to escape.

11.1.8 Visual Intuition

Picture a two-dimensional loss surface drawn as a contour map, like a topographic map of a valley. The $x$ -axis is one weight. The $y$ -axis is another weight. Contour lines trace equal values of the loss. They are tighter where the slope is steep and wider where it is flat.

From your starting point, draw an arrow perpendicular to the contour line you are standing on. That arrow is the gradient direction — it points straight uphill, crossing contour lines at a right angle. The negative of that arrow is your downhill step.

As gradient descent runs, you see a path of dots tracing a curve down toward the valley floor. Each dot is an $X_{n}$ . The spacing between dots shrinks as the slope flattens. At the minimum, the contour lines form concentric ellipses, and all gradient arrows point inward toward the center.

Takeaway: Gradient descent is like water rolling down a topographic map. It always moves perpendicular to the contour lines, following the steepest local slope.

11.1.9 Pitfalls

Pitfall 1 — Believing gradient descent findstheminimum.It findsastationary point (gradient zero). That point could be a local minimum, a global minimum, or a saddle point. On a non-convex surface, there are no guarantees.

Pitfall 2 — Ignoring the learning rate.A learning rate that is too large causes divergence — the loss explodes instead of decreasing. A learning rate that is too small makes training take forever. The learning rate is a hyperparameter you must tune; there is no automatic "correct" value baked into the algorithm.

Pitfall 3 — Confusing the update rule with the goal.The update rule guarantees descentlocally, not globally. It says "from here, this step goes down." It doesnotsay "this step goes toward the global minimum." If you start in the wrong basin of attraction on a multi-basin surface. The algorithm will dutifully walk you to the bottom of the wrong basin.

Pitfall 4 — Assuming all coordinates update at the same effective rate.The gradient is the vector of partial derivatives. If one coordinate's partial derivative is much smaller than another's. Gradient descent will creep along the flat direction while bouncing along the steep direction. The implicit "speed" is different for each coordinate.

11.1.10 Recap and Bridge

Gradient descent is an iterative update rule — $X_{n + 1} = X_{n} - α \nabla f (X_{n})$ — that descends a function one step at a time. It comes directly from the first-order Taylor expansion and the requirement that $δ X \cdot f^{'} (X_{n}) < 0$ . The gradient direction is the steepest descent direction because it maximizes the dot product with the path toward the minimum. But the algorithm only guarantees local descent, not global optimality.

Next, we ask: what does the terrain look like? Can gradient descent get trapped? The answers depend on the shape of the surface — convex vs. non-convex, one basin vs. many. Those are the topics of section 11.2.

11.1.11 Real-World and Domain Connection

Gradient descent is not just an academic algorithm. It is the engine inside every modern deep learning training loop. From the language models in chatbots to the vision models in self-driving cars. When you hear "the model is training. " what you are really hearing is this: "gradient descent (or one of its descendants) is running." It takes millions of downhill steps on a loss surface with billions of parameters.

In fields like quantitative finance, gradient descent calibrates option-pricing models to market data. In computational biology, it fits kinetic models to experimental measurements. In control engineering, it tunes PID controller gains. Any domain where you have a differentiable quality metric. A set of continuous parameters to adjust — gradient descent is a candidate solver.

11.1.12 Student Questions and Answers

Q:Does gradient descent always give us the global minimum?

A:No, it does not guarantee the global minimum. The algorithm only guarantees that it will descend — each step lowers the function value. It can get stuck at a local minimum. The one case where gradient descent guarantees the global minimum is when the surface is strictly convex. A bowl with a single deepest point. On any other surface, local minima can trap the algorithm.

Q:I read that if we use mean squared error as the loss function, it will always reach the global minimum. Is that true?

A:That is correct specifically for linear regression with MSE. The squared error form produces a parabolic, strictly convex surface. The $X^{⊤} X$ matrix that forms in the solution is always convex and bowl-shaped. There is only one minimum. But mix MSE with any other algorithm — neural networks, for example — and the surface becomes highly complex. It develops many local minima. Linear regression's assumption of linearity is very simple. Most relationships in nature are nonlinear, so linear regression fails in many real cases even though it guarantees convexity.

11.2 Global vs Local Minima and Convexity

11.2.1 Local and Global Minima

Why should you care?You would never climb a mountain and stop halfway down because the ground felt flat for a few meters. Yet gradient descent does exactly that. It stops whenever the gradient hits zero, no matter whether it is at the deepest valley. A shallow puddle on a ledge. Understanding the difference between a local dip. The true bottom is the difference between a model that works and a model that barely beats random guessing.

Alocal minimumis a point where the function value is lower than all immediately neighboring points. But it is not necessarily the lowest point overall. Aglobal minimumis the absolute lowest point on the entire function surface.

Intuition — water flowing to the ocean.Think of water flowing down a mountain toward the ocean. The water cannot see the whole path. It feels the steepness of the ground beneath it and flows in the steepest downward direction. Sometimes it hits a depression — a dip in the terrain — and gets trapped. That depression becomes a lake.

The water accumulates, builds momentum, and may eventually spill over the edge and continue downhill. It may form several lakes before reaching the ocean. Each lake is a local minimum. The ocean is the global minimum.

Mapping to gradient descent: the water is the optimizer. The steepness is the gradient. The lake is a local minimum where the gradient is zero but the function is not at its lowest. The ocean is the global minimum. The water's momentum — its accumulated velocity pushing it over the lake's edge — is what momentum-based optimizers try to replicate.

Gradient descent behaves the same way. Without mechanisms like momentum, it can settle into any local minimum. Nature has momentum built in — rolling water, rolling balls, sliding rocks. Standard gradient descent does not — unless you add it.

11.2.2 Symbol Registry

Hessian $H$ — matrix of second partial derivatives of a function — square matrix, shape $d \times d$ for a function of $d$ variables
$v^{⊤} H v = \sum_{i = 1}^{d} \sum_{j = 1}^{d} v_{i} H_{ij} v_{j}$ — the quadratic form defined by $H$ — scalar output
$v^{⊤} H v > 0$ — condition for a matrix $H$ to bepositive definite— must hold for all non-zero vectors $v$

11.2.3 Convexity and the Hessian

What is convexity?A function

f

isconvexwhen the line segment connecting any two points on its graph lies on orabovethe graph. Intuitively: the function curves upward everywhere — shaped like a bowl.

Aconvex set:if you pick any two points in the set. Draw a straight line between them, the entire line segment stays inside the set. A circle is convex; a star shape is not.

The magic property of convex functions: they have exactly one minimum — a global minimum. There are no local minima to get trapped in. Gradient descent, given a small enough learning rate, will find it from any starting point.

Convexity connects to linear algebra throughpositive definite matrices. A symmetric positive definite matrix guarantees that the quadratic form it defines is convex.

TheHessian matrix $H$ — the matrix of second partial derivatives — encodes the curvature of a function. For a function $f (x_{1}, x_{2})$ of two variables:

$H = \frac{\partial ^{2} f}{\partial x _{1}^{2}} \frac{\partial ^{2} f}{\partial x _{2} \partial x _{1}} \frac{\partial ^{2} f}{\partial x _{1} \partial x _{2}} \frac{\partial ^{2} f}{\partial x _{2}^{2}}$

Each diagonal entry is the curvature along one axis. If both diagonal entries are positive at every point, the function curves upward in both directions — it is convex.

More generally: if the Hessian ispositive semidefinite( $v^{⊤} H v \geq 0$ for all $v$ ), the function is convex. If it ispositive definite( $v^{⊤} H v > 0$ for all non-zero $v$ ), the function is strictly convex. Strict convexity means the bowl has a single, unique global minimum.

Equivalently, all eigenvalues of a positive definite matrix are strictly positive. The Hessian describes the local quadratic approximation of the function — like fitting a parabola at every point. If every such parabola opens upward, the function must be convex.

11.2.4 Worked Example — Checking Convexity of a Simple Function

Is $f (x, y) = x^{2} + 3 y^{2}$ convex?

Step 1 — Compute the Hessian.

$\frac{\partial f}{\partial x} = 2 x, \frac{\partial ^{2} f}{\partial x ^{2}} = 2$

$\frac{\partial f}{\partial y} = 6 y, \frac{\partial ^{2} f}{\partial y ^{2}} = 6$

$\frac{\partial ^{2} f}{\partial x \partial y} = 0, \frac{\partial ^{2} f}{\partial y \partial x} = 0$

So:

$H = [2006]$

Step 2 — Check positive definiteness.For any non-zero vector $v = [v_{1}, v_{2}]^{⊤}$ :

$v^{⊤} H v = [v_{1} v_{2}] [2006] [v_{1} v_{2}] = 2 v_{1}^{2} + 6 v_{2}^{2} > 0$

Both eigenvalues are positive (2 and 6).The function is strictly convex.It has a single global minimum at $(0, 0)$ where $f = 0$ .

Sense-check:The function is a sum of two upward-opening parabolas — an elliptical bowl. There is no hidden valley, no ridge. Gradient descent from any starting point will slide to $(0, 0)$ .

11.2.5 Assumptions and Scope

Scope — convexity is a strong assumption that rarely holds in practice.

Assumption for convexity guarantees:The function must be differentiable (for Hessian check), and the Hessian must be positive semidefinite everywhere. If either condition fails, you lose the single-minimum guarantee.

When convexity holds:Linear regression with MSE loss, logistic regression with cross-entropy loss, support vector machines with hinge loss. These are all convex optimization problems. You get a guaranteed global minimum.

When convexity breaks:Neural networks, mixture models, matrix factorization — these have highly non-convex loss surfaces. There are ridges, plateaus, saddle points, and many local minima. Convexity-based guarantees do not apply.

What happens without convexity:You must rely on multiple random restarts, momentum, and adaptive learning rates to find a "good enough" local minimum. You can never certify that you found the global one. This is the practical reality of deep learning.

11.2.6 Visual Intuition

Picture a 3D surface. A convex surface looks like a smooth bowl. Pick any two points on the rim and the straight line between them floats above the bowl's surface. If you drop a marble anywhere on this bowl, it rolls to the same single bottom, regardless of where you let go.

Now picture a non-convex surface — think of a mountain range. The surface has peaks, ridges, valleys, and plateaus. A marble dropped near a shallow depression stays there. Dropped near a deep canyon, it rolls much farther down. Different starting points lead to different resting places. The surface has multiple bowls of different depths.

Takeaway: Convexity means "one bowl, one bottom, one answer." Non-convexity means "many bowls, many possible answers. No map to tell you which one is deepest."

11.2.7 Pitfalls

Pitfall 1 — Assuming your loss function is convex without checking.Many beginners inherit the "MSE is convex" fact from linear regression and assume it extends to neural networks. It does not. The convexity comes from the linear model's structure, not from MSE alone.

Pitfall 2 — Forgetting that "positive definite" must hold everywhere.A function can be convex on one region and non-convex on another. Local convexity near the minimum is not global convexity. Gradient descent can still get stuck in a non-convex region on the way down.

Pitfall 3 — Confusing the Hessian test with the gradient test.Zero gradient tells you "stationary point" — could be minimum, maximum, or saddle. The Hessian tells you what kind. Positive definite Hessian at a stationary point = local minimum. Negative definite = local maximum. Mixed eigenvalues = saddle point.

Pitfall 4 — Ignoring saddle points.In high dimensions (think hundreds or thousands), saddle points are far more common than local minima. Gradient descent stalls at saddle points because the gradient is zero, even though there is a downhill direction available. This is a major practical problem in deep learning that momentum and adaptive methods help address.

11.2.8 Recap and Bridge

A convex function has exactly one global minimum — gradient descent will find it. A non-convex function can have many local minima, and gradient descent may get trapped in any of them. The Hessian matrix, through the positive definiteness check, is your tool for determining convexity. But most real-world ML loss surfaces are non-convex, so you need restart strategies, momentum, and adaptive methods.

Next, we apply gradient descent to a concrete problem you know well: fitting a line to data. Linear regression with MSE is convex — a perfect sandbox to see the algorithm work with real numbers, step by step.

11.2.9 Real-World and Domain Connection

The convexity of MSE in linear regression is not just a theoretical curiosity. It is why linear regression remains the first model run in almost every data science project. You need a baseline. You need something that trains in seconds and gives the same answer every time. That baseline is linear regression with MSE.

In econometrics, the convexity guarantee justifies the Ordinary Least Squares (OLS) estimator as the Best Linear Unbiased Estimator (BLUE). In signal processing, convex formulations of problems like compressed sensing guarantee that the recovered signal is the true one. In operations research, convexity is the dividing line between "solvable in polynomial time" and "likely intractable."

11.2.10 Student Questions and Answers

Q:Can gradient descent converge if the loss function is not convex?

A:Yes, it can converge. Whether it converges to a good minimum depends on where you start. A common practice is to train the model from many different random starting points. If you start from ten different initializations. The algorithm reaches roughly the same point each time, that point is probably the global minimum. If the loss surface has many local minima, you may land in different ones each time. Later algorithms based on momentum add tricks to help escape local minima, but they do not guarantee escape.

Q:With many local minima, how does the model decide when to stop?

A:The model stops when the gradient becomes nearly zero — when further updates produce negligible change. After some number of updates in a row where the gradient is essentially zero, training halts. You do not know whether you are at a local or global minimum. But if you reinitialize the weights and retrain from scratch several times, you may land at the same loss value each time. That point is likely the global minimum. This is the practical iterative approach used in the field.

11.3 Gradient Descent in Linear Regression

11.3.1 The Linear Regression Model

Why should you care?Linear regression is the simplest model where you can watch gradient descent work. Every piece of math has a concrete meaning, and the convexity guarantee means you always land at the right answer. Once you understand gradient descent here, you understand it everywhere.

Multiple linear regression models a dependent variable $Y$ as a linear combination of independent variables (features) plus an error term:

$Y = β_{0} + β_{1} X_{1} + β_{2} X_{2} + \dots + β_{k} X_{k} + ε$

Here $β_{0}$ is the bias (intercept) term — the predicted value when all features are zero. $β_{1}, β_{2}, \dots, β_{k}$ are the coefficients for each feature. How much $Y$ changes when that feature increases by one unit, holding everything else constant. $ε$ is the error — the part of $Y$ that the linear combination of $X$ 's cannot explain. Your goal is to estimate the best values of the $β$ coefficients from the data.

For a dataset with $M$ data points and $N$ features, you can write the model in vectorized form. Let $X$ be the $M \times (N + 1)$ design matrix (with an extra column of ones for the bias term). Let $θ$ be the vector of all coefficients $[β_{0}, β_{1}, \dots, β_{N}]^{⊤}$ . Then the predicted values are:

$Y^= X θ$

The hat on $Y$ means "estimated". "predicted." The hat on $θ$ (when used) means the coefficients are estimates from a sample. They are not the true population parameters. This notation comes from statistics.

Intuition — fitting a line through a cloud of points.You have a scatter plot of data points. You want to draw a straight line (or plane, or hyperplane) that passes as close as possible to all of them. "Close" means the vertical distance from each point to the line is small. The

β

coefficients control the line's slope and intercept. Gradient descent nudges these coefficients until the line sits at the best position. The one that minimizes the sum of squared vertical gaps.

11.3.2 Mean Squared Error Loss Function

To measure how well your coefficients fit the data, you use aloss function. For regression, the most common choice ismean squared error(MSE). It sums the squared differences between true values and predicted values across all data points, then averages:

$J (θ) = \frac{1}{2 M} i = 1 \sum M (Y_{i} - Y^_{i})^{2}$

In vectorized form with $Y, Y^\in R^{M}$ and $X \in R^{M \times (N + 1)}$ :

$J (θ) = \frac{1}{2 M} (Y - X θ)^{⊤} (Y - X θ)$

The factor $\frac{1}{2}$ is there purely for mathematical convenience. When you take the derivative of $x^{2}$ , you get $2 x$ . The $\frac{1}{2}$ cancels the 2 from the derivative, keeping the gradient clean.

The gradient of the MSE loss with respect to $θ$ is derived below. Starting from $J (θ) = \frac{1}{2 M} ∥ Y - X θ ∥^{2}$ :

$\nabla J (θ) = \frac{1}{2 M} \cdot \frac{\partial}{\partial θ} (Y - X θ)^{⊤} (Y - X θ) = \frac{1}{2 M} \cdot 2 \cdot (Y - X θ)^{⊤} \cdot \frac{\partial}{\partial θ} (Y - X θ) = \frac{1}{M} (Y - X θ)^{⊤} \cdot (- X) = - \frac{1}{M} (Y - X θ)^{⊤} X$

As a column vector (transposing the result):

$\nabla J (θ) = - \frac{1}{M} X^{⊤} (Y - X θ) = \frac{1}{M} X^{⊤} (X θ - Y) = \frac{1}{M} X^{⊤} (Y^- Y)$

This is the gradient form used throughout this lecture. When a textbook writes $\frac{1}{M} X^{⊤} (Y - Y^)$ , they are using the same algebra. Distributing the minus sign differently or starting from $J = \frac{1}{2 M} ∥ X θ - Y ∥^{2}$ (which is identical since squaring removes the sign). Both forms are equivalent — the difference is a factor of $- 1$ which the weight update rule $W_{new} = W_{old} - α \nabla J$ absorbs automatically. What matters is consistency: pick one convention and stick with it. In every worked example in this lecture, we use $\nabla J = \frac{1}{M} X^{⊤} (Y^- Y)$ .

The gradient depends on three things: the number of data points $M$ , the transpose of the design matrix $X^{⊤}$ . The error vector $(Y^- Y)$ . When you have only a few features and a small dataset, you can compute this gradient in one shot.

11.3.3 Symbol Registry

$Y$ — true target values — vector of length $M$
$Y^$ — predicted values, $Y^= X θ$ — vector of length $M$
$X$ — design matrix of input features — $M \times (N + 1)$ matrix (extra column of ones for bias)
$θ$ (or $β$ ) — vector of model coefficients $[β_{0}, β_{1}, \dots, β_{N}]^{⊤}$ — vector of length $N + 1$
$M$ — total number of data points — scalar
$N$ — total number of features — scalar
$J (θ)$ — loss function (MSE in this case) — scalar
$\nabla J (θ)$ — gradient of the loss with respect to $θ$ — vector of length $N + 1$
$α$ — learning rate — small positive scalar

11.3.4 Worked Example — Full Batch Gradient Descent Iteration

Consider a simple linear regression with one feature (age) predicting salary. The data:

$X$ (age)	$Y$ (salary, in lakhs)
22	44
26	52
30	60
34	68

The true relationship is $Y = 2 X$ . The best coefficient is $β_{1} = 2$ and $β_{0} = 0$ . But we do not know this — we must learn it.

To accommodate the bias term $β_{0}$ , add a column of ones to the design matrix:

$X = 111122263034, Y = 44526068$

Step 1 — Choose starting values.Pick $β_{0} = 0$ , $β_{1} = 1$ . The coefficient vector is $θ = [0, 1]^{⊤}$ .

Step 2 — Compute predictions. $Y^= X θ$ :

$Y^= 1 \cdot 0 + 22 \cdot 1 1 \cdot 0 + 26 \cdot 1 1 \cdot 0 + 30 \cdot 1 1 \cdot 0 + 34 \cdot 1 = 22263034$

Step 3 — Compute the error vector. $Y^- Y$ :

$Y^- Y = 22 - 44 26 - 52 30 - 60 34 - 68 = - 22 - 26 - 30 - 34$

The error values are all negative and fairly large. The model is severely under-predicting — it predicts roughly half the true salary.

Step 4 — Compute the loss.The MSE loss at this point:

$J (θ) = \frac{1}{2 \cdot 4} [(- 22)^{2} + (- 26)^{2} + (- 30)^{2} + (- 34)^{2}]$

The squared errors are $484 + 676 + 900 + 1156 = 3216$ . So:

$J (θ) = \frac{1}{8} \cdot 3216 = 402$

A loss of 402 is large. We want it near zero.

Step 5 — Compute the gradient. $M = 4$ data points:

$\nabla J (θ) = \frac{1}{4} X^{⊤} (Y^- Y)$

First compute $X^{⊤} (Y^- Y)$ :

$X^{⊤} (Y^- Y) = [122126130134] - 22 - 26 - 30 - 34$

First row (bias component): $1 \cdot (- 22) + 1 \cdot (- 26) + 1 \cdot (- 30) + 1 \cdot (- 34) = - 112$

Second row (slope component): $22 \cdot (- 22) + 26 \cdot (- 26) + 30 \cdot (- 30) + 34 \cdot (- 34)$

Compute the squares: $2 2^{2} = 484$ , $2 6^{2} = 676$ , $3 0^{2} = 900$ , $3 4^{2} = 1156$ . Sum: $484 + 676 + 900 + 1156 = 3216$ .

So the second row is $- 3216$ . The full product:

$X^{⊤} (Y^- Y) = [- 112 - 3216]$

Now divide by $M = 4$ :

$\nabla J (θ) = \frac{1}{4} [- 112 - 3216] = [- 28 - 804]$

Step 6 — Update the coefficients.Use learning rate $α = 0.1$ :

$θ_{new} = θ_{old} - α \nabla J (θ)$

$θ_{new} = [01] - 0.1 [- 28 - 804] = [01] - [- 2.8 - 80.4] = [2.8 81.4]$

After one iteration: $β_{0} = 2.8$ , $β_{1} = 81.4$ . The slope coefficient overshot dramatically (true value is 2). That is because the initial gradient was very large due to the bad starting guess. But the direction was correct — both coefficients moved to reduce the error.

Step 7 — Repeat.Plug the new $θ$ back into Step 2 and iterate. With each iteration, the coefficients adjust and the loss decreases. This process — using all $M$ data points to compute the gradient — is calledbatch gradient descent.

Sense-check:The gradient came out negative for both components $[- 28, - 804]$ . Subtracting a negative means adding. Both $β_{0}$ and $β_{1}$ increased. That is correct since the true $β_{1} = 2$ is larger than the initial guess of 1. The bias overshot past its true value of 0. The overshoot comes from the learning rate, not the direction. With a smaller $α$ (say 0.001), the update would have been gentler, moving $θ$ toward $[0.028, 1.804]^{⊤}$ . Closer to the target but requiring many more iterations.

11.3.5 Why Closed-Form Solution Fails at Scale

There is an alternative to gradient descent: theclosed-form(analytical) solution. To find the optimal coefficients, set the partial derivative of the loss with respect to each coefficient equal to zero:

$\frac{\partial J}{\partial β _{0}} = 0, \frac{\partial J}{\partial β _{1}} = 0, \dots, \frac{\partial J}{\partial β _{k}} = 0$

For $k$ coefficients, you get $k + 1$ equations (including the bias). The closed-form solution involves computing $(X^{⊤} X)^{- 1} X^{⊤} Y$ — inverting a $(k + 1) \times (k + 1)$ matrix. If you have only two features (age and experience predicting salary), you invert a $3 \times 3$ matrix. That is easy — a fraction of a second on any computer, even with millions of data points.

With thousands of features — salary depending on age, experience, location, education, industry, company size. Many more — you must invert a $1001 \times 1001$ matrix. Matrix inversion is an $O (d^{3})$ operation where $d$ is the number of features. At scale, this becomes computationally prohibitive.

Two problems emerge at scale:

Solving huge systems of equations via matrix inversion is slow — $O (d^{3})$ for $d$ features.
The closed form requires $X^{⊤} X$ to be invertible. If features are collinear (one feature is a near-linear combination of others), the matrix is ill-conditioned and the inversion is numerically unstable.

Hence iterative methods like gradient descent exist. You start from a random point, compute the loss, take a step downhill, and repeat. You never solve the full system of equations at once. Each iteration costs $O (M d)$ — linear in both data points and features.

11.3.6 Convexity of MSE in Linear Regression

The MSE loss function for linear regression is always convex. Because of the squared term, the loss surface takes a parabolic, bowl-like shape. The $X^{⊤} X$ matrix that appears in the closed-form normal equations is positive semi-definite. For a well-conditioned problem, it is positive definite, making the surface strictly convex — exactly one global minimum.

This is the reason gradient descent always converges to the global minimum for linear regression with MSE. The bowl shape means something simple: no matter where you start. Left side, right side, or right at the bottom — every downhill path leads to the same lowest point.

But this guarantee does not extend to other algorithms. Neural networks, for instance, have highly complex, non-convex loss surfaces with ridges, plateaus, and many local minima. MSE with a neural network does not inherit the convexity property. The convexity comes from the linear model structureplusthe squared error, not from MSE alone.

11.3.7 Assumptions and Scope

Scope — when gradient descent on linear regression works and when it does not.

Assumption 1: Linear relationship.The model assumes $Y$ is a linear combination of the $X$ 's plus noise. If the true relationship is curved (e.g., $Y = X^{2}$ ), no amount of gradient descent will make a straight line fit well. You need polynomial features or a different model.

Assumption 2: No perfect collinearity.If one feature is an exact linear combination of others, $X^{⊤} X$ is singular — the normal equations have infinitely many solutions. Gradient descent will still converge, but to one of many equivalent minima. The coefficients are not uniquely identifiable.

Assumption 3: Homoscedasticity (for statistical inference).The variance of the errors is assumed constant across all levels of the predictors. Gradient descent does not need this assumption to find the coefficients, but statistical tests (p-values, confidence intervals) do.

Assumption 4: IID errors (for statistical inference).Errors are assumed independent and identically distributed. Again, gradient descent minimizes MSE without needing this, but statistical inference does.

What breaks these?Violating linearity → systematically bad predictions, regardless of convergence. Collinearity → coefficient instability, but predictions may still be fine. Non-constant variance → predictions still unbiased but inefficient; weighted least squares is the fix.

11.3.8 Visual Intuition

Picture a 3D plot with axes $β_{0}$ , $β_{1}$ , and $J (θ)$ . The loss surface is a perfect parabolic bowl. The bottom of the bowl is at $(β_{0} = 0, β_{1} = 2)$ with $J = 0$ . Starting at $(β_{0} = 0, β_{1} = 1)$ , the surface slopes steeply downward toward the true coefficients. The gradient vector at the starting point points toward the steepest part of the bowl wall. Each gradient descent step is a short line segment sliding diagonally down the bowl wall, gradually curving toward the bottom.

The path on a contour plot (looking down from above) would show dots spiraling or zigzagging inward toward the center. With a small learning rate, the path is a smooth inward spiral. With a large learning rate, the path bounces between opposite walls of the bowl before settling.

Takeaway: For linear regression with MSE, the loss surface is a simple bowl. Gradient descent is sliding a marble down that bowl — smooth, predictable, and guaranteed to reach the bottom.

11.3.9 Pitfalls

Pitfall 1 — Forgetting to add the column of ones for the bias.If you omit the bias column from

X

, gradient descent tries to force the line through the origin. If the true intercept is non-zero, the model will never fit well, no matter how many iterations.

Pitfall 2 — Not normalizing features.Features on wildly different scales (age in 20s vs. salary in lakhs) produce a stretched, narrow bowl. The gradient in the salary direction is huge; in the age direction, tiny. Gradient descent bounces along the steep salary axis while creeping along the age axis — convergence is painfully slow. Scale your features to similar ranges.

Pitfall 3 — Using an enormous learning rate on the first iteration.In the worked example, $α = 0.1$ made $β_{1}$ overshoot to 81.4 from an initial guess of 1. If the gradient is large and $α$ is too big, the coefficients can diverge to infinity in one step. Start with a small $α$ ; you can always increase it later.

Pitfall 4 — Confusing the derivative with respect to $θ$ (coefficients) vs. $X$ (features).You differentiate the loss with respect to $θ$ , not $X$ . The $X$ values are fixed — they come from your data. The unknowns you are solving for are the $β$ coefficients.

11.3.10 Recap and Bridge

Gradient descent finds the optimal linear regression coefficients by iteratively updating $θ = θ - α \nabla J (θ)$ , where $\nabla J = \frac{1}{M} X^{⊤} (Y^- Y)$ . Because the MSE loss surface is convex (parabolic bowl), gradient descent always converges to the global minimum from any starting point. The closed-form solution via matrix inversion exists but becomes computationally prohibitive when the number of features is large ( $O (d^{3})$ vs. $O (M d)$ per gradient iteration).

Next, we generalize: what if you do not use all the data for every step? What if you use just one point, or a handful? The batch/mini-batch/stochastic spectrum controls the trade-off between computation cost and gradient accuracy.

11.3.11 Real-World and Domain Connection

Linear regression with gradient descent is used everywhere. Not because it is fancy, but because it is fast, interpretable, and has guarantees. In finance, it models the relationship between market indices and stock returns (the Capital Asset Pricing Model is a linear regression). In epidemiology, it estimates the effect of a treatment while controlling for confounders. In real estate, it powers automated valuation models (Zestimate is, at its core, a large-scale linear regression).

The convexity guarantee is a practical superpower: when you deploy a linear regression model. You can certify that training converged to the unique optimum. You do not need multiple random seeds or early-stopping heuristics. That reliability is why linear regression is the first model applied to any regression problem. And why, when a fancier model fails to beat it, you know the fancier model is probably overfitting.

11.3.12 Student Questions and Answers

Q:We have a linear equation like

Y = 2 X_{1} + 3 X_{2}

. When we differentiate with respect to the variables, they disappear and we get constants. How do we equate to zero to find the local minimum?

A:You do not differentiate with respect to $X$ . You differentiate with respect to the coefficients $β$ . The error function is a function of $β_{0}, β_{1}, \dots$ — not a function of $X$ and $Y$ . Those are known from the data. You write the error as $(Y - β_{0} - β_{1} X_{1})^{2}$ and take derivatives with respect to $β_{0}$ and $β_{1}$ . The $X$ 's come along as constants during differentiation. For $\partial E / \partial β_{0}$ , you get $- 2 (Y - β_{0} - β_{1} X_{1})$ . For $\partial E / \partial β_{1}$ , you get $- 2 X_{1} (Y - β_{0} - β_{1} X_{1})$ . These are then set to zero. The unknowns are the $β$ 's, not the $X$ 's.

Q:The loss function squares the error, but the gradient formula does not have the square. In the worked example, you used the same error values in both places. Is that correct?

A:Yes. The loss function uses the squared error: $(Y^_{i} - Y_{i})^{2}$ . When you take the derivative, the square vanishes — the derivative of $x^{2}$ is $2 x$ . The factor of 2 cancels with the $\frac{1}{2}$ in the loss formula. So the gradient expression uses the raw (unsquared) error vector. At every iteration you compute two things: the loss (squared) to know how well you are doing. The gradient (unsquared) to know which direction and how far to step.

Q:Several students asked about the sign convention for the gradient — in some references it is

\frac{1}{M} X^{⊤} (Y^- Y)

, in others

\frac{1}{M} X^{⊤} (Y - Y^)

. Which is correct, and does the order matter?

A:Both produce equivalent weight updates when used consistently. Here is why: starting from $J = \frac{1}{2 M} ∥ Y - X θ ∥^{2}$ , the gradient is $\frac{1}{M} X^{⊤} (X θ - Y) = \frac{1}{M} X^{⊤} (Y^- Y)$ . Starting from the identical loss $J = \frac{1}{2 M} ∥ X θ - Y ∥^{2}$ , the gradient is also $\frac{1}{M} X^{⊤} (X θ - Y)$ . The forms $\frac{1}{M} X^{⊤} (Y^- Y)$ and $\frac{1}{M} X^{⊤} (Y - Y^)$ differ by a factor of $- 1$ . The update rule $W_{new} = W_{old} - α \nabla J$ absorbs the sign difference — the net weight change is the same. If the model is under-predicting, coefficients increase. If over-predicting, they decrease. Derive it once from first principles and pick one convention. This lecture uses $\nabla J = \frac{1}{M} X^{⊤} (Y^- Y)$ .

11.4 Batch, Mini-Batch, and Stochastic Gradient Descent

11.4.1 Symbol Registry

$B$ — batch size, the number of data points used per gradient calculation — integer, $1 \leq B \leq M$
$M$ — total number of data points in the full dataset — integer
$\nabla J_{i} (θ)$ — gradient of the loss evaluated on the $i$ -th data point — vector

11.4.2 Definitions

Why should you care?Gradient descent looks simple — compute the gradient, take a step, repeat. But "compute the gradient" means summing partial derivatives acrossallyour data. On a billion-row dataset, one gradient calculation could take hours. The batch/mini-batch/SGD spectrum is about deciding how much data to look at before each step. And that choice determines whether your training finishes in minutes or days.

Intuition — how much of the mountain can you see?The three variants map to a single analogy.

Batch gradient descentis like standing on a mountain on a perfectly clear night. You see the entire terrain — the village at the bottom, every ridge, every valley. You plan the full path in advance. You know exactly where to step. But planning takes time because you must survey the entire landscape.

Mini-batch gradient descentis like standing on a foggy mountain where you can see about 100 meters ahead. You chart your path for the visible stretch, walk it, then reassess from the new position. You cannot plan the entire route, but you have enough visibility to avoid erratic turns.

Stochastic gradient descent (SGD)is like standing on a very dark, very foggy mountain. You can barely see your immediate next step. You take that step, reassess, take another, reassess again. Each step is based on very limited information. The path is noisy — it zigzags — but each individual step is cheap to compute.

The three variants of gradient descent differ in how many data points they use to compute each gradient step:

Batch gradient descentuses all $M$ data points to compute the gradient at every step. The update is:

$θ_{new} = θ_{old} - α \cdot \frac{1}{M} i = 1 \sum M \nabla J_{i} (θ)$

Mini-batch gradient descentuses a subset of $B$ data points (where $1 < B < M$ ) per step:

$θ_{new} = θ_{old} - α \cdot \frac{1}{B} i = 1 \sum B \nabla J_{i} (θ)$

Stochastic gradient descent (SGD)uses exactly one data point per step ( $B = 1$ ):

$θ_{new} = θ_{old} - α \cdot \nabla J_{i} (θ)$

The only thing that changes across these variants is the number of data points inside the summation that computes the gradient. The update rule itself — step opposite the estimated gradient — is identical.

11.4.3 Analogies — Visibility on a Foggy Mountain

Another vivid analogy for SGD: it is like a drunk person stumbling down a hillside. The general direction is downhill, but the path is full of random deviations. Batch and mini-batch take more deliberate, evenly-spaced paths. The drunkard sometimes steps sideways, sometimes even slightly uphill — but averaged over many steps, the net movement is downhill.

11.4.4 Practical Comparisons

Speed per iteration:SGD is fastest per step (one data point). Mini-batch is moderate. Batch is slowest (all data points).

Total convergence time:SGD often reaches a usable solution fastest despite the noisy path because each step is so cheap. Batch takes the fewest total steps but each step is expensive.

Path smoothness:Batch produces a smooth, direct path toward the minimum. Mini-batch produces a somewhat bumpy but still directed path. SGD produces a very noisy, zigzag path.

The noisy path of SGD can actually be anadvantage. The noise sometimes helps the algorithm bounce out of shallow local minima. Batch gradient descent would get trapped in those same minima. This is one reason SGD (and mini-batch SGD) is preferred in deep learning — the noise acts as a built-in escape mechanism.

Classification example (logistic regression):Consider a linear decision boundary between two classes (blue and red points). Batch uses all points for every gradient computation — every data point contributes an update arrow. Mini-batch highlights only a subset. SGD uses a single data point per update — the boundary adjusts based on one point at a time. The final boundary converges, but the SGD path to get there involves more wandering.

11.4.5 Worked Example — Mini-Batch on Salary Data

Return to the salary dataset from section 11.3 with $M = 4$ data points. Use mini-batch with $B = 2$ , starting from $θ = [0, 1]^{⊤}$ and $α = 0.1$ .

Mini-batch 1 (first two data points):Ages 22 and 26, salaries 44 and 52.

$X_{batch} = [112226], Y_{batch} = [4452]$

Predictions: $Y^= [2226]$ . Error: $Y^- Y = [- 22 - 26]$ .

Gradient: $\frac{1}{2} X^{⊤} (Y^- Y) = \frac{1}{2} [122126] [- 22 - 26] = \frac{1}{2} [- 48 - 22 \cdot 22 - 26 \cdot 26] = \frac{1}{2} [- 48 - 1160] = [- 24 - 580]$

Update: $θ = [01] - 0.1 [- 24 - 580] = [2.4 59.0]$

Compare to the full batch update from section 11.3: the batch gradient was $[- 28, - 804]^{⊤}$ , updating to $[2.8, 81.4]^{⊤}$ . The mini-batch gradient $[- 24, - 580]^{⊤}$ is a noisier estimate. It sees only half the data. And updates to $[2.4, 59.0]^{⊤}$ , which still moves in the right direction but with a different step size.

11.4.6 Assumptions and Scope

Scope — when each variant is appropriate.

Batch gradient descent:Use when the dataset is small (thousands of points) and fits in memory. You get the exact gradient — no noise, no variance. Convergence is smooth and deterministic. Not practical for datasets with millions of points.

Mini-batch gradient descent:The industry standard. Use for all medium-to-large datasets. Common batch sizes are 32, 64, 128, or 256 — chosen to fill GPU memory efficiently. You get a gradient estimate with moderate variance. Convergence is faster than batch in wall-clock time.

Stochastic gradient descent (SGD, $B = 1$ ):Rarely used in pure form. One data point per update means extreme gradient variance — the path is very noisy. But the extreme cheapness per step means it can process massive streaming datasets. Modern SGD variants add momentum to smooth the noise.

Key trade-off:Larger batch → better gradient estimate but more computation per step. Smaller batch → faster steps but noisier direction. The sweet spot is usually a medium batch size where GPU utilization is maximized.

11.4.7 Visual Intuition

Imagine three hikers descending the same mountain, each with a different visibility radius.

The batch hiker (clear night) walks a straight, smooth line to the bottom. Their path is a clean curve with evenly spaced footprints. Each step is slow — they survey the whole mountain before moving.

The mini-batch hiker (patchy fog) walks a mostly straight path with small wobbles. They sometimes drift slightly left or right before correcting. Footprints are closer together — steps are faster.

The SGD hiker (pitch dark) walks a chaotic, zigzagging path that weaves back and forth but trends downward. Footprints are dense and erratic. They sometimes step sideways, sometimes even slightly uphill. But because each step is instant, they cover ground quickly overall.

Takeaway: The batch hiker takes the fewest steps but wastes time surveying. The SGD hiker takes the most steps but each is instant. The mini-batch hiker balances the two.

11.4.8 Pitfalls

Pitfall 1 — Using batch gradient descent on a massive dataset.If your dataset has 10 million rows, one gradient computation sums over all 10 million. Each epoch takes forever. Use mini-batch.

Pitfall 2 — Using a batch size of 1 (pure SGD) without momentum.The gradient from a single data point can point almost anywhere. Without momentum to smooth the updates, the optimizer bounces around and may never settle near the minimum.

Pitfall 3 — Setting the batch size without considering GPU memory.If your batch size is too small, the GPU is underutilized — you pay for hardware you do not use. If too large, you run out of memory. Powers of 2 (32, 64, 128, 256) are conventional because they align with GPU hardware.

Pitfall 4 — Forgetting to shuffle data between epochs for mini-batch/SGD.If your data is sorted by label (all class A first, then all class B), each mini-batch sees only one class. The gradient is catastrophically biased. Shuffle the data before each epoch.

11.4.9 Recap and Bridge

Batch, mini-batch, and stochastic gradient descent all use the same update rule. The only difference is how many data points go into each gradient computation. More data gives a better gradient estimate but costs more time. Less data is faster but noisier. Mini-batch ( $B = 32$ to $256$ ) is the practical sweet spot in modern machine learning. The noise from small batches can help escape shallow local minima.

Next, we look at the learning rate — the multiplier $α$ that controls step size. Choosing it poorly can make the difference between convergence in seconds and divergence to infinity.

11.4.10 Real-World and Domain Connection

In production deep learning, pure batch gradient descent is almost never used on large datasets. The compute cost of processing millions of examples per update is prohibitive. Mini-batch is the standard — frameworks like PyTorch and TensorFlow have built-inDataLoaderclasses that handle batching and shuffling automatically.

In distributed training across multiple GPUs. Machines, the batch size is scaled up proportionally (e.g., 256 per GPU × 8 GPUs = effective batch size of 2048). This requires adjusting the learning rate accordingly. The "linear scaling rule" says: double the batch size, double the learning rate. The principle is the same: each worker computes a gradient on its mini-batch. The gradients are averaged across workers before the update.

Pure SGD (batch size 1) is uncommon in production — too noisy and underutilizes hardware. However, it finds use in online learning scenarios where data arrives as a continuous stream. The model must update continuously (e.g., ad click prediction, recommendation systems with live user feedback).

11.4.11 Student Questions and Answers

No student questions were asked specifically about the batch/mini-batch/SGD comparison during this session.

11.5 Learning Rate and Adaptive Methods

11.5.1 Symbol Registry

$α_{0}$ — initial learning rate at epoch 0 — small positive scalar, typically 0.1 or 0.01
$T$ — epoch number — non-negative integer, $T = 0, 1, 2, \dots$
$K$ — decay rate (breaking parameter), controls how fast $α$ shrinks — positive scalar

11.5.2 The Role of Learning Rate

Why should you care?The learning rate

α

is the single most important hyperparameter in gradient descent. Set it too small and your model trains for hours with no progress. Set it too large and your loss explodes to infinity in three steps. There is no "correct" value written on the side of the box. You must choose it, and choosing well is the difference between a working model and a broken one.

The learning rate $α$ controls how large each step is. It sits in the update rule as the multiplier on the gradient:

$X_{n + 1} = X_{n} - α \nabla f (X_{n})$

The learning rate is usually chosen between 0 and 1, with common defaults like 0.001 or 0.01. The choice of $α$ dramatically affects how gradient descent behaves.

Intuition — Goldilocks and the three step sizes.Think of gradient descent as walking down a dark staircase. Each step is

α

times the slope you feel underfoot. If you take tiny shuffles (

α

too small), you will eventually reach the bottom, but it will take a thousand steps. If you take giant leaps (

α

too large), you jump over entire flights of stairs. Land somewhere random — maybe even higher than where you started. The right step size lets you descend steadily without overshooting.

11.5.3 Small vs Large Learning Rates

Too small ( $α = 0.0001$ ):The algorithm takes tiny baby steps. It may take an extremely large number of iterations to reach the minimum. In a fixed number of iterations, it may not converge at all — it simply runs out of steps before getting close.

Moderate ( $α = 0.01$ ):The algorithm converges steadily and reaches near the minimum in a reasonable number of steps.

Large ( $α = 0.9$ ):The algorithm takes large steps. It may converge quickly or may oscillate — bouncing back and forth between opposite sides of the valley without settling.

Too large ( $α = 1.1$ or higher):The updates overshoot the minimum. Each step goes past the bottom and up the other side, potentially going farther from the minimum rather than closer. The loss candiverge— it can explode to very large values rather than decrease. The algorithm effectively climbs the function rather than descending it.

The problem with a constant learning rate becomes clear when you consider the shape of the loss surface. When you are far from the minimum, the gradient is large — you naturally take large steps. When you are near the minimum, the gradient is small — you take small steps. But if the gradient becomes too small too early, you might stall before reaching the true minimum.

There is a deeper problem: the terrain itself varies. On a flat plateau, the gradient is near zero and progress stalls regardless of $α$ . On a steep cliff, the gradient is enormous and even a moderate $α$ causes overshoot. A single constant $α$ cannot handle both flat regions and cliffs optimally.

11.5.4 Decay Methods for Adaptive Learning Rate

To address the constant learning rate problem,decay methodsadjust $α$ over time. The idea: start with a larger learning rate for fast early progress, then gradually shrink it as you near the minimum. You do not overshoot.

One simple decay schedule is:

$α = \frac{α _{0}}{1 + K T}$

Here:

$α_{0}$ — the initial learning rate at epoch 0 (e.g., 0.1)
$T$ — the epoch number, starting at $T = 0$ . One epoch is one complete forward pass and backward pass through the dataset. After the first epoch, $T = 1$ ; after the second, $T = 2$ , and so on.
$K$ — thedecay rate(sometimes called the breaking parameter), a positive scalar controlling how aggressively $α$ shrinks.
The "+ 1" in the denominator prevents division by zero when $T = 0$ .

With $K$ large (e.g., 100): $α$ shrinks sharply — from 0.1 at $T = 0$ to approximately $0.1/101 \approx 0.001$ after just one epoch. With $K$ small (e.g., 0.01): $α$ decreases very slowly, staying near 0.1 for many epochs.

This type of decay is aheuristic— a rule of thumb, not derived from first principles. It works reasonably well in practice, but there is no mathematical guarantee that it chooses the optimal step size at each epoch. It simply enforces the intuition that you should take smaller steps as you get closer to the minimum.

Decay schedule numerical example.Start with $α_{0} = 0.1$ . Use $K = 100$ .

At epoch $T = 0$ : $α = \frac{0.1}{1 + 100 \cdot 0} = 0.1$
At epoch $T = 1$ : $α = \frac{0.1}{1 + 100 \cdot 1} = \frac{0.1}{101} \approx 0.001$
At epoch $T = 2$ : $α = \frac{0.1}{1 + 100 \cdot 2} = \frac{0.1}{201} \approx 0.0005$
At epoch $T = 10$ : $α = \frac{0.1}{1 + 100 \cdot 10} = \frac{0.1}{1001} \approx 0.0001$

With $K = 0.01$ (gentle decay):

At epoch $T = 100$ : $α = \frac{0.1}{1 + 0.01 \cdot 100} = \frac{0.1}{2} = 0.05$

Sense-check:A large $K$ aggressively kills the learning rate, which is useful when you need to freeze parameters quickly. A small $K$ lets the model explore for many epochs before settling. The right $K$ depends on how many total epochs you plan to run.

Notation note:The professor initially wrote an exponential variant $α = \frac{α _{0}}{1 + e ^{- K T}}$ on the board. Then corrected to the linear form $α = \frac{α _{0}}{1 + K T}$ when working the numerical example. The exponential form with $K = 100, T = 1$ gives $\frac{0.1}{1 + e ^{- 100}} \approx 0.1$ — essentially no decay. The linear form yields the demonstrated behavior of $α \approx 0.001$ after one epoch. The linear decay schedule is the intended formula for this lecture and for any exam questions on this topic.

11.5.5 Preview — Line Search and Momentum

Two important topics extend beyond basic gradient descent.

Line searchis an algorithm embedded within gradient descent that adaptively chooses $α$ at each step. Unlike decay methods (which are heuristics), line search is a proper algorithmic method. At each point, it searches along the gradient direction for the step size that gives the greatest decrease in the function value. It is a well-defined optimization subroutine.

Exam note:The exam has roughly a 10% chance of including a line search question. The next class will work through enough line search problems to ensure understanding.

Momentumis a class of algorithms that modify the gradient update to carry inertia from previous steps. The idea mimics physical momentum: a rolling ball builds up velocity and does not change direction instantly. Mathematically, the momentum update adds a fraction of the previous step to the current gradient step:

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

$X_{t + 1} = X_{t} + v_{t + 1}$

Thevelocityvector $v_{t}$ accumulates past gradients. Themomentum parameter $β$ (typically 0.9) controls how much of the past velocity is retained. In long, narrow valleys, the side-to-side gradient components cancel out while the along-valley components accumulate, accelerating convergence. On flat plateaus where gradients are small, momentum keeps the optimizer moving. On shallow local minima, momentum can help the optimizer roll through and escape.

These will be covered in a future class.

11.5.6 Assumptions and Scope

Scope — learning rate decay is a heuristic, not a guarantee.

When decay helps:When early iterations need large steps for fast progress and later iterations need small steps for fine-tuning. This is true for most convex optimization problems. The gradient naturally shrinks as you approach the minimum, and decay reinforces this behavior.

When decay hurts:If the decay is too aggressive (large $K$ ), the learning rate becomes tiny after a few epochs. Training stalls early — the model never reaches the minimum because it cannot take meaningful steps. In deep learning, overly aggressive decay can freeze a model in a poor configuration.

What decay does NOT do:It does not adapt to the local geometry of the loss surface. A flat region still gets small steps regardless of epoch number. A steep region still gets large steps. Decay only depends on time, not on where you are standing. This is why modern methods (Adam, RMSprop) adapt the learning rate per-parameter based on gradient history. But those are topics for a later course.

11.5.7 Visual Intuition

Think of the learning rate as the length of the arrow you draw from your current position. Early in training, you want a long arrow — you are far from the minimum and need to cover distance. Later, you want a short arrow — you are close and need precision.

Now picture the decay schedule as a curve. The $x$ -axis is the epoch number $T$ . The $y$ -axis is the learning rate $α$ . With $K = 0$ (no decay), the curve is a flat horizontal line at $α_{0}$ — your steps never shrink. With $K$ large, the curve plunges sharply from $α_{0}$ toward zero — your steps shrink almost immediately. With $K$ moderate, the curve decays gently. Steps shrink gradually, matching the natural shrinking of the gradient as you approach the minimum.

Takeaway: The decay curve should roughly match the natural shrinking of the gradient. If it decays too fast, you stall far from the minimum. If it decays too slow, you overshoot near the minimum.

11.5.8 Pitfalls

Pitfall 1 — Choosing the learning rate without trying a range of values.Do not guess

α = 0.001

and hope. Try powers of 10: 0.1, 0.01, 0.001, 0.0001. Plot the loss curve for each. Pick the one that descends fastest without oscillating. This is called "learning rate range test" in practice.

Pitfall 2 — Using decay without checking if it is even needed.Many problems converge fine with a constant learning rate. Adding decay adds a hyperparameter ( $K$ ) to tune unnecessarily. Try constant first; add decay only if convergence stalls.

Pitfall 3 — Setting $K$ too large.If $α$ drops from 0.1 to 0.001 after one epoch, your model effectively stops learning. The loss curve looks like a sudden flatline — training is dead, not converged.

Pitfall 4 — Confusing "large K means large update" with gradient magnitude.When the professor says "large $K$ gives a large update," he means a largechangein the learning rate value — a big jump downward. This results insmallergradient steps thereafter. The terminology is about the change in $α$ , not the size of the parameter update.

11.5.9 Recap and Bridge

The learning rate $α$ controls step size in gradient descent. Too small → slow convergence. Too large → divergence. Decay methods shrink $α$ over time using $α = α_{0} / (1 + K T)$ , trading fast early progress for precision near the minimum. But decay is a heuristic — it does not adapt to local geometry. Line search and momentum are more sophisticated approaches covered in later classes.

Next, we wrap up with convergence criteria: when do you stop running gradient descent, and how do you know you are done?

11.5.10 Real-World and Domain Connection

The learning rate is the first hyperparameter any ML practitioner tunes. In deep learning, the learning rate is typically tuned alongside the batch size. Doubling the batch size often allows doubling the learning rate (the "linear scaling rule"). Modern frameworks provide learning rate schedulers: step decay, cosine annealing, warm restarts, one-cycle policies.

In production systems, adaptive optimizers like Adam have largely replaced manual learning rate tuning. They maintain a per-parameter learning rate that adapts based on the history of gradients for that parameter. But understanding the underlying learning rate mechanics is essential: when Adam fails to converge. The first thing you check is whether the base learning rate is appropriate for your problem scale.

11.5.11 Student Questions and Answers

Q:Where do the

K

and

T

values come from? How do we choose them?

A: $T$ is the epoch number in your training loop. In a neural network, one epoch is one complete forward pass (making predictions) followed by one complete backward pass (updating weights). $T$ increments from 0 to 1 after the first epoch, then 2, 3, and so on. With every epoch, $α$ updates according to the decay formula. $K$ is a hyperparameter you choose. If you set $K$ large, $α$ decays quickly. If you set $K$ small, $α$ decays slowly. In practice, $K$ is usually kept small to produce gentle, gradual updates.

Q:You said that when

K

is large, the update is large. But

K

is in the denominator — so shouldn't large

K

make the update small?

A:The terminology: moving $α$ from 0.1 to 0.001 in one step is a "large update" to the learningrate— not a large gradient step. You are skipping many intermediate values of $α$ . Moving from 0.1 to 0.11 in one step would be a "small update" to the learning rate. So large $K$ means the learning rate itself receives a large change in value (a big jump downward). This results in very small gradient steps thereafter.

Q:When the learning rate is too small, the model may not reach the minimum in 100 iterations. How do we decide the minimum number of iterations?

A:You track the loss value across iterations. Suppose the loss starts at 800. Then it drops to 700, 400, 200, 100, 80, 78. Then it stops improving — it hovers around 77. You need enough iterations to see this plateau. If you stop after 4 iterations (loss still dropping from 400 to 200), you have not given the algorithm enough time. Increase iterations until the loss stabilizes. The decrease from one iteration to the next is very small, and it stays small for several iterations in a row. When you see this flattening behavior, you can stop. In practice, you monitor both the loss value and the gradient magnitude. When either stabilizes near zero, training is done. Many ML libraries print the loss at each epoch when verbose mode is enabled.

11.6 Convergence, Stopping, and Practical Considerations

11.6.1 Symbol Registry

$∥\nabla J (θ) ∥$ — Euclidean norm (magnitude) of the gradient — scalar, used as stopping criterion
$σ (z) = \frac{1}{1 + e ^{- z}}$ — the sigmoid (logistic) activation function — scalar output in $(0, 1)$
$W_{1}, W_{2}$ — weight matrices connecting layers in a neural network — matrices of appropriate dimensions

11.6.2 Stopping Criteria

Why should you care?Gradient descent does not have a built-in "I'm done" signal. It just keeps stepping. You need to decide when to stop, and stopping too early means a worse model. Stopping too late wastes time. The stopping criteria you choose directly affect the quality of your final model and the cost of training it.

Gradient descent stops when the gradient is essentially zero. At that point, the update $- α \nabla J (θ)$ is also zero — no further movement occurs. You cannot tell from the gradient alone whether you are at a local minimum, a global minimum, or asaddle point. A saddle point has zero gradient, but the surface curves upward in some directions and downward in others. All three have zero gradient.

In practice, you set atolerance— a small threshold like $1 0^{- 6}$ . When $∥\nabla J (θ) ∥$ falls below this threshold for several consecutive iterations, training terminates. The model has converged.

You can also monitor the loss directly. When the loss stops decreasing meaningfully, you stop. The change from one epoch to the next is below a threshold, and it stays low for several epochs in a row. This is often easier to interpret than the gradient magnitude. The loss is a single number with a direct interpretation: how wrong your predictions are.

11.6.3 Non-Convex Surfaces and Restart Strategies

When the loss surface is not convex, gradient descent can land in local minima. The practical workaround: restart training from different random initializations of the weights.

If you train the same model from ten different random starting points. The algorithm may land at the same loss value every time. That value is likely the global minimum — or at least a very good local minimum, effectively as good. If different initializations land at different loss values, you take the best one.

Intuition — trying different doors into the same building.Imagine a building with many entrances, each leading to a different room. You want the room with the lowest floor. You cannot see inside from the outside. The only way to know is to enter through ten different doors, walk to the lowest point inside each room, and compare. The room with the lowest bottom floor is your best bet. This is the restart strategy — each random weight initialization is a different door into the loss landscape.

This is not a guarantee. On highly complex surfaces (like those of deep neural networks), the global minimum may be unreachable from many starting points. But modern optimizers that incorporate momentum, adaptive learning rates, and other tricks significantly improve the odds of finding good minima. You will almost never use vanilla gradient descent in production deep learning.

11.6.4 Neural Network Gradient Descent Preview

A preview of how gradient descent works inside a neural network with one hidden layer:

Input: $X_{1} = 0.5$ , $X_{2} = 1.0$ — two features fed into the network.
Weights:Randomly initialized weight matrices $W_{1}$ (input to hidden) and $W_{2}$ (hidden to output).
Forward pass:Multiply the input vector $X$ by $W_{1}$ and add bias. This gives the raw hidden layer values $Z_{1}$ and $Z_{2}$ .
Activation:Apply the sigmoid function $σ (z) = 1/ (1 + e^{- z})$ to each hidden value. The hidden activations become, for example, 0.663 and 0.679 — squashed into $(0, 1)$ .
Output layer:Multiply hidden activations by $W_{2}$ , add bias. Get a raw output (e.g., 1.205).
Final activation:Apply sigmoid again. Get predicted output (e.g., 0.769).
Loss:Compare to the true target (e.g., 1.0). Compute the squared error.
Backward pass:Compute gradients of the loss with respect to $W_{2}$ , then $W_{1}$ , using the chain rule. Update weights using gradient descent.

This forward-backward cycle is one epoch. Thechain ruledistributes the error signal backward through the network. The gradient of the loss with respect to $W_{1}$ depends on $W_{2}$ , the activation derivatives, and the input $X$ . But at every single weight, the update is still:

$W_{new} = W_{old} - α \cdot \frac{\partial Loss}{\partial W}$

In modern deep learning frameworks (PyTorch, TensorFlow), this entire process is automated throughautomatic differentiation(autograd). You define the forward pass, and the framework computes all gradients for you. But understanding the underlying mechanics. That it is still gradient descent at every layer. Is essential for debugging when training goes wrong (vanishing gradients, exploding gradients, dead neurons).

11.6.5 Assumptions and Scope

Scope — convergence criteria and their limits.

Gradient tolerance:When $∥\nabla J ∥ < 1 0^{- 6}$ , the algorithm has found a stationary point. But a stationary point could be a local minimum, global minimum, or saddle point. The gradient criterion alone cannot distinguish between them.

Loss tolerance:When the loss change between epochs is below a threshold, training has plateaued. But a plateau does not mean the global minimum. It could be a flat region, a saddle point, or a local minimum. Loss monitoring is easy to implement and interpret, but it does not guarantee optimality.

Early stopping:A related technique where you stop training when the validation loss stops improving, even if the training loss is still dropping. This prevents overfitting — the model is memorizing noise in the training data rather than learning generalizable patterns. Early stopping is a regularization technique, not a convergence criterion.

Saddle point problem:In high-dimensional spaces (hundreds of parameters), saddle points are far more common than local minima. The gradient is zero at a saddle point. The gradient tolerance criterion would stop training — but there are downhill directions available. This is why momentum and adaptive methods are essential in deep learning: they carry inertia through saddle points.

11.6.6 Visual Intuition

Picture a 3D loss surface with a saddle point. It looks like a horse saddle or a Pringles chip — curving upward along one axis and downward along the perpendicular axis. If gradient descent lands exactly on the saddle point, the gradient is zero. Training stops, even though you could slide downhill along the downward-curving direction.

Now picture the loss curve over epochs: the $x$ -axis is epoch number, the $y$ -axis is the loss value. A healthy training curve drops sharply at first, then gradually flattens into a plateau. The stopping point is where the plateau begins — the curve has been flat for several epochs. If the curve is still dropping significantly, you have not converged yet. If the curve is flat. The loss is still high (e.g., 400 instead of near 0), you converged to a poor local minimum — try different initializations.

Takeaway: The loss curve over epochs is your dashboard. A steep drop followed by a flat plateau signals convergence. A flat plateau with high loss signals a bad local minimum. No flat plateau at all means you need more epochs.

11.6.7 Pitfalls

Pitfall 1 — Stopping as soon as the loss stops decreasing for one epoch.The loss can plateau briefly and then resume decreasing. Wait for the plateau to persist across several epochs before declaring convergence. A common heuristic: stop when validation loss does not improve for 5–10 consecutive epochs.

Pitfall 2 — Assuming zero gradient means global minimum.At a saddle point, the gradient is zero but there are directions of descent. Dimensionality makes this worse — in a 1000-dimensional space, a saddle point has roughly 500 upward curvatures and 500 downward curvatures. Gradient descent can stop here while still far from any minimum.

Pitfall 3 — Using training loss alone to decide convergence.The training loss always decreases (for convex problems with appropriate $α$ ). But decreasing training loss does not mean the model is improving — it could be overfitting. Always monitor validation loss alongside training loss.

Pitfall 4 — Relying on manual inspection for every run.In production, you automate convergence checks. The framework compares $∥\nabla J ∥$ or loss change to a threshold. If you are manually squinting at loss curves for every experiment, you are wasting time. Build the check into your training loop.

11.6.8 Recap and Bridge

Gradient descent stops when the gradient magnitude or loss change falls below a tolerance for several consecutive epochs. A stationary point (zero gradient) could be a global minimum, a local minimum. A saddle point — you need additional checks (multiple restarts, Hessian analysis) to know which. The loss curve over epochs is your primary diagnostic tool for assessing convergence quality.

This concludes the core lecture material on gradient descent. The algorithm you have studied — $X_{n + 1} = X_{n} - α \nabla f (X_{n})$ — is the foundation underneath every modern deep learning system. Every optimizer you will encounter (Adam, RMSprop. SGD with momentum) is a variation on this single update rule, enhanced with adaptive step sizes and inertia.

11.6.9 Real-World and Domain Connection

In production ML pipelines, convergence monitoring is automated. Training scripts log loss and gradient norm at each epoch to dashboards (TensorBoard, Weights & Biases). If the loss diverges, the run is killed and flagged. If the loss plateaus too early, the learning rate is adjusted and the run is restarted. These checks are not optional. When training a model costs thousands of dollars in cloud compute. You cannot afford to discover at the end that the loss diverged in epoch 3.

In scientific computing, gradient descent (and its constrained cousin. Projected gradient descent) solves inverse problems: given measurements, what parameters of a physical model best explain the data? Seismic imaging, medical CT reconstruction, climate model calibration. All use gradient-based optimization with carefully chosen convergence criteria because the stakes (a misdiagnosed patient, a missed oil reservoir) are high.

11.6.10 Student Questions and Answers

Q:The water-through-sink analogy — is multidimensional gradient descent like how water flows down a sink?

A:Yes. Water going down a sink follows a path determined by the gradient of the surface it flows over. The water always moves in the direction of steepest descent. Lightning strikes also follow gradient-descent-like paths — the electrical discharge finds the path of least resistance, which is mathematically similar. Entropy maximization in gases released from compression also follows gradient principles. Gas particles move in directions that maximize entropy. The gradient of entropy determines the direction each particle takes. These are all examples ofnatural optimizers— physical systems that naturally follow gradient-based paths to reach equilibrium.

Q:In the interactive visualization, a blue ball sits on a red loss surface. A red indicator line shows the gradient. Why does this line get shorter as the ball approaches the minimum?

A:The length of the red line represents themagnitudeof the gradient $∥\nabla f ∥$ . When the ball is high on the surface, the slope is steep. The gradient is large, so the red line is long. As the ball descends and approaches a flat region near the minimum, the slope approaches zero. The gradient magnitude shrinks. The red line shortens accordingly. At the exact minimum, the gradient is zero and the red line disappears — no further movement occurs. This is a direct visual representation of the convergence criterion: training stops when the red line (gradient magnitude) becomes too short to matter.

Exam Guidance Summary

Questions on gradient descent basics, batch/mini-batch/SGD, or learning rate are conceptually important for your ML and neural network understanding. But they are difficult to frame as exam questions. Conceptual questions on these topics are unlikely.
The topic most likely to appear on the exam isline search— an algorithmic method for adaptively choosing the learning rate within gradient descent. There is roughly a 10% chance of a line search question.
The next class will work through enough line search problems to ensure you are prepared.
Decay methods (heuristic learning rate schedules) are also potential exam material. But line search, being an actual algorithm, is the higher-priority topic.
When doing gradient computations on an exam, showevery stepof your work:
1. Write the update formula: $X_{n + 1} = X_{n} - α \nabla f (X_{n})$ .
2. Substitute the specific function and its derivative.
3. Compute intermediate values explicitly.
4. State the final result.
5. A table format for iterative updates (columns: iteration, $X_{n}$ , $f (X_{n})$ , $f^{'} (X_{n})$ , $X_{n + 1}$ ) often grades better.
Write all assumptions explicitly: the learning rate $α$ , the initial weights, the batch size, the number of iterations.

Exam note:Line search is the most examinable topic from this lecture (10% chance). Be ready to describe the algorithm and work through a numerical example from the next class.

Key Industry Applications

Gradient descent is the foundational optimizer behind nearly all modern machine learning. This includes linear regression, logistic regression, neural networks, and deep learning. Every weight update in every training loop is a gradient descent step — or a descendant of one.
Batch gradient descentis rarely used in production on large datasets due to computational cost. Computing the gradient on millions of data points per step is prohibitively expensive.
Mini-batch gradient descent(with batch sizes like 32, 64, 128) is the industry standard. It balances gradient estimate quality against computational cost and fully utilizes GPU hardware.
Purestochastic gradient descent(batch size 1) is uncommon in production — too noisy and underutilizes hardware. Mini-batch strikes the practical balance.
Modern optimizers —Adam,RMSprop,SGD with momentum— build on the basic gradient descent framework. They add adaptive per-parameter learning rates and/or momentum to accelerate convergence and escape local minima. These are the workhorses of production deep learning.
Automated differentiationin frameworks like PyTorch and TensorFlow handles gradient computation, but the underlying algorithm is still gradient descent: compute the gradient, step downhill. Understanding this foundation is essential for debugging training issues like vanishing gradients, exploding gradients, and optimizer divergence.
Interactive visualization tools (such as animatedml.com) help build intuition for how gradient descent traverses different loss surfaces under different hyperparameter choices.
Theconvexity guaranteeof MSE with linear regression is a practical advantage — it makes linear regression deterministic, fast, and reproducible. That is why it remains a widely used baseline model in industry, despite its simplicity. A model that trains in milliseconds. Always converges to the same answer is invaluable as a sanity check before deploying more complex models.

MFML Lecture 11 notes · Gradient Descent

Mathematical Foundations for Machine Learning· postgraduate· 2026-07-11

Sections Breakdown

1Continuous Optimization and Gradient Descent

The update rule, its Taylor-series derivation, and why the gradient is the steepest descent direction.

2Global vs Local Minima and Convexity

Local and global minima, the Hessian, and how positive definiteness certifies convexity.

3Gradient Descent in Linear Regression

MSE loss, its gradient, a full batch worked example, and why the surface is convex.

4Batch, Mini-Batch, and Stochastic Gradient Descent

How many data points feed each gradient step, with a mini-batch worked example.

5Learning Rate and Adaptive Methods

The role of the learning rate, decay schedules, and a preview of line search and momentum.

6Convergence, Stopping, and Practical Considerations

Stopping criteria, restart strategies, and a neural-network gradient descent preview.

Postgraduate students in Machine Learning and related quantitative fields

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review. But if something doesn't make sense, go back to the full explanation in the main content.

Gradient Descent Update Rule

Must-know:The update is $X_{n + 1} = X_{n} - α \nabla f (X_{n})$ . The minus sign points downhill; it follows directly from the first-order Taylor expansion and the descent inequality $δ X \cdot f^{'} (X_{n}) < 0$ . Gradient descent only guarantees local descent, not the global minimum.

$X_{n + 1} = X_{n} - α \nabla f (X_{n})$

⚠️ Top pitfall:Assuming gradient descent finds the global minimum. It finds a stationary point — which may be a local minimum, global minimum, or saddle point. Only a strictly convex surface guarantees the global minimum.

Self-check:Why does the minus sign in the update rule guarantee the function value decreases (to first-order accuracy)?

Connects to:Convexity and the Hessian, Learning Rate and Decay, Convergence and Stopping

Local vs Global Minima and Convexity

Must-know:A convex function has exactly one global minimum. Convexity is certified by a positive semidefinite Hessian: $v^{⊤} H v \geq 0$ for all $v$ . Strict convexity (positive definite) gives a unique minimum.

$v^{⊤} H v > 0 for all non-zero v \Rightarrow strictly convex$

⚠️ Top pitfall:Assuming MSE alone makes a loss convex. Convexity comes from the linear model structure plus the squared error — neural networks with MSE are highly non-convex.

Self-check:Given $f (x, y) = x^{2} + 3 y^{2}$ , compute the Hessian and state whether the function is strictly convex.

Connects to:Gradient Descent Update Rule, Gradient Descent in Linear Regression, Convergence and Stopping

Gradient Descent in Linear Regression

Must-know:For MSE loss, the gradient is $\nabla J = \frac{1}{M} X^{⊤} (Y^- Y)$ . The MSE surface is a convex bowl, so gradient descent always reaches the global minimum. The closed form $(X^{⊤} X)^{- 1} X^{⊤} Y$ is exact but costs $O (d^{3})$ and fails at scale.

$\nabla J (θ) = \frac{1}{M} X^{⊤} (Y^- Y), Y^= X θ$

⚠️ Top pitfall:Differentiating the loss with respect to the features $X$ instead of the coefficients $θ$ . The $X$ values are fixed data; the unknowns you solve for are the $β$ coefficients.

Self-check:In the salary worked example, why did the first gradient come out as $[- 28, - 804]^{⊤}$ and what did subtracting it (times $α$ ) achieve?

Connects to:Gradient Descent Update Rule, Local vs Global Minima and Convexity, Batch, Mini-Batch, and SGD

Batch, Mini-Batch, and Stochastic Gradient Descent

Must-know:All three use the same update rule; they differ only in how many points feed each gradient. Batch uses all $M$ ; SGD uses 1; mini-batch uses $B$ (32–256 typical). Mini-batch is the industry standard; SGD noise can escape shallow local minima.

$θ_{new} = θ_{old} - α \cdot \frac{1}{B} i = 1 \sum B \nabla J_{i} (θ)$

⚠️ Top pitfall:Forgetting to shuffle data between epochs. If data is sorted by label, each mini-batch is biased and training diverges. Also, pure SGD without momentum rarely settles.

Self-check:Why does the noisy path of SGD sometimes help rather than hurt on a non-convex loss surface?

Connects to:Gradient Descent in Linear Regression, Learning Rate and Adaptive Methods, Convergence and Stopping

Learning Rate and Adaptive Methods

Must-know:The learning rate $α$ controls step size. Too small → slow; too large → divergence. Decay shrinks it over time: $α = α_{0} / (1 + K T)$ . Decay is a heuristic, not a guarantee — it ignores local geometry.

$α = \frac{α _{0}}{1 + K T}$

⚠️ Top pitfall:Misreading 'large K' as a large parameter update. Large $K$ means a large change in the learning rate value (a big drop), which yields smaller gradient steps thereafter.

Self-check:With $α_{0} = 0.1$ and $K = 100$ , what is the learning rate after one epoch, and why is that useful?

Connects to:Gradient Descent Update Rule, Batch, Mini-Batch, and SGD, Convergence and Stopping

Convergence and Stopping

Must-know:Stop when $∥\nabla J (θ) ∥$ or the loss change falls below a tolerance for several epochs. A zero gradient could be a local minimum, global minimum. Saddle point — use restarts and validation loss to tell them apart.

$∥\nabla J (θ) ∥ < 1 0^{- 6} \Rightarrow converged (stationary point)$

⚠️ Top pitfall:Stopping the moment the loss plateaus for one epoch, or trusting training loss alone. Wait for a persistent plateau and always watch validation loss to avoid overfitting and saddle-point stalls.

Self-check:Why can a zero gradient at a saddle point in 1000 dimensions still leave downhill directions available?

Connects to:Gradient Descent Update Rule, Local vs Global Minima and Convexity, Learning Rate and Adaptive Methods

Previous LectureLecture 10 · Taylor Series and Hessian-Based Optimization

Next LectureLecture 12 · Challenges of Gradient Descent and Constrained Optimization

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.