Stochastic vs. Batch Gradient Descent: Convergence Analysis

Hello! In our last lesson, we derived the batch gradient descent algorithm and analyzed its convergence, establishing that for convex functions, it reliably finds the global minimum at a sublinear rate of $O (1/ t)$ . A key part of that analysis was the assumption that we can compute the full gradient, $\nabla J (θ) = \sum_{i = 1}^{n} \nabla J_{i} (θ)$ , at every single step.

While theoretically sound, this presents a major practical challenge. For the large datasets common in machine learning, where the number of samples $n$ can be in the millions or even billions, computing this full sum at every iteration is computationally prohibitive. This lesson introduces the workhorse of modern large-scale optimization: Stochastic Gradient Descent (SGD). We will derive SGD as a computationally efficient alternative to batch gradient descent and, crucially, analyze its distinct convergence properties, which are shaped by the trade-off between speed and noise.

The Problem with Batch Gradient Descent and the Rise of SGD

Most objective functions in machine learning are structured as a finite sum over the training data. For a dataset of $n$ examples, the cost function $J (θ)$ is typically:

J (θ) = \frac{1}{n} i = 1 \sum n J_{i} (θ)

where $J_{i} (θ)$ is the loss on the $i$ -th training example.

The batch gradient descent (BGD) update rule you learned previously is:

θ_{t + 1} = θ_{t} - η \nabla J (θ_{t}) = θ_{t} - η (\frac{1}{n} i = 1 \sum n \nabla J_{i} (θ_{t}))

The summation term is the bottleneck. To take just one step, you must process your entire dataset. If your dataset is terabytes in size, this can take hours.

Stochastic Gradient Descent offers a brilliantly simple and effective solution. Instead of computing the full gradient, what if we approximate it using the gradient of just one randomly chosen data point at each step?

The MIT OpenCourseWare video below provides an excellent introduction to this concept, setting up the finite sum problem and motivating the switch to SGD.

25. Stochastic Gradient Descent

This lecture by Prof. Suvrit Sra explains the ubiquitous "finite sum" structure of ML problems and introduces the core idea of SGD as a computationally cheap alternative to full gradient descent.

First, watch the section that frames machine learning optimization as a finite sum problem. Then, see how SGD is introduced as a simple yet powerful modification to the standard gradient descent update from the SGD idea.

As the video explains, the SGD update rule is:

At iteration $t$ , pick an index $i_{t}$ uniformly at random from ${1, 2, \dots, n}$ .
Update the parameters using only the gradient of the loss for that single sample: $θ_{t + 1} = θ_{t} - η_{t} \nabla J_{i_{t}} (θ_{t})$

The computational cost of this update is now independent of the dataset size $n$ , making each iteration orders of magnitude faster than a batch gradient descent step. In the time it takes BGD to perform one update, SGD can perform $n$ updates. But does this seemingly crude approximation actually work?

The Unbiased but Noisy Gradient

The mathematical justification for SGD lies in a key statistical property. The stochastic gradient, $\nabla J_{i_{t}} (θ_{t})$ , is an unbiased estimator of the true, full-batch gradient, $\nabla J (θ_{t})$ . This means that, on average, the stochastic gradient points in the same direction as the true gradient.

Formally, the expectation over the random choice of index $i_{t}$ is:

E_{i_{t} \sim U {1, .., n}} [\nabla J_{i_{t}} (θ_{t})] = i = 1 \sum n \frac{1}{n} \nabla J_{i} (θ_{t}) = \nabla J (θ_{t})

However, being unbiased is not the whole story. For any single iteration, the stochastic gradient is a noisy approximation. The variance of this estimator, $Var (\nabla J_{i_{t}} (θ_{t}))$ , is non-zero and plays a central role in the behavior of SGD. This noise is what causes the characteristic "drunken walk" of the algorithm, as opposed to the smooth descent of BGD.

The following video provides a fantastic visualization of this difference and further elaborates on the properties of the stochastic gradient.

25. Stochastic Gradient Descent

Continuing with the same MIT lecture, this segment visually compares the paths of SGD and BGD, provides a 1D example for intuition, and explains the concepts of unbiasedness and variance.

