The Formal Learning Problem

Formally, a learning problem is built from a small number of ingredients. The input space $\mathcal{X}$ is the set of all possible inputs — images, feature vectors, sequences, sensor readings. The output space $\mathcal{Y}$ is the set of possible answers: a finite set of labels for classification, an interval of $\mathbb{R}$ for regression, or a structured object for structured prediction. A hypothesis, or predictor, is a function $f: \mathcal{X} \to \mathcal{Y}$ (or, more generally, $f: \mathcal{X} \to \mathbb{R}$ producing a score that is later thresholded or ranked). The crucial and easily overlooked assumption is that the pairs $(x, y)$ we observe are not arbitrary. We posit an unknown joint probability distribution $P(X, Y)$ over $\mathcal{X} \times \mathcal{Y}$, and we assume the training data $D = \{(x_1, y_1), \dots, (x_n, y_n)\}$ consists of $n$ samples drawn independently and identically distributed (i.i.d.) from $P$. This single assumption is what makes learning from a finite sample meaningful at all: without some stable, repeatable regularity governing how inputs and outputs co-occur, no amount of past data could say anything about future data. Note that $P$ need not be deterministic — the same $x$ can produce different $y$ with different probabilities, reflecting real label noise (two radiologists might disagree on a borderline scan). To measure how bad a wrong prediction is, we introduce a loss function $L: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$, where $L(y, \hat y)$ is the penalty for predicting $\hat y$ when the true value is $y$. Common choices include the 0-1 loss $L(y, \hat y) = \mathbf{1}[y \ne \hat y]$ for classification, and the squared loss $L(y, \hat y) = (y - \hat y)^2$ for regression. The loss function is a modeling choice — it encodes what "wrong" costs, and different applications (e.g. a false negative in cancer screening versus a false positive in spam filtering) may demand very different loss functions even on the same data. With these three ingredients — $\mathcal{X}, \mathcal{Y}, P$ — and a loss $L$, we can finally define the object learning theory revolves around: the expected risk (also called the true risk or generalization risk) of a hypothesis $f$,

The formal learning problem is to find

over some class of admissible functions $\mathcal{F}$ (a topic taken up in Hypothesis Spaces). The unattainable ideal, $f^\star_{\text{Bayes}} = \arg\min_{f} R(f)$ over all measurable functions, is called the Bayes optimal predictor; its risk $R(f^\star_{\text{Bayes}})$ is the Bayes risk, the fundamental floor of error that not even infinite data and infinite compute can beat, because it is driven by irreducible noise in $P$ itself.

There is no "algorithm" for the formal learning problem itself — it is a specification, not a procedure. But it is worth walking through, step by step, exactly how this specification is turned into something computable, because the translation from the ideal (unknown $P$) to the practical (a finite sample) is the mechanism every learning algorithm actually implements.

Step 1 — Define the spaces. Fix $\mathcal{X}$ (e.g., $\mathbb{R}^d$ for feature vectors) and $\mathcal{Y}$ (e.g., $\{-1, +1\}$ for binary classification, or $\mathbb{R}$ for regression).

Step 2 — Posit the distribution. Assume there is a fixed, unknown $P(X,Y)$ generating all data of interest, past and future. We never get to see $P$; we only see samples from it.

Step 3 — Choose a loss. Pick $L(y, \hat y)$ appropriate to the task and its real-world costs.

Step 4 — State the ideal objective. The true goal is $\min_f R(f) = \min_f \mathbb{E}_{(x,y)\sim P}[L(y, f(x))]$. This cannot be computed directly since $P$ is unknown — there is no way to take an expectation over a distribution you cannot write down.

Step 5 — Approximate with a finite sample. Draw $D = \{(x_i, y_i)\}_{i=1}^n \overset{\text{i.i.d.}}{\sim} P$. Replace the true distribution with the empirical distribution $\hat P_n$ that places mass $1/n$ on each observed point. This yields the empirical risk:

Step 6 — Minimize the proxy. Every concrete learning algorithm (linear regression, logistic regression, a neural network trained by backpropagation, a decision tree splitting criterion) is, at heart, an optimization procedure that approximately solves

over some restricted hypothesis class $\mathcal{F}$ (never all measurable functions — that would let the optimizer memorize the sample with zero empirical risk while learning nothing generalizable). This restriction is the subject of Hypothesis Spaces.

