Linear Algebra for Machine Learning

From Prediction Errors to Least Squares

Suppose a linear regression model must be selected from a class of possible predictors. The training data determine which predictor is best through empirical risk minimization: choose the predictor whose loss on the training set is smallest. When the loss is squared loss, least squares is the algorithm used to carry out this search for the linear regression class.

The important connection is the objective being minimized. Empirical risk minimization supplies the selection principle: choose the predictor with the smallest training loss. Least squares supplies the procedure for the linear regression class when that loss is squared loss. The result is not a separate objective added after regression; least squares is the way this particular empirical risk minimization problem is carried out.

Why the Gradient Condition Matters

Least squares minimizes the squared-loss objective. To locate an optimal set of regression weights, the derivation calculates the gradient of that objective and compares it with zero. The gradient condition is therefore the mathematical condition used to derive the equations that determine the weights.

Setting the gradient equal to zero is not an optional diagnostic performed after training. In this derivation, it is the step that converts the optimization problem into an equation-solving problem. Once the gradient condition has been formed, it can be rewritten as a linear system.

The Central System A w = b

After the gradient condition is formed, the empirical risk minimization problem is rewritten as the compact linear system A w = b. The vector w is the unknown vector of regression weights. The matrix A and vector b are determined by the problem formulation. Solving the system produces the weights that define the selected linear regression predictor.

When A Is Invertible

The next question is whether the matrix A in A w = b is invertible. If A is invertible, the system has the corresponding direct linear-algebra solution for w. In this case, once the gradient condition has been converted into the system, the remaining task is to apply the invertible-matrix case to obtain the regression weights.

What Non-Invertibility Reveals

If A is not invertible, the direct inverse-based route cannot be used. This situation can occur when the training instances do not span the entire space of R d. The system A w = b still has a solution because b is in the range of A, but the matrix requires a different linear-algebra treatment.

Eigenvalue decomposition provides the needed linear-algebra tools for the non-invertible case. Its role here is to expose the structure of A so that the system can be analyzed even though A has no direct inverse-based solution. The important distinction is not that the original optimization problem disappears; rather, the same system A w = b must be handled with a decomposition suited to a non-invertible matrix.

Common Reasoning Mistakes

• Treating empirical risk minimization and least squares as unrelated procedures.

  For linear regression with squared loss, least squares is the algorithm used to carry out the empirical risk minimization search.

  Fix: Connect the objective, loss, and algorithm: squared loss defines the empirical risk, and least squares minimizes it for the linear regression class.

• Treating the zero-gradient condition as an optional diagnostic.

  The gradient condition is used in the derivation to obtain the system that determines the weights.

  Fix: Begin by calculating the gradient of the least-squares objective and comparing it with zero.

• Forgetting which symbol is unknown in A w = b.

  A and b are determined by the problem formulation, while w is the vector of regression weights to be found.

  Fix: Read the system as a request to solve for w.

• Assuming that a non-invertible A means there is no solution.

  In the stated setting, b is in the range of A, so A w = b still has a solution.

  Fix: Move from the direct inverse case to the eigenvalue-decomposition tools for the non-invertible case.

Apply the Derivation

The Complete Mental Model

1. For linear regression with squared loss, least squares solves the empirical risk minimization problem.
2. The derivation calculates the gradient of the objective and compares it with zero to locate the optimal weights.
3. The zero-gradient condition is rewritten as the central linear system A w = b.
4. A and b are determined by the problem formulation, while w is the regression-weight vector to be found.
5. If A is invertible, the system has the corresponding direct solution; if A is not invertible, eigenvalue decomposition provides the needed tools, and the system still has a solution because b is in the range of A.