Stochastic Gradient Descent (SGD) and Variants

While the concept of gradient descent using the entire dataset (often called Batch Gradient Descent) provides a direct path towards minimizing the loss function, it comes with a significant computational cost. Calculating the gradient requires processing every single training example before making even one update to the network's weights and biases. For datasets with millions of examples, this becomes prohibitively slow and memory-intensive.

To address this, several variants of gradient descent have been developed. These methods aim to achieve faster convergence and handle large datasets more effectively.

Stochastic Gradient Descent (SGD)

Stochastic Gradient Descent (SGD) takes the opposite approach to Batch Gradient Descent. Instead of calculating the gradient based on the entire dataset, SGD updates the parameters using the gradient computed from just one randomly selected training example at each step.

The update rule for a weight $W$ looks similar to Batch GD, but the loss and gradient $\nabla Loss$ are computed using only a single sample $(x^{(i)}, y^{(i)})$:

$W_{new} = W_{old} - \eta \nabla Loss(W_{old}; x^{(i)}, y^{(i)})$

Advantages:

• Speed: Updates are extremely fast as only one sample is processed per iteration. This allows for rapid iteration, especially early in training.
• Escaping Local Minima: The inherent noise in the updates (since each gradient is based on just one sample) can help the optimizer jump out of shallow local minima or saddle points that might trap Batch Gradient Descent.

Disadvantages:

• High Variance: The updates can be very noisy, causing the loss function to fluctuate significantly rather than smoothly decreasing. The path towards the minimum can look erratic.
• Slower Convergence (Epochs): While individual updates are fast, it might take more passes through the entire dataset (epochs) to converge compared to Batch GD, and the convergence might oscillate around the minimum without settling precisely.

Imagine navigating down a foggy mountain. Batch GD carefully surveys the entire area around it before taking a step in the best direction. SGD takes a quick look in one direction (based on one piece of information) and immediately takes a step, repeating this rapidly. It moves much faster initially but might zig-zag a lot.

Optimization paths on a loss surface. Batch GD takes a direct route. SGD's path is noisy due to single-sample updates. Mini-batch GD offers a balance.

Mini-batch Gradient Descent

Mini-batch Gradient Descent strikes a balance between the stability of Batch GD and the speed of SGD. It computes the gradient and updates the parameters based on a small, randomly selected subset (a "mini-batch") of the training data. Common batch sizes range from 32 to 512, but can vary depending on the application and hardware capabilities.

The update rule uses the average gradient over the $m$ samples in the mini-batch:

$W_{new} = W_{old} - \eta \frac{1}{m} \sum_{i=1}^{m} \nabla Loss(W_{old}; x^{(i)}, y^{(i)})$

Advantages:

• Efficiency: It uses optimized matrix operations available in libraries like NumPy, TensorFlow, and PyTorch, making gradient computation much faster than iterating one sample at a time like SGD.
• Smoother Convergence: The averaging over a mini-batch reduces the variance of the updates compared to SGD, leading to a more stable convergence path.
• State-of-the-Art: This is the most commonly used variant in practice.

Disadvantages:

• Batch Size Hyperparameter: It introduces an additional hyperparameter (the batch size $m$) that needs to be tuned.
• Still Noisy (Compared to Batch): While less noisy than SGD, the updates are still based on a subset of the data, so the loss might not decrease monotonically.

Mini-batch GD is like navigating the mountain by taking readings from a small area around you (the mini-batch) before taking a step. It's faster than surveying everything (Batch GD) and less erratic than only looking in one spot (SGD).

Advancing Updates: Momentum and Adaptive Methods

While Mini-batch GD is effective, researchers have developed more sophisticated optimization algorithms that often lead to faster convergence and better results. These typically address two main challenges: navigating difficult loss landscapes (e.g., ravines, saddle points) and choosing an appropriate learning rate.

Momentum

Imagine a ball rolling down a hill. It doesn't just stop instantly; it accumulates momentum, helping it roll over small bumps and accelerate down slopes. The Momentum update incorporates a similar idea into gradient descent. It adds a fraction $\beta$ (the momentum coefficient, typically around 0.9) of the previous update vector to the current gradient step.

Let $v_t$ be the update vector (velocity) at step $t$:

$v_t = \beta v_{t-1} + \eta \nabla Loss(W_{t-1})$ $W_t = W_{t-1} - v_t$

(Note: Sometimes the learning rate $\eta$ is factored differently, e.g., $v_t = \beta v_{t-1} + (1-\beta) \nabla Loss$, and the update is $W_t = W_{t-1} - \alpha v_t$. The core idea remains.)

Momentum helps accelerate SGD in the relevant direction and dampens oscillations, especially useful in landscapes with narrow ravines where standard gradient descent might bounce back and forth.

Adaptive Learning Rate Methods

Instead of using a single, fixed learning rate $\eta$ for all parameters, adaptive methods adjust the learning rate during training, often per parameter. They typically give smaller updates to parameters associated with frequently occurring features and larger updates to parameters associated with infrequent features.

• RMSprop (Root Mean Square Propagation): This method maintains a moving average of the squared gradients for each parameter and divides the learning rate by the square root of this average. This effectively decreases the learning rate for parameters with consistently large gradients and increases it for parameters with small gradients. Let $E[g^2]_t$ be the moving average of squared gradients at step $t$: $E[g^2]_t = \gamma E[g^2]_{t-1} + (1-\gamma) (\nabla Loss(W_{t-1}))^2$ The update rule becomes: $W_t = W_{t-1} - \frac{\eta}{\sqrt{E[g^2]_t + \epsilon}} \nabla Loss(W_{t-1})$ Here, $\gamma$ is the decay rate (e.g., 0.9) and $\epsilon$ is a small constant (e.g., $10^{-8}$) to prevent division by zero.

• Adam (Adaptive Moment Estimation): Adam is arguably one of the most popular and effective optimizers currently used. It combines the ideas of Momentum and RMSprop. It keeps track of both an exponentially decaying average of past gradients (first moment, $m_t$) and an exponentially decaying average of past squared gradients (second moment, $v_t$). $m_t = \beta_1 m_{t-1} + (1-\beta_1) \nabla Loss(W_{t-1})$ $v_t = \beta_2 v_{t-1} + (1-\beta_2) (\nabla Loss(W_{t-1}))^2$ Adam also incorporates a bias correction step, which is particularly important during the initial stages of training when the moment estimates are initialized at zero: $\hat{m}_t = \frac{m_t}{1 - \beta_1^t}$ $\hat{v}_t = \frac{v_t}{1 - \beta_2^t}$ The final parameter update uses these bias-corrected estimates: $W_t = W_{t-1} - \frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$ Common default values are $\beta_1 = 0.9$, $\beta_2 = 0.999$, and $\epsilon = 10^{-8}$. Adam often works well with minimal hyperparameter tuning, making it a good default choice for many problems.

Choosing the Right Optimizer

• Mini-batch Gradient Descent (often with Momentum): A solid baseline, computationally efficient.
• Adam: Frequently the default choice due to its robustness and good performance across various tasks. It often converges faster than basic SGD or Momentum.
• SGD: Can sometimes find better (flatter) minima that generalize better, but often requires more careful tuning of the learning rate and learning rate schedule. Might be preferred in some research settings or when computational resources for adaptive methods are limited.

The best optimizer can be problem-dependent. While Adam is a great starting point, experimenting with others like SGD with Momentum or RMSprop might yield better performance for specific network architectures or datasets. Understanding these variants allows you to make informed choices when training your neural networks, towards more practical and powerful training techniques.