Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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, 2σ2p/n2\sigma^2p/n.
  • Relate the conditioning of X⊤XX^\top X 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, slog⁡p/ns\log p/n rates).
  • Derive kernel ridge regression from the push-through identity, and prove the representer theorem.

Least squares as orthogonal projection

With a design matrix X∈Rn×pX\in\R^{n\times p} of full column rank, least squares solves the normal equations X⊤Xw^=X⊤yX^\top X\hat{\mathbf w}=X^\top\mathbf y (derived in The Math Toolkit of AI). The fitted values are a linear map of the data, y^=Hy\hat{\mathbf y}=H\mathbf y, through the hat matrix, and the thin SVD X=UDV⊤X=UDV^\top makes the geometry explicit:

H=X(X⊤X)−1X⊤=UU⊤,w^=VD−1U⊤y,y^=∑j=1puj(uj⊤y)H=X(X^\top X)^{-1}X^\top=UU^\top,\qquad\hat{\mathbf w}=VD^{-1}U^\top\mathbf y,\qquad\hat{\mathbf y}=\sum_{j=1}^p\mathbf u_j\big(\mathbf u_j^\top\mathbf y\big)
HH is the orthogonal projector onto the column space of XX: symmetric, idempotent, with eigenvalues 0 and 1 and trace pp. Its diagonal entries, the leverages hii∈[0,1]h_{ii}\in[0,1], measure how much yiy_i moves its own fit, ∂y^i/∂yi=hii\partial\hat y_i/\partial y_i=h_{ii}. Without full rank, the pseudoinverse solution X+yX^+\mathbf y is the least-squares solution of minimum norm.
DerivationProofs
  1. Ew~=CXw=w  for all w  ⟺  DX=0\E\tilde{\mathbf w}=CX\mathbf w=\mathbf w\ \ \text{for all }\mathbf w\iff DX=0

    Write any linear estimator as w~=Cy\tilde{\mathbf w}=C\mathbf y with C=(X⊤X)−1X⊤+DC=(X^\top X)^{-1}X^\top+D. Unbiasedness for every w\mathbf w means CX=ICX=I, that is, DX=0DX=0:

  2. Cov⁡w~=σ2CC⊤=σ2[(X⊤X)−1+DD⊤]⪰σ2(X⊤X)−1=Cov⁡w^\Cov\tilde{\mathbf w}=\sigma^2CC^\top=\sigma^2\big[(X^\top X)^{-1}+DD^\top\big]\succeq\sigma^2(X^\top X)^{-1}=\Cov\hat{\mathbf w}

    The cross terms then vanish, since (X⊤X)−1X⊤D⊤=(X⊤X)−1(DX)⊤=0(X^\top X)^{-1}X^\top D^\top=(X^\top X)^{-1}(DX)^\top=0, and what remains is a positive semidefinite excess:

  3. y−y^=(I−H)ε,E∥y−y^∥2=σ2(n−p)\mathbf y-\hat{\mathbf y}=(I-H)\boldsymbol\varepsilon,\qquad\E\norm{\mathbf y-\hat{\mathbf y}}^2=\sigma^2(n-p)

    Residuals annihilate the signal, (I−H)Xw=0(I-H)X\mathbf w=\mathbf 0, so they contain only projected noise, with expected squared length σ2tr⁡(I−H)\sigma^2\tr(I-H):

  4. E∥y′−y^∥2=σ2n+σ2tr⁡(H)=σ2(n+p)\E\norm{\mathbf y'-\hat{\mathbf y}}^2=\sigma^2n+\sigma^2\tr(H)=\sigma^2(n+p)

    For fresh responses y′=Xw+ε′\mathbf y'=X\mathbf w+\boldsymbol\varepsilon' at the same inputs, y′−y^=ε′−Hε\mathbf y'-\hat{\mathbf y}=\boldsymbol\varepsilon'-H\boldsymbol\varepsilon, a sum of independent terms. The gap 2σ2p2\sigma^2p is what Mallows' CpC_p adds back to the training error:

Conditioning. Gradient descent on L(w)=1n∥Xw−y∥2L(\mathbf w)=\frac1n\norm{X\mathbf w-\mathbf y}^2 sees the constant Hessian 2nX⊤X\frac2nX^\top X, with eigenvalues λmax⁡≥⋯≥λmin⁡>0\lambda_{\max}\ge\dots\ge\lambda_{\min}>0. Along each eigenvector the error is multiplied by 1−ηλj1-\eta\lambda_j per step, so descent is stable only if η<2/λmax⁡\eta<2/\lambda_{\max}, and the best fixed step, 2/(λmax⁡+λmin⁡)2/(\lambda_{\max}+\lambda_{\min}), contracts the error by (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) per step, where κ=λmax⁡/λmin⁡\kappa=\lambda_{\max}/\lambda_{\min}. Correlated or badly scaled features mean a large κ\kappa and slow descent.

Predict before you look

In the widget below, a line y=wx+by=wx+b is fitted to 12 points with xx spread over [0,1][0,1]. The Hessian of the mean squared error has λmax⁡≈2.55\lambda_{\max}\approx2.55. What is the largest stable learning rate?

Show the answer

0.78

2/λmax⁡≈2/2.55≈0.782/\lambda_{\max}\approx2/2.55\approx0.78; the widget's exact value is 0.785. The Hessian is 2(x2‾xˉxˉ1)2\begin{pmatrix}\overline{x^2}&\bar x\\ \bar x&1\end{pmatrix}, with averages over the data. For xx roughly uniform on [0,1][0,1] that is 2(1/31/21/21)2\begin{pmatrix}1/3&1/2\\1/2&1\end{pmatrix}, whose eigenvalues are about 2.54 and 0.13, a condition number near 19.

Generalized linear models

FamilyA(θ)A(\theta)Mean A′(θ)A'(\theta)Canonical linkModel
Gaussian (unit variance)θ2/2\theta^2/2θ\thetaidentitylinear regression
Bernoulliln⁡(1+eθ)\ln(1+e^\theta)σ(θ)\sigma(\theta)logitlogistic regression
Poissoneθe^\thetaeθe^\thetalogregression for counts
Categorical (vector θ\boldsymbol\theta)ln⁡∑keθk\ln\sum_ke^{\theta_k}softmax⁡(θ)\softmax(\boldsymbol\theta)multinomial logitsoftmax regression
One template, four familiar models. A Gaussian with unknown variance adds a dispersion parameter, which does not change the estimate of w\mathbf w.
DerivationConvexity and IRLS for canonical links
  1. ℓ(w)=∑i=1n[A(xi⊤w)−yi xi⊤w]\ell(\mathbf w)=\sum_{i=1}^n\big[A(\mathbf x_i^\top\mathbf w)-y_i\,\mathbf x_i^\top\mathbf w\big]

    With θi=xi⊤w\theta_i=\mathbf x_i^\top\mathbf w, the negative log-likelihood is, up to a constant,

  2. ∇ℓ(w)=∑i(A′(xi⊤w)−yi)xi=X⊤(μ−y),X⊤(y−μ^)=0\nabla\ell(\mathbf w)=\sum_i\big(A'(\mathbf x_i^\top\mathbf w)-y_i\big)\mathbf x_i=X^\top(\boldsymbol\mu-\mathbf y),\qquad X^\top(\mathbf y-\hat{\boldsymbol\mu})=\mathbf 0

    Its gradient gives the score equations: at the MLE, the residuals y−μ^\mathbf y-\hat{\boldsymbol\mu} are orthogonal to every feature. These are the normal equations of every canonical GLM:

  3. ∇2ℓ(w)=∑iA′′(θi) xixi⊤=X⊤WX⪰0\nabla^2\ell(\mathbf w)=\sum_iA''(\theta_i)\,\mathbf x_i\mathbf x_i^\top=X^\top WX\succeq0

    The Hessian weights each example by its variance, W=diag⁡(A′′(θi))W=\diag(A''(\theta_i)), which is positive, so ℓ\ell is convex, and strictly convex when XX has full rank:

  4. w←(X⊤WX)−1X⊤Wz,z=Xw+W−1(y−μ)\mathbf w\leftarrow(X^\top WX)^{-1}X^\top W\mathbf z,\qquad\mathbf z=X\mathbf w+W^{-1}(\mathbf y-\boldsymbol\mu)

    Newton's method, identical here to Fisher scoring, is weighted least squares on working responses: IRLS. Logistic regression's IRLS is the case W=diag⁡(σi(1−σi))W=\diag(\sigma_i(1-\sigma_i)):

Check your understanding

A Poisson regression with the log link, E[y∣x]=ew⊤x\E[y\mid\mathbf x]=e^{\mathbf w^\top\mathbf x}, includes an intercept. Which equation holds at the maximum-likelihood fit?

  1. ∑i(log⁡yi−xi⊤w^) xi=0\sum_i(\log y_i-\mathbf x_i^\top\hat{\mathbf w})\,\mathbf x_i=\mathbf 0
  2. ∑i(yi−exi⊤w^)2\sum_i\big(y_i-e^{\mathbf x_i^\top\hat{\mathbf w}}\big)^2 is minimized
  3. ∑i(yi−exi⊤w^) xi=0\sum_i\big(y_i-e^{\mathbf x_i^\top\hat{\mathbf w}}\big)\,\mathbf x_i=\mathbf 0, so the fitted counts sum to the observed total
  4. w^=(X⊤X)−1X⊤log⁡y\hat{\mathbf w}=(X^\top X)^{-1}X^\top\log\mathbf y
Show the answer

C. ∑i(yi−exi⊤w^) xi=0\sum_i\big(y_i-e^{\mathbf x_i^\top\hat{\mathbf w}}\big)\,\mathbf x_i=\mathbf 0, so the fitted counts sum to the observed total

The score equations of a canonical GLM are X⊤(y−μ^)=0X^\top(\mathbf y-\hat{\boldsymbol\mu})=\mathbf 0 with μ^i=exi⊤w^\hat\mu_i=e^{\mathbf x_i^\top\hat{\mathbf w}}, and the intercept's column of ones gives ∑iμ^i=∑iyi\sum_i\hat\mu_i=\sum_iy_i. Least squares on log⁡y\log y 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: ∥wt∥\norm{\mathbf w_t} grows like log⁡t\log t, while the direction wt/∥wt∥\mathbf w_t/\norm{\mathbf w_t} 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

DerivationRidge regression through the SVD
  1. w^λ=Vdiag⁡(djdj2+λ)U⊤y,y^λ=∑juj dj2dj2+λ uj⊤y\hat{\mathbf w}_\lambda=V\diag\Big(\frac{d_j}{d_j^2+\lambda}\Big)U^\top\mathbf y,\qquad\hat{\mathbf y}_\lambda=\sum_j\mathbf u_j\,\frac{d_j^2}{d_j^2+\lambda}\,\mathbf u_j^\top\mathbf y

    Ridge regression minimizes ∥y−Xw∥2+λ∥w∥2\norm{\mathbf y-X\mathbf w}^2+\lambda\norm{\mathbf w}^2, so w^λ=(X⊤X+λI)−1X⊤y\hat{\mathbf w}_\lambda=(X^\top X+\lambda I)^{-1}X^\top\mathbf y. In SVD coordinates:

  2. df(λ)=tr⁡(X(X⊤X+λI)−1X⊤)=∑j=1pdj2dj2+λ\mathrm{df}(\lambda)=\tr\big(X(X^\top X+\lambda I)^{-1}X^\top\big)=\sum_{j=1}^p\frac{d_j^2}{d_j^2+\lambda}

    Each principal direction is shrunk by a factor in (0,1)(0,1), most strongly the low-variance directions with small djd_j, where least squares is least reliable. The trace of the smoother defines the effective degrees of freedom:

  3. E∥w^λ−w∥2=∑jσ2dj2+λ2αj2(dj2+λ)2\E\norm{\hat{\mathbf w}_\lambda-\mathbf w}^2=\sum_j\frac{\sigma^2d_j^2+\lambda^2\alpha_j^2}{(d_j^2+\lambda)^2}

    Ridge trades bias for variance. In rotated coordinates α=V⊤w\boldsymbol\alpha=V^\top\mathbf w, the mean squared error splits, direction by direction, into a variance and a squared bias:

  4. ddλE∥w^λ−w∥2∣λ=0=−2σ2∑j1dj4<0\frac{d}{d\lambda}\E\norm{\hat{\mathbf w}_\lambda-\mathbf w}^2\Big|_{\lambda=0}=-2\sigma^2\sum_j\frac1{d_j^4}<0

    At λ=0\lambda=0 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 λ>0\lambda>0 always beats least squares in mean squared error.

The lasso (Tibshirani, 1996) minimizes 12∥y−Xw∥2+λ∥w∥1\frac12\norm{\mathbf y-X\mathbf w}^2+\lambda\norm{\mathbf w}_1. The ℓ1\ell_1 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: Xj⊤(y−Xw^)=λsign⁡(w^j)X_j^\top(\mathbf y-X\hat{\mathbf w})=\lambda\sign(\hat w_j) when w^j≠0\hat w_j\ne0, and ∣Xj⊤(y−Xw^)∣≤λ\abs{X_j^\top(\mathbf y-X\hat{\mathbf w})}\le\lambda when w^j=0\hat w_j=0. In particular w^=0\hat{\mathbf w}=\mathbf 0 exactly when λ≥∥X⊤y∥∞\lambda\ge\norm{X^\top\mathbf y}_\infty, and the solution path is piecewise linear in λ\lambda (LARS; Efron, Hastie, Johnstone & Tibshirani, 2004). Coordinate descent solves it fast in practice (Friedman, Hastie & Tibshirani, 2010).

MethodPenaltyEstimate of coefficient jj from zj=xj⊤yz_j=\mathbf x_j^\top\mathbf y
Least squaresnonezjz_j
Ridgeλ∥w∥22\lambda\norm{\mathbf w}_2^2zj/(1+λ)z_j/(1+\lambda): proportional shrinkage, never exactly 0
Lassoλ∥w∥1\lambda\norm{\mathbf w}_1, with 12\frac12 on the losssign⁡(zj) (∣zj∣−λ)+\sign(z_j)\,(\abs{z_j}-\lambda)_+: soft thresholding
Best subsetλ∥w∥0\lambda\norm{\mathbf w}_0, with 12\frac12 on the losszj 1{∣zj∣>2λ}z_j\,\mathbf 1\{\abs{z_j}>\sqrt{2\lambda}\}: hard thresholding
With orthonormal columns, X⊤X=IX^\top X=I, every method acts coordinate by coordinate. The lasso both selects and shrinks, so it biases large coefficients by λ\lambda; refitting the selected variables, or nonconvex penalties, reduce that bias.

Theory says when the lasso finds the right variables. Suppose the true w∗\mathbf w^* has ss nonzero entries among p≫np\gg n, the columns of XX have norm n\sqrt n, and the design satisfies a restricted eigenvalue condition. Then with λ\lambda of order σnlog⁡p\sigma\sqrt{n\log p}, the lasso achieves ∥w^−w∗∥22=O(σ2slog⁡p/n)\norm{\hat{\mathbf w}-\mathbf w^*}_2^2=\order{\sigma^2s\log p/n} with high probability (Bickel, Ritov & Tsybakov, 2009): not knowing the support costs only a factor log⁡p\log p. 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

DerivationFrom weights to kernels
  1. w^=X⊤α,α=(K+λI)−1y,K=XX⊤,  Kij=xi⊤xj\hat{\mathbf w}=X^\top\boldsymbol\alpha,\qquad\boldsymbol\alpha=(K+\lambda I)^{-1}\mathbf y,\qquad K=XX^\top,\ \ K_{ij}=\mathbf x_i^\top\mathbf x_j

    The push-through identity (X⊤X+λI)−1X⊤=X⊤(XX⊤+λI)−1(X^\top X+\lambda I)^{-1}X^\top=X^\top(XX^\top+\lambda I)^{-1}, which follows from X⊤(XX⊤+λI)=(X⊤X+λI)X⊤X^\top(XX^\top+\lambda I)=(X^\top X+\lambda I)X^\top, rewrites ridge regression with nn dual coefficients:

  2. f^(x)=w^⊤x=∑i=1nαi xi⊤x\hat f(\mathbf x)=\hat{\mathbf w}^\top\mathbf x=\sum_{i=1}^n\alpha_i\,\mathbf x_i^\top\mathbf x

    Predictions need only inner products between the query and the training points:

  3. f^(x)=∑i=1nαi k(xi,x),α=(K+λI)−1y,Kij=k(xi,xj)\hat f(\mathbf x)=\sum_{i=1}^n\alpha_i\,k(\mathbf x_i,\mathbf x),\qquad\boldsymbol\alpha=(K+\lambda I)^{-1}\mathbf y,\quad K_{ij}=k(\mathbf x_i,\mathbf x_j)

    Replace x\mathbf x by a feature map ϕ(x)\boldsymbol\phi(\mathbf x) and every inner product by a kernel k(x,x′)=⟨ϕ(x),ϕ(x′)⟩k(\mathbf x,\mathbf x')=\langle\boldsymbol\phi(\mathbf x),\boldsymbol\phi(\mathbf x')\rangle, the kernel trick. The feature space may be infinite-dimensional, and training costs O(n3)\order{n^3} instead of O(p3)\order{p^3}:

  4. f^(x∗)=k∗⊤(K+σ2I)−1ywithσ2=λ\hat f(\mathbf x_*)=\mathbf k_*^\top(K+\sigma^2I)^{-1}\mathbf y\quad\text{with}\quad\sigma^2=\lambda

    This is exactly the posterior mean of a Gaussian process with covariance kk and noise variance λ\lambda (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 nn-dimensional problem over α\boldsymbol\alpha. And as λ→0\lambda\to0, 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 O(n3)\order{n^3} cost is the practical limit; random features and Nyström approximations trade a little accuracy for near-linear scaling.

Key takeaways

  • Least squares projects y\mathbf y onto the column space of XX with the hat matrix H=UU⊤H=UU^\top; it is BLUE (Gauss–Markov), and its training error is optimistic by 2σ2p/n2\sigma^2p/n.
  • Gradient descent on least squares is stable only for η<2/λmax⁡\eta<2/\lambda_{\max} and contracts at best by (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) per step; standardizing the features improves the conditioning.
  • Canonical GLMs (linear, logistic, Poisson, softmax) share the score equations X⊤(y−μ^)=0X^\top(\mathbf y-\hat{\boldsymbol\mu})=\mathbf 0, a convex negative log-likelihood with Hessian X⊤WXX^\top WX, and IRLS.
  • Ridge shrinks principal directions by dj2/(dj2+λ)d_j^2/(d_j^2+\lambda) and always beats least squares for some λ>0\lambda>0 (Hoerl–Kennard); the lasso soft-thresholds, selects variables, and attains σ2slog⁡p/n\sigma^2s\log p/n rates under restricted eigenvalue conditions.
  • Kernel ridge regression, f^=∑iαik(xi,⋅)\hat f=\sum_i\alpha_ik(\mathbf x_i,\cdot) with α=(K+λI)−1y\boldsymbol\alpha=(K+\lambda I)^{-1}\mathbf y, 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.

Question 1

Least squares with p=10p=10 parameters is fitted to n=100n=100 points with noise variance σ2=1\sigma^2=1, and the model is correct. What is the expected training mean squared error?

  1. 1.0
  2. 1.1
  3. 0.9
  4. 0.81
Show the answer

C. 0.9

E∥y−y^∥2/n=σ2(1−p/n)=0.9\E\norm{\mathbf y-\hat{\mathbf y}}^2/n=\sigma^2(1-p/n)=0.9: the fit absorbs pp of the nn noise dimensions. On fresh responses at the same inputs the expected error is σ2(1+p/n)=1.1\sigma^2(1+p/n)=1.1, so the training error understates it by 2σ2p/n=0.22\sigma^2p/n=0.2.

Question 2

Ridge regression with orthonormal columns (X⊤X=IX^\top X=I, p=5p=5) uses λ=1\lambda=1. What are its effective degrees of freedom?

  1. 5
  2. 2.5
  3. 1
  4. 0
Show the answer

B. 2.5

With every dj=1d_j=1, df=∑jdj2dj2+λ=5×12=2.5\mathrm{df}=\sum_j\frac{d_j^2}{d_j^2+\lambda}=5\times\frac12=2.5: each coefficient is halved, zj/(1+λ)z_j/(1+\lambda). Degrees of freedom interpolate smoothly between pp (no penalty) and 0 (infinite penalty).

Question 3

For the lasso 12∥y−Xw∥2+λ∥w∥1\frac12\norm{\mathbf y-X\mathbf w}^2+\lambda\norm{\mathbf w}_1, what is the smallest λ\lambda at which the solution is exactly 0\mathbf 0?

  1. λ=∥X⊤y∥2\lambda=\norm{X^\top\mathbf y}_2
  2. λ=∥y∥2/2\lambda=\norm{\mathbf y}^2/2
  3. There is none: the lasso only shrinks coefficients toward zero
  4. λ=∥X⊤y∥∞\lambda=\norm{X^\top\mathbf y}_\infty
Show the answer

D. λ=∥X⊤y∥∞\lambda=\norm{X^\top\mathbf y}_\infty

At w=0\mathbf w=\mathbf 0 the KKT conditions require ∣Xj⊤y∣≤λ\abs{X_j^\top\mathbf y}\le\lambda for every jj, that is, λ≥max⁡j∣Xj⊤y∣\lambda\ge\max_j\abs{X_j^\top\mathbf y}. The lasso path starts there; as λ\lambda decreases, variables enter one at a time, first the one most correlated with y\mathbf y.

Question 4

Kernel ridge regression with a Gaussian (RBF) kernel is trained on n=20,000n=20{,}000 points. What dominates the cost, and why is the infinite-dimensional feature space no obstacle?

  1. Nothing can be computed, because the feature space is infinite-dimensional
  2. Solving (K+λI)α=y(K+\lambda I)\boldsymbol\alpha=\mathbf y, about n3/3≈3×1012n^3/3\approx3\times10^{12} operations; the features enter only through the n×nn\times n Gram matrix
  3. Computing the feature map ϕ(x)\boldsymbol\phi(\mathbf x) of each point
  4. Inverting the p×pp\times p matrix X⊤XX^\top X
Show the answer

B. Solving (K+λI)α=y(K+\lambda I)\boldsymbol\alpha=\mathbf y, about n3/3≈3×1012n^3/3\approx3\times10^{12} operations; the features enter only through the n×nn\times n Gram matrix

By the representer theorem, the solution lies in the span of the nn functions k(xi,⋅)k(\mathbf x_i,\cdot), so only the Gram matrix is needed: O(n2)\order{n^2} memory (3.2 GB in double precision here) and O(n3)\order{n^3} time. Beyond about 10510^5 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).