Minimax Lower Bounds

Why This Matters

Proving an upper bound (e.g., "my estimator achieves rate $n^{-1/2}$") is only half the story. The natural question is: can any estimator do better? A minimax lower bound answers this by showing that for every estimator, there exists a problem instance where the estimator must incur at least a certain error.

Lower bounds are intellectually crucial because they tell you when to stop trying to improve. If your estimator achieves rate $n^{-2/(2+d)}$ and you can prove a matching lower bound, you know your estimator is rate-optimal. No amount of cleverness can beat the fundamental statistical limit.

In modern ML theory, lower bounds separate what is statistically possible from what is merely a failure of current algorithms.

Mental Model

Upper bounds say: "here is an estimator that works this well." Lower bounds say: "no estimator can do better than this." Together, they characterize the fundamental difficulty of a statistical problem.

The key technique for lower bounds is reduction to testing: show that estimating a parameter accurately requires distinguishing between hypotheses. If no test can reliably distinguish the hypotheses, no estimator can reliably estimate the parameter.

Formal Setup

Definition

Minimax Risk

The minimax risk over a parameter space $\Theta$ with loss function $\ell$ and sample size $n$ is:

$R_n^*(\Theta, \ell) = \inf_{\hat{\theta}} \sup_{\theta \in \Theta} \mathbb{E}_\theta[\ell(\hat{\theta}, \theta)]$

The infimum is over all estimators $\hat{\theta} = \hat{\theta}(X_1, \ldots, X_n)$, and the supremum is over all parameter values in $\Theta$. This is the best worst-case risk achievable by any estimator.

The minimax framework asks: what is the best any estimator can guarantee, when nature is adversarial? The inf-sup structure captures this game:

1. The statistician chooses an estimator (inf)
2. Nature chooses the worst-case parameter (sup)
3. The minimax risk is the value of this game

A lower bound on $R_n^*$ means: no matter what estimator you use, there exists some $\theta$ where your expected loss is at least this large.

The Reduction to Testing

The fundamental idea behind all minimax lower bound techniques:

If you cannot test, you cannot estimate.

More precisely, if two parameter values $\theta_0$ and $\theta_1$ are far apart (in the loss metric) but the corresponding distributions $P_{\theta_0}$ and $P_{\theta_1}$ are close (in a statistical sense), then no estimator can reliably tell them apart, which means no estimator can accurately estimate $\theta$.

This insight takes three forms, in order of increasing power:

1. Le Cam (two hypotheses): reduce to a single binary test
2. Fano (multiple hypotheses): reduce to an $M$-ary test
3. Assouad (hypercube): reduce to $d$ simultaneous binary tests

Le Cam Two-Point Method

Theorem

Le Cam Two-Point Method

Statement

Let $\theta_0, \theta_1 \in \Theta$ with $\ell(\theta_0, \theta_1) \geq 2s > 0$. Then:

$R_n^*(\Theta, \ell) \geq \frac{s}{2}\left(1 - \|P_{\theta_0}^n - P_{\theta_1}^n\|_{\text{TV}}\right)$

where $\|P - Q\|_{\text{TV}} \in [0, 1]$ is the total variation distance between the joint distributions of $n$ samples. We follow the convention of Yu (1997, Lemma 1) and Tsybakov (2009, Theorem 2.2): $s$ is the half-separation in the loss (assumption $\ell(\theta_0, \theta_1) \geq 2s$), TV is normalized to $[0,1]$, and the $1/2$ factor comes from the average-error bound $\sup \geq \tfrac{1}{2}(\mathbb{E}_{\theta_0}[\ell] + \mathbb{E}_{\theta_1}[\ell])$.

Intuition

If the two distributions $P_{\theta_0}^n$ and $P_{\theta_1}^n$ are nearly indistinguishable (small total variation distance), then any estimator must err on at least one of them. Since $\theta_0$ and $\theta_1$ are far apart in loss, this error is of order $s$.

The total variation distance controls how well you can distinguish the two hypotheses. If $\|P_{\theta_0}^n - P_{\theta_1}^n\|_{\text{TV}} \leq 1/2$, you get a lower bound of at least $s/4$.

Proof Sketch

Any estimator $\hat{\theta}$ satisfies:

$\sup_\theta \mathbb{E}_\theta[\ell(\hat{\theta}, \theta)] \geq \frac{1}{2}\left(\mathbb{E}_{\theta_0}[\ell(\hat{\theta}, \theta_0)] + \mathbb{E}_{\theta_1}[\ell(\hat{\theta}, \theta_1)]\right)$

