Question 6

Can anyone do better?

Is the rate, sample requirement, memory, privacy–utility trade-off or oracle complexity your method achieves unavoidable for every method in the stated model?

Symptoms

Is this your question?

Sub-cases

Which version are you facing?

Case Usually start with
A statistical or minimax estimation rate? Le Cam's two-point method for simple bounds; Fano with a packing for dimension dependence.
Many independent coordinates? Assouad's lemma with a hypercube construction.
Optimization or oracle complexity? A hard function family, a resisting or zero-chain oracle, and Yao's principle for randomized algorithms.
A computational lower bound? A reduction from a known hard problem, with the complexity assumptions stated.
Privacy-constrained learning? Information contraction under the privacy mechanism, then Le Cam or Fano.
Memory or communication? Information or communication complexity, or a hard-query construction.
The recipe

Fix the quantifiers, then build hard instances

Write the minimax quantity before constructing anything:

\[\inf_{\hat\theta \in \mathcal{A}}\ \sup_{P \in \mathcal{P}}\ \mathbb{E}_P\, L\big(\hat\theta, \theta(P)\big).\]

Most flawed lower bounds hide the wrong class of algorithms \(\mathcal{A}\), problems \(\mathcal{P}\), oracle or loss in the prose.

  1. Choose a hard family whose members are far apart in your actual loss but hard to tell apart from data.
  2. Bound KL, total variation or mutual information between them.
  3. Apply Le Cam for two alternatives, Fano for a packing, or an oracle construction for optimization.
  4. Optimize the size of the perturbation.
  5. Put the upper and lower bounds side by side under the same assumptions, instead of declaring optimality because the exponents look alike.
25
0.40
Two hypothesesshaded overlap is \(1 - \mathrm{TV}\)
The lower bound\(\tfrac{\Delta}{4}(1 - \mathrm{TV})\) against \(\Delta\)
data under \(\theta_0\) data under \(\theta_1\) bound at your \(\Delta\) best choice of \(\Delta\)
Le Cam's two-point method for estimating a Gaussian mean. Any estimator must err by at least \(\tfrac{\Delta}{4}(1 - \mathrm{TV})\) on one of the two hypotheses. Far apart, the data tell them apart (TV near 1); close together, the error you force is tiny. The best \(\Delta\) sits near \(1/\sqrt{n}\), so the bound scales like \(1/\sqrt{n}\): watch "best bound \(\times\sqrt{n}\)" stay constant as you change \(n\). That matches the sample mean, so the rate is minimax optimal.
A complete proof

The sample mean is minimax optimal

The claim

Observe \(X_1, \dots, X_n \overset{\text{iid}}{\sim} \mathcal{N}(\theta, 1)\) with unknown \(\theta \in \mathbb{R}\), and measure error by \(\lvert \hat\theta - \theta \rvert\). Then

\[\inf_{\hat\theta}\ \sup_{\theta \in \mathbb{R}}\ \mathbb{E}_\theta \lvert \hat\theta - \theta \rvert \ge \frac{1}{8\sqrt{n}}, \qquad \text{while} \qquad \mathbb{E}_\theta \lvert \bar X - \theta \rvert = \sqrt{\frac{2}{\pi n}} \approx \frac{0.80}{\sqrt{n}} .\]

Upper and lower bounds match up to a constant, so \(n^{-1/2}\) is the minimax rate.

Assumptions
  • Known unit variance and i.i.d. observations.
  • The infimum is over every estimator, measurable in the data. The loss is the same on both sides.
First move, and why

Fix the quantifiers, then shrink the supremum to two hypotheses, \(\theta_0 = 0\) and \(\theta_1 = \Delta\). The worst case over all of \(\mathbb{R}\) is at least as bad as the worst of two, and two hypotheses turn estimation into a testing problem we can analyze exactly.

Show the proof, with commentary

Step 1: estimation to testing. Let \(s = \Delta/2\) and \(A = \{\lvert \hat\theta - \theta_0 \rvert \ge s\}\). If \(A\) fails, then \(\lvert \hat\theta - \theta_1 \rvert \ge s\) by the triangle inequality. Writing \(P_j\) for the distribution of the sample under \(\theta_j\),

\[\max_j \mathbb{E}_j \lvert \hat\theta - \theta_j \rvert \ge \frac{s}{2}\big(P_0(A) + P_1(A^c)\big) \ge \frac{s}{2}\big(1 - \lVert P_0 - P_1 \rVert_{\mathrm{TV}}\big).\]

