Stochastic Gradient Descent: Theory and Implementation in C++

Introduction

Welcome! We're about to explore Stochastic Gradient Descent (SGD), a pivotal optimization algorithm. SGD, a variant of Gradient Descent, is renowned for its efficiency with large datasets due to its unique stochastic nature. Stochastic means "random" and is the opposite of deterministic. A deterministic algorithm runs the same every time, but a stochastic one introduces a randomness. Our journey includes understanding SGD, its theoretical concepts, and implementing it in C++.

Understanding Stochastic Gradient Descent

SGD starts by understanding its structure. Unlike Gradient Descent, SGD calculates an estimate of the gradient using a randomly selected single data point, not the entire dataset. Consequently, SGD is highly efficient for large datasets. While the efficient handling of large datasets by SGD is a blessing, its stochasticity can often lead to a slightly noisier process for convergence, resulting in the model not settling at an absolute minimum.

Defining Data

We are going to use this simple example of data: C++ #include <vector> #include <random> // Linear regression problem std::vector<double> X = {0, 1, 2, 3, 4, 5}; std::vector<double> Y = {0, 1.1, 1.9, 3, 4.2, 5.2};

Math Behind

y = mx + b

Join the 1M+ learners on CodeSignal

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

Implementing Stochastic Gradient Descent

Now, let's dive into C++ to implement SGD. This process encompasses initializing parameters randomly, selecting a random training sample, calculating the gradient, updating the parameters, and running several iterations (also known as epochs).

Let's break it down with the following code:

C++

#include <vector>
#include <random>
#include <iostream>

// Model initialization
std::random_device rd;
std::mt19937 gen(rd());
std::normal_distribution<> dis(0.0, 1.0);

double m = dis(gen);  // Initialize the slope (random number)
double b = dis(gen);  // Initialize the intercept (random number)

double learning_rate = 0.01;  // Define the learning rate
int epochs = 10000;  // Define the number of iterations

// SGD implementation
for (int i = 0; i < epochs; ++i) {
    int random_index = std::rand() % X.size();  // select a random sample
    double x = X[random_index];
    double y = Y[random_index];
    double pred = m * x + b;  // Calculate the predicted y
    // Calculate gradients for m (slope) and b (intercept)
    double grad_m = 2 * (pred - y) * x;
    double grad_b = 2 * (pred - y);
    m -= learning_rate * grad_m;  // Update m using the calculated gradient
    b -= learning_rate * grad_b;  // Update b using the calculated gradient
}

#include <vector>
#include <random>
#include <iostream>

// Model initialization
std::random_device rd;
std::mt19937 gen(rd());
std::normal_distribution<> dis(0.0, 1.0);

double m = dis(gen);  // Initialize the slope (random number)
double b = dis(gen);  // Initialize the intercept (random number)

double learning_rate = 0.01;  // Define the learning rate
int epochs = 10000;  // Define the number of iterations

// SGD implementation
for (int i = 0; i < epochs; ++i) {
    int random_index = std::rand() % X.size();  // select a random sample
    double x = X[random_index];
    double y = Y[random_index];
    double pred = m * x + b;  // Calculate the predicted y
    // Calculate gradients for m (slope) and b (intercept)
    double grad_m = 2 * (pred - y) * x;
    double grad_b = 2 * (pred - y);
    m -= learning_rate * grad_m;  // Update m using the calculated gradient
    b -= learning_rate * grad_b;  // Update b using the calculated gradient
}

After running the SGD implementation, we should see the final optimized values of m (slope) and b (intercept).

Notice, the learning rate in SGD, set to 0.01 in our example, is a crucial hyperparameter. While 0.01 is a common starting value, it may not always guarantee convergence for all datasets. If the learning rate is too high, the algorithm might overshoot the minimum and fail to converge; if it is too low, convergence can be extremely slow. It is often necessary to experiment with different learning rates or use techniques like learning rate schedules to find the most suitable value for your specific problem.