In the early 2010s, as researchers attempted to train neural networks on increasingly large datasets, they encountered a seemingly insurmountable barrier: batch gradient descent simply couldn't scale. Computing exact gradients over millions or billions of training examples for each parameter update was computationally impossible.

The solution, ironically, came from an idea proposed over six decades earlier by Herbert Robbins and Sutton Monro in 1951. Stochastic Gradient Descent (SGD) makes a radical trade-off: instead of computing the exact gradient over all data, it estimates the gradient using just a single randomly selected example.

This seemingly reckless approximation—using one example instead of millions—not only works but often works better than batch methods. Understanding why requires diving deep into the mathematics of stochastic optimization, variance reduction, and the surprising benefits of gradient noise.

Recall that batch gradient descent computes the gradient over the entire dataset:

$$ abla J(\boldsymbol{\theta}) = \frac{1}{N} \sum_{i=1}^{N} abla \mathcal{L}(f_{\boldsymbol{\theta}}(\mathbf{x}^{(i)}), y^{(i)})$$

This is the expectation of the per-example gradient over the empirical data distribution. The key insight of SGD is that we can estimate this expectation using a single sample.

The SGD Update Rule

At each iteration, SGD:

1. Randomly samples one example $(\mathbf{x}^{(i)}, y^{(i)})$ from the dataset
2. Computes the gradient for that single example
3. Updates parameters:

$$\boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \eta abla \mathcal{L}(f_{\boldsymbol{\theta}^{(t)}}(\mathbf{x}^{(i)}), y^{(i)})$$

Notice the critical difference: we use $ abla \mathcal{L}$ (gradient of loss for ONE example) instead of $ abla J$ (average gradient over ALL examples).

The Fundamental Trade-off

SGD makes an extreme trade-off:

The key question is: can we actually converge to a good solution with such noisy gradients? The answer is yes, under appropriate conditions—but the convergence behavior is fundamentally different from batch methods.

To understand SGD rigorously, we must analyze the stochastic gradient as a random variable and quantify its relationship to the true gradient.

Decomposition of the Stochastic Gradient

Let $\mathbf{g}^{(t)} = abla \mathcal{L}(f_{\boldsymbol{\theta}^{(t)}}(\mathbf{x}^{(i_t)}), y^{(i_t)})$ be the stochastic gradient at iteration $t$, where $i_t$ is the randomly selected index. We can decompose:

$$\mathbf{g}^{(t)} = abla J(\boldsymbol{\theta}^{(t)}) + \boldsymbol{\epsilon}^{(t)}$$

where $\boldsymbol{\epsilon}^{(t)}$ is the gradient noise with the crucial property:

$$\mathbb{E}[\boldsymbol{\epsilon}^{(t)}] = \mathbf{0}$$

This zero-mean property is what makes SGD work. The stochastic gradient is an unbiased estimator of the true gradient.

Variance of the Stochastic Gradient

While the expected value of $\mathbf{g}^{(t)}$ equals the true gradient, the variance can be substantial:

$$\text{Var}[\mathbf{g}^{(t)}] = \mathbb{E}[|\boldsymbol{\epsilon}^{(t)}|^2] = \sigma^2(\boldsymbol{\theta}^{(t)})$$

This variance $\sigma^2$ quantifies how different individual gradients can be from the mean. High variance means:

1. Individual updates may go uphill (increasing loss)
2. The optimization path will be noisy
3. More iterations needed to average out noise

The variance is NOT uniform across parameter space. Near a minimum (where gradients are small), individual gradients might point in very different directions, leading to high relative noise.

Bounded Variance Assumption

Convergence proofs typically assume bounded variance:

$$\mathbb{E}[| abla \mathcal{L}(\boldsymbol{\theta}, \mathbf{x}^{(i)}, y^{(i)}) - abla J(\boldsymbol{\theta})|^2] \leq \sigma^2$$

for all $\boldsymbol{\theta}$ and uniformly over all examples. This assumption says the noise is bounded—no single example can produce an arbitrarily large gradient that would destabilize optimization.

