Mathematical Preliminaries: Linear Algebra, Probability, and Convex Analysis

Mathematical Preliminaries: Linear Algebra, Probability, and Convex Analysis

The question organizing this chapter is precise and methodological: what minimum mathematical machinery is required to formulate, analyze, and solve classical supervised learning problems with rigor? Three answers, one in linear algebra, one in probability, and one in convex analysis, together constitute the response, and the rest of the book will draw on each in roughly equal measure. The single elementary example of ordinary least squares linear regression will serve as our recurring touchstone. From the linear-algebraic perspective, the estimator is the orthogonal projection of a target vector onto the column space of a design matrix. From the probabilistic perspective, it is the maximum-likelihood estimator of the conditional mean of a Gaussian random vector. From the analytic perspective, it is the unique global minimizer of a strongly convex quadratic functional. We treat these three facets in sequence, develop the underlying machinery in self-contained form, and close by solving a single concrete regression problem three ways to demonstrate that the three perspectives are not interchangeable vocabularies but distinct proof techniques that converge on the same object.

The structural logic we will develop in the rest of the book is foreshadowed in the figure below. Almost every parametric supervised learning method studied in subsequent chapters—least squares, ridge regression, the lasso, logistic regression, the support vector machine—can be written as an instance of the *projection-plus-penalty* template $$ \min_{w \in \mathbb{R}^d} \; \Phi(w) \;=\; \underbrace{\frac{1}{2n} \|Xw - y\|_2^2}_{\text{projection / data fidelity}} \;+\; \underbrace{\lambda \, \mathcal{R}(w)}_{\text{penalty / regularization}}, $$ where the loss term measures fit to data and the penalty term encodes prior geometric or statistical structure on the parameter. Non-parametric methods, including trees and ensembles, fall outside this convex template but can be reached by relaxing one of its assumptions. The remainder of this chapter constructs the tools required to recognize, analyze, and solve instances of this template rigorously.

```mermaid graph TD A[Supervised Learning] --> B[Empirical Risk Minimization] B --> C[Parametric Models] B --> D[Non-Parametric Models] C --> E[Projection + Penalty Template] E --> F[Linear Regression] E --> G[Ridge Regression] E --> H[Lasso] E --> I[Logistic Regression] E --> J[Support Vector Machine] E --> K[Neural Networks] F --> F1["L = squared, R = 0"] G --> G1["L = squared, R = L2"] H --> H1["L = squared, R = L1"] I --> I1["L = logistic, R = L2"] J --> J1["L = hinge, R = L2"] D --> L[Decision Trees] D --> M[Kernel Methods] M --> E ```

1.1 Vector Space Structure, Inner Products, and the Projection Theorem

The geometric backbone of supervised learning is the theory of finite-dimensional inner product spaces, and the projection theorem is its sharpest tool. We develop the necessary concepts from first principles because the geometric intuition they encode is what makes later derivations feel inevitable rather than memorized.

A real vector space $V$ over the reals is a set equipped with two operations, vector addition $+: V \times V \to V$ and scalar multiplication $\cdot: \mathbb{R} \times V \to V$, satisfying the usual eight axioms (associativity and commutativity of addition, distributivity of scalar multiplication over vector addition and over scalar addition, existence of a zero element and additive inverses, and the requirement that $1 \cdot v = v$). The set $\mathbb{R}^d$ of $d$-tuples of real numbers, with componentwise addition and scalar multiplication, is the canonical example and the only one we will use directly; however, the abstract framework occasionally illuminates constructions such as function spaces and reproducing kernel Hilbert spaces, which we will encounter when we study kernel methods.

A *subspace* $H \subseteq V$ is a subset that is itself a vector space under the inherited operations, equivalently one that is closed under linear combinations. The *column space* (or *image*) of a matrix $X \in \mathbb{R}^{n \times d}$, defined as $\mathrm{col}(X) = \{Xw : w \in \mathbb{R}^d\}$, is a subspace of $\mathbb{R}^n$ of dimension at most $d$ (exactly $d$ if and only if the columns of $X$ are linearly independent). This subspace is the geometric object on which the least-squares estimator projects, and almost everything in this section is a precise formulation of that intuition.

