Interactive demo · Probabilistic Machine Learning · Chapter 8

SGD, iterate averaging and variance reduction

The loss is an average of 569 terms, one per patient: L2-regularised logistic regression on two standardised features of the breast-cancer data, λ = 0.01. Stochastic gradient descent (8.54) uses the gradient of one term (or a minibatch) per step. With a constant step it reaches a noise floor whose height grows with the step; a decaying step (8.64) or the running average of the iterates (8.65) lowers it. SVRG (8.66) and SAGA (8.67) correct each stochastic gradient with a control variate whose variance vanishes at the optimum, and converge linearly with a constant step, like full-batch gradient descent but at the cost of one example per step.

Methods

Learning rate η

Schedule

Minibatch size

Epochs

Random seed

Try these

Indices are drawn with replacement from a seeded generator, the same sequence for every method. One epoch is 569 example gradients (569/B steps of size B); SVRG adds one full gradient per epoch at its snapshot; SAGA always uses one example per step and stores 569 gradients; full-batch gradient descent takes one step per epoch with the same η. Schedules: ηk = η, η/√(1 + k/100) or η/(1 + k/100), with k the step counter (per epoch for gradient descent). Adam uses β1 = 0.9, β2 = 0.999, ε = 10−8 and bias correction.

In the lecture notes