Why Unbiasedness Matters

The zero-mean noise property is crucial. Consider the expected update:

$$\mathbb{E}[\boldsymbol{\theta}^{(t+1)}] = \mathbb{E}[\boldsymbol{\theta}^{(t)} - \eta \mathbf{g}^{(t)}] = \boldsymbol{\theta}^{(t)} - \eta abla J(\boldsymbol{\theta}^{(t)})$$

(treating $\boldsymbol{\theta}^{(t)}$ as fixed given the history)

This shows that on average, SGD moves in the correct direction. Individual steps may be wrong, but the expected direction is correct.

The convergence of SGD is fundamentally different from batch gradient descent. The noise in gradient estimates creates new challenges that require modified analysis and, critically, decaying learning rates.

The Convergence Dilemma

With a fixed learning rate $\eta$, SGD cannot converge to the exact minimum. Here's why:

1. Near the minimum, the true gradient $ abla J \approx \mathbf{0}$
2. But the stochastic gradient $\mathbf{g} = abla J + \boldsymbol{\epsilon} \approx \boldsymbol{\epsilon}$ is dominated by noise
3. Updates of size $\eta |\boldsymbol{\epsilon}|$ cause perpetual oscillation around the minimum

The solution is to decrease the learning rate over time, eventually making steps small enough to overcome the noise.

Convergence Theorems

Theorem 1 (Convergence for Convex Functions)

Let $J$ be convex with $L$-Lipschitz gradient, and assume bounded variance $\sigma^2$. With learning rate $\eta_t = 1/(\sqrt{t})$, SGD satisfies:

$$\mathbb{E}[J(\boldsymbol{\theta}^{(T)}) - J(\boldsymbol{\theta}^*)] \leq O\left(\frac{\sigma + LR}{\sqrt{T}}\right)$$

where $R = |\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^*|$.

This is a sublinear convergence rate of $O(1/\sqrt{T})$—slower than batch GD's $O(1/T)$ for convex functions.

Theorem 2 (Convergence for Strongly Convex Functions)

Let $J$ be $\mu$-strongly convex with $L$-Lipschitz gradient. With learning rate $\eta_t = 1/(\mu t)$, SGD achieves:

$$\mathbb{E}[J(\boldsymbol{\theta}^{(T)}) - J(\boldsymbol{\theta}^*)] \leq O\left(\frac{L\sigma^2}{\mu^2 T}\right)$$

This is $O(1/T)$—matching the batch GD rate for strongly convex functions! Strong convexity compensates for stochastic noise.

The Computation-Iteration Trade-off

While SGD converges slower in iterations, it wins overwhelmingly in wall-clock time for large datasets:

• Batch GD: $O(1/T)$ convergence, $O(N)$ cost per iteration → $O(N/\epsilon)$ total cost to reach error $\epsilon$
• SGD: $O(1/\sqrt{T})$ convergence, $O(1)$ cost per iteration → $O(1/\epsilon^2)$ total cost

For large $N$, SGD's $O(1/\epsilon^2)$ total cost heavily beats batch GD's $O(N/\epsilon)$ when $N >> 1/\epsilon$.

Example: For $N = 10^6$ and $\epsilon = 10^{-3}$:

• Batch GD: ~$10^9$ operations
• SGD: ~$10^6$ operations

SGD is 1000× faster in this scenario!

Perhaps the most counterintuitive aspect of SGD is that the noise—which seems like a pure negative—actually provides significant benefits. Understanding these benefits explains why SGD often outperforms batch methods even when computation is not a constraint.

Benefit 1: Escaping Local Minima

In non-convex optimization, gradient descent can get stuck in local minima. The gradient is zero, so no progress is made. But SGD's noisy gradients are rarely exactly zero—the noise provides 'kicks' that can push parameters out of shallow local minima.

This acts like simulated annealing: early in training (large learning rate = high 'temperature'), the noise helps explore; later (small learning rate = low 'temperature'), the algorithm settles into a good basin.

