Loss Functions & Risk Minimization

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. The Decision-Theoretic Framework
6. Common Loss Functions
7. From Loss to Risk
8. Empirical Risk Minimization
9. Bayes Optimal Predictor
10. Surrogate Loss Functions
11. Generalization and Excess Risk
12. Common Pitfalls
13. Research Perspective
14. Summary
15. Exercises

Learning Objectives

1. Formalize the supervised learning problem in terms of loss, risk, and hypothesis classes.
2. Derive squared error loss from the Gaussian likelihood assumption.
3. Derive cross-entropy loss from maximum likelihood for Bernoulli/categorical models.
4. Distinguish between statistical (population) risk and empirical risk.
5. State and interpret the Bayes optimal predictor for squared and 0-1 loss.
6. Explain why surrogate losses are necessary for classification.
7. Understand the decomposition of excess risk into estimation and approximation error.

Prerequisites

• Bayes' Theorem
• Maximum Likelihood Estimation

Notation

• $\mathcal{X}$ — input space, $\mathcal{Y}$ — output space
• $(X, Y) \sim P$ — joint distribution over data
• $f: \mathcal{X} \to \mathcal{Y}$ — predictor (hypothesis)
• $\mathcal{F}$ — hypothesis class
• $\ell(f(x), y)$ — loss function
• $R(f) = \mathbb{E}_{(X,Y)}[\ell(f(X), Y)]$ — statistical (population) risk
• $\hat{R}_n(f) = \frac{1}{n}\sum_{i=1}^n \ell(f(x_i), y_i)$ — empirical risk
• $f^* = \arg\min_{f} R(f)$ — Bayes optimal predictor
• $\hat{f}_n = \arg\min_{f \in \mathcal{F}} \hat{R}_n(f)$ — ERM solution

Core Intuition

Machine learning is fundamentally an optimization problem: we seek a function $f$ that predicts well on unseen data. But "predicts well" must be defined precisely. The loss function $\ell$ quantifies the penalty for predicting $\hat{y}$ when the truth is $y$. The risk is the expected loss over the true data distribution. Since we cannot compute the risk (we don't know $P$), we minimize the empirical risk over training data and hope it generalizes.

The Decision-Theoretic Framework

Definition (Statistical Learning Problem). Given:

• A joint distribution $P$ over $\mathcal{X} \times \mathcal{Y}$ (unknown)
• A loss function $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\geq 0}$
• A hypothesis class $\mathcal{F} \subseteq \{f: \mathcal{X} \to \mathcal{Y}\}$
• Training data $\{(x_i, y_i)\}_{i=1}^n \overset{\text{iid}}{\sim} P$

Find $\hat{f} \in \mathcal{F}$ that minimizes the population risk:

The unconstrained minimizer (over all measurable functions) is the Bayes predictor $f^*$, and $R(f^*)$ is the Bayes risk — the irreducible error.

Common Loss Functions

Squared Error (Regression)

Probabilistic derivation. Assume $Y = f(X) + \epsilon$ with $\epsilon \sim \mathcal{N}(0, \sigma^2)$. The negative log-likelihood of one observation is:

Minimizing negative log-likelihood $\Leftrightarrow$ minimizing squared loss.

Cross-Entropy (Classification)

For binary classification with $Y \in \{0, 1\}$ and $f(x) = p \in [0,1]$:

Derivation. If $Y \mid X \sim \text{Bernoulli}(f(X))$, the negative log-likelihood is exactly the cross-entropy.

For $K$-class classification with one-hot $\mathbf{y}$ and predicted probabilities $\mathbf{p}$:

0-1 Loss (Classification)

This is the natural measure of classification error, but is non-convex and non-differentiable.

Absolute Loss

More robust to outliers than squared loss. The optimal predictor under absolute loss is the conditional median $\text{med}(Y \mid X = x)$.

From Loss to Risk

Definition (Population Risk).

Definition (Empirical Risk). Given $n$ iid samples:

By the law of large numbers, $\hat{R}_n(f) \xrightarrow{a.s.} R(f)$ for fixed $f$. The challenge is that we are choosing $f$ based on the data — so we need uniform convergence over $\mathcal{F}$.

