Can a few examples give a useful but noisy gradient?

The canonical start is $(w,b)=(0,0)$ with rate $0.1$, seed $42$, and two selected slots. Predict whether its first sampled gradient equals the full gradient $(-7/4,-1)$. The actual selected indices are $[1,0]$, so this batch gives $(-1/2,0)$ instead. Both quantities are valid; they answer different questions.

Intuition: estimate the direction using actual examples

A full-data gradient combines every example’s contribution before an update. A stochastic gradient uses one selected example, and a mini-batch gradient averages several selected slots. This changes the direction supplied to the optimizer while preserving the same full objective we ultimately care about.

Different examples can pull parameters in different directions. Their complete average can vanish even though individual gradients do not. Sampling therefore introduces variation into the path, including motion near a full-data minimum. A larger batch can reduce gradient-estimation variance under a stated sampling model; it does not make every observed update identical to the full gradient.

Definition: one loss per example, one mean objective

Use the four fixed data pairs with zero-based indices:

The model is $\widehat y_i=wx_i+b$, with parameter vector $\theta=(w,b)$. Data coordinates $x_i,y_i$ are fixed observations, not the coordinates being optimized. Define

Differentiating each residual gives its parameter gradient

A selected batch of B slots has indices $I_1,\ldots,I_B$, retains any repeats, and uses

The deterministic full batch is $[0,1,2,3]$ exactly once each. Four random draws with replacement are not automatically that full batch.

Mechanics: one generator transition per selected slot

The default mini-batch has $B=2$, start $(0,0)$, rate $1/10$, and uint32 seed $42$. Each sampled slot advances the explicit generator and maps its new state to one of four indices:

A slot can select an index already present in the same batch. The next slot continues from the updated state; it does not restart from the seed. One sampled example consumes one transition, and a two-slot mini-batch consumes two. Full-batch mode consumes no random draws and preserves the generator state.

Inspect the selected-example table alongside the selected mean gradient, full gradient, full loss, batch loss, and generator states. The update uses the selected gradient, while the displayed objective history evaluates all four examples. Replaying a stored step reveals its actual batch; replay does not draw a replacement batch.

Derivation: unbiasedness is a conditional expectation claim

Suppose that, conditional on the current parameters $\theta$, fresh indices are independent and uniform on $\{0,1,2,3\}$. Every slot then has

Linearity gives $\mathbb E[\widehat g_B\mid\theta]=\nabla L(\theta)$. Independent slots also give

This identity concerns repeated ideal draws at the same current point. It does not require an observed batch to contain distinct examples. Sampling without replacement would need a different covariance calculation; the lesson deliberately uses replacement.

The fixed-seed LCG supplies reproducibility rather than literal iid randomness. Given its seed, the entire sequence is determined. A finite run cannot prove the ideal conditional independence assumptions or an optimizer convergence theorem. Keep the sampling theorem’s assumptions separate from the deterministic implementation used to illustrate it.

For this dataset the full gradient can also be expanded directly:

Solving $\nabla L=0$ gives $(w,b)=(1,1/2)$. The Hessian is positive definite because its leading diagonal entry is positive and determinant is $5/4>0$, so this is the unique full-data global minimum.

Worked example: seed 42 selects a different direction

At $(0,0)$, compute every contribution before averaging:

Thus $L=5/4$ and $\nabla L=(-7/4,-1)$. Seed $42$ advances first to $1083814273$, selecting index 1, then to $378494188$, selecting index 0. The selected loss is $1/2$ and the selected mean gradient is

With $\eta=1/10$ the update is $(1/20,0)$, giving next parameters $(1/20,0)$. Their four residuals are $19/20,-1,-39/20,-19/10$, so the new full loss is

Continue from state $378494188$. The second batch is $[2,0]$, ending at state $955863294$. At the current point its mean gradient is $(-29/20,-1/2)$, giving next parameters $(39/200,1/20)$. Resetting the generator at each iteration would produce a different path.

A full-batch first step instead uses $(-7/4,-1)$, moves to $(7/40,1/10)$, and leaves seed state $42$ unchanged. The optimizer rate is the same, but the supplied gradient and generator transition differ.

Executable reference code

The standard-library program evaluates fixed-data residuals, losses, and gradients exactly with Fraction. Its integer generator computes the specified updated states and indices without floating-point conversion. Assertions verify both seed-42 batches, the first two parameter updates, full-batch non-advancement, repeated indices, and literal full-objective values.

