Minimax Lower Bounds for Nonparametric Estimation: Le Cam, Fano, and Assouad

Intuition Beginner

Every estimation method comes with a promise: feed it data and it returns a guess close to the truth. A lower bound asks the opposite question. Across all possible methods, how close can the best one get with $n$ samples? If even the cleverest method cannot beat a certain error, that error is a wall set by the problem, not by our ingenuity. Minimax lower bounds find that wall.

The trick is to turn estimating into guessing between a few possibilities. Suppose two candidate truths sit close together, yet are far enough apart that getting within the target error tells you which one you are looking at. Then any accurate estimator secretly solves a quiz: which of the two worlds produced this data? If the two worlds make the data look almost the same, no quiz-taker can answer reliably, so no estimator can be accurate. The closeness of the two data-worlds is measured by how hard they are to tell apart.

That is the whole engine. Build a small set of candidate truths, spaced just far enough to matter but producing nearly identical data, and the data simply cannot separate them. The more candidates you can pack into that ambiguous zone, the stronger the wall you prove. Two candidates give a basic wall; many candidates, or a whole grid of them, give the sharp walls that match what the best real estimators actually achieve.

Visual Beginner

Picture two bell-shaped curves that are far apart in what they claim (their peaks sit at different places) but nearly on top of each other in what data they produce. An estimator only ever sees samples; if both curves spit out almost the same samples, the estimator cannot know which curve it came from.

 candidate world 0          candidate world 1
        /\                         /\
       /  \                       /  \
      /    \  <-- overlap: data  /    \
_____/______\####################______\______  parameter axis
     |        |                  |
     peak 0   |<---- 2s -------->| peak 1
              (separation in the loss)

  large overlap  ==  hard to tell apart  ==  big unavoidable error

Two candidate worlds	What it forces
far apart in the loss (separation $2s$)	telling them apart pins the estimate
nearly identical data (large overlap)	no test can reliably separate them
both at once	every estimator has error at least about $s$

The single message: separation in the answer plus overlap in the data equals an error floor no method escapes.

Worked example Beginner

You want to estimate a coin's bias $\theta$ (its chance of heads) from $n=100$ flips, and you are told the truth is one of two values: ${\theta }_0=0.50$ or ${\theta }_1=0.55$. The gap between them is $0.05$, so if an estimator is reliably within $0.025$ of the truth, it also reveals which coin you hold.

Step 1. Set the separation. The two candidates differ by $2s=0.05$, so $s=0.025$. An estimator within $s$ of the truth solves the two-way quiz.

Step 2. Ask how distinguishable the data is. With $n=100$ flips, a $0.50$ coin gives about $50$ heads and a $0.55$ coin about $55$ heads, with a typical spread of about $\sqrt{100\times 0.5\times 0.5}=5$ heads. The two head-counts ($50$ versus $55$) differ by only one spread, so the two flip-records overlap heavily.

Step 3. Read off the floor. Because a one-spread gap means the data frequently looks the same either way, any quiz-taker errs a constant fraction of the time — here on the order of $1/3$. So with constant probability the estimator picks the wrong world and lands at least $s=0.025$ from the truth.

Step 4. See what more data buys. Push to $n=10000$ flips: the spread is $\sqrt{10000\times 0.25}=50$ heads, while the gap in head-counts is now $500$. Ten spreads apart, the worlds are easy to separate, and the floor at this fixed gap disappears. To keep a floor you must shrink the gap as $n$ grows.

What this tells us: a lower bound is a balance — choose candidates close enough that the data confuses them, yet far enough that confusing them costs real error. Tune that balance against $n$ and you get the exact rate at which error must decay.

Check your understanding Beginner

Formal definition Intermediate+

Let $({\mathcal{X}}^n,\mathcal{A},\{P_{\theta }:\theta \in \Theta \})$ be a statistical experiment in which $\theta$ is the object of interest and $d$ is a semi-distance on $\Theta$ (or on a functional $\theta (\cdot )$ of it). For an estimator $\hat{\theta }=\hat{\theta }(X_1,\dots ,X_n)$ the minimax risk with loss $w$ a non-decreasing function with $w(0)=0$ is

$${\mathcal{R}}_n^{\star }=\underset{\hat{\theta }}{\inf }\underset{\theta \in \Theta }{\sup }{\mathbb{E}}_{\theta }w(d(\hat{\theta },\theta )),$$

the inf over all measurable estimators. A sequence ${\psi }_n$ is the minimax rate if ${\mathcal{R}}_n^{\star }\asymp w({\psi }_n)$. The upper bound ${\mathcal{R}}_n^{\star }\lesssim w({\psi }_n)$ is supplied by a concrete estimator (kernel, series, wavelet) controlled with the concentration tools of 45.05.01; the lower bound ${\mathcal{R}}_n^{\star }\gtrsim w({\psi }_n)$ is the subject here.

