Accelerating Convergence: Implementing Momentum in Gradient Descent Algorithms

Hello! Today, we will learn about a powerful technique that makes our Gradient Descent move faster, like a ball rolling down a hill. We call this "Momentum".

Momentum improves our Gradient Descent. How does it do that? Remember how a ball on top of a hill starts rolling down? If the slope is steep, the ball picks up speed, right? That's what momentum does to our Gradient Descent. It makes it move faster when the slope (our 'hill') points in the same direction over time.

Let's get down to coding! Here's a little piece of code to demonstrate the effect of momentum in a gradient descent process. We will use a gradient function, grad_func(). The weight or parameter (theta) starts at a point and moves down the slope by adjusting itself in every iteration or 'epoch':

$v := v \cdot \gamma + \alpha \cdot gradient$

$\theta := \theta - v$

Where:

• $\theta$ is the parameter vector,
• $gradient$ is the gradient of the cost function with regards to the parameters at the current parameter value,
• $\alpha$ is the learning rate,
• $v$ is the velocity vector (initialized to 0), and
• $\gamma$ is the momentum parameter (a new hyperparameter).

A higher $\gamma$ will result in a faster convergence—up to a point. However, if $\gamma$ is set too high (close to 1), the updates can become unstable and the algorithm may overshoot or even diverge. It's important to tune $\gamma$ carefully; typical values are between 0.8 and 0.99.

Here is the C++ implementation:

gradient = grad_func(theta);
v = gamma * v + learning_rate * gradient;
theta = theta - v;

We compute the gradient from the current parameters. Then, we calculate the new momentum, a combination of the old momentum, our learning rate, and the gradient. We update our parameter by subtracting this momentum from it.

Now let's visualize how momentum aids in faster convergence (which means getting to the answer quicker) in the following code snippet:

#include <vector>
#include <iostream>
#include <iomanip>
#include <matplotlibcpp.h>
namespace plt = matplotlibcpp;

double func(double x) {
    return x * x;
}

double grad_func(double x) {
    return 2 * x;
}

int main() {
    double gamma = 0.9;
    double learning_rate = 0.01;
    double v = 0;
    int epochs = 50;

    double theta_plain = 4.0;
    double theta_momentum = 4.0;

    std::vector<double> history_plain;
    std::vector<double> history_momentum;

    for (int i = 0; i < epochs; ++i) {
        history_plain.push_back(theta_plain);
        double gradient = grad_func(theta_plain);
        theta_plain = theta_plain - learning_rate * gradient;

        history_momentum.push_back(theta_momentum);
        gradient = grad_func(theta_momentum);
        v = gamma * v + learning_rate * gradient;
        theta_momentum = theta_momentum - v;
    }
}

Here, we implement plain and momentum gradients within one loop and track the history of weight changes to visualize them later.