A Researcher's Guide to Empirical Risk Minimization

This paper provides a modular guide to deriving high-probability regret bounds for empirical risk minimization through a three-step proof strategy based on critical radii, while extending these guarantees to settings with nuisance components by establishing regret-transfer bounds that hold even under in-sample fitting.

The Gist

Imagine you are a chef trying to create the perfect recipe for a new dish. You have a huge cookbook (the Function Class) with thousands of potential recipes. Your goal is to find the single best recipe that will taste amazing to everyone in the world (the Population Risk).

However, you can't feed the dish to the whole world to test it. You can only cook it a few times for a small group of friends (the Sample) and ask them how it tastes. This is Empirical Risk Minimization (ERM): you pick the recipe that got the best reviews from your friends, hoping it will be the best for everyone.

The problem? Your friends might just really like spicy food, or maybe they were having a bad day. If you pick a recipe just because it worked for them, it might fail miserably when you serve it to the world. This gap between "how it tasted with friends" and "how it tastes with the world" is called Regret (or Excess Risk).

This paper is a guidebook for chefs (researchers) on how to mathematically prove that their chosen recipe won't fail too badly, even with a small sample size.

Here is the breakdown of the paper's main ideas using simple analogies:

1. The Three-Step "Recipe" for Success

The authors say that proving a recipe is good doesn't require reinventing the wheel every time. Instead, you can follow a standard three-step cooking process:

• Step 1: The Basic Inequality (The "Taste Test" Logic)
  Imagine you have a "Best Friend Recipe" (the true best dish) and your "Chosen Recipe." The math starts by saying: "The difference in quality between my chosen dish and the best dish is at most the difference between how my friends rated my dish and how the world would have rated it."

  • Simple version: If my dish is worse than the best, it's only because my friends' opinions were slightly off from reality.

• Step 2: The Local Concentration (The "Spot Check")
  Usually, we worry about any recipe in the cookbook. But we know our chosen recipe is probably close to the "Best Friend Recipe." So, instead of checking the whole library of recipes, we only check the "neighborhood" of recipes that are similar to our choice.

  • Analogy: Instead of checking if any random person in the city is a genius, we only check if the people standing next to our chosen genius are also geniuses. This makes the math much easier and tighter.

• Step 3: The Fixed-Point Argument (The "Self-Correction")
  This is the magic trick. The math creates a loop: "The error depends on how complex the neighborhood is, but the size of the neighborhood depends on the error."

  • Analogy: Imagine a mirror reflecting a mirror. The reflection gets smaller and smaller until it hits a tiny, stable point. The authors solve this loop to find the exact "Critical Radius"—the precise size of the neighborhood where the error stops growing and starts shrinking.

2. The "Critical Radius" (The Sweet Spot)

Think of the Critical Radius as the "Goldilocks Zone."

• If you look at a tiny neighborhood (too small), you might miss the best recipe entirely.
• If you look at a huge neighborhood (too big), there are too many bad recipes that could trick your friends, and the error explodes.
• The Critical Radius is the perfect size of the neighborhood where the math balances out. It tells you exactly how much data you need to be confident your recipe is good.

The paper gives you a calculator to find this radius for different types of cookbooks (mathematical classes like "smooth curves" or "sparse lists").

3. The "Nuisance" Problem (The Hidden Ingredient)

Sometimes, your recipe depends on a secret ingredient you don't know yet, like the exact humidity of the kitchen or the freshness of the eggs. In statistics, these are called Nuisance Components.

• Example: In medical studies, you want to know if a drug works, but you also need to estimate how sick the patients were before taking the drug. That "sickness level" is a nuisance component.

The Old Way: You estimate the sickness level first, then use that estimate to test the drug. If your sickness estimate is slightly wrong, it ruins your drug test.
The New Way (Regret Transfer): The paper shows a clever trick. You can estimate the sickness level, plug it in, and then use a "Regret Transfer" formula. This formula says: "The error in your final result is just the error of your drug test plus a tiny penalty for how bad your sickness estimate was."

• Key Insight: If you use a technique called Sample Splitting (using one group of friends to guess the humidity and a different group to test the dish), you can prove that the error from the humidity guess doesn't ruin the dish test.

4. The "In-Sample" Surprise (Cooking with the Same Friends)

