Understanding SGD: Derivation and Advantages

Introduction

Welcome to our first lesson on the powerful optimization algorithms that drive modern machine learning. In our previous session, we meticulously prepared our neural network for training by establishing principled weight initialization strategies. A well-initialized network is primed for learning, but it doesn't yet know how to adjust its parameters to fit the data. This lesson addresses that "how."

We will start by formalizing the standard gradient descent algorithm, which you've seen implicitly in our discussions of loss minimization. We will then analyze its primary limitation: a crippling computational cost when faced with the large datasets typical of real-world AI applications. This analysis will motivate our main topic: Stochastic Gradient Descent (SGD). You will derive SGD from first principles, understand its theoretical justification as an unbiased estimator, and quantify its significant computational advantages over its "batch" counterpart. This marks our transition from network architecture to the dynamic process of learning.

The Problem with "Batch" Gradient Descent

So far, when we've discussed minimizing a loss function $J(\theta )$, we've been referring to what is more formally known as Batch Gradient Descent (BGD), or sometimes "full" gradient descent. The core idea is to compute the gradient of the loss function with respect to the parameters $\theta$ using the entire training dataset.

Most loss functions in supervised learning are defined as an average or sum of the losses over individual data points. This is the principle of Empirical Risk Minimization we discussed earlier. A typical objective function has this "finite sum" structure:

$$J(\theta )=\frac{1}{m}\sum _{i=1}^{m}L(h_{\theta }(x^{(i)}),y^{(i)})$$

Here, $m$ is the total number of training examples, and $L$ is the loss for a single example $(x^{(i)},y^{(i)})$. To perform one update step in Batch Gradient Descent, we calculate the gradient of this entire sum:

$${\nabla }_{\theta }J(\theta )=\frac{1}{m}\sum _{i=1}^m{\nabla }_{\theta }L(h_{\theta }(x^{(i)}),y^{(i)})$$

The parameter update rule is then:

$$\theta :=\theta -\alpha {\nabla }_{\theta }J(\theta )$$

Where $\alpha$ is the learning rate.

The crucial part is the summation ${\sum }_{i=1}^m$. To compute the true gradient and take just one step, we must iterate over every single example in our training set.

The following video from Andrew Ng's Stanford course provides a clear explanation of this process and its primary drawback.

As you've just seen, if your dataset has millions or billions of data points ($m$ is large), computing this sum for every single update step is immensely expensive. If training requires thousands of epochs (passes through the data), the total computational cost becomes prohibitive. This is the central motivation for finding a more efficient alternative.

Deriving Stochastic Gradient Descent (SGD)

Instead of computing the exact, expensive gradient, what if we could use a cheaper, "good enough" approximation? This is the core idea behind Stochastic Gradient Descent.

The BGD gradient is an average of the gradients of the individual loss terms. SGD's radical proposal is to approximate this average with a single, randomly chosen term. At each step $k$, we randomly sample one data point $(x^{(i_k)},y^{(i_k)})$ from the training set and compute the gradient using only that point:

Stochastic Gradient Estimate: ${\hat{g}}_k={\nabla }_{\theta }L(h_{\theta }(x^{(i_k)}),y^{(i_k)})$

The SGD update rule is then:

$$\theta :=\theta -\alpha {\hat{g}}_k$$

Why This Works: The Unbiased Estimate

This may seem like a reckless approximation, but it has a strong theoretical justification. If we sample $i_k$ uniformly at random from $\{1,...,m\}$, the expected value of our stochastic gradient estimate is exactly the true batch gradient:

$${\mathbb{E}}_{i_k}[{\hat{g}}_k]={\mathbb{E}}_{i_k}[{\nabla }_{\theta }L(h_{\theta }(x^{(i_k)}),y^{(i_k)})]=\frac{1}{m}\sum _{i=1}^m{\nabla }_{\theta }L(h_{\theta }(x^{(i)}),y^{(i_i)})={\nabla }_{\theta }J(\theta )$$

