The Learning Problem

Machine learning, at its most practical, appears to be an empirical art: collect data, train a model, evaluate performance, iterate. But beneath this pragmatic surface lies a profound mathematical structure—one that explains why learning is possible, when it will succeed, and what fundamental limits constrain every learning algorithm ever devised.

This formal structure is Statistical Learning Theory, and understanding it transforms you from a practitioner who applies algorithms to an engineer who understands the guarantees, assumptions, and failure modes that govern machine learning systems.

We begin at the beginning: the formal definition of what it means to learn from data.

To reason precisely about learning, we must first define the mathematical objects involved. Every learning problem consists of several interconnected components. Let us define each with care.

The Input Space X

The input space $\mathcal{X}$ is the set of all possible inputs to our learning system. Depending on the problem domain, $\mathcal{X}$ could be:

• $\mathbb{R}^d$ — a $d$-dimensional Euclidean space for numerical features
• ${0, 1}^n$ — binary feature vectors
• The space of all images of a given resolution
• The space of all natural language sentences
• Any structured space (graphs, sequences, etc.)

Crucially, $\mathcal{X}$ is typically a measurable space, meaning we can define probability distributions over it. We don't assume any special structure unless explicitly stated—$\mathcal{X}$ could be discrete, continuous, or mixed.

The Output Space Y

The output space $\mathcal{Y}$ is the set of all possible outputs or labels. The nature of $\mathcal{Y}$ determines the learning problem type:

The formalism accommodates all these by treating $\mathcal{Y}$ abstractly. For our initial development, we'll focus on classification ($\mathcal{Y}$ finite) and regression ($\mathcal{Y} = \mathbb{R}$), but the framework extends broadly.

The Unknown Distribution D

Here lies the central assumption of statistical learning: there exists an unknown probability distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$.

This distribution encodes everything about the relationship between inputs and outputs in the real world. When we draw a sample $(x, y) \sim \mathcal{D}$:

• $x$ is an input drawn from the marginal distribution $\mathcal{D}_\mathcal{X}$ over inputs
• $y$ is the corresponding output, which may be deterministic given $x$, or may have randomness (noise)

This distribution is unknown to us. If we knew $\mathcal{D}$, there would be no learning problem—we could directly compute the optimal prediction for any input. The essence of machine learning is to infer useful properties of $\mathcal{D}$ from finite samples.

The Training Set S

Given the distribution $\mathcal{D}$, we observe a training set $S$ consisting of $n$ i.i.d. samples:

$$S = {(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)} \sim \mathcal{D}^n$$

We write $S \sim \mathcal{D}^n$ to denote that $S$ is drawn from the product distribution—$n$ independent samples from $\mathcal{D}$.

The training set is our only window into the unknown distribution. Everything we can learn about $\mathcal{D}$ must come from $S$. This is both the opportunity and the challenge: $S$ carries information about $\mathcal{D}$, but as a finite sample, it necessarily provides an incomplete picture.

Notation: We often write $|S| = n$ to denote the training set size. The subscript $n$ or $m$ varies by convention across textbooks.

What is a Hypothesis?

A hypothesis $h$ is a function from inputs to outputs:

$$h: \mathcal{X} \rightarrow \mathcal{Y}$$

Given an input $x$, the hypothesis produces a prediction $h(x)$. In the context of supervised learning, we seek a hypothesis whose predictions match the true outputs as closely as possible.

Examples of hypotheses:

• Linear classifier: $h(x) = \text{sign}(w^\top x + b)$ for binary classification
• Linear regression: $h(x) = w^\top x$ for regression
• Decision tree: $h$ defined by a tree structure mapping $x$ to leaves
• Neural network: $h(x) = f_\theta(x)$ for some parameterized architecture

The term "hypothesis" reflects the epistemological stance: we are hypothesizing that $h$ captures the true relationship between $X$ and $Y$.

The Hypothesis Class H

