Stochastic Gradient Descent: Theory and Implementation in Python

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

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:

# Importing Necessary Library
import numpy as np

# Linear regression problem
X = np.array([0, 1, 2, 3, 4, 5]) 
Y = np.array([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$. Here, the term $(mx_i+ b) - y_i$ presents the difference between the actual data point and the initial model $mx_i + b$ prediction. Multiplying it with a specific feature $x_i$ and averaging over all samples provide the gradient for parameter $m$. The same principle applies to parameter $b$, but without multiplication by $x_i$, as $b$ is the bias term.