Convex optimisation and regularisation: gradient descent, step size, ridge and lasso

Convexity: why a zero gradient is enough

A convex function is a bowl with a single bottom, so the point where the slope vanishes is the best point there is.

A function is convex when the segment joining any two points of its graph never dips below the graph. Least squares and the logistic log-loss are convex; the loss of a neural network is not, and can trap a descent in a local dip. Everything in this session assumes the convex case.

Subtract $f(x)$, divide by $t > 0$ and let $t$ tend to zero: the chord inequality becomes the tangent inequality. The curve lies above every one of its tangents. This is the form used all morning.

If the gradient is zero at $x^\star$, the linear term disappears and $f(y) \ge f(x^\star)$ for every $y$. A stationary point of a convex function is therefore a global minimum. That is why the normal equations of the previous session were enough. The least-squares Hessian is $2X^{\T}X$, and $v^{\T}X^{\T}Xv = \lVert Xv \rVert^2 \ge 0$, so linear regression is convex.

The running example of the deck is the bowl $f(w) = (w - 3)^2 + 1$. Its slope $2(w - 3)$ is negative left of 3, zero at 3, positive to the right, and the height is smallest exactly where the slope vanishes. Two constants then describe the shape of any bowl: $L$, the largest curvature, and $\mu$, the smallest. For a quadratic they are the extreme eigenvalues of the Hessian, and their ratio $\kappa = L/\mu$ is the condition number met with the SVD.

Back to contents.

Gradient descent and the step size η

Feel the slope, step downhill, repeat: the only real decision is how long each step is, and a step too long makes things worse.

The gradient points uphill, so we walk the other way. Among all directions of a given length, the Cauchy-Schwarz inequality shows that $-\nabla f$ decreases $f$ fastest to first order. The step length is the learning rate $\eta$.

If the curvature never exceeds $L$, the function stays under a parabola of curvature $L$ (the descent lemma, admitted in the deck). Plugging the step into it gives a guaranteed decrease as long as $\eta < 2/L$.

On a quadratic the picture is exact. In the eigenbasis of the Hessian, each coordinate of the gap to the minimum is multiplied by $1 - \eta\lambda_i$ at each step. Every factor must have modulus below 1, and the largest eigenvalue gives the tightest constraint: $\eta < 2/L$. The step $\eta = 1/L$ removes the steepest direction in one move.

Same bowl, same start, four step sizes (here 1/L = 0.5 and 2/L = 1)

1. η = 0.25. Factor 0.5: the iterates 1.5, 2.25, 2.625 approach 3 from one side.
2. η = 0.5. Factor 0: the first step lands on 3 and stays there.
3. η = 0.75. Factor −0.5: 4.5, 2.25, 3.375, the descent overshoots and comes back, but still converges.
4. η = 1.2. Factor −1.4, beyond 2/L: 7.2, −2.88, 11.23, each step jumps further away. This is the training run whose loss turns into NaN.

Back to contents.

Why the condition number decides the speed

In a long narrow valley the step must be small for the steep side, so progress along the flat floor is slow; rescaling the variables rounds the valley.

With $\eta = 1/L$ the steep direction is settled at once and the flat direction sets the pace: its factor is $1 - \mu/L = 1 - 1/\kappa$. Dividing the gap by ten therefore costs about $2.3\,\kappa$ iterations.

The deck checks this on least squares with four observations and two correlated columns. The Hessian of the mean loss has eigenvalues 1 and 4, so $L = 4$, $\kappa = 4$ and $\eta = 0.25$. From the second iteration on, each gap to the solution is exactly 0.75 times the previous one, and $\ln 10 / (-\ln 0.75) \approx 8$ iterations divide it by ten.

The consequence is practical. A column in euros next to a column in years makes $\kappa$ enormous: on the credit-default data of the course, the deck reports a condition number of about $4 \cdot 10^{12}$ for the raw columns of the logistic Hessian, against about 300 after centring and scaling, computed on its 18,000-row training split. Standardising is the cheapest acceleration there is. Its mean and standard deviation come from the training set only, otherwise the validation and test sets leak into the model.

Back to contents.

Stochastic gradient, momentum and Adam

Using the slope of a few random observations instead of all of them makes each step far cheaper, at the price of some noise.

The loss is an average of $n$ individual losses, so its gradient is the average of $n$ individual gradients. Stochastic gradient descent (SGD) uses one of them, drawn at random: on average it is the right direction, and one step costs $n$ times less. A mini-batch of $B$ observations keeps the estimate unbiased and divides its variance by $B$.

