Hypothesis Spaces

A hypothesis space, written $\mathcal{H}$, is the set of all functions $h: \mathcal{X} \to \mathcal{Y}$ that a learning algorithm considers as candidate explanations of the data, where $\mathcal{X}$ is the input space and $\mathcal{Y}$ is the output space (e.g., $\{-1, +1\}$ for binary classification or $\mathbb{R}$ for regression). Concrete examples include: the set of linear functions $h(x) = w^\top x + b$; the set of decision trees of depth at most $d$; the set of degree-$k$ polynomials; or the set of functions computable by a neural network with a fixed architecture and any weight setting. In every case, $\mathcal{H}$ is fixed before training begins — training only selects a member of $\mathcal{H}$, it does not expand $\mathcal{H}$ itself. This distinction matters because it separates two different sources of error and difficulty. Representational capacity asks: does $\mathcal{H}$ contain a function close to the true target function $f^*$ at all? Search / optimization asks: given that such a function exists in $\mathcal{H}$, can the learning algorithm actually find it (or something close to it) from finite, noisy data using a tractable procedure? A hypothesis space can be rich enough to contain a near-perfect solution yet still yield poor learning if the search procedure (gradient descent, greedy tree-splitting, etc.) cannot locate it, or if too little data is available to distinguish the good hypothesis from the many bad ones that also fit the training sample. Every choice of $\mathcal{H}$ encodes an inductive bias: a set of assumptions about what kinds of patterns are plausible, adopted before seeing any data. Restricting to linear functions assumes the relationship between input and output is (approximately) linear; restricting to shallow decision trees assumes a small number of axis-aligned rules suffice; restricting to convolutional networks assumes locality and translation-invariance matter for images. No inductive bias means no learning at all — this is formalized by the No Free Lunch theorem, which states that averaged over all possible target functions, every learning algorithm performs identically (equivalent to random guessing), because for every problem an algorithm solves well there exists another, equally likely a priori, that it solves badly. Learning is possible in practice only because the world is not adversarially uniform over all conceivable functions — real targets tend to be smooth, compositional, or low-complexity — and a well-chosen $\mathcal{H}$ exploits exactly that regularity.

Concretely, a learning algorithm operating over hypothesis space $\mathcal{H}$ follows the same generic template regardless of the specific model family. It is given training data, defines a notion of fit (a loss function), and searches $\mathcal{H}$ for the hypothesis that minimizes empirical loss — possibly regularized to control complexity within $\mathcal{H}$ itself. ``` Algorithm: Empirical Risk Minimization over a Hypothesis Space H Input: H - hypothesis space (a set of functions X -> Y) D = {(x_i, y_i)}_{i=1}^n - training data drawn i.i.d. from unknown distribution P L(h(x), y) - loss function measuring prediction error Omega(h) - optional complexity penalty (regularizer) over H 1. Define the empirical risk: R_hat(h) = (1/n) sum_{i=1}^n L(h(x_i), y_i) 2. Search H for a minimizer (possibly regularized): h_star = argmin_{h in H} R_hat(h) + lambda Omega(h) 3. Depending on H's structure, "search" is implemented differently:

• H = linear functions -> solve normal equations / gradient descent
• H = decision trees (depth d)-> greedy recursive splitting (heuristic search)
• H = k-NN rules -> no explicit search; H is defined by the data itself
• H = neural nets (fixed arch)-> stochastic gradient descent over weights

4. Return h_star as the learned predictor. 5. (Implicit, not computed by the algorithm, but what we CARE about:) True risk R(h) = E_{(x,y)~P}[ L(h(x), y) ] Generalization gap = R(h_star) - R_hat(h_star) ``` The crucial conceptual step is step 1–2: the algorithm never sees the true distribution $P$ or the true risk $R(h)$; it only ever minimizes the empirical risk over the fixed set $\mathcal{H}$. Everything the algorithm can possibly output lives inside $\mathcal{H}$ — if the true target function $f^*$ is not in $\mathcal{H}$ (or close to it), no amount of data or compute will let step 2 find it. This is why specifying $\mathcal{H}$ is inseparable from specifying the learning problem itself. Different model families are best understood as different parameterizations of a hypothesis space:

• Linear models: $\mathcal{H} = \{ x \mapsto w^\top x + b : w \in \mathbb{R}^d, b \in \mathbb{R}\}$. Parameterized by $(d+1)$ real numbers; search is convex optimization.
• Polynomial regression of degree $k$: $\mathcal{H}_k = \{ x \mapsto \sum_{j=0}^k w_j x^j \}$. Note $\mathcal{H}_0 \subset \mathcal{H}_1 \subset \mathcal{H}_2 \subset \dots$, an example of a nested hypothesis space hierarchy.
• Decision trees of depth $\le d$: a combinatorial, non-parametric $\mathcal{H}$; search is greedy and heuristic (exact ERM is NP-hard).
• Neural networks with a fixed architecture: $\mathcal{H}$ is the image of the weight space $\mathbb{R}^m$ under the network's forward function; enormous but continuously parameterized, searched via gradient-based methods.