Benefit 2: Implicit Regularization

SGD noise acts as a form of regularization that prefers 'flat' minima over 'sharp' ones. Why?

In a sharp minimum, the loss increases rapidly away from the optimum. The noisy SGD updates frequently push parameters away from the minimum. If the minimum is sharp, these excursions increase the loss significantly, and the parameters are pushed back.

In a flat minimum, small excursions don't change the loss much. The parameters can wander within the flat region without penalty.

The net effect: SGD spends more time in flat minima. This is important because flat minima generalize better—small changes to parameters (as might occur with new data) don't hurt performance much.

Benefit 3: Regularized Loss Landscape

Recent theoretical work shows that SGD effectively optimizes a smoothed version of the loss:

$$\tilde{J}(\boldsymbol{\theta}) = \mathbb{E}_{\boldsymbol{\epsilon}}[J(\boldsymbol{\theta} + \eta \boldsymbol{\epsilon})]$$

This smoothed loss has fewer sharp features, making optimization easier. The amount of smoothing is proportional to the learning rate and gradient variance.

Benefit 4: Better Generalization

Empirical evidence consistently shows that:

1. Models trained with SGD generalize better than those trained with exact gradients
2. Larger learning rates (more noise) often lead to better test performance (up to a point)
3. The 'generalization gap' (train error - test error) is smaller for SGD

This suggests that the implicit regularization from SGD noise is genuinely beneficial for learning, not just a nuisance to be minimized.

Implementing SGD correctly requires attention to several practical details that significantly impact performance. Let's examine a production-quality implementation with careful handling of edge cases.

Algorithm: Stochastic Gradient Descent

Input: Initial θ₀, learning rate schedule η(t), dataset D, max epochs E
Output: Optimized parameters θ*

1. t ← 0
2. for epoch = 1 to E:
      a. Shuffle dataset D randomly
      b. for each example (x, y) in D:
            i.   Compute gradient: g ← ∇L(f_θ(x), y)  // Single example
            ii.  Get learning rate: η_t ← η(t)
            iii. Update: θ ← θ - η_t · g
            iv.  t ← t + 1
3. return θ

Critical detail: Shuffling the dataset each epoch ensures each example is used exactly once per epoch and in random order, which reduces the impact of any ordering in the original dataset.

Unlike batch gradient descent where a constant learning rate can work well, SGD typically requires a learning rate schedule—a systematic reduction of the learning rate over time—to converge properly.

Why Schedules Are Necessary

Recall the convergence dilemma: with fixed $\eta$, parameters oscillate around the minimum with magnitude proportional to $\eta \sigma$ (learning rate × gradient noise). To converge exactly, we must reduce $\eta$ over time so these oscillations vanish.

However, decreasing $\eta$ too quickly means we never reach the minimum. This tension is captured by the Robbins-Monro conditions:

$$\sum_{t=1}^{\infty} \eta_t = \infty \quad \text{(reach anywhere)}$$ $$\sum_{t=1}^{\infty} \eta_t^2 < \infty \quad \text{(noise contribution vanishes)}$$

In Practice: Modern Deep Learning Schedules

For deep learning, the theoretical Robbins-Monro schedules are often too aggressive. Modern practice uses:

Step Decay: Divide learning rate by a factor (e.g., 10) at fixed epochs

if epoch in [30, 60, 90]:
    lr = lr * 0.1

Cosine Annealing: Smooth decrease following a cosine curve $$\eta_t = \eta_{\min} + \frac{1}{2}(\eta_{\max} - \eta_{\min})\left(1 + \cos\left(\frac{t}{T}\pi\right)\right)$$

Warmup + Decay: Start with a small learning rate, increase linearly, then decay $$\eta_t = \begin{cases} \frac{t}{t_w} \cdot \eta_{\max} & t < t_w \ \text{decay}(\eta_{\max}, t - t_w) & t \geq t_w \end{cases}$$

The warmup phase helps stabilize training when initial gradients are large or the loss landscape is poorly conditioned near initialization.