The information quantities driving every lower bound are the divergences between candidate laws. For probability measures $P,Q$ on a common space, the total variation is $\mathrm{TV}(P,Q)={\sup }_A|P(A)-Q(A)|=\frac{1}{2}\int |dP-dQ|$, the Hellinger affinity is $\rho (P,Q)=\int \sqrt{dPdQ}$ with squared Hellinger distance $H^2(P,Q)=2(1-\rho (P,Q))$, and the Kullback-Leibler divergence is $K(P,Q)=\int \log \frac{dP}{dQ}dP$ when $P\ll Q$ (the relative entropy of 37.07.06). For product experiments $K(P^{\otimes n},Q^{\otimes n})=nK(P,Q)$, the additivity that converts a per-sample divergence into the $n$-dependence of the bound. These are linked by the Le Cam inequality $\mathrm{TV}(P,Q)\le \sqrt{1-\rho (P,Q{)}^2}$ and Pinsker's inequality $\mathrm{TV}(P,Q)\le \sqrt{\frac{1}{2}K(P,Q)}$, so controlling $K$ controls $\mathrm{TV}$ and hence the indistinguishability of the candidates.

Definition (reduction to testing). Fix a finite family ${\theta }_0,\dots ,{\theta }_M\in \Theta$ that is $2s$-separated: $d({\theta }_j,{\theta }_k)\ge 2s$ for $j\ne k$. A test is a measurable map $\psi :{\mathcal{X}}^n\to \{0,\dots ,M\}$. The minimax probability of error is $p_{e,M}={\inf }_{\psi }{\max }_{0\le j\le M}{P}_{{\theta }_j}(\psi \ne j)$. The reduction asserts

$$\underset{\hat{\theta }}{\inf }\underset{0\le j\le M}{\max }{P}_{{\theta }_j}(d(\hat{\theta },{\theta }_j)\ge s)\ge p_{e,M},$$

because the minimum-distance test ${\psi }^{\star }(\hat{\theta })=\arg {\min }_{j}d(\hat{\theta },{\theta }_j)$ errs only if $\hat{\theta }$ is at least $s$ from the true ${\theta }_j$ (two centres are $2s$ apart). Combined with Markov's inequality ${\mathbb{E}}_{\theta }w(d(\hat{\theta },\theta ))\ge w(s)P_{\theta }(d(\hat{\theta },\theta )\ge s)$, the estimation problem is bounded below by $w(s)p_{e,M}$ ^{[Tsybakov 2009]}.

Counterexamples to common slips Intermediate+

• "A bigger separation $s$ always gives a bigger lower bound." Only until the candidates become distinguishable. Enlarging $s$ raises $w(s)$ but inflates $K(P_{{\theta }_0},P_{{\theta }_1})$, driving $p_e\to 0$; the bound $w(s)p_e$ is maximized at the balance point where $nK\asymp 1$, not at the largest $s$.

• "Fano needs the candidates pairwise far in KL." Fano needs them pairwise $2s$-separated in the loss $d$ but with small average KL to a reference. Loss-separation and information-closeness are different geometries; the construction must satisfy both at once.

• "Two points always suffice." The two-point method recovers parametric $n^{-1/2}$ rates and pointwise nonparametric rates, but for the integrated $L_2$ risk it loses a logarithmic-to-polynomial factor: the family must grow with $n$ (Fano) or fill a hypercube (Assouad) to match the upper bound.

• "Total variation and KL are interchangeable." Pinsker bounds $\mathrm{TV}$ by $\sqrt{K/2}$, but not conversely; $K$ can be infinite while $\mathrm{TV}<1$. Lower bounds use $\mathrm{TV}/$Hellinger when the densities have disjoint-ish support and KL when product additivity is wanted.

Key theorem with proof Intermediate+

The signature result is Le Cam's two-point method: a single pair of well-chosen candidates already forces a lower bound governed by their statistical distance. The proof is the reduction to testing of the previous section specialized to $M=1$, with the two-point testing error expressed through the affinity.