For any outcome, by the triangle-like property, $\ell(\hat{\theta}, \theta_0) + \ell(\hat{\theta}, \theta_1) \geq 2s$. Define $\psi = \mathbf{1}[\ell(\hat{\theta}, \theta_0) < s]$ as a test. Then:

$\frac{1}{2}(\mathbb{E}_{\theta_0}[\ell(\hat\theta, \theta_0)] + \mathbb{E}_{\theta_1}[\ell(\hat\theta, \theta_1)]) \geq s \cdot \frac{1}{2}(P_{\theta_0}(\psi = 1) + P_{\theta_1}(\psi = 0))$

The last term is the average testing error, which is bounded below by $(1 - \|P_{\theta_0}^n - P_{\theta_1}^n\|_{\text{TV}})/2$ by the Neyman-Pearson lemma.

Why It Matters

Le Cam is the simplest lower bound technique and often the first one to try. It reduces the estimation problem to binary hypothesis testing, which is the most basic statistical task. If even this simple test is hard, estimation must be hard.

Failure Mode

Le Cam only uses two hypotheses. When the parameter space is rich (high-dimensional), two points cannot capture the full difficulty of the problem. Fano and Assouad address this by using many hypotheses simultaneously.

Fano Method (Preview)

Fano extends Le Cam by using $M$ hypotheses instead of 2. The idea: construct $M$ parameter values $\theta_1, \ldots, \theta_M$ that are pairwise well-separated in loss but whose distributions are mutually close (bounded mutual information).

Fano's inequality then gives:

$R_n^* \geq s \cdot \left(1 - \frac{I(X^n; \Theta) + \log 2}{\log M}\right)$

where $I(X^n; \Theta)$ is the mutual information between the data and the uniform index over the $M$ hypotheses. The more hypotheses you can pack while keeping the mutual information small, the stronger the lower bound.

The full treatment of Fano's inequality is in the dedicated topic page.

Assouad Lemma

Lemma

Assouad Lemma

Statement

Let the parameter space be indexed by $\tau \in \{-1, +1\}^d$, with loss $\ell(\hat{\theta}, \theta_\tau) \geq \sum_{j=1}^d s_j \cdot \mathbf{1}[\hat{\tau}_j \neq \tau_j]$. Then:

$R_n^* \geq \frac{1}{2}\sum_{j=1}^d s_j \cdot \left(1 - \|P_{\tau_j = +1}^n - P_{\tau_j = -1}^n\|_{\text{TV}}\right)$

where $P_{\tau_j = \pm 1}^n$ are mixtures over all $\tau$ with the $j$-th coordinate fixed. Convention: Yu (1997, Lemma 2), Tsybakov (2009, Theorem 2.12), Wainwright (2019, Proposition 15.5); $s_j$ is the per-coordinate separation in the loss and TV is normalized to $[0,1]$. The $1/2$ factor arises from reducing each coordinate to a Le Cam two-point test.

Intuition

Assouad reduces the $d$-dimensional estimation problem to $d$ independent binary testing problems, one per coordinate of the hypercube. Each coordinate contributes a Le Cam-style lower bound. The total lower bound is the sum over all coordinates.

Proof Sketch

The loss decomposes across coordinates. For each coordinate $j$, estimating $\tau_j$ correctly is a binary testing problem between the mixture with $\tau_j = +1$ and the mixture with $\tau_j = -1$. Apply Le Cam to each coordinate and sum the results.

Why It Matters

Assouad is the go-to method for lower bounds in high-dimensional problems. When the parameter is a $d$-dimensional vector, Assouad naturally captures the "curse of dimensionality" by showing that each coordinate independently contributes to the difficulty. It is the standard tool for proving lower bounds in nonparametric estimation, where $d$ plays the role of the effective dimensionality.

Failure Mode

Assouad requires the loss to decompose (at least approximately) as a sum over coordinates. When the loss has a more complex structure (e.g., spectral norm for matrix estimation), Assouad may not apply directly, and you may need a modified version or a different technique.

How to Use These Tools

A practical guide to choosing the right lower bound method:

1. Start with Le Cam if the problem is one-dimensional or you only need a rough lower bound. Construct two hypotheses that are far apart in loss but close in total variation.

2. Use Fano when the parameter space is rich and you can construct many well-separated hypotheses. This is the most common method for proving minimax rates in statistics and learning theory.

3. Use Assouad for high-dimensional problems where the loss decomposes coordinate-wise. The hypercube construction naturally yields $2^d$ hypotheses from $d$ binary choices.

In all cases, the art is in the construction: choosing the right hypotheses (or packing) so that the separation is large and the distributions are hard to distinguish.

Canonical Examples

Example

Le Cam for Gaussian mean estimation

