Gradient Descent: Update Rule and Convergence

Welcome back. In our last lesson, we built a rigorous understanding of convexity, establishing the Hessian test to identify convex functions and appreciating why the guarantee that "any local minimum is global" makes optimization so much more tractable. We also acknowledged the sobering reality that training deep neural networks is a fundamentally non-convex problem.

Today, we will derive and analyze gradient descent, the foundational algorithm that powers the training of most models in deep learning. We will derive its update rule from first principles and then, to build our theoretical toolkit, we'll analyze its convergence properties in the idealized setting of smooth, convex functions. This analysis, while not directly applicable to the complex landscapes of deep learning, provides the essential language and intuition—concerning learning rates, convergence rates, and conditioning—that form the basis for understanding more advanced optimizers.

1. The Principle of Steepest Descent

At its core, gradient descent is a remarkably simple and intuitive idea. Imagine you are standing on a hilly terrain, blindfolded, and your goal is to reach the lowest possible point. The most straightforward strategy would be to feel the ground at your feet to determine the direction of the steepest slope downwards and take a small step in that direction. By repeating this process, you hope to eventually arrive at the bottom of a valley.

This is precisely what gradient descent does. In the previous module, we established that the gradient of a function, $\nabla f (w)$ , points in the direction of the steepest ascent. Consequently, the negative gradient, $- \nabla f (w)$ , points in the direction of steepest descent.

The following video provides an excellent visual and intuitive introduction to this core concept.

Intro to Gradient Descent || Optimizing High-Dimensional Equations

This video from Dr. Trefor Bazett, "Intro to Gradient Descent", uses the mountain climbing analogy to explain the fundamental idea of iteratively moving in the direction of the negative gradient.

Please watch the first two segments of the video to grasp the intuition: The core idea of following the steepest path. The gradient vector as the mathematical tool that tells us the steepest direction. Then, skip ahead to the discussion on why this iterative approach is often more practical than trying to analytically solve \nabla f(w) = 0, especially for high-dimensional functions common in machine learning.

2. The Gradient Descent Algorithm

Let's now formalize this intuition. We want to find a minimizer $w^{*}$ for a differentiable function $f (w)$ . We start at some initial point $w_{0}$ and iteratively update our position. At each step $t$ , we move from our current position $w_{t}$ in the direction of the negative gradient.

This leads to the gradient descent update rule:

w_{t + 1} = w_{t} - α \nabla f (w_{t})

Here:

$w_{t}$ is the vector of parameters at iteration $t$ .
$\nabla f (w_{t})$ is the gradient of the function $f$ evaluated at $w_{t}$ .
$α$ is the learning rate (or step size), a positive scalar that controls how large of a step we take in the descent direction.

The process is repeated until some stopping criterion is met, such as the gradient becoming very small, the change in the parameters being negligible, or a maximum number of iterations being reached.

The following reading provides a concise, formal definition of the algorithm.

Optimization

This chapter from "The Mechanics of Machine Learning" formalizes the concepts we've just discussed.

Please read the section titled "Gradient descent". It begins by defining a descent direction, shows that the negative gradient is always one, and presents the formal gradient descent algorithm. Also, note the important distinction made between a stationary point (\nabla f(w) = 0) and a minimizer.

The choice of the learning rate, $α$ , is critical.

If $α$ is too small, the algorithm will take a very long time to converge, as it takes tiny steps.
If $α$ is too large, the algorithm might "overshoot" the minimum and oscillate wildly, potentially even diverging and causing the function value to increase.

Professor Gilbert Strang discusses the practical considerations of choosing this step size, introducing concepts like exact line search.

22. Gradient Descent: Downhill to a Minimum

In this lecture from MIT OpenCourseWare, Professor Strang introduces the gradient descent update rule and immediately focuses on the crucial role of the step size.

Watch the segment from this timestamp. He explains the trade-offs of choosing \alpha and defines two strategies for setting it at each step: exact line search (finding the optimal step size along the gradient direction) and backtracking line search (starting with a large step and reducing it until sufficient decrease is achieved).

3. Convergence Analysis for Smooth Convex Functions

Now we arrive at the central question: Under what conditions can we guarantee that gradient descent will converge to a minimum? And how fast will it converge?

To answer this, we will analyze the algorithm in an idealized setting where the function $f$ has two key properties:

Convexity: As we know from the last lesson, for a convex function, any local minimum is a global minimum.
L-smoothness: This is a new, crucial property. A function is called L-smooth if its gradient is Lipschitz continuous with constant $L$ . Formally, $∥\nabla f (x) - \nabla f (y) ∥ \leq L ∥ x - y ∥$ for all $x, y$ .

Intuitively, L-smoothness means the function's curvature is bounded. The gradient cannot change arbitrarily fast. For a twice-differentiable function, this is equivalent to the largest eigenvalue of its Hessian being at most $L$ . A key consequence of L-smoothness is that the function is globally upper-bounded by a quadratic:

f (y) \leq f (x) + \nabla f (x)^{T} (y - x) + \frac{L}{2} ∥ y - x ∥^{2}

This is often called the Descent Lemma and is the main tool for the analysis.

Convergence Rate

With these assumptions, we can prove convergence. Let's outline the key steps of the proof:

Start with the Descent Lemma: $f (w_{t + 1}) \leq f (w_{t}) + \nabla f (w_{t})^{T} (w_{t + 1} - w_{t}) + \frac{L}{2} ∥ w_{t + 1} - w_{t} ∥^{2}$ .
Substitute the gradient descent update $w_{t + 1} - w_{t} = - α \nabla f (w_{t})$ .
This yields: $f (w_{t + 1}) \leq f (w_{t}) - α (1 - \frac{α L}{2}) ∥\nabla f (w_{t}) ∥^{2}$ .
This inequality is very informative. It shows that as long as we choose the learning rate $α < 2/ L$ , the term $α (1 - \frac{α L}{2})$ is positive, and the function value is guaranteed to decrease at every step (unless we are at a minimum where $\nabla f (w_{t}) = 0$ ).

By choosing a fixed step size $α = 1/ L$ , one can continue this derivation to show that the error $f (w_{T}) - f (w^{*})$ after $T$ steps decreases at a rate of $O (1/ T)$ . This is known as sublinear convergence.

4. The Impact of Strong Convexity and Conditioning

We can achieve a much faster convergence rate if we add a stronger assumption: $μ$ -strong convexity. A function is strongly convex if it is lower-bounded by a quadratic with curvature $μ$ . For a twice-differentiable function, this means the smallest eigenvalue of its Hessian is at least $μ > 0$ .

When a function is both L-smooth and $μ$ -strongly convex, gradient descent with a constant step size $α \leq 2/ (L + μ)$ achieves linear convergence. This means the distance to the optimum decreases by a constant factor at each iteration:

∥ w_{t + 1} - w^{*} ∥^{2} \leq (1 - \frac{2 α μL}{μ + L}) ∥ w_{t} - w^{*} ∥^{2}

The rate of this convergence is governed by the condition number, $κ = L / μ$ . For a quadratic function $f (w) = \frac{1}{2} w^{T} Qw$ , $L = λ_{m a x} (Q)$ and $μ = λ_{m i n} (Q)$ , so the condition number is simply the ratio of the largest to the smallest eigenvalue of the Hessian.

A large condition number ( $κ ≫ 1$ ) means the loss landscape has long, narrow valleys. In this scenario, gradient descent tends to oscillate across the narrow walls of the valley, making very slow progress along the valley floor.

Let's study this phenomenon in detail using a simple quadratic example.

Optimization

This section provides a complete analysis of gradient descent on a general quadratic function. It serves as the perfect concrete illustration of the abstract concepts of smoothness and strong convexity.

Please read the entire section Insights from quadratic functions. Pay close attention to: The closed-form expression for the iterates: w_{t}-w\_\star = (I-\alpha Q)^t (w\_0 - w\_\star). The derivation of how the condition number \kappa = \lambda_1/\lambda_d controls the convergence rate.

Professor Strang provides an excellent visualization of this exact issue.

22. Gradient Descent: Downhill to a Minimum

Returning to the MIT OCW lecture, Professor Strang analyzes a specific 2D quadratic function, f(x,y) = x^2 + By^2, where the condition number is 1/B.

Watch the final part of the lecture, from this analysis. He derives the exact convergence rate and shows how it depends on the condition number. Most importantly, he draws the elliptical level sets for an ill-conditioned problem (small B) and explains how gradient descent follows a slow, "zigzag" path toward the minimum. This visual perfectly captures the challenge of optimizing in narrow valleys.

Convergence of gradient descent on a well-conditioned quadratic (left, small $κ$ ) vs. an ill-conditioned one (right, large $κ$ ). The elliptical contours are the level sets of the function. Notice the slow, oscillating path taken on the ill-conditioned problem.

This analysis of ill-conditioned problems is not just a theoretical curiosity. The loss landscapes of deep neural networks are notoriously ill-conditioned, featuring complex "ravines" and "valleys". Understanding this behavior is the key motivation for developing more sophisticated optimization algorithms.

Conclusion

In this lesson, we have moved from the "what" of optimization (convexity) to the "how" (gradient descent).

Key Takeaways:

The gradient descent update rule, $w_{t + 1} = w_{t} - α \nabla f (w_{t})$ , is derived from the principle of moving in the direction of steepest descent.
The learning rate $α$ is a critical hyperparameter that balances convergence speed with the risk of overshooting and divergence.
For L-smooth convex functions, gradient descent is guaranteed to converge at a sublinear rate of $O (1/ T)$ with an appropriate step size (e.g., $α = 1/ L$ ).
For functions that are also $μ$ -strongly convex, convergence is much faster—a linear rate where the error is reduced by a constant factor at each step.
The convergence rate is heavily influenced by the condition number $κ = L / μ$ . Ill-conditioned problems ( $κ ≫ 1$ ) lead to slow, oscillating convergence, a phenomenon visualized by the "zigzag" path in narrow valleys.

You now have a solid theoretical foundation for the most fundamental optimization algorithm. You understand how it works, why it works (in an idealized setting), and what factors govern its performance.

In our next lesson, we will see how to improve upon the "vanilla" gradient descent. We will derive the momentum and Nesterov accelerated gradient updates, which are specifically designed to accelerate convergence, particularly in the ill-conditioned ravines that we have just analyzed.