It also enumerates all 16 ordered pairs under the ideal uniform two-draw model and checks that their mean gradient equals the full gradient. That is a finite expectation calculation for this dataset, separate from any claim about a seeded PRNG’s independence.

The NumPy program uses gathered design-matrix rows and vectorized residual and gradient calculations across several seeds. Slots advance sequentially, while the seed axis is vectorized. It uses the same explicit LCG rather than substituting NumPy’s random generator, then independently checks full gradients, ordered-pair expectations, and noisy movement at the optimum.

"""Exact fixed-data gradients with a reproducible uint32 LCG; sampling is with replacement."""
from fractions import Fraction as F
from itertools import product

DATA = ((-1, -1), (0, 1), (1, 2), (2, 2))
MODULUS = 2**32


def sample(state, size=2):
    if type(state) is not int or not 0 <= state < MODULUS:
        raise ValueError("Require a uint32 seed/state")
    if type(size) is not int or not 1 <= size <= 64:
        raise ValueError("Require an integer batch size in [1,64]")
    indices = []
    for _ in range(size):
        state = (1664525*state+1013904223) % MODULUS
        indices.append((4*state)//MODULUS)
    return tuple(indices), state


def batch(theta, indices):
    w, b = map(F, theta)
    indices = tuple(indices)
    if not indices or any(type(i) is not int or not 0 <= i < 4 for i in indices):
        raise ValueError("Require a nonempty sequence of data indices 0..3")
    examples = []
    for index in indices:
        x, y = DATA[index]
        residual = w*x+b-y
        examples.append({"index": index, "residual": residual,
                         "loss": residual*residual/2, "gradient": (residual*x, residual)})
    count = len(examples)
    return {
        "loss": sum(item["loss"] for item in examples)/count,
        "gradient": tuple(sum(item["gradient"][j] for item in examples)/count for j in (0, 1)),
        "examples": examples,
    }


def step(theta=(0, 0), state=42, eta=F(1, 10), batch_size=2, full_batch=False):
    theta, eta = tuple(map(F, theta)), F(eta)
    if eta <= 0 or type(state) is not int or not 0 <= state < MODULUS:
        raise ValueError("Require a positive learning rate and uint32 state")
    if type(batch_size) is not int or not 1 <= batch_size <= 64:
        raise ValueError("Require an integer batch size in [1,64]")
    if type(full_batch) is not bool:
        raise ValueError("full_batch must be a boolean")
    if full_batch:
        indices, next_state = (0, 1, 2, 3), state
    else:
        indices, next_state = sample(state, batch_size)
    selected, full = batch(theta, indices), batch(theta, (0, 1, 2, 3))
    update = tuple(-eta*g for g in selected["gradient"])
    next_theta = tuple(theta[j]+update[j] for j in (0, 1))
    return {
        "theta": theta, "indices": indices, "state_before": state, "state_after": next_state,
        "batch_loss": selected["loss"], "gradient": selected["gradient"],
        "full_loss": full["loss"], "full_gradient": full["gradient"],
        "update": update, "next_theta": next_theta,
        "next_full_loss": batch(next_theta, (0, 1, 2, 3))["loss"],
    }


def main():
    assert sample(42, 1) == ((1,), 1083814273)
    assert sample(42, 2) == ((1, 0), 378494188)
    assert sample(42, 4) == ((1, 0, 2, 0), 955863294)
    full = batch((0, 0), (0, 1, 2, 3))
    assert full["loss"] == F(5, 4) and full["gradient"] == (F(-7, 4), -1)
    first = step()
    assert first["gradient"] == (F(-1, 2), 0) and first["batch_loss"] == F(1, 2)
    assert first["next_theta"] == (F(1, 20), 0) and first["next_full_loss"] == F(1863, 1600)
    second = step(first["next_theta"], first["state_after"])
    assert second["indices"] == (2, 0) and second["state_after"] == 955863294
    assert second["gradient"] == (F(-29, 20), F(-1, 2))
    assert second["next_theta"] == (F(39, 200), F(1, 20))
    deterministic = step(full_batch=True)
    assert deterministic["indices"] == (0, 1, 2, 3) and deterministic["state_after"] == 42
    assert deterministic["next_theta"] == (F(7, 40), F(1, 10))
    assert step() == first  # Replaying the same seed and start repeats the actual batch.
    optimum = batch((1, F(1, 2)), (0, 1, 2, 3))
    assert optimum["gradient"] == (0, 0) and optimum["loss"] == F(1, 8)
    duplicate = batch((1, F(1, 2)), (0, 0))
    assert duplicate["gradient"] == (F(-1, 2), F(1, 2))
    assert batch((F(21, 20), F(9, 20)), (0, 1, 2, 3))["loss"] == F(203, 1600)
    ordered_pairs = list(product(range(4), repeat=2))
    average = tuple(sum(batch((0, 0), pair)["gradient"][j] for pair in ordered_pairs)/16 for j in (0, 1))
    assert average == full["gradient"]  # Enumerates the ideal uniform two-draw model, not a PRNG theorem.
    for invalid in (-1, MODULUS, True, 1.5):
        try:
            sample(invalid)
        except ValueError:
            pass
        else:
            raise AssertionError("Invalid uint32 seed accepted")
    print("Exact first seed-42 mini-batch frame:", first)
    print("Exact second frame:", second)
    print("Full batch uses every index once and does not advance the generator.")
    print("A fixed PRNG seed is a reproducible illustration, not proof of iid sampling.")


if __name__ == "__main__":
    main()

"""Vectorized fixed-data residuals and parallel LCG streams; no NumPy RNG substitution."""
from itertools import product
import numpy as np

DESIGN = np.array([[-1, 1], [0, 1], [1, 1], [2, 1]], dtype=np.float64)
TARGET = np.array([-1, 1, 2, 2], dtype=np.float64)


def sample(states, size=2):
    states = np.asarray(states)
    if states.ndim != 1 or not np.issubdtype(states.dtype, np.integer) or np.any(states < 0) or np.any(states >= 2**32):
        raise ValueError("Require a vector of uint32 seeds/states")
    if type(size) is not int or not 1 <= size <= 64:
        raise ValueError("Require an integer batch size in [1,64]")
    states = states.astype(np.uint64, copy=True)
    indices = np.empty((len(states), size), dtype=np.int64)
    for slot in range(size):
        states = (np.uint64(1664525)*states+np.uint64(1013904223)) % np.uint64(2**32)
        indices[:, slot] = (np.uint64(4)*states)//np.uint64(2**32)
    return indices, states


def batch(points, indices):
    points, indices = np.asarray(points, dtype=np.float64), np.asarray(indices)
    if points.ndim != 2 or points.shape[1] != 2 or not np.all(np.isfinite(points)):
        raise ValueError("Require finite parameter points of shape (n,2)")
    if indices.ndim != 2 or indices.shape[0] != len(points) or indices.shape[1] == 0:
        raise ValueError("Require a nonempty batch per point")
    if not np.issubdtype(indices.dtype, np.integer) or np.any(indices < 0) or np.any(indices >= 4):
        raise ValueError("Require data indices 0..3, retaining any repeats")
    selected = DESIGN[indices]
    residuals = np.einsum("nbi,ni->nb", selected, points)-TARGET[indices]
    losses = np.mean(residuals**2/2, axis=1)
    gradients = np.mean(residuals[..., None]*selected, axis=1)
    if not np.all(np.isfinite(losses)) or not np.all(np.isfinite(gradients)):
        raise OverflowError("Non-finite binary64 loss or gradient")
    return losses, gradients


def main():
    initial_states = np.array([42, 43, 0], dtype=np.uint64)
    indices, states = sample(initial_states)
    np.testing.assert_array_equal(indices[0], [1, 0])
    assert states[0] == 378494188 and initial_states[0] == 42
    np.testing.assert_array_equal(sample([42], 4)[0][0], [1, 0, 2, 0])
    points = np.zeros((3, 2))
    losses, gradients = batch(points, indices)
    np.testing.assert_array_equal(gradients[0], [-0.5, 0])
    points -= 0.1*gradients
    np.testing.assert_allclose(points[0], [0.05, 0], rtol=0, atol=1e-14)
    full_indices = np.broadcast_to(np.arange(4), (3, 4))
    full_losses, _ = batch(points, full_indices)
    np.testing.assert_allclose(full_losses[0], 1.164375, rtol=0, atol=1e-14)
    next_indices, states = sample(states)
    np.testing.assert_array_equal(next_indices[0], [2, 0])
    _, gradients = batch(points, next_indices)
    points -= 0.1*gradients
    np.testing.assert_allclose(points[0], [0.195, 0.05], rtol=0, atol=1e-14)
    full_losses, full_gradients = batch(np.zeros((3, 2)), full_indices)
    np.testing.assert_array_equal(full_losses, [1.25]*3)
    np.testing.assert_array_equal(full_gradients, [[-1.75, -1]]*3)
    full_next = -0.1*full_gradients  # This full-batch computation draws nothing.
    np.testing.assert_allclose(full_next[0], [0.175, 0.1], rtol=0, atol=1e-14)
    assert initial_states[0] == 42
    pairs = np.array(list(product(range(4), repeat=2)), dtype=np.int64)
    _, pair_gradients = batch(np.zeros((16, 2)), pairs)
    np.testing.assert_array_equal(pair_gradients.mean(axis=0), [-1.75, -1])
    duplicate_loss, duplicate_gradient = batch([[1, 0.5]], [[0, 0]])
    np.testing.assert_array_equal(duplicate_gradient, [[-0.5, 0.5]])
    noisy_next = np.array([[1, 0.5]])-0.1*duplicate_gradient
    np.testing.assert_allclose(batch(noisy_next, [[0, 1, 2, 3]])[0], [0.126875], rtol=0, atol=1e-14)
    print("Selected seed-42 batches:", indices[0], next_indices[0])
    print("Binary64 mini-batch iterates after two steps ≈", points)
    print("Binary64 full-batch next point ≈", full_next[0], "; RNG state unchanged.")
    print("Ideal uniform pair enumeration checks unbiasedness; fixed seeds do not prove iid behavior.")


if __name__ == "__main__":
    main()

Explore: reproduce a path, then change its sampling

Replay the canonical path and verify its first two batches before changing anything. Switch to full batch and confirm that the selected indices are always $[0,1,2,3]$ and the generator state does not advance. Switch to one sampled example: the first index uses the same stream, but subsequent iteration boundaries occur after a different number of draws.

Keep the start and rate fixed while changing the seed. The full gradient at that initial point stays fixed; the selected gradient and path can change. Increase mini-batch size to four and inspect repeats. Seed 42 begins $[1,0,2,0]$, omitting index 3, so this sampled four-slot batch is still not the full batch.

At the full-data optimum $(1,1/2)$, individual residuals are $1/2,-1/2,-1/2,1/2$. As a repeat example, two slots selecting $[0,0]$ have mean gradient $(-1/2,1/2)$. A rate $1/10$ moves to $(21/20,9/20)$ and raises full loss from $1/8=200/1600$ to $203/1600$. A fixed-rate sampled update need not stop at the exact full minimum.

Common mistakes and counterexamples

Unbiased does not mean every observed estimate equals its target. The first canonical selected gradient already differs from the full one. More draws can reduce estimation variance under the ideal assumptions, while a particular observed batch can still point away from a full-data minimum.

Do not remove duplicate indices or divide by the number of distinct examples. Both would change the requested with-replacement average. Do not call a sampled size-four batch a full batch. Do not reseed each slot or iteration unless deliberately teaching a different deterministic process.

Numerical considerations

The uint32 transitions and their four index bins are exact integer operations. The standard-library reference uses a floor-equivalent integer quotient, preserving the updated-state convention. Residual, loss, and gradient trajectories in the stage and NumPy reference use binary64 approximations and are labeled accordingly.

Summation and division can introduce rounding even with a tiny fixed dataset. On larger data, residual magnitude and feature scale can amplify it. Separate genuine batch variation from numerical error and display rounding; a jagged path is not evidence that every source of variation is stochastic.

A seed is only part of a reproducibility record. Retain current parameters, generator state, draw order, batch size, sampling mode, objective normalization, and optimizer settings. Switching from mini to full changes how many draws occur; reverse replay must select saved states rather than advance the stream again.

Engineering and ML connections

Least squares supplies the fixed-data objective, and expectation explains why a uniformly selected contribution has the full average as its mean. Covariance describes how independent averaging reduces variability. Those links depend on the stated sampling model, not on the appearance of a particular path.

A small batch uses fewer example-gradient evaluations per update, while a larger batch carries more information about the full mean. Comparing algorithms therefore requires counting work as well as steps. Momentum can filter a sampled gradient history, and Adam retains both signed and squared-gradient averages. Neither memory mechanism makes conditional sampling assumptions automatic or supplies a global convergence guarantee.

Exercises

Use zero-based indices, preserve repeated slots, and distinguish batch values from full-data values. State the ideal probability assumptions separately from the seeded demonstration.

Summary and checkpoints

A sampled update averages the actual selected example gradients, with repeats, while the full objective remains the mean of all four losses. Check that you can reconstruct seed 42’s batches, recover full gradient $(-7/4,-1)$ and selected gradient $(-1/2,0)$ at the origin, and explain movement at a full-data optimum. Reproducible finite paths illustrate sampling; unbiasedness and variance reduction require their ideal conditional assumptions.