Empirical Risk Minimization

ERM Principle. Choose the predictor that minimizes empirical risk:

Theorem (Consistency of ERM). If $\mathcal{F}$ has finite VC-dimension $d$, then for any $\delta > 0$, with probability at least $1 - \delta$:

where $f^*_{\mathcal{F}} = \arg\min_{f \in \mathcal{F}} R(f)$ is the best-in-class predictor.

Bayes Optimal Predictor

Theorem. For squared loss, the Bayes optimal predictor is the conditional expectation:

Proof. Expand:

The cross term vanishes by the tower property. The second term is irreducible noise. The first is minimized when $f = f^*$. $\blacksquare$

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

Surrogate Loss Functions

The 0-1 loss is computationally intractable (NP-hard to minimize over linear classifiers). We use surrogate losses that upper-bound 0-1 loss and are convex:

• Hinge loss (SVM): $\ell(m) = \max(0, 1-m)$ where $m = y \cdot f(x)$
• Logistic loss: $\ell(m) = \log(1 + e^{-m})$
• Exponential loss (AdaBoost): $\ell(m) = e^{-m}$

All satisfy $\mathbf{1}[m \leq 0] \leq \ell(m)$ for all $m$, providing classification-calibrated surrogates.

Theorem (Zhang, 2004; Bartlett et al., 2006). A convex surrogate $\phi$ is classification-calibrated if and only if it is differentiable at 0 and $\phi'(0) < 0$. In this case, minimizing the surrogate risk is consistent for 0-1 loss.

Generalization and Excess Risk

The excess risk decomposes as:

• Estimation error: decreases with $n$ (more data), increases with complexity of $\mathcal{F}$.
• Approximation error: decreases with richer $\mathcal{F}$, zero if $f^* \in \mathcal{F}$.

This is the formal counterpart of the bias-variance tradeoff.

Common Pitfalls

Pitfall 1. Choosing loss based on convenience rather than the actual problem. Squared loss is sensitive to outliers; in heavy-tailed settings, Huber loss or absolute loss is more appropriate.

Pitfall 2. Confusing empirical risk with population risk. Low training loss does not guarantee low test loss — the gap depends on the complexity of $\mathcal{F}$ relative to $n$.

Pitfall 3. Assuming cross-entropy is always correct. Cross-entropy assumes the model outputs calibrated probabilities; if it doesn't (e.g., softmax temperatures), the loss may be misleading.

Research Perspective

The risk-minimization framework dates to Vapnik's statistical learning theory (1960s–90s). Modern deep learning challenges classical bounds (VC-dimension of neural networks is enormous, yet they generalize), leading to new frameworks: PAC-Bayes bounds, compression-based bounds, and the implicit regularization perspective from gradient flow analysis.

Summary

• A loss function quantifies prediction errors; the choice is motivated by probabilistic assumptions.
• Population risk is the expected loss; empirical risk is the training average.
• ERM finds the hypothesis minimizing empirical risk; generalization depends on the complexity of $\mathcal{F}$.
• The Bayes predictor achieves irreducible error; excess risk = estimation + approximation error.
• Surrogate losses make 0-1 classification computationally tractable while preserving consistency.

Exercises

Exercise 1. Derive that the Bayes optimal predictor under absolute loss $|f(x) - y|$ is the conditional median.

Exercise 2. Show that for squared loss, $R(f) = \text{Var}(Y \mid X) + \mathbb{E}[(f(X) - \mathbb{E}[Y \mid X])^2]$.

Exercise 3. Prove that the hinge loss upper bounds the 0-1 loss: $\mathbf{1}[yf(x) \leq 0] \leq \max(0, 1 - yf(x))$.

Exercise 4. For exponential loss $\ell(f, y) = e^{-yf(x)}$, derive the population minimizer and show it equals $\frac{1}{2}\log\frac{P(Y=1|X=x)}{P(Y=-1|X=x)}$.

Exercise 5. Show that ERM with squared loss and the class of linear functions $f(x) = \mathbf{w}^T\mathbf{x}$ reduces to ordinary least squares.