Empirical Risk Minimization

Let $\mathcal{X}$ be the space of inputs and $\mathcal{Y}$ the space of labels, and suppose data pairs $(x, y)$ are drawn i.i.d. from some fixed but unknown distribution $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$. Given a hypothesis $h: \mathcal{X} \to \mathcal{Y}$ (or, in regression/probabilistic settings, $h: \mathcal{X} \to \mathbb{R}$ or a distribution) and a loss function $\ell(h(x), y)$ quantifying prediction error, the quantity we actually want to minimize is the true risk (also called generalization error or expected risk):

This is an expectation over the entire population — every email that could ever be sent, every image that could ever be photographed. It is not computable, because $\mathcal{D}$ is unknown and infinite (or effectively so). What we have instead is a training sample $S = \{(x_1,y_1), \dots, (x_n,y_n)\}$ drawn i.i.d. from $\mathcal{D}$. The empirical risk is the average loss on this sample:

The Empirical Risk Minimization principle says: given a hypothesis class $\mathcal{H}$ (linear models, decision trees, neural networks of a given architecture, etc.), choose

The word "empirical" is doing real epistemological work here — it flags that $\hat R_S$ is a statistic, a random variable that depends on which particular sample $S$ we happened to draw. Two different samples of the same size from the same distribution will generally yield two different empirical risks, and two different minimizers $\hat h$. ERM is only sensible as a strategy because, under reasonable conditions, $\hat R_S(h)$ is an unbiased and concentrating estimator of $R(h)$ for every fixed $h$: $\mathbb{E}_S[\hat R_S(h)] = R(h)$, and by concentration inequalities the empirical average is unlikely to deviate far from this expectation once $n$ is moderately large. This is precisely what licenses treating "minimize training loss" as a reasonable surrogate for "minimize true risk," and it connects ERM directly to the broader logic of Learning as Optimization: once risk is replaced by a finite sum, learning becomes a tractable optimization problem over the parameters defining $h$.

In practice, ERM is not applied to an abstract hypothesis class directly; it is applied to a parameterized family $h_\theta$, $\theta \in \Theta \subseteq \mathbb{R}^d$ (e.g., weights of a linear model or a neural network). The learning problem becomes a finite-dimensional optimization:

where the bracketed regularization term $\Omega(\theta)$ is optional — pure ERM omits it, but nearly every practical deployment includes it as a hedge against the overfitting failure mode discussed below. The generic ERM recipe has four steps: define the loss, form the empirical risk as a sum over the sample, choose an optimizer suited to that sum's structure (closed-form, convex solver, or stochastic gradient descent), and evaluate on held-out data to check that minimizing training loss actually reduced risk on unseen data. ``` ALGORITHM: Empirical Risk Minimization (generic, gradient-based) INPUT: training sample S = {(x_1, y_1), ..., (x_n, y_n)} hypothesis family h_theta parameterized by theta loss function ell(prediction, label) learning rate schedule eta_t, number of steps T (optional) regularizer Omega(theta), coefficient lambda INITIALIZE theta_0 (e.g., small random values, or zeros for convex ell) DEFINE empirical_risk(theta): return (1/n) sum_{i=1}^{n} ell(h_theta(x_i), y_i) [+ lambda Omega(theta)] FOR t = 0, 1, ..., T-1:

# compute gradient of empirical risk w.r.t. theta

# (full batch, or mini-batch estimate over a random subset B of S) g_t = (1/|B|) sum_{(x,y) in B} grad_theta ell(h_{theta_t}(x), y) [+ lambda grad Omega(theta_t)] theta_{t+1} = theta_t - eta_t * g_t RETURN theta_T

# Model selection wrapper (choosing among hypothesis classes / regularization strengths) SPLIT data into S_train, S_val FOR each candidate (H_k, lambda_k) in a set of configurations: theta_k = ERM(S_train, H_k, lambda_k) # inner training loop above score_k = empirical_risk_on(S_val, theta_k) # unbiased estimate on unseen data CHOOSE k = argmin_k score_k RETURN theta_{k}, refit optionally on S_train + S_val ``` Two structural points about this pseudocode deserve emphasis. First, the inner loop is exactly gradient descent (or SGD) applied to a function that happens to be an average over data points — this is why ERM turns statistics into an optimization problem tractable by the standard machinery of calculus. Second, the outer model-selection wrapper is not optional cosmetic advice: it exists because the training-set empirical risk of the chosen hypothesis is a biased (optimistic) estimate of its true risk, precisely because the choice was made to minimize that same quantity. A separate validation split (or cross-validation) is needed to get an honest read on generalization, foreshadowing the Bias-Complexity Tradeoff.

