SECTION 03 / 4

Stochastic and Mini-Batch Gradient Descent

On this page 8 headings

BUILD INTUITION WITH NUMBERS

Count actual parameter updates

There are 10 training examples and 2 epochs. For mini-batches of 4, keep the final partial batch rather than dropping it.

Batch gradient descent updates once per epoch.
$2\times1=2\text{ updates}$
SGD updates once per example.
$2\times10=20\text{ updates}$
Mini-batch sizes are 4, 4 and 2, so there are three updates per epoch.
$\left\lceil\frac{10}{4}\right\rceil=3,\qquad2\times3=6\text{ updates}$

What changed? An epoch is a pass through the dataset; an update is a parameter change. The last partial batch matters when the dataset size is not divisible by the batch size.

Quick check: With batch size 4, how many updates would one epoch over 12 examples take?

3 updates, now with no partial batch.

Swipe long formulas, tables or code sideways to see the rest.

Start here With a million training examples, plain gradient descent does a million calculations just to take one step. That is very slow. Stochastic gradient descent updates after every single example; mini-batch gradient descent updates after a small group. This page explains the trade-off: speed versus noisy steps.

1. Batch (vanilla) gradient descent

def do_gradient_descent():
    w, b, eta, max_epochs = -2, -2, 1.0, 1000
    for i in range(max_epochs):
        dw, db = 0, 0
        for x, y in zip(X, Y):          # go over ALL the data
            dw += grad_w(x, w, b, y)
            db += grad_b(x, w, b, y)
        w = w - eta * dw                 # then update ONCE
        b = b - eta * db

The algorithm goes over the entire data once before updating the parameters.

Why? Because this sum is the true gradient of the loss (the loss is the sum of the losses of all points). No approximation. So the theory holds: each step is guaranteed to decrease the loss (for a small enough $\eta$ ).

The flip side: with a million points, one update needs a million gradient calculations. Very slow.

2. Stochastic gradient descent (SGD)

def do_stochastic_gradient_descent():
    w, b, eta, max_epochs = -2, -2, 1.0, 1000
    for i in range(max_epochs):
        for x, y in zip(X, Y):
            dw = grad_w(x, w, b, y)      # gradient of ONE point
            db = grad_b(x, w, b, y)
            w = w - eta * dw             # update immediately
            b = b - eta * db

The algorithm updates the parameters for every single data point. With a million points, that is a million updates per pass.

Two words to know:

1 epoch $=$ one pass over the entire data
1 step $=$ one update of the parameters

The flip side: it is an approximate (stochastic $=$ random-ish) gradient. We estimate the total gradient from one data point — almost like tossing a coin once and estimating P(heads). There is no guarantee that each step decreases the loss.

3. Why SGD oscillates

SGD makes greedy decisions. Each point pushes the parameters in the direction best for itself, without knowing how this affects the other points. An update that is good for one point may hurt others — it’s almost as if the data points are competing with each other. Result: many oscillations.

Everyday example A class decides where to go for a trip. If the teacher changes the plan after each single student’s opinion, the plan keeps flip-flopping. If she asks a group of 25 students each time, the plan changes more steadily.

4. Mini-batch gradient descent

Improve the estimate: update after seeing B points (a mini-batch), not 1.

def do_minibatch_stochastic_gradient_descent():
    w, b, eta, max_epochs = -2, -2, 1.0, 500
    mini_batch_size = 25
    for i in range(max_epochs):
        dw, db, num_points_seen = 0, 0, 0
        for x, y in zip(X, Y):
            dw += grad_w(x, w, b, y)
            db += grad_b(x, w, b, y)
            num_points_seen += 1
            if num_points_seen % mini_batch_size == 0:
                w = w - eta * dw         # update after every 25 points
                b = b - eta * db
                dw, db = 0, 0            # reset for the next batch

Coin-toss analogy: one toss gives a wild guess; 25 tosses give a steadier guess; the matching paths are noisy vs calmer — More points per estimate → better gradient estimate → fewer oscillations.

With $k = 25$ , the oscillations reduce to a good extent. Why? The gradient estimate is better — like tossing the coin 25 times to estimate P(heads). The higher the batch size, the more accurate the estimate.

But some oscillations always remain, as long as we use an approximate gradient instead of the true one.

5. Steps per epoch

$N =$ number of data points, $B =$ mini-batch size.

Table: batch GD takes 1 step per epoch, SGD takes N steps, mini-batch takes N divided by B steps — How many parameter updates happen in one full pass over the data.

Algorithm	Steps in 1 epoch
Vanilla (batch) gradient descent	1
Stochastic gradient descent	N
Mini-batch gradient descent	N / B

Lecture example — numbers $N = 1000$ points, $B = 25$ . Batch GD: 1 step per epoch. SGD: 1000 steps per epoch. Mini-batch: $1000 / 25 =$ 40 steps per epoch.

6. Stochastic versions of momentum and NAG

We can also make stochastic (and mini-batch) versions of momentum and NAG — just compute the gradient from one point (or one mini-batch) at a time.

Lecture example — stochastic momentum vs NAG SGD with momentum ( $\beta = 0.5$ , green) and SGD with $NAG$ (β = 0.85, blue) both oscillate, but NAG still takes shorter U-turns than momentum. Both are much faster than plain SGD: after 500 steps, plain SGD (black) still has a very high error, while NAG and momentum are close to convergence.

The mini-batch versions of momentum and NAG are left as an exercise in the lecture — they follow the same pattern.

In one line: Batch GD uses all points per update (exact but slow), SGD uses one (fast but noisy), and mini-batch uses B points (a balance) — giving 1, N and N/B steps per epoch.

Exam words: batch gradient descent, stochastic gradient descent, mini-batch, epoch, step, true gradient, approximate gradient, greedy updates, oscillations, batch size, steps per epoch $= N/B$ .

Quick check

$N = 50,000, B = 100$ . Steps per epoch for batch, SGD and mini-batch?

Batch: 1. SGD: 50,000. Mini-batch:

50,000 / 100 = 500

Which method guarantees that the loss decreases at each step (small $\eta$ )?

Batch (vanilla) gradient descent, because it uses the true gradient.

Why is SGD called “stochastic”?

It estimates the full gradient from one randomly picked point, so the estimate is random (noisy).

20 epochs of SGD on 1000 points — how many updates?

20 \times 1000 = 20,000

updates.

Will a larger mini-batch remove all oscillations?

No. It reduces them, but some remain as long as the gradient is an estimate

(B < N)

YOUR STUDY PROGRESS

Finished this section? Save your progress.

Stochastic and Mini-Batch Gradient Descent

Count actual parameter updates

1. Batch (vanilla) gradient descent #

2. Stochastic gradient descent (SGD) #

3. Why SGD oscillates #

4. Mini-batch gradient descent #

5. Steps per epoch #

6. Stochastic versions of momentum and NAG #

Quick check #