A hypothesis class $\mathcal{H}$ is the set of all hypotheses that a learning algorithm can potentially output. It represents the space of models we are willing to consider.

$$\mathcal{H} \subseteq {h : \mathcal{X} \rightarrow \mathcal{Y}}$$

The choice of $\mathcal{H}$ is one of the most consequential decisions in machine learning design. It embodies our assumptions about the problem:

Finite vs. Infinite Hypothesis Classes

Hypothesis classes can be:

Finite: $|\mathcal{H}| < \infty$

Examples include decision stumps on a finite feature space, or any explicitly enumerable set of hypotheses. Finite hypothesis classes are theoretically simpler—we can analyze them using basic counting arguments.

Infinite (but parameterized): $|\mathcal{H}| = \infty$ but $\mathcal{H} = {h_\theta : \theta \in \Theta}$

Linear classifiers in $\mathbb{R}^d$ form an infinite class (infinitely many possible weight vectors), but the class has finite VC dimension (as we'll see later), making analysis tractable.

Infinite (nonparametric): Truly massive classes like all bounded functions

These require sophisticated tools (Rademacher complexity, covering numbers) to analyze.

Much of learning theory is concerned with characterizing the complexity of $\mathcal{H}$ in ways that predict generalization ability.

The Realizable vs. Agnostic Settings

Two important modeling assumptions:

Realizable Setting: There exists a hypothesis $h^* \in \mathcal{H}$ such that $h^*(x) = y$ with probability 1 under $\mathcal{D}$. That is, the true labeling function is in our hypothesis class, and there's no label noise.

Agnostic Setting: No such assumption. The best hypothesis in $\mathcal{H}$ may still have non-zero error. This is the realistic setting—our model class may be misspecified, and data may be noisy.

The realizable setting is useful for developing intuition and proving foundational results, but practical learning theory must handle the agnostic case where:

• Our hypothesis class may not contain the true function
• Labels may be corrupted by noise
• The relationship between $X$ and $Y$ may be inherently probabilistic

Measuring Prediction Quality: The Loss Function

To evaluate hypotheses, we need a quantitative measure of prediction quality. A loss function $\ell: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}_{\geq 0}$ measures the discrepancy between a prediction $\hat{y} = h(x)$ and the true label $y$.

$$\ell(h(x), y) = \text{penalty for predicting } h(x) \text{ when truth is } y$$

Important properties of loss functions:

• Non-negativity: $\ell(\hat{y}, y) \geq 0$ always
• Zero loss for correct prediction: Often (but not always) $\ell(y, y) = 0$
• Domain-specific design: Loss functions encode what matters in the application

The True Risk (Expected Risk)

The true risk (or expected risk or population risk) of a hypothesis $h$ is the expected loss over the unknown distribution:

$$R(h) = \mathbb{E}{(x,y) \sim \mathcal{D}}[\ell(h(x), y)] = \int{\mathcal{X} \times \mathcal{Y}} \ell(h(x), y) , d\mathcal{D}(x, y)$$

This is the quantity we truly care about. It measures how well $h$ will perform on new, unseen data drawn from the same distribution—the very essence of generalization.

For classification with 0-1 loss: $$R(h) = \mathbb{P}_{(x,y) \sim \mathcal{D}}[h(x) eq y]$$

This is simply the probability of misclassification on a random draw from $\mathcal{D}$—exactly what we mean by "error rate."

The Bayes Optimal Predictor

Given full knowledge of $\mathcal{D}$, what is the best possible prediction for any input $x$?

For 0-1 loss, the optimal predictor is the Bayes classifier:

$$h^*(x) = \arg\max_{y \in \mathcal{Y}} \mathbb{P}[Y = y \mid X = x]$$

This predicts the most probable label given the input. The risk of the Bayes classifier, called the Bayes error $R^* = R(h^*)$, is the lowest achievable by any classifier.

For squared loss in regression, the Bayes optimal predictor is the conditional expectation:

$$h^*(x) = \mathbb{E}[Y \mid X = x]$$

The Bayes risk is the irreducible minimum error. It represents inherent noise in the labeling process that no algorithm can overcome. Any risk $R(h) > R^*$ reflects suboptimality of $h$ compared to the best possible.

What Does a Learning Algorithm Do?

With the components defined, we can now precisely state what a learning algorithm is:

Definition (Learning Algorithm): A learning algorithm $\mathcal{A}$ is a function that takes a training set $S \in (\mathcal{X} \times \mathcal{Y})^n$ and outputs a hypothesis $h_S \in \mathcal{H}$:

$$\mathcal{A}: (\mathcal{X} \times \mathcal{Y})^n \rightarrow \mathcal{H}$$ $$\mathcal{A}(S) = h_S$$

The algorithm examines the training data $S$ and produces a hypothesis $h_S$. The subscript $S$ emphasizes that the output depends on the particular training set.

Note that $\mathcal{A}$ may be deterministic (same $S$ always yields same $h_S$) or randomized (incorporating random choices during training).

The Ideal Goal: Minimize True Risk

Ideally, we want a learning algorithm that finds the hypothesis minimizing true risk:

$$h^* \in \arg\min_{h \in \mathcal{H}} R(h)$$

This $h^*$ is the best hypothesis in our class according to the unknown distribution.

But we face a fundamental obstacle: $R(h)$ depends on the unknown $\mathcal{D}$. We cannot evaluate, let alone minimize, a quantity we cannot compute.

This gap—between what we want (low true risk) and what we can compute (only training data)—is the central tension of statistical learning theory.

The Bridge: Empirical Surrogate

The central strategy of statistical learning is to replace the true risk with an empirical surrogate that we can compute:

Empirical Risk: Given training set $S = {(x_1, y_1), \ldots, (x_n, y_n)}$, the empirical risk of $h$ is:

$$\hat{R}S(h) = \frac{1}{n} \sum{i=1}^{n} \ell(h(x_i), y_i)$$

The empirical risk is the average loss on the training set—an estimate of $R(h)$ using the available samples.

For classification with 0-1 loss: $$\hat{R}S(h) = \frac{1}{n} \sum{i=1}^{n} \mathbb{1}[h(x_i) eq y_i] = \frac{\text{number of training mistakes}}{n}$$

This is simply the training error rate.

We can now state the learning problem with full precision:

THE SUPERVISED LEARNING PROBLEM

Given:

• Input space $\mathcal{X}$ and output space $\mathcal{Y}$
• Unknown distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$
• Training set $S = {(x_i, y_i)}_{i=1}^n$ drawn i.i.d. from $\mathcal{D}$
• Hypothesis class $\mathcal{H}$
• Loss function $\ell: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}_{\geq 0}$

Find: A hypothesis $h_S \in \mathcal{H}$ using only $S$ such that $R(h_S)$ is small.

The learning algorithm is a mapping from training sets to hypotheses: $\mathcal{A}: (\mathcal{X} \times \mathcal{Y})^* \rightarrow \mathcal{H}$.

Specifying "Small" Risk: Types of Guarantees

What does it mean for $R(h_S)$ to be "small"? Different formulations provide different guarantees:

1. Absolute Performance: $$R(h_S) \leq \epsilon$$

The error is below some threshold $\epsilon$. Often achievable only in the realizable setting.

2. Relative to Best in Class: $$R(h_S) \leq \min_{h \in \mathcal{H}} R(h) + \epsilon$$

The error is within $\epsilon$ of the best hypothesis in $\mathcal{H}$. This is the agnostic formulation—we don't assume $\mathcal{H}$ contains the perfect hypothesis.

3. Relative to Bayes: $$R(h_S) - R^* \leq \epsilon$$

The excess risk over Bayes optimal is at most $\epsilon$. This is the ideal but may require $\mathcal{H}$ to be rich enough to approximate $h^*$.

The PAC Framework

