Gradient Descent
Learning Objectives
After reading this page, you should be able to:
- Explain the intuition behind the gradient descent update rule.
- Explain termination criteria and methods for selecting learning rate for gradient descent.
- Derive the vectorized gradient descent updates for variants of linear regression.
1 Introduction
As we saw in the previous section, learning a linear regression predictor relies on turning the learning problem into an optimization problem (Fundamental Idea #1). Being able to solve optimization problems of this kind is therefore extremely important in Machine Learning.
The previous section also showed one approach to solving this particular optimization problem, called the direct solution approach. This approach directly finds a minimum of the objective function \(\mathcal{E}(\textbf{w})\) by setting its gradient with respect to the weights equal to the zero vector and solving for the critical points of the objective function algebraically.
This direct solution approach has two limitations. First, for many models, the critical points of the objective function have no closed-form solution, so we cannot solve for it algebraically. Second, even for linear regression, where a closed-form solution does exist, the matrix inversion operation from the previous page becomes expensive as the number of features grows.
For these reasons, we will explore a more general and scalable optimization approach that will generalize to more complex models that we will study later.
2 Gradient Descent in 1D
Suppose you are standing at the top of a mountain in the fog. Your car is at the lowest point in the valley. What is a good strategy for getting back to the car? What you might naturally do at this point is feel around with your feet, and using that local information, take a step in the direction of steepest descent. You might then repeat this process: feel around again, since the steepest descent direction could have changed, and take another step. And another. Until you reach your car.
Gradient descent is an iterative method to find a minimum of a function, and it does exactly that: we start from an initial “guess” \(w_0\) of where a minimum might be (or, realistically, just a random point), and iteratively move towards the “downhill direction”.
This last part of “iteratively moving towards the downhill direction” requires some thought in order to operationalize into a concrete algorithm. To help us develop intuition for gradient descent, let’s start by “deriving” gradient descent for a scalar function \(J(w): \mathbb{R} \rightarrow \mathbb{R}\), shown below. This function has a unique local minimum at \(w = w^*\). Our intuition will generalize to more complex functions.
Scalar objective \(J(w)\)
In order to operationalize this procedure into a concrete algorithm, we need to answer two questions.
- What is the downhill direction at each point? (direction of the update)
- How large of a step should we take at each point? (step size of the update)
Both questions can be answered by considering the derivative at a point, \(J'(w)\).
Direction of update. Consider the two points in Figure 2: \(w_0\) (orange) and \(w_0'\) (blue).
Points on either side of the minimum
Question: At \(w = w_0\) (orange), is the derivative of \(J(w)\) positive or negative? To minimize \(J(w)\), should we move \(w\) to the positive or negative direction?
Answer:
At \(w = w_0\), the derivative of \(J(w)\) is negative. We should move \(w\) in the positive direction.
Question: At \(w = w_0'\) (blue), is the derivative of \(J(w)\) positive or negative? To minimize \(J(w)\), should we move \(w\) to the positive or negative direction?
Answer:
At \(w = w_0'\), the derivative of \(J(w)\) is positive. We should move \(w\) in the negative direction.
Summarizing the observations from the two exercises, we conjecture that the downhill direction is the opposite of the sign of the gradient. This is indeed the case since the gradient points in the steepest uphill direction.
Step size of update. Consider, now, the two points in Figure 3: \(w_0\) (orange) is far from \(w^*\) where the curve is steep, and \(w_0'\) (blue) is close to \(w^*\) where the curve is nearly flat.
Gradient magnitude near and far from the minimum
Question: Would you want a larger update toward the minimum at \(w_0\) (orange) or \(w_0'\) (blue)? Where is the magnitude of the derivative \(J'(w)\) larger?
Answer:
We would want a larger step at \(w_0\), where \(J'(w)\) is larger.
Summarizing this observation, it would make sense for the magnitude of the update to be proportional to the magnitude of the gradient. This observation leverages the fact that \(J'(w) = 0\) at the minimum, so for functions with continuous derivatives, \(J'(w)\) approaches \(0\) near the minimum.
Now, we are ready to formally define the gradient descent update rule minimizing a scalar function.
Definition: The gradient descent optimization algorithm for minimizing a scalar function \(J(w): \mathbb{R} \rightarrow \mathbb{R}\) involves the following steps:
- Initialize \(w = w_0\) as the starting point
- Repeatedly apply the update rule \(w \leftarrow w - \alpha J'(w)\) until a stopping criterion is met. The term \(\alpha \in \mathbb{R}\) is the learning rate.
Definition: Each application of the gradient descent update rule is one iteration.
Definition: In the gradient descent update rule, the value \(\alpha \in \mathbb{R}\) is called the learning rate.
In typical machine learning problems, \(\alpha\) is set between \(<0.001\) and \(0.1\), but specific problems will have their own optimal value that may require tuning. We will come back to the question of tuning the learning rate later in this page.
The figure below shows how the gradient descent algorithm works on the function \(J(w)\) from above. You should see that as we get closer to the minimum, steps get smaller and the algorithm converges. Try setting \(w_0\) to different values to see the effect of different initial values.
Interactive 1D gradient descent
Step: 0 Initial \(w_0\): -1.0 (= 0.15)
3 Gradient Descent
When minimizing functions \(J(\mathbf{w}): \mathbb{R}^D \rightarrow \mathbb{R}\) with vector inputs \(\mathbf{w} = [w_1, w_2, \dots, w_D]^{\top}\),
we can continue to use a similar idea: start somewhere, and iteratively move “downhill”, in the direction of the steepest descent.
But which direction is the “steepest descent”? We leverage results from multivariate calculus, which tell us that if \(J\) is differentiable at \(\mathbf{w}\) then the direction of the steepest ascent is exactly the gradient \(\nabla_{\mathbf{w}} J(\mathbf{w})\). So the direction of the steepest descent is \(-\nabla_{\mathbf{w}} J(\mathbf{w})\). Recall that the notation \(\nabla_{\mathbf{w}} J(\mathbf{w})\) is defined as follows: \[\begin{align*} \nabla_{\mathbf{w}} J(\mathbf{w}) = \begin{bmatrix} \frac{\partial J}{\partial w_1} \\ \frac{\partial J}{\partial w_2} \\ \vdots \\ \frac{\partial J}{\partial w_D} \end{bmatrix}. \end{align*}\]
(The full argument is outside the scope of the course, and requires a concept from multivariate calculus called the directional derivative. The directional derivative of \(J\) at \(\mathbf{w}\) in a unit direction \(\mathbf{u}\) is \(D_{\mathbf{u}} J(\mathbf{w}) = \nabla J(\mathbf{w}) \cdot \mathbf{u}\). Among all unit vectors \(\mathbf{u}\), this inner product is maximized when \(\mathbf{u} = \nabla J(\mathbf{w})\).)
We now define the general gradient descent algorithm:
Definition: The gradient descent optimization algorithm for minimizing a function \(J(\mathbf{w}): \mathbb{R}^D \rightarrow \mathbb{R}\) involves the following steps:
- Initialize \(\textbf{w} \in \mathbb{R}^D\) to some initial value
- Repeatedly apply the following update rule until a stopping criterion is met: \[\textbf{w} \leftarrow \textbf{w} - \alpha \nabla_{\textbf{w}} J(\textbf{w})\]
Question: Write out the scalar components in the (vectorized) gradient descent update rule \(\textbf{w} \leftarrow \textbf{w} - \alpha \nabla_{\textbf{w}} J(\textbf{w})\)
Answer:
\[\begin{align*} \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_D \end{bmatrix} &= \begin{bmatrix} w_1 - \alpha \frac{\partial J}{\partial w_1} \\ w_2 - \alpha \frac{\partial J}{\partial w_2} \\ \vdots \\ w_D - \alpha \frac{\partial J}{\partial w_D} \end{bmatrix} \end{align*}\] Note that the updates all happen simultaneously (not one coordinate at a time, otherwise earlier updates would affect where \(\frac{\partial J}{\partial w_j}\) is computed). The same \(\alpha\) is used for all components of \(\textbf{w}\).Again, it is helpful to develop intuition in low dimensions. Figure 5 shows gradient descent for minimizing a function \(J: \mathbb{R}^2 \rightarrow \mathbb{R}\). One useful way to visualise the landscape of a 2D function \(J(w_1, w_2)\) is a contour plot. Each curve in the plot connects all points \((w_1, w_2)\) where \(J\) takes the same value, analogous to elevation contours on a topographic map. In this case, moving inward toward the centre of the “bulls-eye” pattern corresponds to decreasing loss. Press Step to watch the path descend toward the minimum.
Interactive 2D gradient descent
Step: 0 Initial \(w_1\): 0.5 Initial \(w_2\): 2.5 (= 0.1)
Notice how, in the above figure, each arrow cuts across the contours perpendicularly. A key geometric fact from multivariate calculus is that the gradient \(\nabla_{\mathbf{w}} J\) is always perpendicular to the contour lines. Because gradient descent steps in the direction \(-\nabla_{\mathbf{w}} J\), each update crosses the contour lines at a right angle, always pointing in the direction of the steepest descent. The proof of this is beyond the scope of this course.
4 Gradient Descent for Linear Regression
Let’s apply gradient descent to linear regression. Our goal is to find the weights \(\mathbf{w}\) that minimize the cost function \(\mathcal{E}(\mathbf{w})\). The previous page showed that the cost function for linear regression with squared loss has the following vectorized form: \[ \mathcal{E}(\mathbf{w}) = \frac{1}{2N} \lVert \mathbf{X} \mathbf{w} - \mathbf{t} \rVert_2 ^2 = \frac{1}{2N} (\mathbf{X} \mathbf{w} - \mathbf{t})^\top (\mathbf{X} \mathbf{w} - \mathbf{t}) \]
The gradient of the cost function has the following vectorized form:
\[ \nabla_{\mathbf{w}} \mathcal{E}(\mathbf{w}) = \frac{1}{N} \mathbf{X}^\top (\mathbf{X} \mathbf{w} - \mathbf{t}) \]
We use the same gradient descent update as earlier on this page, \[ \mathbf{w} \leftarrow \mathbf{w} - \alpha \nabla_{\mathbf{w}}\mathcal{E}(\mathbf{w}), \] where \(\nabla_{\mathbf{w}}\mathcal{E}(\mathbf{w})\) is the gradient evaluated at the current parameters and \(\alpha\) is the learning rate that controls the scale of each update.
Substituting the vectorized gradient above yields the vectorized update \[ \mathbf{w} \leftarrow \mathbf{w} - \frac{\alpha}{N} \mathbf{X}^{\top} (\mathbf{X} \mathbf{w} - \mathbf{t}). \]
Definition: The gradient descent update rule for linear regression is \[ \mathbf{w} \leftarrow \mathbf{w} - \frac{\alpha}{N} \mathbf{X}^{\top} ( \mathbf{X} \mathbf{w} - \mathbf{t} ), \] where
- \(\mathbf{w} \in \mathbb{R}^{(D+1) \times 1}\) is the vector of weights (including the bias term),
- \(\alpha > 0\) is the learning rate,
- \(N\) is the number of training examples,
- \(\mathbf{X} \in \mathbb{R}^{N \times (D+1)}\) is the design matrix (each row is the feature vector for one training example),
- \(\mathbf{t} \in \mathbb{R}^{N \times 1}\) stacks the scalar targets \(t^{(i)}\).
5 Considerations
Gradient descent is a simple optimization method, but its use requires several considerations.
5.1 Learning Rate
The learning rate \(\alpha\) scales how far each step moves along the direction of the steepest descent. The choice of \(\alpha\) is an important consideration:
- If \(\alpha\) is too small, each step is conservative and training can require many iterations.
- If \(\alpha\) is too large, updates can actually overshoot a minimum. That is, an update can go so far past the minimum that the gradient magnitude is larger at this new point than the original! This pattern continues, and we move further away from the minimum.
The figure below shows what happens if we choose different values of \(\alpha\). In practice, we run gradient descent for thousands of iterations (sometimes more), not just a few.
Learning rate comparison
In practice, good choices of \(\alpha\) need to be determined empirically. We typically do so by examining the training curve.
Definition: The training curve is a plot of the training cost as a function of iteration count. It is used to monitor whether gradient descent is converging and to diagnose problems with the learning rate.
Figure 7 shows the effect of the learning rate on the training curve.
Training curves for different learning rates
5.2 Stopping Criteria
The gradient descent algorithm does not specify a stopping criterion. In theory, one would like to stop when the parameters have converged, i.e., when \(\mathbf{w}\) barely changes from one iteration to the next. For low-dimensional problems, where the number of scalar parameters in \(\mathbf{w}\) is low, this is tractable. In practice, \(\mathbf{w}\) can be large and changes in \(\mathbf{w}\) can be difficult to track.
In practice, we use a different notion of convergence, and track the training cost \(\mathcal{E}\). We stop when the improvement in \(\mathcal{E}\) falls below a threshold, that is, when the training cost has converged.
Alternatively, we may only be able to run gradient descent for a fixed number of iterations due to time or resource constraints. This is especially relevant for models that are large, or where the input is large (e.g., videos).
5.3 Local vs Global Minima
Gradient descent uses only local information about the function. Thus, gradient descent is only able to find local minima, not necessarily the global minimum. Moreover, different initializations can lead to convergence to different minima. There is no guarantee that the minimum found with gradient descent is the “best” or even a “good” minimum. In practice, this is a workable limitation: we generally want to find hypotheses (ML models) that are “good enough”; the true evaluation of these hypotheses is multifaceted and goes beyond the achievement of the lowest training loss.
However, the situation for linear regression with squared error is much nicer. Since the mean squared error as a function of \(\mathbf{w}\) is convex (a bowl-shaped quadratic), it has only a single minimum. Thus, gradient descent will find the global minimum given enough iterations.
5.4 Feature Scaling
Before running gradient descent, it is common to put input features on comparable scales (for example by standardizing columns of the design matrix).
When one feature dominates others in magnitude, its partial derivatives inflate and the loss surface forms a ravine: steep in one direction and nearly flat in the other. Gradient descent then tends to zig-zag across the narrow dimension while making very slow progress along the valley floor.
For example, consider fitting \(y = x_1 w_1 + x_2 w_2\) to a dataset where \(x_1\) is in the hundreds and \(x_2\) is on the order of thousandths:
| \(x_1\) | \(x_2\) | \(t\) |
|---|---|---|
| 114.8 | 0.00323 | 5.1 |
| 338.1 | 0.00183 | 3.2 |
| 98.8 | 0.00279 | 4.1 |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
Since \(\frac{\partial \mathcal{L}}{\partial w_1} = x_1(y - t)\) and \(\frac{\partial \mathcal{L}}{\partial w_2} = x_2(y - t)\), the gradient component for \(w_1\) is roughly \(100{,}000\times\) larger than for \(w_2\), even if both weights need equal adjustment. This creates a wildly elongated loss surface; Figure 8 illustrates the effect.
Effect of feature scaling
Normalizing inputs (for example by subtracting the mean and dividing by the standard deviation, i.e. standardization) yields a gentler optimization landscape where a single \(\alpha\) often behaves more reliably and convergence can speed up materially. Note that only the input features need to be standardized; the target \(\mathbf{t}\) can remain in its original units.
However, standardization alone does not guarantee a well-conditioned loss surface. If two features are highly correlated, for example if both measure nearly the same underlying quantity, their weights trade off almost identically in the model. The loss surface forms an elongated ravine rotated at 45° in weight space, and gradient descent zig-zags across it just as before, even after both columns have been standardized.
For instance, consider a dataset where \(x_1\) and \(x_2\) track each other closely:
| \(x_1\) | \(x_2\) | \(t\) |
|---|---|---|
| 1003.2 | 1005.1 | 3.3 |
| 1001.1 | 1008.2 | 4.8 |
| 998.3 | 1003.4 | 2.9 |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
After standardizing both columns, \(w_1\) and \(w_2\) still trade off nearly identically in the model prediction. The loss surface is still an elongated ravine, just now rotated 45 degrees in weight space, along the \(w_1 = w_2\) diagonal. Figure 9 illustrates the effect.
Correlated features after standardization
6 Summary
Gradient descent is a foundational algorithm in machine learning. Its core idea is to iterate in the direction of steepest descent until convergence, is simple enough to state in one line, yet powerful enough to train models with billions of parameters.
This chapter is a clear illustration of Fundamental Idea #1: Learning is Optimization. For linear regression we derived a closed-form solution, but that approach only works when the loss is algebraically tractable. Gradient descent provides a general optimization strategy that applies to any differentiable loss, regardless of whether a closed-form solution exists.
Fundamental Idea #4 (ML Describes Geometric Processes) runs throughout the chapter. Thinking geometrically helps us develop intuition about the algebraic operations. We considered both plots for 1D functions \(J(w)\), and contour plots for \(J(w_1, w_2)\). The gradient is always perpendicular to the contour lines, so gradient descent traces the steepest-descent trajectory on this landscape. The geometry of that landscape, a circular bowl, an elongated ravine, or a rotated ellipse, directly determines how quickly and smoothly convergence happens. Feature scaling is therefore a geometric intervention: by reshaping the loss surface into something “rounder”, we make gradient descent behave better.
More importantly, we used these contour plots to understand the shape of the loss surface in the weight space. We saw that each point in this weight space actually represents a hypothesis: a mapping of inputs (in the data space) to target outputs. Our contour plots and optimization methods rely on the geometry of the weight space: we iteratively change hypotheses to ones nearby that are “better”.