Computational complexity. ERM's cost splits into per-step cost and number of steps. For a single gradient evaluation over the full sample, computing $\nabla \hat R_S(\theta)$ costs $O(n \cdot c)$, where $c$ is the cost of computing $\nabla_\theta \ell(h_\theta(x_i), y_i)$ for one example (for a linear model in $d$ dimensions, $c = O(d)$; for a neural network, $c$ is the cost of one forward-backward pass). Full-batch gradient descent for $T$ iterations therefore costs $O(T n c)$. Mini-batch stochastic gradient descent with batch size $b$ reduces the per-step cost to $O(bc)$, trading off gradient variance against per-step speed — the standard reason SGD dominates in large-$n$ settings, since it makes progress without ever touching the full dataset in one step. For special cases, ERM is exactly solvable: ordinary least squares ERM with squared loss has a closed-form solution $\hat\theta = (X^TX)^{-1}X^Ty$, computable in $O(nd^2 + d^3)$ via normal equations, or $O(nd^2)$ via QR without forming $X^TX$ explicitly. Space complexity is $O(nd)$ to store the design matrix (or $O(d)$ if streaming mini-batches from disk).

Convexity and solvability. When $\ell(h_\theta(x), y)$ is convex in $\theta$ for every fixed $(x,y)$ — true for squared loss with linear $h_\theta$, and for logistic/hinge loss with linear $h_\theta$ — the empirical risk $\hat R_S(\theta) = \frac1n\sum_i \ell(h_\theta(x_i),y_i)$ is a sum of convex functions, hence convex. This guarantees that any local minimum found by gradient descent is a global minimum, and convex optimization theory gives explicit convergence rates (e.g., $O(1/T)$ for gradient descent on smooth convex functions, $O(1/\sqrt T)$ for subgradient methods on non-smooth ones like hinge loss). For non-convex $h_\theta$ (deep networks), ERM training only guarantees convergence to a stationary point, and correctness of the optimization is a separate, weaker claim than correctness of the learning — a stationary point of empirical risk need not be a good solution.

Statistical correctness — why minimizing $\hat R$ is justified at all. The real theoretical content of ERM is not the optimization; it's the argument that a small $\hat R_S(\hat h)$ implies a small $R(\hat h)$. Fix any single hypothesis $h$. Since $(x_i, y_i)$ are i.i.d., the losses $\ell(h(x_i), y_i)$ are i.i.d. random variables with mean $R(h)$, so by the (weak) Law of Large Numbers,

If the loss is bounded, $\ell \in [0, M]$, Hoeffding's inequality sharpens this to a finite-sample, exponential concentration bound: for any $\varepsilon > 0$,

This says empirical risk is a good estimate of true risk for a fixed h chosen in advance. But ERM does not fix $h$ in advance — it searches over $\mathcal{H}$ and picks the empirically best one, which means the bound above cannot be applied directly to $\hat h$: the act of selecting the minimizer correlates the choice of $h$ with the sample, invalidating the naive argument (this is the same trap that makes training-set accuracy optimistic). The fix is a uniform convergence bound over the whole class, via a union bound (for finite $\mathcal{H}$) or VC-dimension / Rademacher complexity arguments (for infinite $\mathcal{H}$):

If this uniform bound holds, then in particular it holds for $h = \hat h$, and one can show

where $h^* = \arg\min_{h\in\mathcal{H}} R(h)$ is the best possible hypothesis in the class. This chain of inequalities is the crux: it shows ERM's output is nearly as good as the best hypothesis in the class, with excess risk controlled by the uniform convergence rate. This is exactly the machinery formalized by PAC Learning, and the rate $\delta(n,\varepsilon,\mathcal H)$ depends critically on the complexity of $\mathcal H$ (e.g., VC dimension), which is why controlling that complexity — via Regularization Theory or restricting $\mathcal H$ — is unavoidable, not optional, once $\mathcal H$ is rich.

Honest tradeoff. ERM alone gives no guarantee if $\mathcal H$ is unrestricted: with enough capacity, $\hat R_S(\hat h)$ can be driven to zero (e.g., a lookup table memorizing the sample) while $R(\hat h)$ stays at the level of random guessing, because a memorizing hypothesis generalizes to nothing outside the sample. The theory above only bites when $\mathcal H$'s complexity is controlled relative to $n$ — this is precisely the content of the Bias-Complexity Tradeoff.