The figure below depicts this nesting: as we allow richer function classes, the hypothesis space grows, and the true target function $f^*$ may or may not fall inside it.

Notice that $f^*$ sits inside $\mathcal{H}_5$ but outside $\mathcal{H}_1$. This is the geometric picture of underfitting: if you commit to the smallest, innermost space ($\mathcal{H}_1$, lines) and the truth requires a richer curve, no algorithm operating over $\mathcal{H}_1$ can ever close that gap — this is an irreducible approximation error, distinct from any error caused by finite sample size or optimization failure.

Approximation error vs. estimation error. The total error of a learned hypothesis decomposes cleanly. Let $f^*$ be the Bayes-optimal predictor, $h^*_{\mathcal H} = \arg\min_{h \in \mathcal H} R(h)$ the best hypothesis achievable within $\mathcal{H}$, and $\hat h$ the hypothesis actually returned by the learning algorithm. Then

The approximation error depends only on $\mathcal{H}$ and the true distribution — it measures how well the best possible member of $\mathcal{H}$ could do, and it shrinks (weakly monotonically) as $\mathcal{H}$ grows, since a richer space can only contain functions at least as good. The estimation error arises because we only have $n$ finite samples and must search among many equally-plausible-looking hypotheses in $\mathcal{H}$; it tends to grow with the size/complexity of $\mathcal{H}$, because there are more ways for a rich space to fit noise in the training sample rather than signal. This is exactly the tension that will be formalized quantitatively in The Bias-Variance Tradeoff: approximation error behaves like (squared) bias, and estimation error behaves like variance.

Measuring the size of $\mathcal{H}$. For finite hypothesis spaces, a basic sample-complexity bound from PAC learning theory states that with $n$ i.i.d. training examples, for any $\delta \in (0,1)$, with probability at least $1-\delta$ every $h \in \mathcal{H}$ satisfies

