Unit 2.1 · about 4 h
136 / 324Least squares: residuals, normal equations and stable solvers
Least squares is the baseline every later model is compared against. Its two failure modes, singular designs and outlier sensitivity, recur in every fitting method after it.
- derive
- implement
You can now
- Derive the normal equations from the squared-error objective and state when the solution is unique.
- Implement least squares three ways (normal equations, SVD least squares, minibatch gradient descent) with a gradient check, and match them on well-conditioned data.
- Explain why squared loss punishes large residuals quadratically and when that sensitivity becomes a liability.
Covers
- Linear regression, residuals and squared versus absolute loss
- Normal equations, stable solvers and gradient descent
Study, in this order
6 steps
- Linear regression: model, squared loss, analytic solution and minibatch SGDDive into Deep Learning - linear models slice
Sections 3.1.1.1 to 3.1.1.4 (model, squared-error loss with the \(\frac{1}{2}\) factor, analytic solution, minibatch SGD update) and 3.1.3 (Gaussian noise makes squared loss maximum likelihood)
- Linear regression from scratchDive into Deep Learning - linear models slice
Sections 3.4: Defining the Model, Defining the Loss Function, Defining the Optimization Algorithm, Training
Depth · D2L shows framework tabs only; there is no plain NumPy tab. Implement in NumPy first, as the section use note asks, and read the PyTorch tab only as a differential reference.
- Simple and multiple linear regressionAn Introduction to Statistical Learning with Python
Chapter 3, Sections 3.1 to 3.2 (pp. 70-90): the RSS objective, least squares coefficient estimates and the multiple-regression setup
- Linear regression labAn Introduction to Statistical Learning with Python
Simple Linear Regression and Multiple Linear Regression sections on the Boston data: fit with statsmodels
OLSand read coefficients, standard errors and \(R^2\) - Ordinary least squares semantics and solverscikit-learn - linear models, discriminant analysis and naive Bayes
Section 1.1.1 including 1.1.1.2:
LinearRegressionminimizes the residual sum of squares, storescoef_andintercept_, and solves through the SVD of \(X\) at \(O(n p^2)\) cost - Normal equation and batch gradient descentHands-On Machine Learning with Scikit-Learn and PyTorch - classification and linear models
Book Chapter 4: The Normal Equation (printed pp. 138-141) and Batch Gradient Descent (pp. 145-148). Notebook 04 cells: The Normal Equation section (
theta_bestwith the explicit inverse, then thenp.linalg.lstsqand pseudoinverse cross-checks) and Gradient Descent (the batch loop: gradient 2/m X_b'(X_b theta - y),eta0.1, 1000 epochs from a random start)
Focus on
- D2L scales its per-example loss by \(\frac{1}{2}\) while HoML differentiates the plain mean of squares with a \(\frac{2}{m}\) gradient. The minimizer is identical but the largest stable learning rate differs by that constant.
- \(X^\top Xw = X^\top y\) has a unique solution only when \(X\) has full column rank. With duplicate or nearly collinear columns the fitted values stay well determined but the coefficients do not: in the 1e-4 demo below both solvers return slopes near 229 and -228, and only their sum, 1.012, is pinned by the data.
- The course notebooks show
inv(X'X)@X'yto teach the formula; sklearn never forms that inverse and solves through the SVD instead.
Reproduce closed-book
default_rng(1), \(n = 200\), \(x_1\) standard normal, \(x_2 = x_1 + 10^{-4}\) times standard normal noise, an intercept column, \(y = 3 + 2x_1 - x_2 + 0.1\,\text{noise}\), drawn in that order. Show \(\operatorname{cond}(X)\) = 2.08e4 and \(\operatorname{cond}(X^\top X)\) = 4.34e8, its square. The explicit inverse and lstsq agree to about 1e-5, but both return about [3.002, 229.2, -228.2], not [3, 2, -1]. Then rebuild with default_rng(0), \(n = 60\), \(x_2 = x_1 + 10^{-8}\,\text{noise}\) and \(y = 3 + 2x_1 + 0.5\,\text{noise}\): \(\operatorname{cond}(X)\) = 1.8e8 and \(\operatorname{cond}(X^\top X)\) = 3.25e15, and the explicit inverse stops at residual norm 3.8314 while lstsq reaches the minimum, 3.7978.Traps
- Shipping
inv(X'X)@X'yas the solver. Forming \(X^\top X\) squares the condition number, so a design with \(\operatorname{cond}(X)\) near 1e8 makes \(X^\top X\) numerically singular near \(1/\epsilon\) infloat64whilelstsqstill minimizes the residual. - Hand-rolling a bias column while the differential test keeps
fit_intercept=True. sklearn centers the columns, so your ones column becomes all zeros: it gets coefficient 0 andintercept_takes the offset. Predictions agree but a coefficient-by-coefficient comparison fails. Drop the column or passfit_intercept=False. - Reading the second Deep-ML 15 test as the exact solution. It expects
[2.9699, 2.0078], the gradient-descent iterate after 1000 steps atlr0.05; the exact minimizer is[3, 2]. Zero initialization and the exact update decide it.
Practice
Deep-ML 15: Linear Regression Using Gradient Descent
Gradient descent on the \(\frac{1}{2m}\) mean squared error from zero initialization. Test 1 expects [1, 2]; test 2 pins the 1000-step iterate [2.9699, 2.0078] at lr 0.05 rather than the exact [3, 2]
Pass both tests, then show your lstsq solution agrees with test 1 and explain why it cannot match test 2 exactly.
NeetCode ML: Linear Regression Forward and Linear Regression Training
Math Foundations pair: implement the forward pass, then full training cold
After the section gate, compare the learned weights against your lstsq fit on the same data before moving on.
Self-test
-
D2L multiplies its loss by \(\frac{1}{2}\) and HoML does not. Why is the minimizer unchanged but the stable learning rate different?
The constant scales the loss and every gradient without moving the stationary point, so the optimum is identical. A fixed step size moves half as far per step under the \(\frac{1}{2}\) convention, so its stability limit on \(\eta\) is twice as large. -
Two columns of \(X\) are identical. What happens to \(X^\top X\), the coefficients and the predictions?
\(X^\top X\) is singular so the coefficients are not unique. The fitted values \(Xw\) stay unique as the projection onto the column space, and SVD-based solvers return the minimum-norm coefficient vector. -
\(\operatorname{cond}(X)\) is 2.08e4. What is \(\operatorname{cond}(X^\top X)\), and at what point does the explicit inverse break down?
About 4.34e8, the square of \(\operatorname{cond}(X)\). The explicit inverse loses all precision once \(\operatorname{cond}(X^\top X)\) approaches \(1/\epsilon\), about 4.5e15 infloat64, which needs only \(\operatorname{cond}(X)\) near 7e7. At 1.8e8 it no longer reaches the least-squares minimum. -
One label is corrupted upward by 100. Why does the squared-loss fit move far, and which single change to the loss limits the damage?
The quadratic penalty lets that one residual dominate the objective. An absolute-error loss grows only linearly with it, so the fit moves far less.
Completion criterion
Stop when
Your normal-equation and lstsq fits agree to 1e-8 on well-conditioned data, minibatch SGD with a decaying step lands within 1e-3 of them (a constant step leaves it rattling about 1e-2 away), a float64 gradient check passes, and you can say for each Deep-ML 15 test whether it pins the optimum or the optimization path.
Leads to
- 2.2 Conditioning, basis expansions, ridge, lasso and elastic net Repair the singular and badly scaled designs met here with standardization and penalties.
- 2.5 Residual, leverage, separation and misspecification diagnostics Read residuals and leverage on the fits built here.
Comes after
- 1.3 The four subspaces, rank and solution setsDiagnose non-identifiable coefficients in an applied design matrix.
- 1.5 Projections, residuals and least squaresApply this derivation to solver choice on an ill-conditioned design.
- 1.7 SVD, pseudoinverse and low-rank approximationUse singular values and the pseudoinverse when coefficient identifiability fails.
- 1.8 Batched shapes, operation costs and conditioningApply the SVD proof of condition-number squaring to solver comparisons.
- 4.5 Regression diagnostics, calibration and uncertaintySeparate statistical assumptions from numerical conditioning of a fit.
- 5.8 Residuals, tolerances and iterative-solver errorUse residual and solution-error checks when comparing linear solvers.
- 1.8 Snapshots, lineage, pipeline serialization and serving parityDeepen the label-free linear baseline into solvers and diagnostics.
Resources for this unit
- An Introduction to Statistical Learning with Python Use Chapters 3, 4 and 6 with their Python labs as the first pass: least squares and its diagnostics, logistic regression, LDA, QDA and naive Bayes, basis expansion and regularization paths.
- Dive into Deep Learning - linear models slice Use 3.1, 3.4, 3.6, 3.7, 4.1, 4.4, 22.7 and 22.9 for linear regression, generalization, weight decay, softmax, maximum likelihood and naive Bayes. Implement with NumPy first and use the PyTorch versions only as a differential reference.
- scikit-learn - linear models, discriminant analysis and naive Bayes Use the official Linear Models, LDA and QDA, and Naive Bayes guides to verify estimator semantics and selected edge cases after the independent implementation works.
- Hands-On Machine Learning with Scikit-Learn and PyTorch - classification and linear models Read the Chapter 3 and 4 sections each unit names, then run notebooks 03 and 04 for classification diagnostics, linear and polynomial regression, regularization and logistic regression. Recreate the target mechanism independently before inspecting worked exercise code.
Also in this section
- NeetCode ML - linear-model closing drill After the section gate, solve Gradient Descent, Sigmoid and ReLU, Softmax, Cross-Entropy Loss, Linear Regression Forward and Linear Regression Training cold. Repeat only failed items from a blank file with changed values.
- Deep-ML - linear and probabilistic model problems Use 15 Linear Regression Using Gradient Descent, 106 Train Logistic Regression with Gradient Descent and 140 Bernoulli Naive Bayes Classifier as unit checks after the local implementation passes. Their tests were read in review; each card states what they pin. The local implementation remains the evidence.
- Tom Mitchell - Generative and Discriminative Classifiers: Naive Bayes and Logistic Regression Read Sections 2 (naive Bayes, the smoothed estimates (7) and (9), parameter counts), 3 (Gaussian naive Bayes implies the logistic form, gradient ascent, the \(L_2\) penalty, the \(K\)-class rules) and 4 (generative versus discriminative, Ng and Jordan rates). This is the CS446 reading for Lectures 6-8; rework each derivation on a hand-sized dataset.