An Overview of Basic Gradient Descent Optimization Algorithms

Gradient Descent is a method for unconstrained mathematical optimization. It is a first-order iterative algorithm for minimizing a differentiable multivariate function.

The basic idea of the gradient descent algorithm is to take repeated steps in the opposite direction of the gradient of the function at the current point, which leads to a path that eventually minimizes the objective function. Gradient descent is one of the most popular algorithms in machine learning and artificial intelligence for minimizing the cost or loss function and optimizing neural networks.

At present, there are multiple methods that we have in gradient descent optimization to optimize advanced neural network. In this series of article, we will discuss only the below mentioned algorithms in depth for our understanding as these are most common we use in our day to day purpose.

Basic Gradient Descent Variants

There are three variants of gradient descent algorithm, which differ in how much data we use to compute the gradient of the objective function. Depending on the amount of data, we make a trade-off between the accuracy of the parameter update and time it takes to perform an update. The following are the detail discussion on these algorithm variants

Batch Gradient Descent

Vanilla gradient descent aka. batch gradient descent is an optimization algorithm used to minimize the loss/cost function by computing the gradient of the cost function w.r.t. the parameters of the entire training dataset before making one parameter update. Formula of batch gradient descent is given by,

As we need to calculate the gradient for the whole dataset to perform just one update, batch gradient descent can be very slow and is intractable for the datasets that do not fit in a memory.Batch gradient descent also does not allow us to update our model online, i.e. with new examples on-the-fly.

Pseudocode of batch gradinet descent can be written as,

For a predefined number of epochs first we compute the gradient vector of the loss function for the whole dataset w.r.t. our parameter vector. We then update our parameters in the direction of the gradients with the learning rate determining how big of an update we perform. Batch gradient descent is gauranteed to converge to the global minimum for the convex error surfaces and to a local minimum for non-convex surfaces.

When evaluating batch gradient descent algorithm for the following example as specified below,

import numpy as np
np.random.seed(42)

x = np.linspace(0, 10, 200)
y = (4 * x + 7 + np.random.normal(0, 3, 200))

def batch_gradient_descent(x, y, learning_rate=0.01, epochs=1000):
    n = len(x)
    m = 0.0
    b = 0.0
    history = {"m": [], "b": [], "loss": []}

    for _ in range(epochs):
        y_pred = m * x + b
        mse = np.mean((y - y_pred) ** 2)
        dm = (-2 / n * np.sum((y - y_pred) * x))
        db = (-2 / n * np.sum(y - y_pred))

        history["m"].append(m)
        history["b"].append(b)
        history["loss"].append(mse)

        m -= learning_rate * dm
        b -= learning_rate * db

    return m, b, history

The relationship between epoch and mean suqared error loss we get as,

Parameter trajectory by the algorithm we get as,

Stochastic Gradient Descent

Stochastic gradient descent in contrast performs parameter update for each random training example and label. Formula for stochastic gradient descent is,

Batch gradient descent performs redundant computations for large datasets, as it recomputes gradients for similar examples before each parameter update. SGD does away with this redundancy by performing one update at a time. It is therefore usually much faster and can also be used to learn online. SGD performs frequent updates with a high variance that cause the objective function to fluctuate heavily.

While batch gradient descent converges to the minimum of the basin the parameters are placed in, SGD’s fluctuation, on the one hand, enables it to jump to new and potentially better local minima. On the other hand, this ultimately complicates convergence to the exact minimum, as SGD will keep overshooting. However, it has been shown that when we slowly decrease the learning rate, SGD shows the same convergence behaviour as batch gradient descent, almost certainly converging to a local or the global minimum for non-convex and convex optimization respectively.

Pseudocode of stochastic gradient descent can be written as,

When evaluating stochastic gradient descent algorithm for the following example as specified below,

import numpy as np
np.random.seed(42)

x = np.linspace(0, 10, 200)
y = 4 * x + 7 + np.random.normal(0, 3, 200)

def stochastic_gradient_descent(x, y, learning_rate=0.01, epochs=1000):
    n = len(x)
    m = 0.0
    b = 0.0
    history = {"m": [], "b": [], "loss": []}

    for epoch in range(epochs):
        # For stochastic gradient descent, shuffling matters for random datapoints
        indices = np.random.permutation(n)
        for i in indices:
            x_i = x[i]  # Selecting random sample
            y_i = y[i]
            y_pred = m * x_i + b
            error = y_i - y_pred
            dm = -2 * error * x_i
            db = -2 * error
            m -= learning_rate * dm
            b -= learning_rate * db

        # Calculate full-dataset loss after epoch
        y_pred = m * x + b
        mse = np.mean((y - y_pred) ** 2)
        history["m"].append(m)
        history["b"].append(b)
        history["loss"].append(mse)
    return m, b, history

The relationship between epochs and mean squared error loss we get as,

Parameter trajectory by the algorithm we get as,

Mini-Batch Gradient Descent

In both batch gradient descent and stochastic gradient descent we saw the limitations. For the first we take consideration a full dataset and perform gradient computing, hence results into computationally expensive operation. For the second one, as gradient computing done for random training sample, objective function fluctuate heavily.

Mini-batch gradient descent finally takes the best of both worlds and performs an update for every mini-batch B of n training samples as,

This way, it reduces the variance of the parameter updates, which can lead to more stable convergence; and can make use of highly optimized matrix optimizations common to state-of-the-art deep learning libraries that make computing the gradient w.r.t. a mini-batch very efficient. Common mini-batch sizes range between 50 and 256, but can vary for different applications.

Pseudocode for mini-batch gradient descent can be written as,

When evaluating mini-batch gradient descent for the following example as specified below,

import numpy as np
np.random.seed(42)

x = np.linspace(0, 10, 200)
y = 4 * x + 7 + np.random.normal(0, 3, 200)

def mini_batch_gradient_descent(x, y, learning_rate=0.01, epochs=1000, batch_size=32):
    n = len(x)
    m = 0.0
    b = 0.0
    history = {"m": [], "b": [], "loss": []}

    for epoch in range(epochs):

        # Shuffle the dataset at the beginning of every epoch
        indices = np.random.permutation(n)
        x_shuffled = x[indices]  # Shuffling data
        y_shuffled = y[indices]

        # Process data in mini-batches
        for start in range(0, n, batch_size):
            end = start + batch_size
            # Selecting current mini batch
            x_batch = x_shuffled[start:end]
            y_batch = y_shuffled[start:end]
            y_pred = m * x_batch + b
            error = y_batch - y_pred
            dm = (-2 / len(x_batch) * np.sum(error * x_batch))
            db = (-2 / len(x_batch) * np.sum(error))
            m -= learning_rate * dm
            b -= learning_rate * db

        y_pred = m * x + b
        mse = np.mean((y - y_pred) ** 2)
        history["m"].append(m)
        history["b"].append(b)
        history["loss"].append(mse)

    return m, b, history

The relationship between epoch and mean squared error we get as,

Parameter trajectory by the algorithm we get as,

The End

Thank you for reading this article. In this article we covered basic gradient descent optimization algorithm variants. In the upcoming we cover the rest. You can get the source code from official github repository. Thank you once again. Please follow for more such articles,

1. Github: https://github.com/AbhinandanMandal
2. LinkedIn: https://www.linkedin.com/in/abhinandanmandal/