With a fixed step the noise never dies and the iterates keep circling around the minimum. Robbins and Monro (1951) gave the conditions on a decreasing step: $\sum \eta_k = \infty$ so that the walk can go anywhere, $\sum \eta_k^2 < \infty$ so that the noise fades. On the deck's two-variable example the four individual gradients at the origin differ, but their mean is the full gradient $(-3.5, -4.5)$, with a spread $\sigma^2 = 10$.

Two refinements close the first half. Momentum (Polyak, 1964) accumulates past gradients: in the steep direction they alternate in sign and cancel, along the floor they add up. Adam (Kingma and Ba, 2015) adds a step per coordinate, scaled by a running average of squared gradients, which acts as an automatic standardisation. It is the default for neural networks, but it carries no convergence guarantee in the convex case; for a logistic regression, plain descent or L-BFGS is enough.

Back to contents.

Ridge regression: shrinkage, direction by direction

Ridge adds a cost on large coefficients, which pulls them towards zero and tames the directions that the data barely determine.

Nearly collinear columns make $X^{\T}X$ almost singular, and the least-squares coefficients become huge with unstable signs. Ridge (Hoerl and Kennard, 1970, also known as Tikhonov regularisation) adds $\lambda \lVert \beta \rVert^2$ to the criterion. The gradient stays linear, so the solution is the normal equations with $\lambda$ on the diagonal, invertible for every $\lambda > 0$. The intercept is not penalised: centre $y$ and the columns first.

On a toy set of four rows with two orthogonal columns of $\pm 1$, $X^{\T}X = 4I$ and $X^{\T}y = (9.6, 4.8)$. Least squares give $(2.4, 1.2)$, and ridge divides by $4 + \lambda$ instead of 4, so both coefficients are multiplied by $4/(4 + \lambda)$, that is 0.8 at $\lambda = 1$, 0.5 at $\lambda = 4$, 0.1 at $\lambda = 36$. They shrink; they never reach zero.

The SVD $X = UDV^{\T}$ gives the exact mechanism. Least squares divide each projection $u_j^{\T}y$ by the singular value $d_j$, and a tiny $d_j$ is where the variance blows up. Ridge multiplies each direction by a factor between 0 and 1.

Recomposed in the original basis, this gives $\hat\beta = (0.55, 1.05)$ against $(0.5, 1.5)$ for least squares, the same as the direct formula. The sum of the factors, 1.3 here instead of 2, is the effective number of parameters the model really uses.

Back to contents.

Lasso: soft thresholding, corners and priors

The lasso subtracts a fixed amount from each coefficient and sets to exactly zero those that would cross zero, so it selects variables.

The lasso (Tibshirani, 1996) replaces the squared norm by the sum of absolute values. With orthonormal columns ($X^{\T}X/n = I$, the scikit-learn convention with $1/2n$ in front of the squared error), the criterion separates into one problem per coordinate. Each has a corner at zero, handled with the subgradient $[-1, 1]$ of $|b|$, and the solution is soft thresholding of the least-squares coefficient $z_j$.

A check from the deck: at $\lambda = 1$ the criterion is 2.605 at the thresholded point $(1.4, 0.2)$, 2.625 if the second coefficient is forced to zero too early, and 3.605 at the least-squares point. Without orthonormal columns there is no closed form, and solvers iterate a gradient step followed by a thresholding (ISTA) or run coordinate descent, as scikit-learn does.

Geometry. Penalising is equivalent to minimising the loss inside a budget $\lVert\beta\rVert \le t$. The L2 budget is a disc, the L1 budget a diamond with corners on the axes; the elliptical contours of the loss usually first touch the diamond at a corner, where some coordinates are exactly zero.

Bayesian reading. Adding a prior on $\beta$ turns the maximum a posteriori into loss plus penalty. A Gaussian prior $\mathcal{N}(0, \tau^2)$ gives ridge with $\lambda = \sigma^2/\tau^2$, and a Laplace prior gives the lasso. Choosing a large $\lambda$ is stating that you expect small coefficients compared with the noise, and with the lasso that you expect many of them to be zero.

Back to contents.

Choosing λ by cross-validation, never on the test set

The strength of the penalty is a setting chosen on held-out folds of the training data; the test set is opened once, at the very end.

$\lambda$ is a hyperparameter. Fitted on the training data it would always fall to zero, and tuned on the test set it would leave nothing honest to report. The answer is the cross-validation of the previous session: a grid of $\lambda$ on a log scale starting from $\lambda_{\max}$, where every lasso coefficient is zero, five folds of the training set, and the mean validation error per value with its standard error. Standardisation is refitted inside each fold.