Watch the segment from SGD vs. GD simulation, which shows how SGD's path fluctuates but still makes progress. The following section uses a simple 1D example to build intuition about why SGD makes rapid initial progress. Finally, pay close attention to the discussion on the unbiased estimate and variance, as this is the theoretical core of why SGD works.

The difference in optimization paths is striking.

This figure compares the behavior of different gradient descent variants. Batch gradient descent (top left) shows a smooth decrease in cost. Its optimization path (bottom, green line) is direct. Mini-batch gradient descent (top right), which includes SGD as the b=1 case, has a noisy cost decrease. Its path (bottom, purple line) is stochastic and wanders toward the minimum.

While BGD marches steadily downhill, SGD takes a much more erratic path. It makes rapid progress when far from the minimum, but as it gets closer, the noise can cause it to "bounce around" the optimal point rather than converging directly to it.

Convergence Analysis of SGD

The convergence behavior of SGD is fundamentally different from BGD due to the gradient's variance. The analysis hinges on how we manage this variance, which is primarily controlled by the learning rate schedule, $η_{t}$ .

For a formal treatment, we'll turn to the "Handbook of Convergence Theorems," a rigorous resource that precisely lays out the necessary assumptions and results.

Handbook of Convergence Theorems for (Stochastic) ...

This document provides detailed mathematical proofs for the convergence of various optimization algorithms, including SGD. We will focus on the setup and the main convergence theorem.

First, familiarize yourself with the problem formulation in Section 4.1 and the definition of gradient noise \sigma_f^* in Definition 4.16. This \sigma_f^* measures the variance of the individual gradients at the optimal point and is a crucial quantity. Next, read through Algorithm 5.1 to see the formal definition of SGD. Finally, focus on Theorem 5.5 (Part 1). This theorem presents the convergence bound for SGD with a constant step size \gamma. You don't need to follow the entire proof, but carefully examine the final bound and understand its components.

The convergence bound from Theorem 5.5 for a constant step size $γ$ can be simplified and interpreted as:

E [f (x ˉ_{t}) - f (x^{*})] \leq \frac{∥ x _{0} - x ^{*} ∥ ^{2}}{C _{1} t} + C_{2} γ σ_{f}^{*}

Let's dissect this bound:

Bias Term: The first term, $\frac{∥ x _{0} - x ^{*} ∥ ^{2}}{C _{1} t}$ , depends on the initial distance to the solution and decreases as the number of iterations $t$ increases. This term goes to zero as $t \to \infty$ .
Variance Term: The second term, $C_{2} γ σ_{f}^{*}$ , is the critical one. It depends on the learning rate $γ$ and the inherent noise of the problem $σ_{f}^{*}$ . This term does not decrease with more iterations.

This analysis leads to a key insight: with a constant step size, SGD does not converge to the exact minimum $x^{*}$ . Instead, it converges to a region or "ball" around the minimum, where the suboptimality is bounded by the variance term. A smaller learning rate $γ$ leads to a smaller final error, but also slower convergence.

Achieving True Convergence with a Decreasing Step Size

To converge to the exact minimum, the variance term must also be driven to zero. This can be achieved by using a decreasing step size schedule that satisfies the Robbins-Monro conditions:

t = 1 \sum \infty η_{t} = \infty and t = 1 \sum \infty η_{t}^{2} < \infty

The first condition ensures that the algorithm can explore the entire parameter space, while the second condition ensures that the noise is eventually squashed, allowing for convergence. A typical choice that satisfies these conditions is $η_{t} = O (1/ t)$ .

With such a schedule, the convergence rate for SGD on convex, smooth functions is typically $O (1/ t)$ . Notice this is slower than the $O (1/ t)$ rate for batch gradient descent. This is the price we pay for the enormous per-iteration computational savings.

The Spectrum: Mini-Batch SGD

In practice, neither pure BGD (using all $n$ samples) nor pure SGD (using 1 sample) is the most common choice. The sweet spot is Mini-Batch SGD, which uses a small batch $B$ of samples (e.g., 32, 64, 256) for each update:

