Empirical Risk Minimization

One-Line Summary: Minimizing average loss on training data as a proxy for true risk -- the theoretical framework underlying most ML algorithms.

Prerequisites: Loss Functions, What Is Machine Learning, basic probability, expected value.

What Is Empirical Risk Minimization?

Imagine you are a restaurant critic trying to determine the best restaurant in a city. Ideally, you would eat every meal at every restaurant -- but that is impossible. Instead, you sample a few meals from each and judge based on those samples. You are using your empirical experience as a proxy for the true quality. Empirical Risk Minimization (ERM) is the same principle applied to learning: since we cannot compute the expected loss over the entire data distribution, we minimize the average loss over our finite training sample.

Formally, let $(X,Y)\sim P$ be the true data-generating distribution. The true risk (or expected risk) of a hypothesis $h$ is:

$R(h)={\mathbb{E}}_{(X,Y)\sim P}\left[\mathcal{L}(h(X),Y)\right]$

Since $P$ is unknown, we approximate with the empirical risk over $n$ training samples:

${\hat{R}}_n(h)=\frac{1}{n}{\sum }_{i=1}^n\mathcal{L}(h({\mathbf{x}}_i),y_i)$

The ERM principle selects:

$h_{\text{ERM}}^{\ast }=\arg {\min }_{h\in \mathcal{H}}{\hat{R}}_n(h)$

How It Works

Why ERM Makes Sense

By the law of large numbers, as $n\to \infty$:

${\hat{R}}_n(h)\stackrel{p}{\to }R(h)$

for any fixed $h$. So with enough data, the empirical risk converges to the true risk. The deeper question is whether this convergence happens uniformly over all $h\in \mathcal{H}$, which determines whether the ERM solution is close to the true risk minimizer.

The Generalization Gap

The generalization gap is the difference between true risk and empirical risk:

$\text{Gap}=R(h_{\text{ERM}}^{\ast })-{\hat{R}}_n(h_{\text{ERM}}^{\ast })$

This gap is always non-negative in expectation (the model is optimized for the training data, so it naturally performs at least as well there). The central challenge of learning theory is bounding this gap.

For a finite hypothesis class $|\mathcal{H}|=M$, Hoeffding's inequality gives:

$P\left({\sup }_{h\in \mathcal{H}}|R(h)-{\hat{R}}_n(h)|>ϵ\right)\le 2M\exp (-2n{ϵ}^2)$

This says the gap is small when $n$ is large relative to $\log M$. For infinite hypothesis classes, we need more sophisticated measures of complexity.

VC Dimension

The Vapnik-Chervonenkis (VC) dimension measures the capacity of a hypothesis class. It is the largest number of points that $\mathcal{H}$ can shatter -- that is, classify in all $2^d$ possible ways.

Examples:

• Linear classifiers in ${\mathbb{R}}^2$ have VC dimension 3 (can shatter any 3 non-collinear points, but not 4).
• Linear classifiers in ${\mathbb{R}}^d$ have VC dimension $d+1$.
• A single neuron with sigmoid activation has VC dimension $d+1$ (same as linear).

The VC generalization bound states:

$R(h)\le {\hat{R}}_n(h)+O\left(\sqrt{\frac{d_{\text{VC}}\log (n/d_{\text{VC}})}{n}}\right)$

This bound tells us that generalization improves with more data ($n$) and worsens with higher model capacity ($d_{\text{VC}}$).

PAC Learning

The Probably Approximately Correct (PAC) framework, introduced by Valiant (1984), formalizes learnability. A concept class $\mathcal{C}$ is PAC-learnable if there exists an algorithm that, for any $ϵ>0$ and $\delta >0$, using at most $\text{poly}(1/ϵ,1/\delta ,d)$ samples, outputs a hypothesis $h$ such that:

$P(R(h)\le ϵ)\ge 1-\delta$

That is, with high probability ($1-\delta$), the learned hypothesis has low true risk (at most $ϵ$). PAC learning provides the theoretical foundation for understanding when and why learning is possible.

The sample complexity for PAC learning a finite hypothesis class is:

$n\ge \frac{1}{2{ϵ}^2}\left(\ln |\mathcal{H}|+\ln \frac{2}{\delta }\right)$

Structural Risk Minimization

Pure ERM can overfit: a sufficiently complex $\mathcal{H}$ can achieve zero empirical risk while having high true risk. Structural Risk Minimization (SRM), proposed by Vapnik, addresses this by jointly minimizing empirical risk and model complexity:

$h_{\text{SRM}}^{\ast }=\arg {\min }_{h\in \mathcal{H}}\left[{\hat{R}}_n(h)+\Phi (d_{\text{VC}}(\mathcal{H}),n,\delta )\right]$