Understanding SGD from a variance reduction perspective provides insight into why mini-batches help and motivates more advanced algorithms.

The Variance-Convergence Trade-off

SGD's convergence rate depends on the gradient variance $\sigma^2$. Lower variance means:

• Less oscillation around the minimum
• Potentially larger stable learning rates
• Faster convergence in iterations

This motivates strategies to reduce variance while maintaining computational efficiency.

Strategy 1: Averaging (The Polyak-Ruppert Average)

Instead of using the final iterate $\boldsymbol{\theta}^{(T)}$, average over the trajectory:

$$\bar{\boldsymbol{\theta}} = \frac{1}{T} \sum_{t=1}^{T} \boldsymbol{\theta}^{(t)}$$

This averaged iterate has lower variance than the final iterate and can achieve better convergence rates. The intuition: while individual iterates oscillate, their average stabilizes near the minimum.

Strategy 2: Mini-batching (Preview)

Instead of using one example, use $B$ examples:

$$\mathbf{g} = \frac{1}{B} \sum_{j=1}^{B} abla \mathcal{L}(\boldsymbol{\theta}, \mathbf{x}^{(i_j)}, y^{(i_j)})$$

The variance decreases by factor $B$:

$$\text{Var}[\mathbf{g}] = \frac{\sigma^2}{B}$$

This is the key insight behind mini-batch SGD, which we'll cover in detail in the next page. It interpolates between pure SGD ($B=1$) and batch GD ($B=N$).

Strategy 3: Advanced Variance Reduction Methods

More sophisticated methods actively reduce variance:

• SVRG (Stochastic Variance Reduced Gradient): Periodically compute exact gradient and use it to correct stochastic estimates

• SAGA: Maintain a table of gradients for each example, enabling variance reduction without periodic exact computation

These methods achieve the $O(1/T)$ or even linear convergence rates of batch methods while using $O(1)$ computation per update. They're less common in deep learning due to memory requirements but important in convex optimization.

SGD has a deep connection to online learning—a paradigm where data arrives sequentially and the model must update after each example. This connection provides theoretical grounding and suggests practical applications.

The Online Learning Setting

In online learning:

1. An example $(\mathbf{x}^{(t)}, y^{(t)})$ arrives
2. The learner makes a prediction $\hat{y}^{(t)} = f_{\boldsymbol{\theta}^{(t)}}(\mathbf{x}^{(t)})$
3. The true label is revealed
4. The learner updates parameters: $\boldsymbol{\theta}^{(t+1)}$
5. The example may be discarded (never seen again)

SGD naturally fits this paradigm: each update uses only the current example, and we don't need to store or revisit past data.

Regret Analysis

Online learning is analyzed via regret—the difference between the learner's cumulative loss and the best fixed predictor in hindsight:

$$R_T = \sum_{t=1}^{T} \mathcal{L}(\boldsymbol{\theta}^{(t)}) - \min_{\boldsymbol{\theta}} \sum_{t=1}^{T} \mathcal{L}(\boldsymbol{\theta})$$

A good algorithm has sublinear regret: $R_T = o(T)$, meaning per-round regret $R_T/T \to 0$.

Theorem (Online Gradient Descent Regret)

For convex losses with gradients bounded by $G$ and learning rate $\eta = \frac{R}{G\sqrt{T}}$:

$$R_T \leq \frac{RG\sqrt{T}}{2} + \frac{RG\sqrt{T}}{2} = RG\sqrt{T}$$

This $O(\sqrt{T})$ regret bound is optimal for online convex optimization, and SGD achieves it!

We've thoroughly examined Stochastic Gradient Descent—the algorithm that made large-scale machine learning practical. Let's consolidate the key insights:

What's Next

The next page introduces Mini-batch SGD—the practical middle ground that combines the computational benefits of stochastic methods with variance reduction through batching. Mini-batch SGD is what's actually used in nearly all deep learning, and understanding it requires understanding both batch GD and pure SGD, which we've now covered.