SGD, Exactly

Why the Steps Differ

The difference between the full-batch and sample updates is just exact rational arithmetic.

highlighted = computed this step

The gradients differ

The sample gradient minus the full gradient is (-1/3, -2/3). That exact difference is why the steps land in different places.

gs2−gfull=(−1/3,−2/3)g_{s2}-g_{\text{full}}=(-1/3,-2/3)
Full batch versus one sampleTwo exact updates with the same eta.per-sample gradients; full batch is the averagesampleresidualgrad agrad bs1-1-10s2-1-1-1s3000full gradient=(-2/3, -1/3)same eta=1/2, different gradient sourceupdategrad agrad bnew anew bfull batch-2/3-1/31/37/6sample s2-1-11/23/2new = old - eta*gradientone exact step only; sample is chosen before the update; NOT convergence; NOT generalization;NOT learning

The landing points differ

The sample update minus the full update is (1/6, 1/3). The difference is exact, not noise added by the renderer.

(a,b)s2−(a,b)full=(1/6,1/3)(a,b)_{s2}-(a,b)_{\text{full}}=(1/6,1/3)
Full batch versus one sampleTwo exact updates with the same eta.per-sample gradients; full batch is the averagesampleresidualgrad agrad bs1-1-10s2-1-1-1s3000full gradient=(-2/3, -1/3)same eta=1/2, different gradient sourceupdategrad agrad bnew anew bfull batch-2/3-1/31/37/6sample s2-1-11/23/2new = old - eta*gradientone exact step only; sample is chosen before the update; NOT convergence; NOT generalization;NOT learning

Summary

Full-batch uses all rows in the average. SGD uses the chosen row's gradient for this one step.

average gradient≠chosen-row gradient\text{average gradient}\ne\text{chosen-row gradient}
Full batch versus one sampleTwo exact updates with the same eta.per-sample gradients; full batch is the averagesampleresidualgrad agrad bs1-1-10s2-1-1-1s3000full gradient=(-2/3, -1/3)same eta=1/2, different gradient sourceupdategrad agrad bnew anew bfull batch-2/3-1/31/37/6sample s2-1-11/23/2new = old - eta*gradientone exact step only; sample is chosen before the update; NOT convergence; NOT generalization;NOT learning