Linear Models & Their Geometry
Least squares, logistic regression and projections.
Least squares is an orthogonal projection, ridge regression is a filter on singular values, the lasso is soft thresholding, and logistic regression is one member of a family whose losses are all convex. Seen geometrically, linear models explain much of what goes right or wrong in supervised learning, and they remain the laboratory where modern theory, from benign overfitting to implicit bias, is first made precise.
What you’ll learn
- Interpret least squares through the hat matrix and the SVD, prove the Gauss–Markov theorem, and compute the optimism of the training error, .
- Relate the conditioning of to the stability and speed of gradient descent.
- Define generalized linear models with canonical links, prove that their negative log-likelihoods are convex, and derive IRLS.
- Analyze ridge regression (shrinkage factors, effective degrees of freedom, the Hoerl–Kennard theorem) and the lasso (soft thresholding, KKT conditions, rates).
- Derive kernel ridge regression from the push-through identity, and prove the representer theorem.
Least squares as orthogonal projection
With a design matrix of full column rank, least squares solves the normal equations (derived in The Math Toolkit of AI). The fitted values are a linear map of the data, , through the hat matrix, and the thin SVD makes the geometry explicit:
Write any linear estimator as with . Unbiasedness for every means , that is, :
The cross terms then vanish, since , and what remains is a positive semidefinite excess:
Residuals annihilate the signal, , so they contain only projected noise, with expected squared length :
For fresh responses at the same inputs, , a sum of independent terms. The gap is what Mallows' adds back to the training error:
Conditioning. Gradient descent on sees the constant Hessian , with eigenvalues . Along each eigenvector the error is multiplied by per step, so descent is stable only if , and the best fixed step, , contracts the error by per step, where . Correlated or badly scaled features mean a large and slow descent.
In the widget below, a line is fitted to 12 points with spread over . The Hessian of the mean squared error has . What is the largest stable learning rate?
Show the answer
0.78
; the widget's exact value is 0.785. The Hessian is , with averages over the data. For roughly uniform on that is , whose eigenvalues are about 2.54 and 0.13, a condition number near 19.
Generalized linear models
| Family | Mean | Canonical link | Model | |
|---|---|---|---|---|
| Gaussian (unit variance) | identity | linear regression | ||
| Bernoulli | logit | logistic regression | ||
| Poisson | log | regression for counts | ||
| Categorical (vector ) | multinomial logit | softmax regression |
With , the negative log-likelihood is, up to a constant,
Its gradient gives the score equations: at the MLE, the residuals are orthogonal to every feature. These are the normal equations of every canonical GLM:
The Hessian weights each example by its variance, , which is positive, so is convex, and strictly convex when has full rank:
Newton's method, identical here to Fisher scoring, is weighted least squares on working responses: IRLS. Logistic regression's IRLS is the case :
A Poisson regression with the log link, , includes an intercept. Which equation holds at the maximum-likelihood fit?
- is minimized
- , so the fitted counts sum to the observed total
Show the answer
C. , so the fitted counts sum to the observed total
The score equations of a canonical GLM are with , and the intercept's column of ones gives . Least squares on is a different estimator, and it breaks down on zero counts.
On linearly separable data the logistic MLE does not exist, yet gradient descent on the logistic loss still behaves predictably: grows like , while the direction converges, slowly, to that of the hard-margin support vector machine, the maximum-margin separator (Soudry, Hoffer, Nacson, Gunasekar & Srebro, 2018). The optimizer selects a solution even where the loss does not, a theme continued in Kernels & Support Vector Machines.
Ridge and lasso: shrinkage and sparsity
Ridge regression minimizes , so . In SVD coordinates:
Each principal direction is shrunk by a factor in , most strongly the low-variance directions with small , where least squares is least reliable. The trace of the smoother defines the effective degrees of freedom:
Ridge trades bias for variance. In rotated coordinates , the mean squared error splits, direction by direction, into a variance and a squared bias:
At the derivative is negative: the variance falls at first order while the squared bias grows only at second order. This proves the Hoerl–Kennard theorem (1970): some always beats least squares in mean squared error.
The lasso (Tibshirani, 1996) minimizes . The ball has corners on the coordinate axes, and solutions tend to sit on them, so many coefficients are exactly zero. The subgradient (KKT) conditions make this precise: when , and when . In particular exactly when , and the solution path is piecewise linear in (LARS; Efron, Hastie, Johnstone & Tibshirani, 2004). Coordinate descent solves it fast in practice (Friedman, Hastie & Tibshirani, 2010).
| Method | Penalty | Estimate of coefficient from |
|---|---|---|
| Least squares | none | |
| Ridge | : proportional shrinkage, never exactly 0 | |
| Lasso | , with on the loss | : soft thresholding |
| Best subset | , with on the loss | : hard thresholding |
Theory says when the lasso finds the right variables. Suppose the true has nonzero entries among , the columns of have norm , and the design satisfies a restricted eigenvalue condition. Then with of order , the lasso achieves with high probability (Bickel, Ritov & Tsybakov, 2009): not knowing the support costs only a factor . The Bayesian reading of both penalties, as Gaussian and Laplace priors, is in Bayesian Reasoning, and implicit regularization in Regularization Theory.
Kernel ridge regression and the representer theorem
The push-through identity , which follows from , rewrites ridge regression with dual coefficients:
Predictions need only inner products between the query and the training points:
Replace by a feature map and every inner product by a kernel , the kernel trick. The feature space may be infinite-dimensional, and training costs instead of :
This is exactly the posterior mean of a Gaussian process with covariance and noise variance (see Gaussian Processes & Bayesian ML): one estimator, read once as penalized least squares and once as Bayesian inference.
Two consequences. Every regularized kernel method, from kernel ridge regression and kernel logistic regression to the support vector machine, reduces to an -dimensional problem over . And as , kernel ridge regression tends to the minimum-norm interpolant of the data, the object at the center of the modern analysis of overparameterized models (Double Descent & Modern Generalization). The cost is the practical limit; random features and Nyström approximations trade a little accuracy for near-linear scaling.
Key takeaways
- Least squares projects onto the column space of with the hat matrix ; it is BLUE (Gauss–Markov), and its training error is optimistic by .
- Gradient descent on least squares is stable only for and contracts at best by per step; standardizing the features improves the conditioning.
- Canonical GLMs (linear, logistic, Poisson, softmax) share the score equations , a convex negative log-likelihood with Hessian , and IRLS.
- Ridge shrinks principal directions by and always beats least squares for some (Hoerl–Kennard); the lasso soft-thresholds, selects variables, and attains rates under restricted eigenvalue conditions.
- Kernel ridge regression, with , follows from the push-through identity, and the representer theorem extends this form to every regularized kernel method.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Least squares with parameters is fitted to points with noise variance , and the model is correct. What is the expected training mean squared error?
- 1.0
- 1.1
- 0.9
- 0.81
Show the answer
C. 0.9
: the fit absorbs of the noise dimensions. On fresh responses at the same inputs the expected error is , so the training error understates it by .
Ridge regression with orthonormal columns (, ) uses . What are its effective degrees of freedom?
- 5
- 2.5
- 1
- 0
Show the answer
B. 2.5
With every , : each coefficient is halved, . Degrees of freedom interpolate smoothly between (no penalty) and 0 (infinite penalty).
For the lasso , what is the smallest at which the solution is exactly ?
- There is none: the lasso only shrinks coefficients toward zero
Show the answer
D.
At the KKT conditions require for every , that is, . The lasso path starts there; as decreases, variables enter one at a time, first the one most correlated with .
Kernel ridge regression with a Gaussian (RBF) kernel is trained on points. What dominates the cost, and why is the infinite-dimensional feature space no obstacle?
- Nothing can be computed, because the feature space is infinite-dimensional
- Solving , about operations; the features enter only through the Gram matrix
- Computing the feature map of each point
- Inverting the matrix
Show the answer
B. Solving , about operations; the features enter only through the Gram matrix
By the representer theorem, the solution lies in the span of the functions , so only the Gram matrix is needed: memory (3.2 GB in double precision here) and time. Beyond about points one switches to random features, Nyström approximations or iterative solvers.
Further reading
- T. Hastie, R. Tibshirani & J. Friedman, The Elements of Statistical Learning, 2nd ed. (Springer, 2009), chapters 3–5.
- J. A. Nelder & R. W. M. Wedderburn, "Generalized linear models," Journal of the Royal Statistical Society, Series A 135(3), 370–384 (1972).
- A. E. Hoerl & R. W. Kennard, "Ridge regression: biased estimation for nonorthogonal problems," Technometrics 12(1), 55–67 (1970).
- R. Tibshirani, "Regression shrinkage and selection via the lasso," Journal of the Royal Statistical Society, Series B 58(1), 267–288 (1996).
- P. L. Bartlett, P. M. Long, G. Lugosi & A. Tsigler, "Benign overfitting in linear regression," Proceedings of the National Academy of Sciences 117(48), 30063–30070 (2020).