Gradient Descent Update Rule

Hello! Welcome to your next lesson in the "Theory of Unconstrained Optimization" module.

Introduction

In our last session, we established a crucial theoretical guarantee: for any convex function, a local minimum is also a global minimum. This is a cornerstone of optimization because it assures us that if we find a valley, we've found the deepest valley.

Today, we address the natural follow-up question: how do we algorithmically find that minimum? We will answer this by deriving the update rule for gradient descent, arguably the most important and foundational iterative optimization algorithm in machine learning. This lesson is dedicated to rigorously deriving the famous update rule:

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \nabla f({\mathbf{x}}_k)$$

We will explore why moving in the direction of the negative gradient is the optimal local choice. This will connect the calculus you've been learning (gradients) with the practical goal of function minimization.

Part 1: The Principle of Steepest Descent

The core idea behind gradient descent is simple: to minimize a function, we should iteratively take small steps in the direction where the function's value decreases most rapidly. This is known as the direction of "steepest descent".

From your previous lessons on multivariate calculus, you'll recall that the gradient, $\nabla f(\mathbf{x})$, points in the direction of the steepest ascent of the function $f$ at point $\mathbf{x}$. It seems intuitive, then, that the direction of steepest descent would be its opposite, $-\nabla f(\mathbf{x})$. Let's prove this formally.

Our goal is to find a direction vector $\mathbf{d}$ (with unit norm, $\Vert \mathbf{d}{\Vert }_2=1$) that minimizes the function's value when we take an infinitesimally small step in that direction. We can analyze this using a first-order Taylor expansion around our current point $\mathbf{x}$:

$$f(\mathbf{x}+\alpha \mathbf{d})\approx f(\mathbf{x})+\alpha \nabla f(\mathbf{x}{)}^T\mathbf{d}$$

where $\alpha >0$ is a very small step size.

To decrease the function value, we want to make the change, $f(\mathbf{x}+\alpha \mathbf{d})-f(\mathbf{x})\approx \alpha \nabla f(\mathbf{x}{)}^T\mathbf{d}$, as negative as possible. Since $\alpha$ is a positive scalar, we need to minimize the dot product $\nabla f(\mathbf{x}{)}^T\mathbf{d}$.

The following document provides a concise and formal derivation of the direction that achieves this.

As the text shows, the inner product $\nabla f(\mathbf{x}{)}^T\mathbf{d}$ is minimized when $\mathbf{d}$ is in the direction of $-\nabla f(\mathbf{x})$. This confirms our intuition and formally establishes $-\nabla f(\mathbf{x})$ as the direction of steepest descent.

Part 2: Deriving the Update Rule

Now that we've established the direction, we can construct the full update rule. We start at a point ${\mathbf{x}}_k$ and move to a new point ${\mathbf{x}}_{k+1}$ by taking a step in the direction of the negative gradient.

This process is wonderfully explained in the following video, which uses a first-order Taylor series approximation to justify the update rule. The logic is very similar to what we just saw, but the step-by-step walkthrough is invaluable for cementing the concept.

The video, using single-variable notation for simplicity, shows that to guarantee a decrease in the function value (for a sufficiently small step), we must choose a direction $\mathbf{d}$ such that ${\mathbf{d}}^T\nabla f(\mathbf{x})<0$. The choice $\mathbf{d}=-\nabla f({\mathbf{x}}_k)$ makes this term $-\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2$, which is always negative unless the gradient is zero (meaning we are at a critical point).

Combining the direction $-\nabla f({\mathbf{x}}_k)$ with a step size parameter $\eta >0$ (also called the learning rate), we get the final update rule for gradient descent:

$${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \nabla f({\mathbf{x}}_k)$$

Part 3: An Alternative Derivation via Quadratic Approximation

There is another powerful way to derive this update rule, which is common in more advanced optimization literature. Instead of just finding the best direction, we build a simple local model of the function around our current point $\mathbf{x}$ and then find the exact minimum of that model.

We can approximate $f(\mathbf{y})$ for $\mathbf{y}$ near $\mathbf{x}$ using a quadratic model:

$$f(\mathbf{y})\approx f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{1}{2t}\Vert \mathbf{y}-\mathbf{x}{\Vert }_2^2$$

Here, the first two terms are the familiar linear Taylor approximation. The third term, $\frac{1}{2t}\Vert \mathbf{y}-\mathbf{x}{\Vert }_2^2$, is a proximity term. It penalizes moving too far from our current point $\mathbf{x}$. The parameter $t>0$ controls how much we trust our linear approximation; a small $t$ keeps $\mathbf{y}$ very close to $\mathbf{x}$.

To find the next iterate, we find the $\mathbf{y}$ that minimizes this entire quadratic approximation. This is an unconstrained quadratic optimization problem, which we can solve by setting its gradient (with respect to $\mathbf{y}$) to zero.

The following reading walks through this elegant derivation.

This second perspective is extremely valuable. It recasts gradient descent as a sequence of steps, where each step involves solving a very simple local approximation of the original, more complex problem.

Test your understanding!

In the second derivation, we approximated the function as $f(\mathbf{y})\approx f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{1}{2t}\Vert \mathbf{y}-\mathbf{x}{\Vert }_2^2$. The true second-order Taylor expansion is $f(\mathbf{y})\approx f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{1}{2}(\mathbf{y}-\mathbf{x}{)}^T{\nabla }^{2}f(\mathbf{x})(\mathbf{y}-\mathbf{x})$, where ${\nabla }^{2}f(\mathbf{x})$ is the Hessian matrix.

What matrix did we use to approximate the Hessian ${\nabla }^{2}f(\mathbf{x})$ in our quadratic model? What does this imply about the algorithm's knowledge of the function's curvature?

Show answer

We approximated the Hessian matrix ${\nabla }^{2}f(\mathbf{x})$ with $\frac{1}{t}\mathbf{I}$, where $\mathbf{I}$ is the identity matrix.

This implies that the basic gradient descent algorithm does not use any information about the function's true second-order structure or curvature (as captured by the Hessian). It implicitly assumes the curvature is uniform in all directions (isotropic). Algorithms that do use the Hessian, like Newton's method, can often converge much faster but at the cost of computing and inverting the Hessian at each step, which can be very expensive.

Part 4: The Critical Role of the Step Size

Both derivations implicitly assume a "small" step. The step size $\eta$ (or $t$ in the second derivation) is a hyperparameter that you must choose. Its value is critical for the algorithm's performance.

As you heard, selecting a good step size is a non-trivial problem. We will revisit this when we analyze the convergence properties of gradient descent in a future lesson.

Conclusion

Today, we have rigorously derived the gradient descent update rule from first principles. This is the mechanism that powers the training of a vast number of machine learning models.

Key Takeaways:

• The direction of steepest descent of a function is the negative of its gradient, $-\nabla f(\mathbf{x})$.
• We derived the gradient descent update rule, ${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \nabla f({\mathbf{x}}_k)$, by formalizing the idea of taking a small step in this direction.
• We explored two formal derivations: one based on minimizing the first-order Taylor approximation, and another based on minimizing a local quadratic model of the function.
• The step size (or learning rate) $\eta$ is a crucial hyperparameter that balances convergence speed with the risk of overshooting the minimum.

Preview of the Next Lesson:
With the theory now firmly in place, our next step is to bring it to life. In the next lesson, you will implement the gradient descent algorithm in Python to find the minimum of a simple convex function. This will connect the mathematical derivations from today's lesson directly to your practical programming experience.