Let $X_1, \ldots, X_n \sim \mathcal{N}(\theta, 1)$ with $\theta \in \mathbb{R}$. Take $\theta_0 = -\delta/2$ and $\theta_1 = +\delta/2$. The total variation distance satisfies:

$\|P_{\theta_0}^n - P_{\theta_1}^n\|_{\text{TV}} \leq \sqrt{\frac{n\delta^2}{4}} = \frac{\delta}{2}\sqrt{n}$

by Pinsker's inequality $\|P - Q\|_{\text{TV}} \leq \sqrt{D_{\text{KL}}(P\|Q)/2}$ applied to $D_{\text{KL}}(P_{\theta_0}^n \| P_{\theta_1}^n) = n\delta^2/2$ (KL for Gaussians with unit variance and mean gap $\delta$). Setting $\delta = c/\sqrt{n}$ makes the TV distance bounded by a constant, and the lower bound gives $R_n^* \geq c'/n$ for squared error loss. This matches the upper bound from the sample mean ($\text{Var}(\bar{X}) = 1/n$).

Example

Why lower bounds matter: nonparametric regression

For estimating a function in the Sobolev ball of smoothness $s$ in $d$ dimensions, the minimax rate for squared error is $n^{-2s/(2s+d)}$. Without the lower bound, you would not know whether this rate is optimal or whether a better estimator exists. The lower bound (typically proved via Assouad) shows this rate is tight -- no estimator can do better, and the curse of dimensionality ($d$ in the exponent) is unavoidable.

Common Confusions

Watch Out

A lower bound does not mean all estimators achieve that rate

The minimax lower bound says: the best worst-case risk is at least this large. It does not say that every estimator achieves this rate. Most estimators are much worse than minimax-optimal. The lower bound is a statement about the best possible estimator, not about typical estimators.

Watch Out

Minimax optimality does not mean the estimator is good for your problem

Minimax theory is worst-case. An estimator that is minimax-optimal may be overly conservative for specific easy instances. Adaptive estimators try to achieve near-minimax rates while also exploiting favorable structure when it is present.

Watch Out

Total variation and KL divergence are different

Le Cam uses total variation distance. Fano uses mutual information (related to KL divergence). They are connected by Pinsker's inequality: $\|P - Q\|_{\text{TV}} \leq \sqrt{D_{\text{KL}}(P \| Q)/2}$. But they are not interchangeable. Using the wrong divergence in the wrong method gives incorrect bounds.

Summary

• Minimax risk = $\inf_{\hat\theta} \sup_\theta \mathbb{E}[\ell(\hat\theta, \theta)]$: the best worst-case performance
• Lower bounds prove that no estimator can beat a certain rate
• All methods reduce estimation to hypothesis testing: if you cannot test, you cannot estimate
• Le Cam: two hypotheses, uses total variation distance
• Fano: $M$ hypotheses, uses mutual information
• Assouad: $2^d$ hypotheses on a hypercube, decomposes into $d$ binary tests
• A matching upper and lower bound proves an estimator is rate-optimal

Exercises

ExerciseAdvanced

Problem

Use Le Cam's two-point method to prove a lower bound for estimating the mean of a Bernoulli distribution. Let $X_1, \ldots, X_n \sim \text{Bernoulli}(p)$ with $p \in [0, 1]$. Show that for squared error loss, $R_n^* \geq c/n$ for some constant $c > 0$.

Hint

Reveal Solution

ExerciseResearch

Problem

Why does Le Cam give a suboptimal lower bound for high-dimensional problems? Specifically, for estimating a $d$-dimensional Gaussian mean with identity covariance, Le Cam with two points gives $R_n^* \geq c/n$, while the true minimax rate for squared $\ell_2$ loss is $d/n$. Where does the factor of $d$ come from?

Hint

Reveal Solution

Related Comparisons

• Cramér-Rao Bound vs. Minimax Lower Bounds
• Fano's Method vs. Le Cam's Method

References

Canonical:

• Tsybakov, Introduction to Nonparametric Estimation (2009), Chapter 2 -- the best textbook treatment
• Le Cam, "Convergence of Estimates Under Dimensionality Restrictions" (1973)
• Yu, "Assouad, Fano, and Le Cam" (1997) -- a unified exposition

Current:

• Duchi, Information-Theoretic Methods in Statistics (lecture notes, Stanford) -- modern treatment

• Wainwright, High-Dimensional Statistics (2019), Chapter 15

• Casella & Berger, Statistical Inference (2002), Chapters 5-10

Next Topics

Deepening the lower bound toolkit:

• Fano inequality: the detailed mechanics of the most widely used lower bound technique