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

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.

We are going to use this simple example of data:

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

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:

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

We apply our SGD function and then visualize the progress using matplotlib-cpp.

#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");

Here is the result:

This plot visualizes the implementation of SGD on a simple linear regression problem, showcasing the resulting model.

Today's lesson unveiled critical aspects of the Stochastic Gradient Descent algorithm. We explored its significance, advantages, disadvantages, mathematical formulation, and C++ implementation. You'll soon practice these concepts in upcoming tasks, cementing your understanding of SGD and enhancing your C++ coding skills in machine learning. Happy learning!