Usually, statisticians say, "Never use the same data to guess the nuisance and test the model; you'll overfit." (Don't use the same friends to guess the humidity and taste the dish).

However, this paper shows that if your "cookbook" (the function class) is smooth and well-behaved (like a nice, continuous curve), you can use the same friends for both tasks!

• Analogy: If your recipe is very simple and predictable, you don't need a second group of friends. You can use the first group to guess the humidity and immediately taste the dish, and the math still holds up. This saves a lot of data and is much more efficient.

Summary: What's the Big Takeaway?

This paper is a toolkit for confidence.

1. It simplifies the math: It gives you a standard 3-step recipe to prove that your machine learning model won't fail, no matter what specific problem you are solving.
2. It handles the messy stuff: It shows you how to deal with "nuisance" variables (unknown factors) without needing to throw away half your data.
3. It finds the limit: It calculates the exact "Critical Radius" (the complexity limit) for different types of problems, telling you exactly how fast your model will learn as you get more data.

In short: Don't panic about the complexity. Follow the three-step recipe, check the critical radius, and you can prove your model is working, even when you have to estimate hidden variables along the way.

Technical Summary

This document provides a detailed technical summary of the research paper "A Researcher's Guide to Empirical Risk Minimization" by Lars van der Laan (University of Washington, March 2026).

1. Problem Statement

The paper addresses the theoretical analysis of Empirical Risk Minimization (ERM), a foundational principle in statistics and machine learning where an estimator $\hat{f}_n$ is chosen to minimize the empirical risk $R_n(f) = \frac{1}{n}\sum \ell(Z_i, f)$ over a function class $\mathcal{F}$.

The core objective is to derive high-probability regret bounds (excess risk) of the form:
$$R(\hat{f}_n) - R(f_0) \leq \epsilon(n, \eta)$$
where $f_0$ is the population risk minimizer, $R(f) = \mathbb{E}[\ell(Z, f)]$, and $\eta$ is a failure probability.

The paper specifically targets two challenging scenarios often encountered in modern causal inference and semi-parametric statistics:

1. Nuisance Components: Situations where the loss function $\ell$ depends on an estimated nuisance parameter $\hat{g}$ (e.g., propensity scores, conditional expectations) rather than a fixed ground truth.
2. In-Sample Estimation: The regime where the nuisance parameter and the main estimator are fit on the same data, avoiding the data-splitting (sample splitting or cross-fitting) typically required to decouple dependencies.

2. Methodology

The author proposes a modular, three-step proof template that unifies various ERM rate derivations under a single framework. This approach bridges the gap between localized Rademacher complexity arguments and uniform entropy/metric-entropy techniques.

The Three-Step Recipe

1. Basic Inequality (Deterministic):
   Establish a deterministic upper bound on the regret using the optimality of the ERM solution:
   $$R(\hat{f}_n) - R(f_0) \leq (P_n - P)\{ \ell(\cdot, f_0) - \ell(\cdot, \hat{f}_n) \}$$
   This reduces the problem to controlling the empirical process fluctuation of the loss difference.

2. Uniform Local Concentration (Probabilistic):
   Derive high-probability bounds for the empirical process term $(P_n - P)\{ \ell(\cdot, f_0) - \ell(\cdot, f) \}$ that hold uniformly over $f \in \mathcal{F}$.

   • Key Tool: The paper utilizes Uniform Local Concentration Inequalities. Unlike global bounds, these adapt to the local variance of the loss difference.
   • Condition: The bounds rely on a Bernstein-type variance-risk condition, where the variance of the loss difference is bounded by the regret itself ($\text{Var}(\ell(f) - \ell(f_0)) \lesssim R(f) - R(f_0)$). This is often satisfied by strongly convex risks or via Tikhonov regularization.

3. Fixed-Point Argument:
   Combine the basic inequality with the concentration bound to form a self-bounding (fixed-point) inequality for the regret.

   • The bound typically takes the form: $\text{Regret} \lesssim \sigma_{\hat{f}_n} \delta_n + \delta_n^2$, where $\delta_n$ is a complexity term.
   • Using the Bernstein condition ($\sigma^2 \lesssim \text{Regret}$), this becomes a fixed-point equation in the regret, which is solved to yield the final rate.

Complexity Measures

The methodology centers on the Critical Radius ($\delta_n$), defined via the Localized Rademacher Complexity of the loss-difference class $\mathcal{F}_\ell$:
$$\delta_n(\mathcal{F}_\ell) := \inf \{ \delta > 0 : \mathcal{R}_n(\text{star}(\mathcal{F}_\ell), \delta) \leq \delta^2 \}$$
The paper provides tools to upper bound this critical radius using Metric Entropy Integrals (covering numbers), allowing rates to be derived for standard classes (VC-subgraph, Sobolev, Hölder, RKHS).

3. Key Contributions

A. Unified Proof Template for ERM

The paper formalizes a "recipe" that separates the statistical task (controlling local complexity via critical radii) from the algebraic task (solving the fixed-point inequality). This allows researchers to derive rates for new loss functions and function classes by simply verifying the Bernstein condition and computing the critical radius, rather than re-deriving proofs from scratch.

B. ERM with Nuisance Components (Weighted & Orthogonal)

The paper extends the framework to Weighted ERM and Neyman-Orthogonal Losses (common in causal inference).

• Regret Transfer: It establishes bounds linking the regret under an estimated loss (using $\hat{g}$) to the regret under the true loss (using $g_0$).
• Sample Splitting: Under sample splitting, the nuisance estimation error is decoupled, allowing standard ERM bounds to apply directly.
• In-Sample Regime (Novel Contribution): The paper derives regret bounds for the case where $\hat{g}$ and $\hat{f}_n$ are fit on the same data.
  • It introduces specialized maximal inequalities for empirical inner products of the form $(P_n - P)(f \cdot g)$.
  • It shows that oracle rates (rates as if $g_0$ were known) are attainable without sample splitting, provided the nuisance class satisfies a Donsker-type condition (specifically, that its critical radius scales as $O(n^{-1/2})$) and the main class satisfies specific smoothness/interpolation conditions (Hölder/Sobolev classes).

C. Concrete Rates for Standard Classes

The guide explicitly recovers familiar minimax rates for:

• VC-subgraph classes: $\delta_n \sim \sqrt{V \log n / n}$.
• Sobolev/Hölder classes: $\delta_n \sim n^{-s/(2s+d)}$.
• RKHS classes: Rates determined by eigenvalue decay of the kernel operator.

4. Key Results

1. General Regret Theorem (Theorem 3):
   Under a Bernstein condition and assuming the critical radius $\delta_n$ satisfies $\mathcal{R}_n(\text{star}(\mathcal{F}_\ell), \delta_n) \lesssim \delta_n^2$, the regret is bounded with probability $1-\eta$ by:
   $$R(\hat{f}_n) - R(f_0) \lesssim \delta_n^2 + \frac{\log(1/\eta)}{n}$$
   This implies the convergence rate is $O_p(\delta_n^2)$.

2. L2 Error Bounds (Theorem 4):
   If the risk is strongly convex, the $L_2(P)$ error satisfies $\|\hat{f}_n - f_0\| \lesssim \delta_n$.

3. In-Sample Nuisance Estimation (Theorem 9):
   For ERM with in-sample nuisance estimation, the $L_2$ error satisfies:
   $$\|\hat{f}_n - \hat{f}_0\|^2 \lesssim \delta_{n,F}^2 + \left( \delta_{n,G}^2 + \delta_{n,G} \varepsilon_{\text{nuis}} \right)^{\frac{4\beta}{2\beta+1}}$$
   where $\delta_{n,F}$ and $\delta_{n,G}$ are critical radii for the main and nuisance classes, and $\beta$ is a smoothness parameter.

   • Corollary 4: If the nuisance class is "simple" enough (Donsker-type, $\delta_{n,G} = O(n^{-1/4})$) and the main class is smooth ($\beta > 1/2$), the oracle rate $\delta_{n,F}^2$ is achieved even without sample splitting.

5. Significance and Impact

• Bridging Theory and Practice: The paper serves as a practical "cookbook" for researchers, demystifying the complex machinery of empirical process theory required for modern ERM analysis. It connects abstract Rademacher complexity with concrete metric entropy calculations.
• Advancing Causal Inference: By rigorously treating in-sample nuisance estimation, the paper addresses a critical bottleneck in causal inference and domain adaptation. It demonstrates that computationally expensive sample splitting is not always necessary to achieve optimal rates, provided the nuisance estimators are not too complex (Donsker condition).
• Modularity: The separation of the "basic inequality," "concentration," and "fixed-point" steps allows for easy adaptation to new settings, such as unbounded losses or dependent data (future work directions mentioned).
• Educational Value: The inclusion of detailed proofs, appendices on concentration inequalities, and examples for standard function classes makes it a valuable reference for graduate students and researchers in statistical learning theory.

In summary, this guide provides a rigorous, unified, and accessible framework for analyzing ERM, with a specific and novel contribution regarding the statistical efficiency of learning with nuisance parameters in the absence of data splitting.