SGD, Exactly

Mini-Batch Gradient

A mini-batch step averages a chosen subset of sample gradients before applying the same update rule.

highlighted = computed this step

Choose a small subset

A mini-batch step uses more than one row but not all rows. Here the chosen subset is s1+s2. Their sample gradients are (-1, 0) and (-1, -1).

gs1=(−1,0),gs2=(−1,−1)g_{s1}=(-1,0),\quad g_{s2}=(-1,-1)
Mini-batch gradientAverage the chosen subset s1+s2.per-sample gradients; full batch is the averagesampleresidualgrad agrad bs1-1-10s2-1-1-1s3000full gradient=(-2/3, -1/3)same start and eta=1/2; three gradient sourcessourcerows usedgrad agrad bnew anew bfull batchs1+s2+s3-2/3-1/31/37/6mini batchs1+s2-1-1/21/25/4sample s2s2-1-11/23/2mini gradient = average of s1+s2one exact update only; no convergence claimone exact step only; sample is chosen before the update; NOT convergence; NOT generalization;NOT learning

Average those gradients

The mini-batch gradient averages just those 2 rows: (-1 + -1) over 2 gives -1, and (0 + -1) over 2 gives -1/2.

gmini=(−1,−1/2)g_{\text{mini}}=(-1,-1/2)
Mini-batch gradientAverage the chosen subset s1+s2.per-sample gradients; full batch is the averagesampleresidualgrad agrad bs1-1-10s2-1-1-1s3000full gradient=(-2/3, -1/3)same start and eta=1/2; three gradient sourcessourcerows usedgrad agrad bnew anew bfull batchs1+s2+s3-2/3-1/31/37/6mini batchs1+s2-1-1/21/25/4sample s2s2-1-11/23/2mini gradient = average of s1+s2one exact update only; no convergence claimone exact step only; sample is chosen before the update; NOT convergence; NOT generalization;NOT learning

Apply the same update rule

With eta=1/2, the mini-batch update lands at (1/2, 5/4). The full-batch landing is (1/3, 7/6), and the one-sample landing is (1/2, 3/2).

(a,b)mini=(1/2,5/4)(a,b)_{\text{mini}}=(1/2,5/4)
Mini-batch gradientAverage the chosen subset s1+s2.per-sample gradients; full batch is the averagesampleresidualgrad agrad bs1-1-10s2-1-1-1s3000full gradient=(-2/3, -1/3)same start and eta=1/2; three gradient sourcessourcerows usedgrad agrad bnew anew bfull batchs1+s2+s3-2/3-1/31/37/6mini batchs1+s2-1-1/21/25/4sample s2s2-1-11/23/2mini gradient = average of s1+s2one exact update only; no convergence claimone exact step only; sample is chosen before the update; NOT convergence; NOT generalization;NOT learning