SGD, Exactly

One Sample Gradient

A stochastic step uses one chosen sample gradient instead of the full average.

highlighted = computed this step

Choose one sample first

A stochastic step uses one selected row. Here the selected row is sample s2, chosen before the update.

chosen sample=s2\text{chosen sample}=s2
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

Its gradient

For sample s2, the residual is -1, so the sample gradient is (-1, -1).

gs2=(−1,−1)g_{s2}=(-1,-1)
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 stochastic update

With eta=1/2, the sample update changes (a,b) to (1/2, 3/2).

(a,b)sample=(1/2,3/2)(a,b)_{\text{sample}}=(1/2,3/2)
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