Stochastic Gradient Descent (SGD)

As discussed previously, calculating the gradient using the entire dataset (Batch Gradient Descent) for every single parameter update becomes computationally prohibitive, especially with the massive datasets common in deep learning. Imagine computing the loss and gradients over millions of images just to take one small step! This approach also requires loading the entire dataset into memory, which is often infeasible.

Stochastic Gradient Descent (SGD) offers a practical and surprisingly effective alternative. Instead of using the full dataset, SGD approximates the gradient using only a single training example at each step.

The Mechanics of SGD

The core idea is simple:

1. Pick one training example $(x^{(i)}, y^{(i)})$ randomly from the dataset.
2. Compute the loss $L(f(x^{(i)}; W), y^{(i)})$ for this single example.
3. Calculate the gradient of the loss with respect to the parameters $W$, using only this example: $\nabla_W L(f(x^{(i)}; W), y^{(i)})$.
4. Update the parameters using this gradient: $$W \leftarrow W - \eta \nabla_W L(f(x^{(i)}; W), y^{(i)})$$ where $\eta$ is the learning rate.

This process is repeated, typically by iterating through the dataset one example at a time. An pass through the entire dataset is called an epoch. Because each update uses only one example, the gradient calculated is a "noisy" estimate of the true gradient (the one calculated over the full dataset).

Why Use a Noisy Gradient?

While using a single example introduces noise, it comes with significant advantages:

1. Computational Efficiency: Updates are extremely fast. You only need to perform forward and backward propagation for one example, drastically reducing the computation per update compared to Batch GD.
2. Frequent Updates: Parameters are updated much more frequently (N times per epoch, where N is the dataset size), leading to potentially faster convergence in terms of wall-clock time, even if more total steps might be needed.
3. Memory Efficiency: Only one training example needs to be in memory at a time for the gradient calculation.

The term "stochastic" refers to this random sampling of a single example to estimate the gradient. While each individual step might not point directly towards the minimum of the overall loss function, the average behavior over many steps tends to move the parameters in the right direction.

The SGD Update Path

The noisy nature of the gradient estimate means that the path taken by SGD towards the minimum is often erratic, zigzagging around the optimal path that Batch GD might take. However, this noise isn't always detrimental.

Comparison of optimization paths on a simple loss surface. Batch GD follows a smoother path directly towards the minimum, while SGD takes a noisier, zigzagging path due to single-example gradient estimates.

This noise can sometimes help the optimization process escape shallow local minima or saddle points, regions where the gradient is close to zero but which are not the true optimal solution. The random fluctuations might "bump" the parameters out of such areas.

However, the noise also means that SGD might struggle to converge precisely to the minimum. The parameters often continue to oscillate around the minimum even late in training. This is why techniques like reducing the learning rate over time are important when using SGD.

Data Shuffling

A standard practice when using SGD (and its variants like Mini-batch GD) is to shuffle the training dataset before each epoch. If the data were presented in a fixed, meaningful order (e.g., all examples of class A, then all examples of class B), the gradients would be highly correlated within batches of the same class, potentially biasing the updates and hindering convergence. Shuffling ensures that consecutive updates are based on more diverse examples, leading to a more representative, albeit still noisy, gradient estimate over time.

Connection to Online Learning

SGD is essentially performing "online learning" where the model learns from one example at a time as it arrives. This makes it suitable for scenarios where data streams in continuously and cannot be stored entirely.

While pure SGD (using just one example) provides the theoretical foundation, in practice, its noisy updates can make convergence slow or unstable. This leads us to Mini-batch Gradient Descent, which offers a compromise between the stability of Batch GD and the efficiency of SGD.