Skip to content
Glacius
OptimizationConcept reference

Stochastic gradient descent

SGD subtracts a learning-rate-scaled sampled gradient from the current parameter.

2 min read1 figureSources & further reading
On this page 8 sections
  1. Overview
  2. Understand the idea
  3. For successive steps, carry the new parameter forward
  4. A sampled direction need not reduce the full empirical objective
  5. A closer look
  6. Key takeaway
  7. Sources & further reading
  8. Concept connections

01Understand the idea#

Stochastic gradient descent uses a randomly selected example to estimate a training direction. Its arithmetic resembles full gradient descent, but each sampled direction can disagree with the whole dataset’s gradient. This makes individual steps noisy while reducing work per step.

SGD takes a step using a randomly selected example’s gradient. Given that sampled gradient g, the arithmetic is:

θnew=θ−ηg\theta_{\mathrm{new}}=\theta-\eta g

At θ=(3,−2), sampled g=(−4,2) and rate 0.25 give an update of (4,−2.5).

Current parameter θ=(3,−2), sampled gradient (−4,2), rate .25. The displacement is (1,−.5), beginning at θ and ending at (4,−2.5). This single sampled direction need not match the full gradient.Current parameter θ=(3,−2), sampled gradient (−4,2), rate .25. The displacement is (1,−.5), beginning at θ and ending at (4,−2.5). This single sampled direction need not match the full gradient.
Figure 1Current parameter θ=(3,−2), sampled gradient (−4,2), rate .25. The displacement is (1,−.5), beginning at θ and ending at (4,−2.5). This single sampled direction need not match the full gradient.
Link to this figure ↗Download SVGDownload PNG

Starting from parameter 4 with sampled gradient 2 and rate 0.5 gives 4−0.5(2)=34-0.5(2)=3. If the next iteration supplies gradient −1-1, start from 3 and get 3−0.5(−1)=3.53-0.5(-1)=3.5. Carry the updated parameter forward, and use the gradient assigned to each iteration.

Check your reasoning

θ=(3,1)\theta=(3, 1), sampled g=(2,−2)g=(2, -2), η=0.5\eta=0.5. Find the SGD update.

  1. A(2,3)(2, 3)
  2. B(2,2)(2, 2)
  3. C(3,2)(3, 2)
Show answer and explanation
(2,2)(2, 2)

Subtract ηg\eta g: (2,2)(2, 2).

02For successive steps, carry the new parameter forward#

For successive steps, carry the new parameter forward. Each supplied gradient belongs to its specified iteration.

The gradients can differ because the example or current parameter changed; use the value supplied for that step.

Check your reasoning

Start x=2. Step1: gradient -4, rate 0.25. Step2: gradient 2, rate 0.5. Find final x.

Show answer and explanation
2

First x=3; then x=2.

03A sampled direction need not reduce the full empirical objective#

A sampled direction need not reduce the full empirical objective. It can improve one example while worsening the dataset average.

For losses (w−a)²/2 and (w+a)²/2, their average is J(w)=(w²+a²)/2. At w=0, the first example has gradient −a while the full gradient is zero.

Check your reasoning

J(w)=(w2+25)/2J(w)=(w^2+25)/2. Start w=0, sampled g=−5, rate 0.5. A report predicts lower J. Compute the new J.

Show answer and explanation
15.625

New w=2.5. J rises from 12.5 to 15.625.

04A closer look#

Uniformly sampling an example gives an unbiased estimate of the mean-loss gradient under the usual differentiability assumptions. Unbiased refers to the average over possible samples, not a promise that one sampled step reduces the full objective.

Key takeaway

Use the supplied sampled gradient at each step; one update need not reduce the full dataset objective.

  • Compute a parameter update using a supplied sampled gradient.

Sources & further reading

  1. [1]
    D2L §12.4.1, equation12.4.3 ↗D2L §12.4.1, equation12.4.3 · Article

Reference this concept

Link to this page, a section, or an individual figure.

Glacius. “Stochastic gradient descent.” Math behind ML. /learn/o-sgd