The Probably Approximately Correct (PAC) framework, introduced by Leslie Valiant in 1984, formalizes these probabilistic guarantees:

Definition (PAC Learnable): A hypothesis class $\mathcal{H}$ is PAC learnable if there exists an algorithm $\mathcal{A}$ and a function $n_\mathcal{H}: (0,1)^2 \rightarrow \mathbb{N}$ (the sample complexity) such that for every distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$, for every $\epsilon, \delta \in (0,1)$:

If $n \geq n_\mathcal{H}(\epsilon, \delta)$, then with probability at least $1 - \delta$ over $S \sim \mathcal{D}^n$: $$R(\mathcal{A}(S)) \leq \min_{h \in \mathcal{H}} R(h) + \epsilon$$

Interpretation:

• Probably: With high probability $(1 - \delta)$
• Approximately: Within $\epsilon$ of optimal
• Correct: According to the true distribution $\mathcal{D}$

We will develop this framework in detail in the next section of this module.

The formal framework reveals that successful learning depends critically on assumptions. Without appropriate assumptions, learning is provably impossible.

Assumption 1: The I.I.D. Assumption

Training and test data are drawn independently from the same distribution $\mathcal{D}$. This assumption enables:

• Statistical estimation theory (law of large numbers, concentration inequalities)
• Guarantees that training performance indicates test performance

When it fails: Distribution shift (training data from one population, test from another), temporal dependence (time series), adversarial selection of test points. These scenarios require specialized theory.

Assumption 2: The Hypothesis Class Assumption

We assume the learner commits to a hypothesis class $\mathcal{H}$. This assumption:

• Provides the inductive bias necessary for generalization
• Constrains the search space to something analyzable
• May or may not contain the true labeling function

The fundamental tradeoff:

• $\mathcal{H}$ too small: May not contain good approximations to the truth (high bias)
• $\mathcal{H}$ too large: Hard to find the right hypothesis from finite data (high variance)

This is the bias-variance tradeoff in its most fundamental form, which we'll analyze rigorously later in this chapter.

You might wonder why we need such abstract machinery. After all, practitioners often train models without thinking deeply about probability spaces and measurability. Here's why the formal framework is essential:

1. It Explains Why Learning Works

Without the formal framework, machine learning is empirical alchemy: we throw data at algorithms and hope for good results. The framework provides principled explanations:

• Why does increasing data help? Concentration inequalities show empirical risk converges to true risk.
• Why does regularization prevent overfitting? It constrains the effective hypothesis class, reducing variance.
• Why do some algorithms generalize better? Their implicit hypothesis class has lower complexity.
• When will learning fail? When assumptions are violated or hypothesis class is mismatched.

2. It Provides Guarantees and Bounds

The framework enables provable guarantees:

• Sample complexity bounds: How much data is needed for a given accuracy?
• Generalization bounds: How far can test error differ from training error?
• Computational bounds: How much computation is required?

These aren't just academic exercises. In high-stakes applications (medical diagnosis, autonomous vehicles, financial systems), knowing the worst-case behavior of algorithms is crucial.

3. It Guides Algorithm Design

Understanding the theory suggests improved algorithms:

• Regularization techniques emerge from analyzing variance in high-dimensional settings
• Model selection procedures (cross-validation, structural risk minimization) are grounded in the theory
• Novel algorithms are developed by optimizing theoretical bounds

We have established the foundational mathematical framework for statistical learning theory. Let us consolidate the key components:

What's Next

With the formal framework established, we can now ask the central question: How do we actually find a good hypothesis?

The next page introduces Empirical Risk Minimization (ERM)—the principle of choosing the hypothesis that minimizes error on the training set. We'll analyze when ERM works, why it can fail, and what additional conditions ensure that minimizing training error leads to low test error.

This will lead us to the deep questions of generalization: the gap between empirical and true risk, and the theoretical tools (VC dimension, Rademacher complexity) that characterize when learning is possible.