Accelerating Convergence: Implementing Momentum in Gradient Descent Algorithms

Getting Started with Momentum

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".

What's Momentum and How It Works

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.

How to Add Momentum to Gradient Descent

Compare Gradient Descents: Setup

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.

Compare Gradient Descends: Visualization

Let's visualize the comparison:

#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;
    }

    // Convert history to cost values for plotting
    std::vector<double> cost_plain, cost_momentum;
    for (double theta : history_plain) {
        cost_plain.push_back(func(theta));
    }
    for (double theta : history_momentum) {
        cost_momentum.push_back(func(theta));
    }

    // Create x-axis values (epochs)
    std::vector<double> epochs_vec;
    for (int i = 0; i < epochs; ++i) {
        epochs_vec.push_back(i);
    }

    plt::figure_size(1200, 700);
    plt::plot(epochs_vec, cost_plain, {{"label", "Gradient Descent"}});
    plt::plot(epochs_vec, cost_momentum, {{"label", "Momentum-based Gradient Descent"}});
    plt::xlabel("Epoch");
    plt::ylabel("Cost");
    plt::legend();
    plt::grid(true);
    plt::save("static/images/plot.png");
}

Here is the result:

Here, we compare Gradient Descent (without momentum) and Momentum-based Gradient Descent on the same function (x^2). The graph shows how the cost (value of the function) changes over time (or epochs). The cost gets smaller faster for the Momentum-based method. That's because it gets a speed boost from the momentum, just like the ball rolling down the hill!

Wrapping Up

You've done it! You've understood how to use momentum to improve Gradient Descent and seen it in action. Doesn't the ball-on-a-hill analogy make it easier to understand? Now, it's time to put your knowledge into practice! If you remember how a rolling ball picks up speed, you'll never forget how momentum improves Gradient Descent. Happy practicing and coding!

Previous LessonNext Lesson: Understanding and Implementing RMSProp in C++
Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal