Stochastic Gradient Descent

Definition

To minimize $R_n(w)=\frac{1}{n}{\sum }_i\ell (y_i,f_w(x_i))$: gradient descent uses the full gradient, $w_{t+1}=w_t-\eta {\nabla }_w{R}_n(w_t)$. SGD picks a random $i$ and uses only its gradient.

Formula

$$w_{t+1}=w_t-\eta {\nabla }_w\ell (y_i,f_{w_t}(x_i))$$

with step size (learning rate) $\eta$.

The perceptron is SGD with $\eta =1$ on the linear loss, visiting the points in order. SGD does not pick just any minimizer of the empirical risk: it has an implicit bias, which later lectures use (stability of SGD, implicit regularization).

Appears in

• Lecture 2, recap of GD and SGD
• Lecture 2, the perceptron is SGD
• Lecture 2, implicit regularization of SGD (preview)
• Lecture 4, stability of GD
• Lecture 4, stability of SGD (convex and non-convex)

Related concepts

• Perceptron
• Empirical Risk Minimization