Theorem (Le Cam's two-point method). Let ${\theta }_0,{\theta }_1\in \Theta$ with $d({\theta }_0,{\theta }_1)\ge 2s$, and write $P_0=P_{{\theta }_0}^{\otimes n}$, $P_1=P_{{\theta }_1}^{\otimes n}$ for the $n$-fold product laws. Then

$$\underset{\hat{\theta }}{\inf }\underset{j\in \{0,1\}}{\max }{\mathbb{E}}_{{\theta }_j}w(d(\hat{\theta },{\theta }_j))\ge w(s)\cdot \frac{1}{2}(1-\mathrm{TV}(P_0,P_1))\ge w(s)\cdot \frac{1}{2}(1-\sqrt{\frac{n}{2}K(P_{{\theta }_0},P_{{\theta }_1})}).$$

In particular, if $nK(P_{{\theta }_0},P_{{\theta }_1})\le \alpha <2$ then the minimax risk is at least $w(s)\cdot \frac{1}{2}(1-\sqrt{\alpha /2})>0$. ^{[Tsybakov 2009]}

Proof. By the reduction to testing it suffices to bound the two-point testing error $p_{e,1}={\inf }_{\psi }{\max }_j{P}_j(\psi \ne j)$ from below, since ${\mathbb{E}}_{{\theta }_j}w(d(\hat{\theta },{\theta }_j))\ge w(s)P_{{\theta }_j}(d(\hat{\theta },{\theta }_j)\ge s)$ and the minimum-distance test turns an estimator into a test that errs whenever the estimator does. For any test $\psi$,

$$\underset{j}{\max }{P}_j(\psi \ne j)\ge \frac{1}{2}(P_0(\psi =1)+P_1(\psi =0))=\frac{1}{2}(P_0(\psi =1)+1-P_1(\psi =1)).$$

Minimizing the right side over events $A=\{\psi =1\}$ gives $\frac{1}{2}(1-{\sup }_A(P_1(A)-P_0(A)))=\frac{1}{2}(1-\mathrm{TV}(P_0,P_1))$, the optimum attained by the likelihood-ratio (Neyman-Pearson) test. Hence $p_{e,1}\ge \frac{1}{2}(1-\mathrm{TV}(P_0,P_1))$, the first inequality. For the second, Pinsker's inequality gives $\mathrm{TV}(P_0,P_1)\le \sqrt{\frac{1}{2}K(P_0,P_1)}$, and product additivity gives $K(P_0,P_1)=K(P_{{\theta }_0}^{\otimes n},P_{{\theta }_1}^{\otimes n})=nK(P_{{\theta }_0},P_{{\theta }_1})$. Substituting yields the stated KL form. The positivity claim is immediate: $nK\le \alpha <2$ forces the bracket positive. $\square$

Corollary (parametric $n^{-1/2}$ floor). For a smooth one-dimensional family with $K(P_{\theta },P_{{\theta }^{\prime }})\le c|\theta -{\theta }^{\prime }{|}^2$ near a point, take ${\theta }_1={\theta }_0+h$ with $h=c^{\prime }/\sqrt{n}$. Then $nK\le c{c}^{\prime 2}$ is bounded, $s=h/2\asymp n^{-1/2}$, and with squared loss $w(t)=t^2$ the two-point bound is ${\mathcal{R}}_n^{\star }\gtrsim n^{-1}$, recovering the Cramér-Rao order. Proof. Insert $h=c^{\prime }/\sqrt{n}$ into the theorem; $nK\le n\cdot c{h}^2=c{c}^{\prime 2}$ is constant, $w(s)=(h/2{)}^2\asymp n^{-1}$, and the bracket is a positive constant. $\square$

Bridge. Le Cam's two-point method is the foundational reason a lower bound is an information-distance computation rather than an estimator-by-estimator search: the reduction to testing converts ${\inf }_{\hat{\theta }}$ into a likelihood-ratio test whose error is exactly $\frac{1}{2}(1-\mathrm{TV})$, and Pinsker plus product additivity make that error a function of the single number $nK(P_{{\theta }_0},P_{{\theta }_1})$. This is exactly the same Kullback divergence that governs the large-deviation rate of 37.07.06 and that appears again in Fano's method below, where a single pair is replaced by a packing of $M$ candidates and total variation is replaced by mutual information. The two-point bound generalises in two directions: increasing $M$ to capture the $\log M$ gain of Fano, and arranging the candidates on a hypercube so coordinatewise errors add, which is Assouad's lemma. Putting these together, the entire minimax lower-bound calculus is one principle — separate the candidates in the loss, keep them close in information — instrumented at three scales, and the bridge is that each scale trades a richer hard subproblem for a sharper floor; this builds toward the $n^{-2s/(2s+1)}$ rate of the Advanced results, where two points give only the pointwise rate and the full integrated rate needs the many-point machinery, and the central insight is that the achievable rate is pinned by how many loss-separated worlds fit inside a fixed information budget $nK\asymp 1$.

Exercises Intermediate+

Advanced results Master

The two-point method is the base of a three-level calculus. Fano's method replaces the pair by a packing whose size enters logarithmically; Assouad's lemma arranges the candidates on a hypercube so that risk adds across coordinates; and the explicit construction over a smoothness class delivers the exact $n^{-2s/(2s+1)}$ rate, certifying the kernel and wavelet estimators as minimax-optimal.

Theorem 1 (Fano's method). Let ${\theta }_0,\dots ,{\theta }_M$ be $2s$-separated in $d$, with product laws $P_j=P_{{\theta }_j}^{\otimes n}$ satisfying the average-KL bound $\frac{1}{M+1}{\sum }_{j=0}^{M}K(P_j,\bar{P})\le \alpha \log M$ for the mixture $\bar{P}=\frac{1}{M+1}{\sum }_k{P}_k$, equivalently $I(\theta ;X)\le \alpha \log M$ with $\theta$ uniform. Then the minimax probability of error obeys $p_{e,M}\ge 1-\alpha -\frac{\log 2}{\log M}$, so for $\alpha <1/2$ and $M$ large,

$${\mathcal{R}}_n^{\star }\ge w(s)(1-\alpha -\frac{\log 2}{\log M})\gtrsim w(s).$$

The mutual information is controlled by the convexity bound $I(\theta ;X)=\frac{1}{M+1}{\sum }_{j}K(P_j,\bar{P})\le \frac{1}{(M+1{)}^2}{\sum }_{j,k}K(P_j,P_k)\le {\max }_{j,k}K(P_{{\theta }_j},P_{{\theta }_k})\cdot n$, so a family that is pairwise loss-separated yet pairwise information-close gives $I\le n{\max }_{j,k}K(P_{{\theta }_j},P_{{\theta }_k})$; choosing the packing with $n{\max }_{j,k}K\asymp \log M$ achieves $\alpha \asymp$ const ^{[Tsybakov 2009]}. Fano sharpens the two-point bound exactly because $\log M$ in the denominator lets the average information grow with the packing while the error stays bounded away from zero — the relative-entropy budget of 37.07.06 is spent against a logarithmically larger menu.

Theorem 2 (Assouad's lemma, the hypercube method). Index a family by the hypercube: $\{{\theta }_{\omega }:\omega \in \{0,1{\}}^m\}$ such that for some $c>0$ the loss is Hamming-additive, $d({\theta }_{\omega },{\theta }_{{\omega }^{\prime }})\ge c{\sum }_{i=1}^{m}1[{\omega }_i\ne {\omega }_i^{\prime }]=c\rho (\omega ,{\omega }^{\prime })$. Then for any estimator and $P_{\omega }=P_{{\theta }_{\omega }}^{\otimes n}$,

$$\underset{\hat{\theta }}{\inf }\underset{\omega }{\max }{\mathbb{E}}_{{\theta }_{\omega }}d(\hat{\theta },{\theta }_{\omega })\ge \frac{cm}{2}\underset{\rho (\omega ,{\omega }^{\prime })=1}{\min }(1-\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }}))\ge \frac{cm}{2}(1-\sqrt{\frac{n}{2}\underset{i}{\max }{K}_i}),$$