This is a uniform convergence bound (derived via a union bound over $|\mathcal H|$ hypotheses combined with Hoeffding's inequality per hypothesis) and it makes the tradeoff numerically explicit: doubling $|\mathcal{H}|$ only adds $\ln 2$ inside a square root, so the generalization gap grows slowly (logarithmically) with the number of candidate hypotheses, but grows all the same. For infinite hypothesis spaces (e.g., all linear separators in $\mathbb{R}^d$), $|\mathcal{H}| = \infty$ and this bound is vacuous, so we instead use the VC dimension $\mathrm{VC}(\mathcal{H})$ — the size of the largest set of points $\mathcal{H}$ can shatter (label in every possible way). The analogous bound becomes

replacing $\ln|\mathcal H|$ with an effective combinatorial capacity that stays finite even for infinite function classes. For linear separators in $\mathbb{R}^d$, $\mathrm{VC}(\mathcal{H}) = d+1$; for decision trees, VC dimension grows roughly linearly in the number of leaves; for neural networks it typically scales with the number of parameters (though modern over-parameterized networks complicate this picture, which is why norm-based and margin-based capacity measures are used alongside VC dimension in practice).

Search complexity. Separately from statistical estimation error, we must ask how expensive it is to compute $\arg\min_{h\in\mathcal H} \hat R(h)$:

• Linear regression: closed form via the normal equations, $O(nd^2 + d^3)$ time — exact ERM is efficiently solvable because the objective is convex.
• Decision trees: exact ERM over all trees of depth $d$ is NP-hard; practical algorithms use greedy, heuristic recursive splitting, costing roughly $O(n d \cdot \text{depth})$ per tree but giving no optimality guarantee.
• Neural networks: the loss landscape is non-convex; gradient descent finds a local optimum in $\mathcal H$ in time proportional to (number of parameters) $\times$ (number of gradient steps), with no general guarantee of reaching the global ERM solution, though empirically it often generalizes well regardless.

Correctness argument (why restricting $\mathcal H$ is necessary, not just convenient). The No Free Lunch theorem gives the formal reason a hypothesis space is unavoidable: consider the space of all functions $\mathcal{X}\to\mathcal{Y}$. For any learning algorithm $A$ and any finite training sample, there exist target functions $f^*$ agreeing with $A$'s training data perfectly but on which $A$'s output performs at chance level on unseen points — because unconstrained function space contains a function realizing every possible labeling of the unseen points, consistent with the seen ones. Averaging uniformly over all such adversarial targets, every algorithm has identical expected performance. The only way out is to restrict $\mathcal H$ to functions that respect some structural regularity (smoothness, low-degree, sparsity, compositionality) that we believe the true target shares — this restriction is precisely what makes the uniform-convergence bounds above non-vacuous, and it is the price and the payoff of choosing $\mathcal H$ correctly.

Consider fitting data generated by the true (unknown to the learner) function $f^*(x) = \sin(2\pi x)$ on $x \in [0,1]$, observed with noise: $y_i = f^*(x_i) + \varepsilon_i$, $\varepsilon_i \sim \mathcal N(0, 0.1^2)$, with $n = 10$ training points. We compare three hypothesis spaces: constant functions ($\mathcal H_0$), lines ($\mathcal H_1$), and degree-9 polynomials ($\mathcal H_9$), fitting each by least squares (ERM under squared loss).

Walking through what happens inside each search: $\mathcal H_0$ and $\mathcal H_1$ have so little capacity that even the best possible member of the space (the true minimizer of $R(h)$, not just $\hat R(h)$) is far from $f^*$ — this is approximation error, and it would remain even with infinite training data, because a straight line is structurally incapable of oscillating. Moving to $\mathcal H_3$, the space now contains functions close to $\sin(2\pi x)$ over $[0,1]$ (a cubic can approximate one hump-and-a-half of a sine reasonably well), so approximation error drops sharply, and with only 4 parameters versus 10 data points there is enough data to pin down the coefficients reliably — estimation error stays low too. At $\mathcal H_9$, something different happens: with exactly as many free parameters (10) as data points (10), the least-squares solution can drive training error to essentially zero by threading the polynomial through every noisy observation exactly. But this uses up its 10 degrees of freedom to fit the noise $\varepsilon_i$ as much as the signal $f^*(x_i)$, since ERM cannot tell noise from signal — it only sees $y_i$. The result is a hypothesis with near-zero empirical risk but catastrophically high true risk: the polynomial swings wildly between the training points (the classical Runge phenomenon), which is exactly the estimation-error blow-up predicted by the capacity bound in the previous section — $\mathrm{VC}$-like capacity of $\mathcal H_9$ is large relative to $n=10$, so the generalization gap bound is loose and, empirically, realized. The lesson generalizes far beyond polynomials: the same underfit/sweet-spot/overfit pattern reappears when varying tree depth, the number of nearest neighbors $k$, or the width of a neural network layer — it is a structural property of hypothesis-space capacity versus sample size, not an accident of this particular example.

The formal theory of hypothesis spaces emerged from the fusion of statistics and computational learning theory in the late twentieth century, though the core intuition — that restricting the space of admissible explanations is what makes inference from finite data possible — traces back to earlier work on inductive inference and statistical estimation.

The concept of a hypothesis space is not an abstraction confined to theory courses — it is a daily engineering decision. When a practitioner chooses "linear regression vs. random forest vs. deep network" for a production system, they are choosing a hypothesis space, with direct consequences for how much data is required, how interpretable the result is, and how the model will behave on inputs unlike anything seen in training. Regularized linear models (Lasso, Ridge) are ubiquitous in finance and healthcare precisely because their small, well-understood hypothesis space gives interpretable, statistically stable estimates from limited data, where a richer model would overfit given the small sample sizes typical of clinical trials. In deep learning, the architecture itself is the specification of the hypothesis space: convolutional networks restrict $\mathcal H$ to functions respecting spatial locality and translation equivariance, which is why they dominate image tasks with far less data than a fully-connected network of comparable size would need — the inductive bias built into the architecture compensates for limited data by shrinking the effective search space to functions plausible for images. Transformer architectures encode a different inductive bias (permutation-equivariant attention over sets of tokens), suited to language and sequence data. AutoML and neural architecture search systems are, in effect, automated procedures for searching over a meta-hypothesis-space of architectures, each of which defines its own downstream $\mathcal H$. Kernel methods (including the Support Vector Machine) make the choice of hypothesis space explicit and mathematically elegant: the kernel function implicitly defines an entire (often infinite-dimensional) hypothesis space of functions in a reproducing kernel Hilbert space, and regularization (the margin) controls effective capacity within that space without ever materializing it directly. Every discussion of underfitting, overfitting, regularization strength, early stopping, or model selection in modern machine learning — from a spreadsheet regression to a foundation model with billions of parameters — is ultimately a discussion about the size, shape, and appropriateness of a hypothesis space for the problem at hand.

Ask the tutor: How does regularization mathematically change the effective hypothesis space, and can we quantify that shrinkage the same way we quantify VC dimension?