Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 38 · Applications in Machine Learning

Ridge Regression as an Optimization Problem

Treat ridge regression as a strongly convex problem: derive the closed-form solution, solve it with gradient descent, and see how the penalty stabilizes correlated features.

Ordinary least squares chooses weights w that minimize the squared error ½‖Xw − y‖². It works well when features are independent and plentiful. But with strongly correlated features or few samples, the solution becomes unstable: a tiny change in the data can flip the weights from large positive to large negative. Ridge regression fixes this by adding a penalty on the size of the weights:

Text
minimize over w    ½ ‖X w − y‖² + (λ/2) ‖w‖²         (λ > 0)

This is a convex optimization problem with a special bonus: it is strongly convex, so the minimizer exists, is unique and is found quickly. In this lesson you solve it three ways and watch what the penalty does.

Why it is strongly convex

The Hessian of the objective is H = XᵀX + λI. The matrix XᵀX is positive semidefinite (all eigenvalues ≥ 0), so every eigenvalue of H is at least λ > 0. A function whose Hessian is always at least λI is λ-strongly convex. Two consequences:

  • The solution is unique, even if X has dependent columns or fewer rows than columns.
  • Gradient descent converges geometrically, at a rate tied to the condition number κ = (σ_max² + λ) / (σ_min² + λ) of H, where σ are the singular values of X. Larger λ means smaller κ and faster convergence.

The closed-form solution

Set the gradient to zero: Xᵀ(Xw − y) + λw = 0. Then:

Text
w_ridge = (XᵀX + λI)⁻¹ Xᵀ y

Notice that XᵀX + λI is always invertible when λ > 0. In practice, solve the linear system (np.linalg.solve) rather than forming the inverse.

Three ways to solve it

We build a dataset with 100 samples and 8 features, where two columns are nearly copies of each other (a typical cause of instability).

Python Closed form, gradient descent and the augmented trick

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.

The three answers agree. Method 3 shows an elegant fact: ridge is ordinary least squares on a dataset with d extra "pseudo-samples" that pull each weight toward zero.

Also note how much the penalty lowers the condition number. Gradient descent on plain least squares would be far slower on this data.

What the penalty does to the weights

As λ grows, the weights shrink toward zero (but never reach it exactly). Small λ gives a low training error but wild weights on the near-duplicate columns. Large λ shrinks everything and increases bias. The best λ balances the two, which we measure on held-out data.

Python Shrinkage and held-out error

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.

Look at w[0] and w[1], the nearly identical columns. With almost no penalty, the weights are huge and have opposite signs (about -31 and +32), because only their sum is well determined by the data. With λ = 1 they become nearly equal (about 0.8 and 0.9), splitting the shared effect evenly, which is far more sensible. Training error rises steadily with λ. In this particular run the validation error is also smallest for the tiniest λ: the huge opposite weights cancel on data that has the same near-duplicate structure. The gain from ridge here is stable, interpretable weights, and it would show as lower error if the validation columns stopped being near-copies. On other datasets a moderate λ often gives the lowest validation error, so always choose λ by validation.

Always standardize features (zero mean, unit variance) before using a penalty. Otherwise a feature measured in tiny units would need a huge weight and be penalized unfairly. Do not penalize the intercept; center y and the features instead.

Ridge as a constrained problem

Penalty form and constraint form are two views of one thing. By Lagrangian duality, for every λ > 0 there is a radius r such that the ridge solution also solves:

Text
minimize  ½ ‖X w − y‖²    subject to  ‖w‖² ≤ r²

The multiplier of this constraint is λ/2. Bigger λ means a smaller ball, and (by the sensitivity lesson) tells how much error you save per unit of extra budget in the ball.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Why does ridge regression always have a unique solution when λ > 0?

    All eigenvalues of XᵀX + λI are at least λ, which makes the objective strongly convex with a single minimizer.
  2. 2. What is the closed-form ridge solution?

    Setting the gradient Xᵀ(Xw − y) + λw to zero gives this formula.
  3. 3. What happens to the weights as λ increases?

    The L2 penalty shrinks all weights smoothly. Exact zeros come from the L1 penalty (the lasso).
  4. 4. How does a larger λ affect gradient descent on ridge?

    Adding λ to every eigenvalue shrinks the ratio between the largest and smallest curvature.

Summary

  • Ridge minimizes ½‖Xw − y‖² + (λ/2)‖w‖², a strongly convex problem with a unique solution.
  • Closed form: w = (XᵀX + λI)⁻¹ Xᵀ y; gradient descent also works, faster with larger λ.
  • Ridge equals least squares on augmented data and also the constrained problem ‖w‖ ≤ r.
  • The penalty stabilizes correlated features; choose λ using validation data.

Next: The Lasso and Sparsity