Stochastic Gradient Descent › The SGD Update Rule

The SGD update rule is simple. At iteration $t$, we randomly select example index $i_t$ and update:

where:

• $\boldsymbol{\theta}_{t+1}$: the updated parameters after step $t$
• $\boldsymbol{\theta}_t$: the current parameters before step $t$
• $\eta$: the learning rate (a fixed positive scalar, or one that changes according to a schedule)
• $i_t$: a uniformly random index drawn at iteration $t$
• $\nabla_{\boldsymbol{\theta}} \ell(\boldsymbol{\theta}_t; \mathbf{x}_{i_t}, y_{i_t})$: the gradient of the loss on the single selected example

In practice, we almost never sample a single example at a time. We use mini-batches.