Step 7 — Hope, and later verify, that $\hat R_n(f)$ tracks $R(f)$. The entire theoretical apparatus of generalization bounds exists to control the gap $|\hat R_n(f) - R(f)|$, which is exactly the subject taken up under Training Error vs Test Error. ``` ALGORITHM: EmpiricalRiskMinimization(D, F, L) Input: D = {(x_1, y_1), ..., (x_n, y_n)} // i.i.d. sample from unknown P F // hypothesis class (restricted!) L // loss function // Step 1: define the computable proxy for the true risk define R_hat(f) := (1/n) sum_{i=1..n} L(y_i, f(x_i)) // Step 2: search F for a minimizer of the proxy f_hat := argmin_{f in F} R_hat(f) // Step 3: return the learned predictor return f_hat // NOTE: R(f) = E_{(x,y)~P}[L(y, f(x))] is NEVER computed here — // P is unknown. R_hat(f) is the only quantity the algorithm // ever touches. The entire theory of generalization is about // how well R_hat(f_hat) approximates R(f_hat), and how far // R(f_hat) is from R(f) = min_{f in F} R(f). ``` The pseudocode above is deliberately generic: whether $\mathcal{F}$ is the set of linear functions, decision trees of depth $\le k$, or a fixed-architecture neural network, and whatever optimizer is used (closed-form least squares, gradient descent, greedy tree splitting), the shape of the problem is always: minimize an empirical average of losses in place of an unreachable expectation. This is why the formal learning problem is foundational — it is the common abstraction underlying every algorithm covered elsewhere in the curriculum.

Complexity. The formal learning problem itself has no algorithmic complexity — it is a mathematical statement, not a procedure — but the empirical-risk-minimization proxy that instantiates it does. Given $n$ samples in $\mathcal{X} \subseteq \mathbb{R}^d$:

• Computing $\hat R_n(f)$ for a fixed $f$ costs $O(n)$ loss evaluations, each $O(1)$ to $O(d)$ depending on how $f(x_i)$ is computed, giving $O(nd)$ total for one evaluation of the empirical risk.
• Minimizing $\hat R_n(f)$ over $\mathcal{F}$ is where all the real cost lives, and it is entirely algorithm-dependent: closed-form linear least squares costs $O(nd^2 + d^3)$ via normal equations; gradient-based methods cost $O(nd)$ per iteration times the number of iterations; tree-based greedy splitting costs $O(nd\log n)$ per level. None of this complexity is dictated by the formal learning problem itself — it is dictated by the choice of $\mathcal{F}$ and optimizer, which is exactly why the problem statement is deliberately separated from the algorithm.
• Space is $O(nd)$ to hold the sample, plus whatever the hypothesis class needs to store its parameters (e.g., $O(d)$ for a linear model, $O(\text{number of nodes})$ for a tree).

The one complexity fact that is intrinsic to the formal learning problem is statistical, not computational: as $n \to \infty$, under mild regularity conditions, $\hat R_n(f) \to R(f)$ almost surely for any fixed $f$, by the strong law of large numbers, since $\hat R_n(f)$ is literally a sample average of the i.i.d. random variables $L(y_i, f(x_i))$. The rate of this convergence, uniformly over an entire hypothesis class $\mathcal{F}$ rather than a single fixed $f$, is governed by concentration inequalities and complexity measures of $\mathcal{F}$ (VC dimension, Rademacher complexity) — this is precisely the machinery developed under Training Error vs Test Error and is foreshadowed, not derived, here.

Correctness. What does "correctness" even mean for a specification with no algorithm? It means the following chain of reasoning holds: 1. Well-posedness: because $(x_i,y_i)$ are i.i.d. draws from a single fixed $P$, the quantity $L(y_i, f(x_i))$ for fixed $f$ is itself an i.i.d. sequence of real-valued random variables with mean $R(f)$. This is what licenses calling $\hat R_n(f)$ an unbiased estimator of $R(f)$:

2. Consistency for a fixed $f$: by the law of large numbers, $\hat R_n(f) \to R(f)$ in probability (and almost surely) as $n \to \infty$, for any fixed $f$ with finite loss variance. 3. The subtlety: point 2 holds for one fixed $f$ chosen before seeing the data. But empirical risk minimization chooses $\hat f_n$ after seeing the data, specifically to make $\hat R_n(\hat f_n)$ small — so $\hat R_n(\hat f_n)$ is a biased (optimistically low) estimate of $R(\hat f_n)$. This is the formal origin of overfitting, and it is exactly why $\hat R_n(\hat f_n) \ne R(\hat f_n)$ in general, and why held-out test data is needed to estimate $R(\hat f_n)$ honestly. This tension is the seed from which Training Error vs Test Error grows. 4. Bayes-optimality as ground truth: for 0-1 loss and known $P$, the function $f^\star(x) = \arg\max_y P(Y = y \mid X = x)$ provably minimizes $R(f)$ over all functions — a fact provable by pointwise minimization of the conditional risk $\mathbb{E}[L(Y, f(x)) \mid X = x]$ for each $x$ independently, since the overall risk is an expectation (integral) over $x$ of these conditional risks, and each is minimized independently by choosing the most probable class. This gives a concrete, checkable sense in which the formal setup is "correct": it recovers exactly the intuitively right answer (predict the most likely label) when $P$ is fully known.