This means the stochastic gradient is an unbiased estimator of the true gradient. While any single SGD step might point in a slightly "wrong" direction, on average, the updates point in the correct direction of steepest descent.

This lecture from MIT OpenCourseWare provides a rigorous framing of this concept.

Computational Advantages and The Optimization Path

The computational benefit of SGD is immediately apparent.

• Batch GD step cost: $O(m\cdot d)$, where $d$ is the number of features/parameters.
• SGD step cost: $O(d)$.

Each SGD step is $m$ times faster than a BGD step. For a dataset with a million examples, we can perform a million SGD updates in the time it takes to do just one BGD update.

Of course, there is a trade-off. The path SGD takes towards the minimum is not a smooth, direct descent like BGD. Because each step is based on a noisy gradient estimate from a single example, the parameter updates fluctuate, creating a "zigzag" or "drunken walk" trajectory.

This noisy path has two important consequences:

1. Slower Convergence (per epoch): SGD requires more updates to reach the minimum compared to BGD because its steps are not always optimal.
2. Fluctuation around the minimum: Unlike BGD, which converges to a specific point, SGD tends to oscillate in a region around the minimum, never settling completely.

Despite these points, the massive per-step computational saving almost always makes SGD the superior choice for large-scale problems. The rapid initial progress it makes far outweighs the fine-grained instability near the optimum.

Let's return to Andrew Ng's lecture to see a visualization of this process and a summary of the trade-offs.

Mini-Batch Gradient Descent: The Practical Standard

In practice, a compromise between the two extremes of Batch GD (using all $m$ samples) and SGD (using 1 sample) is most common. This is Mini-Batch Gradient Descent.

The idea is to use a small batch of $b$ samples (where $1<b\ll m$) to estimate the gradient at each step. Typical mini-batch sizes are powers of two, such as 32, 64, 128, or 256.

The Mini-Batch update is:

$$\theta :=\theta -\alpha \left(\frac{1}{b}\sum _{j=1}^b{\nabla }_{\theta }L(h_{\theta }(x^{(j)}),y^{(j)})\right)$$

This approach offers two key advantages:

1. Variance Reduction: By averaging over a small batch, the gradient estimate becomes more stable and less noisy than pure SGD, leading to a smoother convergence path (as seen in the image above).
2. Computational Efficiency: Modern hardware, particularly GPUs, is highly optimized for parallel, vectorized operations. Computing the gradient for a mini-batch of 32 or 64 can be nearly as fast as for a single sample, making it a highly efficient use of computational resources.

For these reasons, when people in the field refer to "SGD," they are very often implicitly referring to Mini-Batch SGD, as it is the de facto standard for training deep neural networks.

The following document provides a concise summary of the derivation and comparison.

Conclusion

In this lesson, we transitioned from the static structure of a neural network to the dynamic process of training it. We have dissected the fundamental optimization algorithm used in deep learning, moving from a naive approach to a practical, scalable solution.

Your key takeaways should be:

• Batch Gradient Descent (BGD) computes the exact gradient over the entire dataset for each update. This is computationally infeasible for large datasets.
• Stochastic Gradient Descent (SGD) approximates the gradient using a single, randomly sampled data point. This creates a computationally cheap but noisy update.
• The validity of SGD rests on the fact that its gradient estimate is unbiased; on average, it points in the right direction.
• SGD's primary advantage is its computational efficiency. The cost of an update step is independent of the dataset size, making it the only viable option for large-scale problems.
• Mini-Batch SGD is the practical industry standard, offering a balance between the stability of BGD and the speed of SGD while efficiently leveraging modern parallel hardware.

We have established the basic mechanism for descending the loss surface. However, the noisy path of SGD can still be inefficient, and navigating complex, high-dimensional loss landscapes presents further challenges. In our next lesson, we will explore advanced optimization techniques—specifically momentum-based methods like RMSProp and Adam—that build upon SGD to accelerate convergence and navigate these landscapes more effectively.