The first inequality uses "maximum \(\ge\) average" and Markov's inequality; the second uses \(P_1(A) - P_0(A) \le \mathrm{TV}\), where \(\lVert P - Q \rVert_{\mathrm{TV}} = \sup_A \lvert P(A) - Q(A) \rvert\). This is Le Cam's two-point bound.

Step 2: bound the distinguishability. KL tensorizes over independent samples, and Pinsker converts it to total variation:

\[D_{\mathrm{KL}}(P_0 \Vert P_1) = n\cdot\frac{\Delta^2}{2}, \qquad \lVert P_0 - P_1 \rVert_{\mathrm{TV}} \le \sqrt{\tfrac12 \cdot \tfrac{n\Delta^2}{2}} = \frac{\Delta\sqrt{n}}{2}.\]

Step 3: choose the separation. The bound is \(\tfrac{\Delta}{4}\big(1 - \tfrac{\Delta\sqrt{n}}{2}\big)\). Take \(\Delta = 1/\sqrt{n}\), so the total variation is at most \(1/2\):

\[\inf_{\hat\theta}\ \sup_\theta\ \mathbb{E}_\theta \lvert \hat\theta - \theta \rvert \ge \frac{1}{4\sqrt{n}}\cdot\frac12 = \frac{1}{8\sqrt{n}}.\]

This is the balance the demo shows: a larger \(\Delta\) makes errors costlier but the hypotheses easier to tell apart. The best choice scales as \(1/\sqrt{n}\), and so does the bound.

Step 4: the matching upper bound. \(\bar X - \theta \sim \mathcal{N}(0, 1/n)\) and \(\mathbb{E}\lvert Z \rvert = \sqrt{2/\pi}\) for a standard normal \(Z\), so \(\mathbb{E}_\theta \lvert \bar X - \theta \rvert = \sqrt{2/(\pi n)}\) for every \(\theta\). \(\blacksquare\)

A tempting approach that fails

Spread the hypotheses far apart to make the factor \(\Delta/4\) large. Once \(\Delta \gg 1/\sqrt{n}\), the two sampling distributions barely overlap, the total variation approaches 1, and the bound collapses to zero. Lower bounds need hypotheses that are far apart in the loss but close in distribution.

If you relax an assumption
  • \(d\) dimensions: two points only give \(1/\sqrt{n}\). A packing of many hypotheses with Fano's inequality recovers the \(\sqrt{d/n}\) dependence.
  • Squared loss: the same construction gives a \(1/n\) lower bound, matched by the sample mean.
  • A local privacy constraint: the mechanism shrinks the KL in Step 2, which raises the lower bound; this is the route Duchi, Wainwright & Jordan take.
Try it yourself

A coin instead of a Gaussian

The exercise

You observe \(n\) independent flips of a coin with unknown bias \(p\). Adapt the Le Cam argument above to show that every estimator has \(\max_p \mathbb{E}\lvert \hat p - p \rvert \ge c/\sqrt n\) for a constant \(c\), and check that the sample mean matches the rate.

Hint

Use the hypotheses \(p_0 = 1/2\) and \(p_1 = 1/2 + \Delta\). For Bernoulli distributions, \(\mathrm{KL}\) is at most the \(\chi^2\) divergence: \(\mathrm{KL}(\mathrm{Bern}(q) \,\Vert\, \mathrm{Bern}(p)) \le (q - p)^2/(p(1 - p))\).

Show a solution

Distinguishability. One flip has \(\mathrm{KL} \le \Delta^2/(1/4) = 4\Delta^2\), so \(n\) flips have \(\mathrm{KL} \le 4n\Delta^2\), and Pinsker gives \(\mathrm{TV} \le \sqrt{2n}\,\Delta\).

Le Cam. As in Step 1 above, \(\max_j \mathbb{E}_j\lvert \hat p - p_j \rvert \ge \tfrac{\Delta}{4}(1 - \sqrt{2n}\,\Delta)\). This is largest at \(\Delta = 1/(2\sqrt{2n})\), giving

\[\max_p \mathbb{E}\lvert \hat p - p \rvert \ge \frac{1}{16\sqrt{2n}} \approx \frac{0.044}{\sqrt n}.\]

Upper bound. For the sample mean, \(\mathbb{E}\lvert \bar X - p \rvert \le \sqrt{p(1 - p)/n} \le 1/(2\sqrt n)\) by Jensen. Both bounds are of order \(1/\sqrt n\), so the rate is optimal; only the constant is loose.