Two choices are defensible: $\lambda_{\min}$, the minimum of the curve, or the one-standard-error rule (Breiman and co-authors, 1984), the largest $\lambda$ whose error stays within one standard error of the minimum. The second gives a simpler model that the data cannot tell apart from the best, and it is the one usually deployed. In scikit-learn the logistic regression is parametrised by $C$, the inverse of the penalty strength.

The regularisation path plots every coefficient against $\lambda$. For the lasso it is piecewise linear: all coefficients start at zero and the variables enter one by one as the penalty relaxes, the most informative first. The deck adds a deployment test: refit the lasso on many resamples of the training set and count how often each variable is kept (stability selection, Meinshausen and Bühlmann, 2010). A short, stable list of variables is what a credit committee can read, explain and maintain, which is the subject of the next session on thresholds and reproducible delivery.

Back to contents.

Key takeaways

1. For a convex function, a point where the gradient vanishes is a global minimum: chord above the curve, curve above its tangents.
2. Gradient descent converges for a step η < 2/L, where L is the largest curvature; beyond that the loss rises at every step.
3. The number of iterations grows with the condition number κ = L/μ, which is why columns are standardised, with statistics computed on the training set only.
4. SGD and mini-batches trade an unbiased but noisy gradient for a far cheaper step; the noise falls like 1/B, and the step must decrease to settle.
5. Ridge shrinks each singular direction by d²/(d² + λ) and never sets a coefficient to zero; the lasso subtracts λ by soft thresholding and produces exact zeros.
6. Ridge corresponds to a Gaussian prior and the lasso to a Laplace prior: λ compares the expected noise with the expected size of the coefficients.
7. λ is chosen by cross-validation on the training folds, often with the one-standard-error rule; the test set stays closed until the final report.

Glossary

Convex function

A function whose chords lie above its graph; any point with zero gradient is a global minimum.

Gradient descent

Iterative method that moves against the gradient, by a step proportional to the learning rate.

Learning rate (η)

Length of a gradient step per unit of slope; it must stay below 2/L for the descent to converge.

Condition number (κ)

Ratio L/μ of the largest to the smallest curvature; it sets the number of iterations gradient descent needs.

Stochastic gradient descent (SGD)

Gradient descent that uses one observation or a mini-batch per step, unbiased but noisy.

Momentum

Accumulation of past gradients in a velocity, which damps oscillations and speeds up flat directions.

Ridge

Least squares with an L2 penalty λ‖β‖²; shrinks coefficients without setting them to zero.

Shrinkage

Pulling estimated coefficients towards zero to reduce their variance, at the cost of some bias.

Lasso

Least squares with an L1 penalty λ‖β‖₁; produces exact zeros and so selects variables.

Soft thresholding

The map z ↦ sign(z)(|z| − λ)₊, the lasso solution coordinate by coordinate when the columns are orthonormal.

Regularisation path

The fitted coefficients plotted as a function of λ, from all-zero to the unpenalised fit.

Prior

Distribution on the parameters before seeing the data; a Gaussian prior gives ridge, a Laplace prior the lasso.

Cross-validation

Rotating split of the training set into folds, used to choose hyperparameters such as λ without the test set.

The other notes of the course

One public summary per deck, in the order of the course.

Previous: Maximum likelihood and logistic regressionNext: Decision threshold and reproducible ML

1. IntroductionAI winters, jobs and method
2. ToolsKaggle, GitHub, Python: the tools
3. Session 1Project framing and least squares
4. Session 2Maximum likelihood and logistic regression
5. Session 3Gradient descent, ridge and lasso
6. Session 4Decision threshold and reproducible ML
7. HomeworkA defensible baseline model
8. Session 5Kernels, SVM and decision trees
9. Session 6Forests, boosting, honest comparison
10. Session 7SHAP, fairness, PCA and clustering
11. HomeworkA documented champion model
12. Session 8Neural networks, drift, conformal prediction
13. HomeworkA delivered machine learning project
14. Session 9Defending a machine learning project
15. ReferenceCredit default scoring project
16. ReferenceAsset returns: XGBoost and sentiment
17. ReferencePython code for every ML model
18. ReferenceDeep learning essentials
19. ReferenceOpen data ML projects by sector
20. ReferenceData and AI engineer handbook
21. ReferenceData engineering, SRE and cloud
22. ReferencePanorama of machine learning models

All the notes, as a reading list

Attention and transformers, step by step

About these notes

Written by the lecturer from the slides of the deck, as a public summary: the key ideas, the formulas and one worked example. The exercises, their solutions, the tests and the grading stay in the deck, for the students of the course.

Revision: 16 October 2026.