Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 39 · Optimization in Several Variables

Least Squares and Gradient Descent

Fit a line to data by minimizing the sum of squared errors, solve it exactly with partial derivatives, and then find the same answer with gradient descent.

One of the most useful optimization problems in science is also a two-variable calculus problem: fit a straight line to scattered data. The "best" line is the one that makes the total squared error as small as possible. Finding it is a direct application of critical points, and it leads naturally to gradient descent, the workhorse of machine learning.

The error function

Suppose you have data points (x₁, y₁), ..., (xₙ, yₙ) and you want a line y = m x + b. For any choice of slope m and intercept b, the sum of squared errors is

Text
E(m, b) = Σ (yᵢ - (m xᵢ + b))²

E is a function of two variables, m and b. Smaller E means a better fit. Squaring makes every error count positively and punishes big misses more than small ones. It also makes E smooth, so calculus applies.

Solving with partial derivatives

Set both partial derivatives to zero:

Text
∂E/∂m = -2 Σ xᵢ (yᵢ - m xᵢ - b) = 0
∂E/∂b = -2 Σ    (yᵢ - m xᵢ - b) = 0

Rearranged, these are the normal equations:

Text
m Σxᵢ² + b Σxᵢ = Σxᵢyᵢ
m Σxᵢ  + b n   = Σyᵢ

That is a 2 × 2 linear system with a unique solution whenever the x values are not all equal. The Hessian of E is 2 · [[Σx², Σx], [Σx, n]], whose determinant is positive (by the Cauchy-Schwarz inequality) and whose top-left entry is positive, so by the second derivative test the critical point is a minimum. In fact it is the global minimum, because E is a bowl-shaped (convex) quadratic.

Python Normal equations from scratch, checked against NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods should agree, and nudging the slope away from the solution should increase E.

Gradient descent

Normal equations work well for lines. For huge models with millions of parameters, there is no neat closed form. Gradient descent needs only the gradient.

Remember from earlier that ∇E points in the direction of steepest increase. So moving the opposite way lowers E fastest. The update rule is

Text
(m, b)  ←  (m, b) - η ∇E(m, b)

where η (eta) is the learning rate, a small positive step size. Repeat until the gradient is nearly zero.

For our error function, ∇E = (-2 Σ xᵢ rᵢ, -2 Σ rᵢ) with residuals rᵢ = yᵢ - m xᵢ - b.

flowchart LR
    A["Start with a guess (m, b)"] --> B["Compute gradient of E"]
    B --> C["Step downhill: subtract η times gradient"]
    C --> D{"Gradient small?"}
    D -- "no" --> B
    D -- "yes" --> E["Stop: near the minimum"]

Gradient descent loops: compute the slope of the error surface and step downhill until it flattens.

Python Gradient descent for the line fit

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If it looks slow, raise the number of steps. The rate of convergence depends on how stretched the bowl is.

Choosing the learning rate

The step size η matters a lot:

  • Too small: the descent crawls and needs many steps.
  • Just right: it homes in on the minimum quickly.
  • Too large: each step overshoots, the error grows and the iteration diverges.

You can see this directly. Try several values of η and record the final error.

Python Learning rates: slow, good and too big

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the largest rate the error should blow up, showing divergence. A rule of thumb for quadratic bowls: the step must be smaller than 2 divided by the largest eigenvalue of the Hessian.

Beyond lines

The same pattern fits curves such as y = a x² + b x + c, planes in many variables, and even neural networks. In every case:

  1. Define an error function of the parameters.
  2. Compute its gradient (by hand, with SymPy, or automatically).
  3. Step downhill, or solve ∇E = 0 exactly if the structure allows.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Why do we square the errors in E(m, b)?

    Squaring prevents positive and negative errors from cancelling, penalizes large misses and leaves a smooth function.
  2. 2. In gradient descent, which way do you move?

    The gradient points toward steepest increase, so subtracting it moves toward steepest decrease.
  3. 3. What happens if the learning rate η is too large?

    Overshooting the bottom of the bowl can make each step land higher than the last, so the iteration diverges.
  4. 4. The normal equations come from setting what to zero?

    Setting ∂E/∂m = 0 and ∂E/∂b = 0 finds the critical point of the error function, which is the global minimum.

Summary

  • Fitting a line means minimizing E(m, b) = Σ(yᵢ - m xᵢ - b)².
  • Setting both partial derivatives to zero gives the normal equations, a linear system.
  • The solution is the global minimum because the Hessian is positive definite.
  • Gradient descent repeats p ← p - η ∇E and reaches the same answer without solving equations.
  • The learning rate must be chosen with care: too small is slow, too large diverges.

Next: Double Integrals over Rectangles