where $K_i$ is the per-sample KL between two laws differing only in coordinate $i$ ^{[Tsybakov 2009]}. The proof reduces the summed risk to $m$ independent two-point tests, one per coordinate, via the identity $\mathbb{E}d(\hat{\theta },{\theta }_{\omega })\ge c{\sum }_i\mathrm{Pr}({\hat{\omega }}_i\ne {\omega }_i)$ and a coordinatewise minimum-distance decoder; each coordinate contributes a Le Cam factor. Assouad is the structural statement that the risk of estimating a function is the sum of the risks of estimating its independent features — the mechanism by which integrated $L_2$ risk over a smoothness class accumulates to $h^{2s}$.

Theorem 3 (the $n^{-2s/(2s+1)}$ minimax rate). Let $\Sigma (s,L)$ be the Hölder (or the Sobolev $W^{s,2}(L)$) ball of smoothness $s$ on $[0,1]$. For density estimation from $n$ i.i.d. samples, or for the fixed-design regression model $Y_i=f(x_i)+{\xi }_i$, the minimax $L_2$ risk satisfies

$$\underset{\hat{f}}{\inf }\underset{f\in \Sigma (s,L)}{\sup }{\mathbb{E}}_f\Vert \hat{f}-f{\Vert }_{L_2}^2\asymp n^{-2s/(2s+1)}.$$

The lower bound is Assouad (or Fano) applied to $m\asymp h^{-1}$ disjoint scaled bumps of bandwidth $h\asymp n^{-1/(2s+1)}$: each bump carries $L_2$-energy $\asymp h^{2s+1}$ and per-coordinate KL $\asymp h^{2s+1}$, so $n{h}^{2s+1}\asymp 1$ keeps neighbours indistinguishable while the $m$ coordinates accumulate risk $\asymp m{h}^{2s+1}=h^{2s}\asymp n^{-2s/(2s+1)}$ ^{[Tsybakov 2009][Wasserman 2006]}. The matching upper bound is achieved by a kernel estimator of bandwidth $h\asymp n^{-1/(2s+1)}$ or by a wavelet/orthogonal-series estimator thresholded at the same resolution, controlled with the variance-aware concentration of 45.05.01; the bias-squared $\asymp h^{2s}$ and the variance $\asymp 1/(nh)$ balance at exactly the same $h$, which is why the rate is two-sided and those estimators are minimax-optimal.

Theorem 4 (Le Cam-Birgé equivalence and the testing-affinity master bound). The three methods are instances of one inequality. For any prior $\pi$ on a $2s$-separated family, the Bayes risk lower-bounds the minimax risk, and the Bayes testing error between the two mixtures induced by splitting the family in two is governed by their Hellinger affinity:

$${\mathcal{R}}_n^{\star }\ge w(s)(1-\mathrm{TV}(\int P_{\theta }d{\pi }_0,\int P_{\theta }d{\pi }_1\left)\right)/2,$$

and bounding this mixture total variation by a Hellinger or ${\chi }^2$ affinity recovers Le Cam (${\pi }_0,{\pi }_1$ point masses), Fano (uniform $\pi$ with the entropy bound), and Assouad (product $\pi$ on the hypercube) as the three canonical choices of prior ^{[Le Cam 1973]}. The ${\chi }^2$-divergence variant (the Ingster-Suslina method) replaces TV by ${\chi }^2({\bar{P}}_1,{\bar{P}}_0)$ and is the route to sharp constants and to detection-boundary (rather than estimation-rate) lower bounds.

Synthesis. The minimax lower-bound calculus is one principle read at three scales, and the foundational reason it works is the reduction to testing: ${\inf }_{\hat{\theta }}$ over all estimators collapses to a likelihood-ratio test whose error is $\frac{1}{2}(1-\mathrm{TV})$, so a floor on estimation is a ceiling on distinguishability, an information-distance computation in the Kullback divergence of 37.07.06. Le Cam, Fano, and Assouad are the same inequality against three priors — two point masses, a uniform packing, a hypercube product — and they generalise one another: Fano is dual to Le Cam in that it spends the same per-pair information budget against a logarithmically larger menu, gaining the $\log M$ that the integrated risk needs, while Assouad is the central insight that risk is additive over independent features, so $m\asymp h^{-1}$ coordinatewise two-point tests accumulate to the $h^{2s}$ that a single pair cannot produce. Putting these together, the achievable rate $n^{-2s/(2s+1)}$ is pinned by the arithmetic $n{h}^{2s+1}\asymp 1$ — the largest perturbation a fixed information budget hides — and this is exactly the bandwidth at which the bias-variance balance of the kernel and wavelet upper bounds sits, so the lower bounds of this unit and the concentration-driven upper bounds of 45.05.01 meet, certifying optimality. The bridge upward at every level is the same: separate the candidate worlds in the loss, keep them within a constant information budget, and count how many such worlds the data cannot tell apart.

Full proof set Master

Proposition 1 (reduction to testing). If ${\theta }_0,\dots ,{\theta }_M$ are $2s$-separated and $w$ is non-decreasing with $w(0)=0$, then ${\inf }_{\hat{\theta }}{\max }_j{\mathbb{E}}_{{\theta }_j}w(d(\hat{\theta },{\theta }_j))\ge w(s)p_{e,M}$, where $p_{e,M}={\inf }_{\psi }{\max }_j{P}_{{\theta }_j}(\psi \ne j)$.

Proof. Given an estimator $\hat{\theta }$, define the minimum-distance test ${\psi }^{\star }=\arg {\min }_{j}d(\hat{\theta },{\theta }_j)$ (ties broken arbitrarily). If ${\psi }^{\star }\ne j$ under $P_{{\theta }_j}$, then $d(\hat{\theta },{\theta }_{{\psi }^{\star }})\le d(\hat{\theta },{\theta }_j)$ while $d({\theta }_j,{\theta }_{{\psi }^{\star }})\ge 2s$; the triangle inequality $2s\le d({\theta }_j,{\theta }_{{\psi }^{\star }})\le d(\hat{\theta },{\theta }_j)+d(\hat{\theta },{\theta }_{{\psi }^{\star }})\le 2d(\hat{\theta },{\theta }_j)$ forces $d(\hat{\theta },{\theta }_j)\ge s$. Hence $P_{{\theta }_j}({\psi }^{\star }\ne j)\le P_{{\theta }_j}(d(\hat{\theta },{\theta }_j)\ge s)$, so ${\max }_j{P}_{{\theta }_j}(d(\hat{\theta },{\theta }_j)\ge s)\ge {\max }_j{P}_{{\theta }_j}({\psi }^{\star }\ne j)\ge p_{e,M}$. Markov's inequality gives ${\mathbb{E}}_{{\theta }_j}w(d(\hat{\theta },{\theta }_j))\ge w(s)P_{{\theta }_j}(d(\hat{\theta },{\theta }_j)\ge s)$, and taking the max over $j$ then the inf over $\hat{\theta }$ yields the claim. $\square$

Proposition 2 (Le Cam two-point bound). For $P_0,P_1$ on a common space, ${\inf }_{\psi }{\max }_{j\in \{0,1\}}{P}_j(\psi \ne j)=\frac{1}{2}(1-\mathrm{TV}(P_0,P_1))$, hence with $2s$-separation ${\mathcal{R}}_n^{\star }\ge w(s)\cdot \frac{1}{2}(1-\mathrm{TV}(P_0,P_1))$.

