Stochastic Gradient Descent: Theory and Implementation in C++

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

In terms of math, SGD can be formulated as follows. Imagine we are looking for a best-fit line, setting the parameters of the familiar $y = mx + b$ equation. Remember, $m$ is the slope and $b$ is the y-intercept. Then:

$m' = m - 2\alpha \cdot ((mx_i + b) - y_i) \cdot x_i$

$b' = b - 2\alpha \cdot ((mx_i + b) - y_i)$

where:

• $m$ and $b$ are the initial values of your parameters
• $m'$ and $b'$ are the updated parameters
• $x_i$ is a particular feature of your training set
• $y_i$ is the actual output for the given feature $x_i$
• $\alpha$ is the learning rate

These formulas represent the update rules for parameters $m$ and $b$ in Stochastic Gradient Descent. Here, the term $((mx_i + b) - y_i)$ is the difference between the model's prediction and the actual value for a single data point. For the slope $m$, this difference is multiplied by the feature $x_i$ of the selected sample. For the intercept $b$, the difference is used directly. In SGD, these updates are performed using only one randomly chosen data point at each iteration, making the process faster but noisier compared to Batch Gradient Descent, which averages the gradients over all samples.