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

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
}

C++

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

// Plot the data points
plt::scatter(X, Y, {{"color", "m"}, {"marker", "o"}, {"s", 30}});

// Predicted line for the model
std::vector<double> y_pred;
for (double x : X) {
    y_pred.push_back(m * x + b);
}

// Plotting the predicted line
plt::plot(X, y_pred, {{"color", "g"}});

// Adding labels to the plot
plt::xlabel("X");
plt::ylabel("Y");

plt::save("static/images/plot.png");

Introduction

Understanding Stochastic Gradient Descent

Defining Data

Math Behind

Join the 1M+ learners on CodeSignal

Implementing Stochastic Gradient Descent

Testing the Algorithm

Lesson Summary and Practice