Honest tradeoffs. The formal framework assumes i.i.d. data from a fixed distribution — violated by distribution shift, temporal drift, or adversarial adaptation, all common in deployed systems. It also assumes the loss function fully captures real-world costs, which is often only an approximation (e.g., 0-1 loss ignores calibration, squared loss is sensitive to outliers). None of these are flaws in the framework so much as reminders that it is an idealization whose assumptions must be checked against reality.

Consider a tiny, fully concrete instance to make every symbol tangible. Suppose $\mathcal{X} = \{$small, medium, large$\}$ (house sizes, categorical) and $\mathcal{Y} = \{0, 1\}$ (0 = "sells under $300k", 1 = "sells over $300k"). Suppose, purely for illustration, that the true (unknown, in reality) joint distribution $P$ is:

We use 0-1 loss: $L(y,\hat y) = \mathbf 1[y \ne \hat y]$. If we knew $P$ (which real learners never do), the Bayes-optimal classifier predicts the majority label per $x$: $\hat y=0$ for small ($P(Y{=}1)=0.10<0.5$), $\hat y = 1$ for medium and large. Its Bayes risk is:

Even the best possible classifier is wrong 18% of the time — this is irreducible noise, not a flaw of any algorithm. Now suppose we don't know $P$; we only observe a sample of $n = 10$ houses drawn i.i.d. from it:

Consider the hypothesis class $\mathcal{F} = \{$all functions constant on each of the three categories$\}$ (equivalent to $2^3 = 8$ possible predictors, one bit per category). Empirical risk minimization picks, for each category, whichever label is the sample majority within that category:

• small: labels $\{0,0,0,1\}$ → majority 0, empirical error contribution $1/4$ within-group.
• medium: labels $\{1,0,1\}$ → majority 1, empirical error contribution $1/3$ within-group.
• large: labels $\{1,1,0\}$ → majority 1, empirical error contribution $1/3$ within-group.

This exactly recovers $\hat f_n(\text{small}) = 0$, $\hat f_n(\text{medium}) = 1$, $\hat f_n(\text{large}) = 1$ — matching the true Bayes rule in this case, purely because $n$ happened to be large enough for majorities to align. The empirical risk is:

Notice $\hat R_{10}(\hat f_n) = 0.30 \ne R(\hat f_n) = R(f^\star_{\text{Bayes}}) = 0.18$: the empirical risk on this particular small sample overestimates the true risk here (it could equally have underestimated it with different random draws), illustrating concretely that $\hat R_n(f)$ is only a noisy, sample-dependent proxy for $R(f)$ — exactly the point the LLN-based argument made abstractly above. With $n=10$, sampling noise is large; as $n$ grows toward thousands, the law of large numbers guarantees $\hat R_n(\hat f_n)$ will concentrate tightly around the true risk of whatever function is learned — the quantitative rate of that concentration is the subject taken up next in Training Error vs Test Error.

The formal learning problem as stated here — unknown distribution, loss function, expected risk — crystallized out of decades of work bridging probability theory, statistics, and computer science.

:::physicist[Vladimir Vapnik|born 1936|co-creator, with Alexey Chervonenkis, of statistical learning theory| Vapnik formalized empirical risk minimization as the central object of learning theory and, with Chervonenkis, developed VC dimension to explain when and why minimizing empirical risk over a restricted hypothesis class controls the true risk — directly foreshadowing the next topic in this sequence.

Every supervised learning system deployed today is, underneath its specific architecture, an instance of empirical risk minimization standing in for the formal learning problem. Search ranking systems minimize a proxy for the risk of showing irrelevant results; recommendation engines minimize a proxy for the risk of recommending items users won't engage with; medical diagnosis models minimize a proxy for the risk of misclassifying a scan, often with an asymmetric loss that penalizes missed cancers far more than false alarms. Autonomous vehicle perception stacks are trained by minimizing empirical risk over enormous labeled datasets, with the entire safety case resting on the (imperfect) assumption that deployment-time driving conditions resemble the training distribution. The formal framework also underlies the theoretical guarantees that regulators and engineers increasingly demand: PAC-learning bounds, generalization certificates, and risk-based model cards all trace back to this same skeleton — an unknown $P$, a loss $L$, a true risk $R(f)$, and an empirical proxy $\hat R_n(f)$. Understanding this skeleton is what lets a practitioner diagnose why a model that looked perfect in a notebook fails in production: almost always, it is because $\hat R_n(f)$ and $R(f)$ silently diverged, a phenomenon the next articles on Hypothesis Spaces and Training Error vs Test Error explain in full quantitative detail. It is also the conceptual backbone connecting supervised learning to the broader landscape introduced in Types of Learning: Supervised, Unsupervised, Reinforcement, since even unsupervised and reinforcement learning formulations define analogous risk functionals over their own respective distributions and loss (or reward) structures.

Ask the tutor: If the empirical risk is a biased estimate of the true risk once we've chosen the minimizing hypothesis, how do held-out test sets and cross-validation actually fix this problem?