Machine Learning · AI216

Gradient Descent: Batch, Stochastic and Mini-batch

Machine Learning Study guides

Gradient descent is a generic optimization algorithm that tweaks model parameters iteratively in the direction that lowers the cost function, until it reaches a minimum.

Start with random parameter values, measure the local gradient of the cost function, and take a step downhill. The size of the step is set by the learning rate. If the learning rate is too small, convergence takes many iterations; if it is too high, you can jump across the valley and diverge. For the convex MSE cost of linear regression there are no local minima, only one global minimum, and gradient descent is guaranteed to get arbitrarily close to it given enough time and a reasonable learning rate. All features should have a similar scale or it takes much longer.

Batch gradient descent uses the whole training set at every step: slow on huge data but steady. Stochastic gradient descent (SGD) picks one random instance at every step and computes gradients on that alone: much faster per step and can train on huge sets, but the cost bounces up and down instead of settling, so final parameters are good but not optimal. The randomness helps escape local minima. Instances must be independent and identically distributed (shuffle them).

Mini-batch gradient descent computes gradients on small random sets called mini-batches, which gives hardware speed-ups and is less erratic than SGD. A learning schedule, a function that lowers the learning rate over iterations, helps SGD settle (simulated annealing is the idea behind it).

Key points

  • Step size = learning rate: too small is slow, too large diverges.
  • Batch GD: whole set per step. SGD: one instance. Mini-batch: small random sets.
  • MSE of linear regression is convex: no local minima.
  • Scale features before using gradient descent.
  • SGD final values are good but not optimal; a learning schedule helps.

Worked example

For cost J(w) = w squared and learning rate 0.1, starting at w = 4: gradient = 2w = 8, so w becomes 4 - 0.1 x 8 = 3.2, then 2.56, then 2.05, shrinking toward 0 each step.

Common questions

Why scale features for gradient descent?

With very different scales the cost bowl is elongated and the algorithm zigzags and converges slowly.

Is SGD guaranteed to reach the minimum?

No. It gets close but keeps bouncing around, unless the learning rate is gradually reduced.

Practice questions on this topic

Try these, then open the app to check your answers with explanations.

  1. If you set a high learning rate, then your system will rapidly adapt to new data, but it will also tend to quickly forget the old data
    • A. true
    • B. false
  2. SGD well suited for ............ learning
    • A. batch
    • B. online
    • C. all of them
    • D. none of them
  3. SGD is stands for ..............
    • A. Stochastic Gradient Descent
    • B. Stochastic Graded Descent
    • C. Stochastic Gradient Description
    • D. none of them
  4. SGDClassifier computes a score based on a .............. function
    • A. decision
    • B. Precision
    • C. F1-score
    • D. none of them
  5. The SGDClassifier relies on randomness during training (hence the name “stochastic”).
    • A. true
    • B. false
  6. SGD deals with training instances dependently, one at a time (which makes SGD well suited for online learning).
    • A. false
    • B. true