Least Squares: gradient descent

The normal equations give us a beautiful closed-form answer, but they are not always the most practical way to solve a least squares problem. When the dataset is huge, when the number of variables is very large, or when we want to update a model gradually as new data arrive, an iterative method can be more useful [1],[2].

Gradient descent is the simplest iterative idea: start somewhere, look at the direction in which the error increases most quickly, and move the other way.

In other words: walk downhill.

The error surface

For linear least squares, we want to minimize:

If there is only one parameter, this error is a curve. If there are two parameters, it becomes a surface. With many parameters, it lives in a space we cannot draw, but the same idea remains: every possible set of parameters has an associated error.

The interactive plot below starts with the simplest possible case. The algorithm moves along a curve until it reaches the bottom:

Now we can make the picture a little closer to a real linear regression, with slope and intercept as two parameters. The error becomes a bowl-shaped surface. Click on the plot to choose a starting point and watch how the path descends toward the minimum:

This bowl shape is important. Ordinary linear least squares is convex, so there is one global minimum. Gradient descent does not have to worry about hidden local valleys in this case [2].

The gradient

The gradient is a vector of derivatives. It tells us which direction makes the function increase fastest.

For the least squares objective:

the gradient is:

That vector points uphill. Since we want to minimize the error, we move in the opposite direction:

This is the whole intuition of gradient descent.

The update rule

We start with an initial guess:

Then we update the parameters step by step:

Here, $k$ is the iteration number and $\alpha$ is the step size, often called the learning rate [1].

For linear least squares, substituting the gradient gives:

This equation says: compute the residuals, translate them into a direction in parameter space, and take a step that reduces the error.

Choosing the step size

The step size $\alpha$ controls how boldly the algorithm moves.

• If $\alpha$ is too small, convergence is painfully slow.
• If $\alpha$ is too large, the algorithm can jump over the minimum and oscillate.
• If $\alpha$ is well chosen, the path descends smoothly.

For simple least squares problems, it is sometimes possible to calculate a good step size analytically. In practice, many algorithms use line search or adaptive learning-rate rules.

When gradient descent is useful

Gradient descent is not the fastest method for a small calibration curve. If you have ten standards and one predictor, the normal equations will solve the problem immediately.

Gradient descent becomes more interesting when:

• The dataset is too large to process comfortably in one matrix operation.
• The number of variables is very high, as in full-spectrum modeling.
• The objective includes extra penalty terms, such as in regularized regression.
• New data arrive continuously and the model needs to update over time.

In modern machine learning, gradient descent is everywhere. But its roots are older and very close to the least squares problem itself [1],[2].

What it gives up

Gradient descent trades exact one-step algebra for flexibility. It needs a starting point, a step-size rule, and a stopping criterion. It may require many iterations. But in return, it can handle problems where direct methods are too expensive or inconvenient.

The key idea is modest but powerful: we do not need to solve everything at once. Sometimes we can get there by improving the answer, one step at a time.

References