θ_{t + 1} = θ_{t} - η_{t} (\frac{1}{∣ B ∣} i \in B_{t} \sum \nabla J_{i} (θ_{t}))

Mini-batching provides two key benefits:

Reduced Variance: By averaging gradients over a small batch, the variance of the gradient estimate is reduced compared to pure SGD. This leads to a more stable convergence path and often faster convergence in practice.
Computational Efficiency: Modern computing hardware, especially GPUs, are optimized for parallel, vectorized operations. Processing a mini-batch of data is far more efficient than processing single data points sequentially. Your experience with deep learning frameworks has undoubtedly leveraged this capability.

Theoretically, mini-batching provides a beautiful bridge between SGD and BGD.

Handbook of Convergence Theorems for (Stochastic) ...

This section of the handbook formally introduces Mini-batch SGD and analyzes its properties.

Read the introduction in Section 6.1. Pay close attention to Remark 6.6, which explicitly discusses how the batch size b interpolates between SGD (b=1) and full-batch GD (b=n) by affecting the variance term \sigma_b^*.

As the notes show, the variance of the mini-batch gradient is $σ_{b}^{*} = \frac{n - b}{b ( n - 1 )} σ_{f}^{*}$ .

When $b = 1$ , this reduces to $σ_{1}^{*} \approx σ_{f}^{*}$ , the variance of SGD.
When $b = n$ , this becomes $σ_{n}^{*} = 0$ , matching the zero-variance of batch GD.

This mathematically confirms that by increasing the mini-batch size, we are trading off per-iteration cost for reduced gradient variance and a more stable convergence path.

Summary and Comparison

Let's consolidate the trade-offs between Batch, Mini-Batch, and Stochastic Gradient Descent.

Feature	Batch Gradient Descent (BGD)	Stochastic Gradient Descent (SGD)	Mini-Batch SGD
Gradient	Exact gradient from all $n$ samples	Noisy estimate from 1 random sample	Noisy estimate from $b$ random samples ( $1 < b ≪ n$ )
Cost per iteration	$O (n d)$ - Very high	$O (d)$ - Very low	$O (b d)$ - Low, scalable
Update Frequency	Once per epoch	$n$ times per epoch	$n / b$ times per epoch
Convergence Path	Smooth, direct path to minimum	Noisy, "drunken walk"	Less noisy than SGD, smoother path
Convergence Rate	$O (1/ t)$ (sublinear for convex)	$O (1/ t)$ (with decreasing $η$ )	Between SGD and BGD, depends on $b$
Hardware	Poor utilization of parallel hardware	Poor utilization (sequential)	Excellent utilization via vectorization

In summary, SGD trades the guaranteed, steady progress of BGD for massive computational gains per iteration. This makes it indispensable for large-scale problems. Its convergence is slower in terms of iterations due to gradient noise, but much faster in terms of wall-clock time. Mini-batch SGD emerges as the de-facto standard in practice, offering a masterful compromise that combines computational efficiency, hardware utilization, and stable convergence.

Conclusion

In this lesson, we have moved from the deterministic world of batch gradient descent to the practical and powerful realm of stochastic optimization.

Here are the key takeaways:

Stochastic Gradient Descent (SGD) approximates the full gradient using a single, randomly chosen data point, making each iteration independent of the total dataset size.
The stochastic gradient is an unbiased but noisy estimate of the true gradient. This noise is the source of SGD's characteristic erratic convergence path.
SGD's convergence depends on the learning rate schedule. A constant rate leads to convergence to a noise ball around the minimum, while a carefully chosen decreasing rate (e.g., $O (1/ t)$ ) allows convergence to the exact minimum, albeit at a sublinear rate of $O (1/ t)$ .
Mini-batch SGD is the practical algorithm of choice, balancing the trade-off between the computational cost of BGD and the variance of SGD, while maximizing hardware efficiency.

So far, our exploration of optimization has focused on first-order methods, which use only gradient information. In the next lesson, we will investigate Newton's method, a powerful second-order technique that incorporates curvature information (the Hessian matrix) to achieve quadratic convergence, promising much faster convergence near the optimum.

Recommended resources