Consider a tiny 1-D regression problem: predicting a house's price (in $100k) from its size (in units of 1000 sq ft), using$n = 6$training examples, fitting$h_\theta(x) = \theta_0 + \theta_1 x$under squared loss$\ell(h(x),y) = (h(x)-y)^2$.

Step 1 — form the empirical risk. With $\theta = (\theta_0, \theta_1)$:

This is convex quadratic in $\theta$, so ERM here is exactly solvable via the normal equations, no iterative solver needed.

Step 2 — closed-form minimization. Compute sufficient statistics: $\bar x = 1.8\overline{3}$, $\bar y = 2.766\overline{6}$. The least-squares slope and intercept are

Carrying out the arithmetic (deviations $x_i - \bar x$: $-1.033, -0.833, -0.333, 0.167, 0.667, 1.167$; $y_i - \bar y$: $-1.267, -0.767, -0.367, 0.333, 0.833, 1.233$):

So $\theta_1 \approx 4.121 / 3.707 \approx 1.112$, and $\theta_0 \approx 2.767 - 1.112 \times 1.833 \approx 0.72$.

Step 3 — evaluate empirical risk at the minimizer. Plugging $\hat h(x) = 0.72 + 1.112x$ back in gives predictions $\{1.61, 1.83, 2.39, 2.94, 3.50, 4.06\}$ against actual $\{1.5, 2.0, 2.4, 3.1, 3.6, 4.0\}$; squared errors are roughly $\{0.012, 0.029, 0.0001, 0.026, 0.010, 0.004\}$, averaging to $\hat R_S(\hat\theta) \approx 0.013$.

Step 4 — the generalization question. This small $\hat R_S$ is not automatically the true risk. If size is measured with noise, or if the true relationship is mildly nonlinear (say prices actually follow $y = 0.5 + 1.3x - 0.15x^2$), a linear ERM fit will have systematically higher risk on new houses than $0.013$ suggests, because the linear class $\mathcal H$ cannot represent the curvature — an instance of the bias term in the bias-complexity decomposition. Conversely, if we had instead fit a degree-5 polynomial through these same 6 points (7 parameters, 6 constraints — heavily overparameterized), $\hat R_S$ would drop to nearly zero by interpolating every point, while true risk on new houses would likely be worse than the simple line, since the curve would oscillate wildly between the sparse training points. This second scenario — near-zero empirical risk, high true risk — is the canonical ERM overfitting failure, and it is why the uniform-convergence argument above is essential: with 7 free parameters and 6 data points, $\mathcal H$'s effective complexity is too large relative to $n$ for the concentration guarantees to bite.

The formal articulation of ERM as a learning principle, with rigorous guarantees on when it succeeds, is largely due to the Soviet/Russian statistician Vladimir Vapnik, working with Alexey Chervonenkis, whose VC-dimension theory turned "does minimizing training error generalize?" into a precisely answerable mathematical question. Their work built on and extended earlier statistical ideas — the method of least squares itself traces to Gauss and Legendre, and the general framework of estimating parameters by minimizing a sample-based criterion connects to Fisher's development of maximum likelihood estimation, which is itself an instance of ERM under log-loss.

ERM is the operating principle underneath essentially all supervised machine learning in production today. Training a logistic regression spam filter, fitting a gradient-boosted tree for credit scoring, or backpropagating through a deep convolutional network for image classification are all, at their core, instances of minimizing an empirical average of a loss function over a training set — differing only in the hypothesis class, the loss, and the optimizer. Large-scale systems at companies running recommendation engines, ad-click prediction, fraud detection, and speech recognition all train models by ERM with mini-batch stochastic gradient descent, precisely because the empirical-risk-as-a-sum structure is what makes stochastic gradient estimates (computed on small batches) unbiased estimators of the full-batch gradient. Frameworks like scikit-learn, PyTorch, and TensorFlow are, in large part, engineering infrastructure for defining losses and hypothesis classes and then solving the resulting ERM optimization efficiently at scale. Understanding ERM's statistical justification — and its failure mode without complexity control — is also the conceptual prerequisite for understanding why practitioners add weight decay, dropout, early stopping, and explicit regularization terms, all of which are direct responses to the fact that pure ERM overfits once the hypothesis class is rich enough, motivating Regularization Theory as ERM's necessary complement.

Ask the tutor: How does the VC dimension of a hypothesis class quantitatively determine the sample size needed for ERM's generalization guarantee to hold?