Why Gradient Descent Became Stochastic

A step-by-step journey from calculus-based optimization to Stochastic Gradient Descent

The post Why Gradient Descent Became Stochastic appeared first on Towards Data Science.

Introduction to Optimization

Optimization is a fundamental concept in machine learning and deep learning. It is the process of adjusting the parameters of a model to minimize the difference between the model’s predictions and the actual values. In other words, optimization is used to find the best possible solution to a problem by minimizing or maximizing a function.

One of the most widely used optimization algorithms is Gradient Descent (GD). GD is a first-order optimization algorithm that uses the gradient of the loss function to update the model’s parameters. The gradient of the loss function is computed using calculus, and it represents the direction of the steepest ascent.

Calculus-Based Optimization

Gradient Descent is based on the concept of calculus, specifically the gradient of a function. The gradient of a function is a vector that points in the direction of the steepest ascent. In the context of optimization, the gradient of the loss function is used to update the model’s parameters.

The update rule for GD is as follows:

w = w - α \* ∇L(w)

where w is the model’s parameter, α is the learning rate, and ∇L(w) is the gradient of the loss function.

The gradient of the loss function is computed using the chain rule of calculus. The chain rule is a fundamental concept in calculus that allows us to compute the derivative of a composite function.

For example, consider a simple linear regression model with one feature and one target variable. The loss function for this model is the Mean Squared Error (MSE) between the predicted values and the actual values.

The MSE loss function is as follows:

L(w) = (1/2) \* (y - (w \* x + b))^2

where y is the target variable, x is the feature, w is the model’s parameter, and b is the bias term.

The gradient of the MSE loss function is as follows:

∇L(w) = - (y - (w \* x + b)) \* x

The update rule for GD is as follows:

w = w - α \* (- (y - (w \* x + b)) \* x)

This update rule is used to update the model’s parameter w at each iteration of the GD algorithm.

Batch Gradient Descent

Batch Gradient Descent (BGD) is a variant of GD that uses the entire training dataset to compute the gradient of the loss function. BGD is also known as Full Batch Gradient Descent.

The update rule for BGD is as follows:

w = w - α \* (1/m) \* ∑[∇L(w; x(i), y(i))]

where m is the number of training examples, x(i) is the i-th feature, y(i) is the i-th target variable, and ∇L(w; x(i), y(i)) is the gradient of the loss function computed using the i-th training example.

BGD is a straightforward extension of GD, but it has some limitations. One of the main limitations of BGD is that it can be computationally expensive to compute the gradient of the loss function using the entire training dataset.

Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) is a variant of GD that uses a single training example to compute the gradient of the loss function. SGD is also known as Online Gradient Descent.

The update rule for SGD is as follows:

w = w - α \* ∇L(w; x(i), y(i))

where x(i) is the i-th feature, y(i) is the i-th target variable, and ∇L(w; x(i), y(i)) is the gradient of the loss function computed using the i-th training example.

SGD is a simple and efficient algorithm that can be used to optimize large datasets. One of the main advantages of SGD is that it can be used to update the model’s parameters in real-time, as new training examples become available.

Why Gradient Descent Became Stochastic

So, why did Gradient Descent become Stochastic? There are several reasons for this:

• Computational Efficiency: SGD is computationally more efficient than BGD. With BGD, we need to compute the gradient of the loss function using the entire training dataset, which can be time-consuming. With SGD, we only need to compute the gradient of the loss function using a single training example, which is much faster.
• Real-Time Learning: SGD allows us to update the model’s parameters in real-time, as new training examples become available. This makes it suitable for applications where the data is streaming in, such as online advertising or recommendation systems.
• Large Datasets: SGD is well-suited for large datasets. As the dataset grows, the computational cost of BGD increases, making it impractical. SGD, on the other hand, can handle large datasets with ease.
• Noise Robustness: SGD is more robust to noise in the training data. With BGD, the gradient of the loss function is computed using the entire training dataset, which can include noisy or outliers. SGD, on the other hand, uses a single training example to compute the gradient, which reduces the impact of noise.

Conclusion

In conclusion, Gradient Descent became Stochastic due to its computational efficiency, real-time learning capabilities, ability to handle large datasets, and noise robustness. SGD is a simple and efficient algorithm that has become a cornerstone of machine learning and deep learning.

While BGD is still used in some applications, SGD has become the de facto standard for many machine learning tasks. The stochastic nature of SGD allows it to handle large datasets and noisy data, making it a versatile and powerful algorithm for optimization.

As machine learning continues to evolve, it’s likely that we’ll see even more innovative applications of SGD and its variants. Whether you’re working on a simple linear regression model or a complex deep learning architecture, SGD is an essential tool to have in your toolkit.