Comparing optimizers for ridge regression

Ridge regression has an analytical solution. So why would you ever use an iterative optimizer on it?

The honest answer is: you probably wouldn’t in practice. But working through all four paths — exact solution, scipy minimizers, hand-rolled gradient descent, and gradient descent with Armijo line search — on the same synthetic dataset exposed something that’s easy to miss when you only ever reach for the closed form: the choice of optimizer matters a lot for how quickly you can iterate on related problems that don’t have closed forms.

The setup

120 predictor variables, 1000 observations, coefficients drawn uniformly from [-5, 5]. Ridge regression with a fixed penalty ρ. The closed-form solution is:

β̂ = (XᵀX + ρI)⁻¹ Xᵀy

That’s the ground truth. Everything else is trying to hit the same target iteratively.

Scipy minimizers: four bets

Using scipy.optimize.minimize, I tried Nelder-Mead, CG (conjugate gradient), BFGS (quasi-Newton), and Newton-CG — each seeded at the same starting point, each minimizing the same ridge objective.

BFGS converged to the lowest objective function value across all four. The ranking by final error was roughly: BFGS ≈ Newton-CG > CG > Nelder-Mead. Nelder-Mead was the slowest by a large margin — it doesn’t use gradient information at all, so in 120 dimensions it’s navigating nearly blind.

The practical takeaway: when you have a differentiable objective and can supply (or approximate) a gradient, quasi-Newton methods like BFGS win handily. They’re also what most production ML libraries use under the hood.

Hand-rolled gradient descent

Implementing gradient descent from scratch makes clear what BFGS is doing for you. The gradient of the ridge objective is:

def gradient(beta, X, y, rho):
    return -2 * X.T @ (y - X @ beta) + 2 * rho * beta

With a fixed step size α, convergence is sensitive — too large and it oscillates, too small and it crawls. After ~500 iterations with a carefully chosen α, it hit objective values comparable to CG but nowhere near BFGS.

Armijo line search

The fix for the step-size problem is a line search that adapts α at each iteration: try a step, check if the objective decreased enough (the Armijo condition), backtrack and halve α if not.

With Armijo, gradient descent became significantly more robust — fewer iterations to convergence and less sensitivity to the initial α. It still didn’t match BFGS on raw speed-to-solution, but it got close, and more importantly it never diverged.

The lesson from implementing both: fixed learning rates are for debugging. For any real problem, use at minimum a backtracking line search. The extra bookkeeping per step is trivially cheap compared to the cost of tuning a fixed rate.

Full notebook: Optimization.md