Proof. For any test write $A=\{\psi =1\}$. Then ${\max }_j{P}_j(\psi \ne j)\ge \frac{1}{2}(P_0(A)+P_1(A^c))=\frac{1}{2}(1-(P_1(A)-P_0(A)))$. Taking the inf over tests is taking the sup over $A$ of $P_1(A)-P_0(A)$, which equals $\mathrm{TV}(P_0,P_1)$ attained at $A^{\star }=\{d{P}_1\ge d{P}_0\}$ (the likelihood-ratio test); at $A^{\star }$ the average equals the max, so the inf is exactly $\frac{1}{2}(1-\mathrm{TV})$. The estimation bound follows from Proposition 1 with $M=1$. $\square$

Proposition 3 (Fano's inequality and its estimation corollary). For a Markov chain $\theta \to X\to \hat{\theta }$ with $\theta$ uniform on $\{0,\dots ,M\}$ and $p_e=\mathrm{Pr}(\hat{\theta }\ne \theta )$: $H(p_e)+p_e\log M\ge H(\theta \mid X)$, and consequently $p_e\ge 1-\frac{I(\theta ;X)+\log 2}{\log M}$.

Proof. Let $E=1[\hat{\theta }\ne \theta ]$. Expand $H(E,\theta \mid \hat{\theta })$ two ways. First, $H(E,\theta \mid \hat{\theta })=H(\theta \mid \hat{\theta })+H(E\mid \theta ,\hat{\theta })=H(\theta \mid \hat{\theta })$ since $E$ is determined by $(\theta ,\hat{\theta })$. Second, $H(E,\theta \mid \hat{\theta })=H(E\mid \hat{\theta })+H(\theta \mid E,\hat{\theta })\le H(E)+H(\theta \mid E,\hat{\theta })$. Now $H(\theta \mid E,\hat{\theta })=\mathrm{Pr}(E=0)H(\theta \mid \hat{\theta },E=0)+\mathrm{Pr}(E=1)H(\theta \mid \hat{\theta },E=1)\le 0+p_e\log M$, because $E=0$ pins $\theta =\hat{\theta }$ and $E=1$ leaves $\theta$ among $M$ remaining values. Thus $H(\theta \mid \hat{\theta })\le H(p_e)+p_e\log M$, and the data-processing inequality $H(\theta \mid \hat{\theta })\ge H(\theta \mid X)$ gives Fano. With $\theta$ uniform, $H(\theta \mid X)=\log (M+1)-I(\theta ;X)\ge \log M-I(\theta ;X)$; bounding $H(p_e)\le \log 2$ and rearranging gives $p_e\ge 1-(I(\theta ;X)+\log 2)/\log M$. $\square$

Proposition 4 (mutual information bounded by average pairwise KL). For $\theta$ uniform on $\{0,\dots ,M\}$ inducing $P_j=P_{{\theta }_j}^{\otimes n}$ with mixture $\bar{P}$, $I(\theta ;X)=\frac{1}{M+1}{\sum }_{j}K(P_j,\bar{P})\le \frac{1}{(M+1{)}^2}{\sum }_{j,k}K(P_j,P_k)\le n{\max }_{j,k}K(P_{{\theta }_j},P_{{\theta }_k})$.

Proof. The identity $I(\theta ;X)=\frac{1}{M+1}{\sum }_{j}K(P_j,\bar{P})$ is the definition of mutual information for a uniform mixture. Convexity of $K(P,\cdot )$ in its second argument (relative entropy is jointly convex) gives $K(P_j,\bar{P})=K(P_j,\frac{1}{M+1}{\sum }_k{P}_k)\le \frac{1}{M+1}{\sum }_{k}K(P_j,P_k)$, so averaging over $j$ yields the double-sum bound. Each term satisfies $K(P_j,P_k)=K(P_{{\theta }_j}^{\otimes n},P_{{\theta }_k}^{\otimes n})=nK(P_{{\theta }_j},P_{{\theta }_k})\le n{\max }_{j,k}K(P_{{\theta }_j},P_{{\theta }_k})$ by product additivity, and the average of terms each $\le$ the max is $\le$ the max times $n$. $\square$

Proposition 5 (Assouad's lemma). Let $\{{\theta }_{\omega }:\omega \in \{0,1{\}}^m\}$ satisfy $d({\theta }_{\omega },{\theta }_{{\omega }^{\prime }})\ge c\rho (\omega ,{\omega }^{\prime })$ (Hamming-additive loss) and $P_{\omega }=P_{{\theta }_{\omega }}^{\otimes n}$. Then ${\inf }_{\hat{\theta }}{\max }_{\omega }{\mathbb{E}}_{{\theta }_{\omega }}d(\hat{\theta },{\theta }_{\omega })\ge \frac{cm}{2}{\min }_{\rho (\omega ,{\omega }^{\prime })=1}(1-\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }}))$.

Proof. From the Hamming lower bound, ${\mathbb{E}}_{{\theta }_{\omega }}d(\hat{\theta },{\theta }_{\omega })\ge c{\mathbb{E}}_{{\theta }_{\omega }}\rho (\hat{\omega },\omega )=c{\sum }_{i=1}^m{\mathrm{Pr}}_{{\theta }_{\omega }}({\hat{\omega }}_i\ne {\omega }_i)$, where $\hat{\omega }=\arg {\min }_{\nu }d(\hat{\theta },{\theta }_{\nu })$ is the induced hypercube decoder. Replacing the worst case by the average over $\omega$ uniform on the cube, ${\max }_{\omega }{\mathbb{E}}_{{\theta }_{\omega }}d\ge c{\sum }_i\frac{1}{2^m}{\sum }_{\omega }{\mathrm{Pr}}_{{\theta }_{\omega }}({\hat{\omega }}_i\ne {\omega }_i)$. For each coordinate $i$, pair $\omega$ with its flip ${\omega }^{\oplus i}$; the inner average is, per pair, a two-point testing error between $P_{\omega }$ and $P_{{\omega }^{\oplus i}}$, so by Proposition 2 it is $\ge \frac{1}{2}(1-\mathrm{TV}(P_{\omega },P_{{\omega }^{\oplus i}}))\ge \frac{1}{2}{\min }_{\rho =1}(1-\mathrm{TV})$. Summing the $m$ coordinates, ${\max }_{\omega }{\mathbb{E}}_{{\theta }_{\omega }}d\ge c\cdot m\cdot \frac{1}{2}{\min }_{\rho (\omega ,{\omega }^{\prime })=1}(1-\mathrm{TV}(P_{\omega },P_{{\omega }^{\prime }}))$. $\square$

Proposition 6 (the integrated $L_2$ lower bound $n^{-2s/(2s+1)}$). Over $\Sigma (s,L)$ on $[0,1]$, ${\inf }_{\hat{f}}{\sup }_{f\in \Sigma (s,L)}{\mathbb{E}}_f\Vert \hat{f}-f{\Vert }_2^2\gtrsim n^{-2s/(2s+1)}$.

Proof. Fix a smooth bump $K$ supported on $[0,1]$ with $\int K=0$, $\Vert K{\Vert }_2>0$. Partition $[0,1]$ into $m=\lfloor 1/h\rfloor$ cells of width $h$ and set, for $\omega \in \{0,1{\}}^m$, $f_{\omega }=f_0+{\sum }_{i=1}^m{\omega }_{i}L{h}^{s}K((\cdot -x_i)/h)$ on a baseline density $f_0$ bounded below on its support. Each summand has $C^s$-norm $\asymp L$, so $f_{\omega }\in \Sigma (s,cL)$ for a fixed $c$. The squared-$L_2$ loss is Hamming-additive: $\Vert f_{\omega }-f_{{\omega }^{\prime }}{\Vert }_2^2={\sum }_{i}1[{\omega }_i\ne {\omega }_i^{\prime }]L^2{h}^{2s}\Vert K{\Vert }_2^{2}h=\rho (\omega ,{\omega }^{\prime })L^2\Vert K{\Vert }_2^2{h}^{2s+1}$, so the semi-distance $d=\Vert \cdot {\Vert }_2$ obeys $d(f_{\omega },f_{{\omega }^{\prime }})\ge c^{\prime }\rho (\omega ,{\omega }^{\prime }{)}^{1/2}{h}^{s+1/2}$; applying Assouad in the squared loss (each coordinate contributing $\asymp h^{2s+1}$) gives summed risk $\ge \frac{m}{2}{L}^2\Vert K{\Vert }_2^2{h}^{2s+1}{\min }_{\rho =1}(1-\mathrm{TV})$. Neighbours differ in one cell, with per-sample KL $K(P_{f_{\omega }},P_{f_{{\omega }^{\oplus i}}})\asymp \int (f_{\omega }-f_{{\omega }^{\oplus i}}{)}^2/f_0\asymp h^{2s+1}$, so $\mathrm{TV}\le \sqrt{\frac{n}{2}{h}^{2s+1}\cdot }$ stays $\le \frac{1}{2}$ once $n{h}^{2s+1}\le c_0$. Choose $h\asymp n^{-1/(2s+1)}$ so $n{h}^{2s+1}\asymp 1$ and $m\asymp h^{-1}\asymp n^{1/(2s+1)}$; the risk is $\gtrsim m{h}^{2s+1}=h^{2s}\asymp n^{-2s/(2s+1)}$. $\square$

Connections Master

This unit is the lower-bound companion of the concentration toolkit in 45.05.01: there the variance-aware Bernstein tail controls the stochastic error of a kernel or series estimator and yields the upper bound $\mathbb{E}\Vert \hat{f}-f{\Vert }_2^2\lesssim h^{2s}+1/(nh)\asymp n^{-2s/(2s+1)}$ at bandwidth $h\asymp n^{-1/(2s+1)}$; here the Le Cam-Fano-Assouad calculus proves the matching floor, so the two together pin the minimax rate exactly and certify those estimators as optimal. The bias-variance balance that fixes $h$ in the upper bound is the same arithmetic $n{h}^{2s+1}\asymp 1$ that fixes the hard subproblem in the lower bound.

The information quantity at the centre of every bound is the Kullback-Leibler divergence developed as a rate function in 37.07.06: product additivity $K(P^{\otimes n},Q^{\otimes n})=nK(P,Q)$ converts a per-sample divergence into the sample-size dependence of the floor, Pinsker's inequality routes it to total variation in Le Cam, and the average-KL bound on mutual information routes it to Fano. The relative entropy that measures how fast empirical frequencies betray a wrong model in large-deviation theory is the same quantity that measures how well an estimator can betray which of several candidate models generated the data.

The reduction of estimation to testing is the statistical-decision analogue of the No-Free-Lunch argument in 45.07.02: both lower-bound a learner by exhibiting a family of targets the data cannot separate and averaging the error over that family. No-Free-Lunch packs all labelings of a shattered set and averages with a uniform prior — a discrete Fano/Assouad instance — while the nonparametric bound packs loss-separated densities inside a fixed information budget; the shared mechanism is that a worst-case adversary over an indistinguishable family forces irreducible error, and the inductive-bias restriction No-Free-Lunch demands is the smoothness class $\Sigma (s,L)$ that makes the nonparametric rate finite.

The wavelet/orthogonal-series estimator whose thresholded form attains the upper bound at the same resolution as this unit's hard subproblem is the constructive optimal estimator these bounds match; its adaptivity across smoothness levels is exactly the question of whether one estimator can meet the $n^{-2s/(2s+1)}$ floor simultaneously for all $s$, which the lower-bound calculus reframes as the cost of not knowing $s$ in advance.

Historical & philosophical context Master

The reduction of estimation to testing and the systematic use of affinities between candidate measures originate with Lucien Le Cam, whose 1973 Annals of Statistics paper on convergence of estimates under dimensionality restrictions introduced the two-point comparison and the Hellinger-affinity control that bear his name ^{[Le Cam 1973]}. Le Cam's broader programme — the comparison of statistical experiments through their deficiency and the asymptotic equivalence of estimation and testing — placed minimax lower bounds on an information-geometric footing rather than a case-by-case one.

The hypercube method was given its clean form by Patrice Assouad in 1983, isolating the additivity of risk over independent coordinates as the device that produces integrated rates ^{[Tsybakov 2009]}. The information-theoretic route through Fano's inequality descends from Robert Fano's 1950s lecture notes on channel coding and entered statistics through the recognition that a multiple-hypothesis estimation problem is a noisy channel whose capacity bounds the achievable error; the modern packaging with mutual information and the Kullback diameter is standard in the information-theory literature ^{[Cover Thomas 2006]}. The synthesis of the three methods into a single calculus for nonparametric rates, together with the explicit constructions that yield $n^{-2s/(2s+1)}$ over Hölder and Sobolev classes, is the content of Tsybakov's 2009 monograph ^{[Tsybakov 2009]}, with the density-estimation rates also recorded in Wasserman's treatment ^{[Wasserman 2006]}. The ${\chi }^2$-divergence refinement and the detection-boundary theory are due to Yuri Ingster and collaborators in the 1980s-1990s.

Bibliography Master

@book{tsybakov2009,
  author    = {Tsybakov, Alexandre B.},
  title     = {Introduction to Nonparametric Estimation},
  publisher = {Springer},
  year      = {2009}
}

@book{wasserman2006,
  author    = {Wasserman, Larry},
  title     = {All of Nonparametric Statistics},
  publisher = {Springer},
  year      = {2006}
}

@article{lecam1973,
  author  = {Le Cam, Lucien},
  title   = {Convergence of estimates under dimensionality restrictions},
  journal = {The Annals of Statistics},
  volume  = {1},
  number  = {1},
  pages   = {38--53},
  year    = {1973}
}

@article{assouad1983,
  author  = {Assouad, Patrice},
  title   = {Deux remarques sur l'estimation},
  journal = {Comptes Rendus de l'Acad\'emie des Sciences, Paris, S\'erie I},
  volume  = {296},
  number  = {23},
  pages   = {1021--1024},
  year    = {1983}
}

@book{coverthomas2006,
  author    = {Cover, Thomas M. and Thomas, Joy A.},
  title     = {Elements of Information Theory},
  edition   = {2},
  publisher = {Wiley-Interscience},
  year      = {2006}
}

@article{ingstersuslina2003,
  author    = {Ingster, Yuri I. and Suslina, Irina A.},
  title     = {Nonparametric Goodness-of-Fit Testing Under Gaussian Models},
  journal   = {Lecture Notes in Statistics 169, Springer},
  year      = {2003}
}

@article{birge1983,
  author  = {Birg\'e, Lucien},
  title   = {Approximation dans les espaces m\'etriques et th\'eorie de l'estimation},
  journal = {Zeitschrift f\"ur Wahrscheinlichkeitstheorie und verwandte Gebiete},
  volume  = {65},
  number  = {2},
  pages   = {181--237},
  year    = {1983}
}