The toolkit

What each tool gives you, and what it costs

Le Cam's two-point method

\[\inf_{\hat\theta}\ \max_{j \in \{0, 1\}} \mathbb{E}_j\, d(\hat\theta, \theta_j) \ge \frac{s}{2}\big(1 - \lVert P_0 - P_1 \rVert_{\mathrm{TV}}\big)\]

If \(d(\theta_0, \theta_1) \ge 2s\) and \(P_0, P_1\) are the corresponding distributions of the data.

Gives
A fast, clean minimax lower bound.
Costs
Two well-separated but statistically indistinguishable hypotheses.
Wrong tool when
You need dimension dependence, which takes many hypotheses.

Fano's inequality

\[\Pr(\hat V \ne V) \ge 1 - \frac{I(V; X) + \ln 2}{\ln M}\]

For \(V\) uniform over \(M\) hypotheses and observation \(X\).

Gives
Turns a large packing with small information into a minimax error.
Costs
\(M\) separated alternatives and control of their information or KL.
Wrong tool when
\(M = 2\); Le Cam is cleaner.

Pinsker and KL tensorization

\[\lVert P - Q \rVert_{\mathrm{TV}} \le \sqrt{\tfrac12 D_{\mathrm{KL}}(P \Vert Q)}, \qquad D_{\mathrm{KL}}(P^{\otimes n} \Vert Q^{\otimes n}) = n\, D_{\mathrm{KL}}(P \Vert Q)\]

The second identity is for independent product observations.

Gives
Lets KL calculations feed Le Cam, and sets the critical separation as a function of \(n\).
Costs
Absolute continuity; independent observations for tensorization.
Wrong tool when
Observations are adaptive or interacting; use conditional chain rules instead.

Packing reduction

\[d(\theta_i, \theta_j) \ge 2s\ \ \forall i \ne j \;\Longrightarrow\; \text{error} < s \text{ gives an } M\text{-way decoder}\]

Choose \(\{\theta_1, \dots, \theta_M\}\) separated in the metric you report.

Gives
A bridge from estimation to hypothesis testing.
Costs
Separation measured in the loss you actually report.
Wrong tool when
Parameters are separated but the predictions or risks are not.

Yao's minimax principle

\[\min_{\text{rand. } A}\ \max_{x}\ \mathbb{E}\, C(A, x) \;\ge\; \max_{\mu}\ \min_{\text{det. } a}\ \mathbb{E}_{x \sim \mu}\, C(a, x)\]

In finite settings.

Gives
Lower bounds for randomized algorithms from one hard input distribution and deterministic algorithms.
Costs
A correct minimax setup; care with infinite spaces and measurability.
Wrong tool when
Your lower bound already holds pointwise for randomized algorithms.
Worked examples

How published papers answer it

  1. Duchi, Wainwright & Jordan, Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation, NeurIPS 2013. NeurIPS

    Combines Le Cam- and Fano-style reasoning with the contraction of information that local privacy causes, giving sharp privacy–efficiency trade-offs. A model for adding an ML-specific constraint to classical testing tools.

  2. Carmon, Duchi, Hinder & Sidford, Lower Bounds for Finding Stationary Points I, Mathematical Programming 184, 2020. arXiv

    Shows that even algorithms with access to all derivatives up to order \(p\) need on the order of \(\epsilon^{-(p+1)/p}\) queries to find an \(\epsilon\)-stationary point of a smooth non-convex function. The canonical modern hard-function and oracle construction.

  3. Agarwal & Hazan, Lower Bounds for Higher-Order Convex Optimization, COLT 2018. PMLR

    Builds hard convex instances showing that access to higher derivatives does not remove polynomial dependence on accuracy, making accelerated higher-order methods nearly tight.

  4. Diakonikolas & Guzmán, Lower Bounds for Parallel and Randomized Convex Optimization, COLT 2019. PMLR

    Limits algorithms to batches of local-oracle queries and shows parallelism cannot generally collapse sequential complexity. A good example of why the oracle model is part of the theorem, not an implementation detail.

  5. Blanchard, Zhang & Jaillet, Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal, COLT 2023. PMLR

    Proves a memory–query trade-off for deterministic first-order algorithms: using less than quadratic memory forces extra queries.

Common traps

Where proofs of this kind go wrong

Resources

Where to go next

← Back to the guide

Found an error, or have a better example or a question this guide should cover? Email [email protected]. Corrections and contributions are welcome. Last updated October 5, 2026.