An *inner product* on $V$ is a function $\langle \cdot, \cdot \rangle: V \times V \to \mathbb{R}$ that is bilinear (linear in each argument), symmetric, and positive definite ($\langle v, v \rangle > 0$ for $v \neq 0$). On $\mathbb{R}^n$ the standard inner product is $\langle u, v \rangle = u^\top v = \sum_{i=1}^n u_i v_i$. The inner product induces a norm $\|v\| = \sqrt{\langle v, v \rangle}$, which satisfies the triangle inequality $\|u + v\| \leq \|u\| + \|v\|$ and absolute homogeneity $\|\alpha v\| = |\alpha| \|v\|$.

The fundamental inequality for an inner product space is the Cauchy–Schwarz inequality: for all $u, v \in V$, $$ |\langle u, v \rangle| \leq \|u\| \, \|v\|. $$ Equality holds if and only if $u$ and $v$ are linearly dependent. The proof is the prototype of inner product arguments: for any scalar $t$, $$ 0 \leq \|u - t v\|^2 = \|u\|^2 - 2t \langle u, v \rangle + t^2 \|v\|^2. $$ The right-hand side is a quadratic polynomial in $t$. Choosing $t = \langle u, v \rangle / \|v\|^2$ to minimize it yields $0 \leq \|u\|^2 - \langle u, v \rangle^2 / \|v\|^2$, which rearranges to the claim. The proof reveals the deeper content of the inequality: it is the assertion that the projection of $u$ onto the line spanned by $v$ has length at most $\|u\|$.

Two vectors $u, v$ are *orthogonal*, written $u \perp v$, if $\langle u, v \rangle = 0$. A set of nonzero mutually orthogonal vectors is automatically linearly independent. A *basis* $\{u_1, \ldots, u_k\}$ of a subspace $H$ is *orthonormal* if $\langle u_i, u_j \rangle = \delta_{ij}$. The Gram–Schmidt procedure shows that every finite-dimensional subspace admits an orthonormal basis. Given an orthonormal basis and a vector $v \in V$, the projection of $v$ onto $H$ is $$ P_H v = \sum_{i=1}^k \langle v, u_i \rangle u_i. $$ The vector $v - P_H v$ is orthogonal to $H$ and is called the *residual*. The Pythagorean theorem in inner product form states $\|v\|^2 = \|P_H v\|^2 + \|v - P_H v\|^2$, the geometric fact that the two orthogonal components are independent in their squared-length contributions.

The projection theorem generalizes this construction to arbitrary closed subspaces and arbitrary convex sets. We state and prove the version for convex sets because the additional generality is needed for later chapters and the proof is not much harder.

> Theorem (Projection onto a closed convex set). Let $(V, \langle \cdot, \cdot \rangle)$ be a finite-dimensional inner product space and $C \subseteq V$ a nonempty closed convex set. For every $v \in V$ there exists a unique $p^\star \in C$ such that > $$ > \|v - p^\star\| = \min_{p \in C} \|v - p\|. > $$ > Moreover, $p^\star$ is the minimizer if and only if > $$ > \langle v - p^\star, \, p - p^\star \rangle \leq 0 \quad \text{for all } p \in C. > $$

*Proof.* The existence of a minimizer follows from the fact that a continuous function attains its minimum on a nonempty closed set that is bounded below. Closedness is the relevant hypothesis; the set $\{p \in C : \|v - p\| \leq \|v - p_0\|\}$ is closed and bounded for any fixed $p_0 \in C$, hence compact, so the continuous function $p \mapsto \|v - p\|$ attains its infimum there.

For uniqueness, suppose $p_1$ and $p_2$ are two minimizers. By the parallelogram law, $$ \|v - p_1\|^2 + \|v - p_2\|^2 = 2 \left\| v - \tfrac{p_1 + p_2}{2} \right\|^2 + \tfrac{1}{2} \|p_1 - p_2\|^2