where $\Phi$ is a complexity penalty that increases with VC dimension and decreases with sample size. This is the theoretical justification for regularization: the regularization term $\lambda \Omega (\theta )$ is a practical proxy for the complexity penalty.

When ERM Works and When It Fails

ERM works well when:

• The sample size $n$ is large relative to the complexity of $\mathcal{H}$.
• The training data is representative of the true distribution (i.i.d. assumption holds).
• The hypothesis class contains a good approximation to the true function.

ERM fails when:

• The model is too complex for the data (overfitting).
• The training distribution differs from the test distribution (distribution shift).
• The sample size is too small for the hypothesis class capacity.

Approximation-Estimation Tradeoff

The true risk of the ERM solution can be decomposed:

$R(h_{\text{ERM}}^{\ast })=\underset{\text{Approximation error}}{\underbrace{R(h_{\mathcal{H}}^{\ast })}}+\underset{\text{Estimation error}}{\underbrace{R(h_{\text{ERM}}^{\ast })-R(h_{\mathcal{H}}^{\ast })}}$

where $h_{\mathcal{H}}^{\ast }=\arg {\min }_{h\in \mathcal{H}}R(h)$ is the best hypothesis in the class. Approximation error decreases with larger $\mathcal{H}$ (more expressive). Estimation error increases with larger $\mathcal{H}$ (harder to estimate the best $h$ from finite data). This mirrors the bias-variance tradeoff.

Why It Matters

ERM is not just one algorithm -- it is the meta-algorithm. Linear regression, logistic regression, SVMs, neural network training, decision trees -- all of these can be viewed as ERM with specific choices of $\mathcal{H}$ and $\mathcal{L}$. Understanding ERM provides a unified lens through which to view all of supervised learning. It also reveals why certain things work (regularization, cross-validation) and when they might fail (distribution shift, insufficient data).

Key Technical Details

• Uniform convergence is the property that ${\hat{R}}_n(h)\to R(h)$ simultaneously for all $h\in \mathcal{H}$. It is sufficient (but not necessary) for ERM to succeed.
• Rademacher complexity provides tighter generalization bounds than VC dimension by measuring how well $\mathcal{H}$ can correlate with random noise in the specific data at hand.
• The agnostic PAC learning setting does not assume the true function is in $\mathcal{H}$, only that the algorithm finds the best approximation.
• Consistency: An ERM algorithm is consistent if $R(h_{\text{ERM}}^{\ast })\to {\inf }_{h\in \mathcal{H}}R(h)$ as $n\to \infty$.
• Modern deep learning often uses models with VC dimension far exceeding $n$, yet they generalize. This suggests classical VC bounds are loose, and tighter complexity measures (PAC-Bayes bounds, compression-based bounds) are needed.

Common Misconceptions

• "ERM means just minimizing training loss." Technically yes, but the theory tells us when and why this succeeds, and what additional ingredients (regularization, proper $\mathcal{H}$ choice) are needed.
• "VC dimension is the number of parameters." VC dimension and parameter count are related but not identical. Some models with few parameters have high VC dimension, and vice versa.
• "PAC bounds are practical." Classical PAC and VC bounds are typically too loose to be useful for predicting actual test error. They are valuable as theoretical tools for understanding qualitative behavior.
• "If training error is zero, the model has memorized everything." Zero training error with a low-complexity model (e.g., linearly separable data with a linear classifier) can indicate good generalization, not memorization.

Connections to Other Concepts

• loss-functions.md: The $\mathcal{L}$ in ERM -- different losses define different risk functionals and lead to different learned models.
• regularization.md: Structural risk minimization adds a complexity term to ERM, which is regularization's theoretical justification.
• bias-variance-tradeoff.md: The approximation-estimation decomposition in ERM directly parallels bias vs. variance.
• overfitting-and-underfitting.md: Overfitting is ERM's primary failure mode; underfitting occurs when $\mathcal{H}$ is too restrictive.
• curse-of-dimensionality.md: High dimensions increase the VC dimension and estimation error, requiring exponentially more data.

Further Reading

• Vapnik, V., The Nature of Statistical Learning Theory (1995) -- The foundational text on ERM, VC theory, and SRM.
• Shalev-Shwartz, S. & Ben-David, S., Understanding Machine Learning: From Theory to Algorithms (2014) -- Accessible and rigorous treatment of PAC learning and ERM.
• Valiant, L., "A Theory of the Learnable" (1984) -- The original PAC learning paper.
• Bartlett, P. & Mendelson, S., "Rademacher and Gaussian Complexities" (2002) -- Modern complexity measures that yield tighter bounds than VC dimension.