TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Gaussian sparse-sequence minimax lower bound

Statement

Assume the Axiom of Choice. Let $n, d \geq 1$ , $σ > 0$ , and let $1 \leq s \leq d / 2$ be integers. Observe $Z \in R^{d}$ with independent coordinates $Z_{j} \sim N (θ_{j}, σ^{2} / n)$ for a parameter $Θ_{s, d} : = {θ \in R^{d} : ∣ {j \in {1, \dots, d} : θ_{j} \neq 0} ∣ \leq s} .$ For every Borel estimator $T : R^{d} \to R^{d}$ , $\sup_{θ \in Θ_{s, d}} E_{θ} ∥ T (Z) - θ ∥_{2}^{2} \geq \frac{σ^{2} s \log (e d / s)}{200000 n} .$

Facts & Assumptions

Given: AC, integers $n, d \geq 1$ , $σ > 0$ , $1 \leq s \leq d / 2$ , the independent-coordinate Gaussian sequence experiment, and a Borel estimator $T : R^{d} \to R^{d}$ .

[A1]

Assume AC, as required by the Fano, KL, and Gaussian-location suppliers (The Axiom of Choice).

[F1]

For $1 \leq s \leq d / 2$ , there is a finite code of binary vectors with exactly $s$ ones, pairwise squared Euclidean distance greater than $s / 2$ , and $\log M \geq (s / 1024) \log (e d / s)$ (A sparse Hamming packing for every $1 \leq k \leq d / 2$ ).

[F2]

For independent coordinates $N (θ_{j}, σ^{2} / n)$ , the KL divergence between two sequence laws is $n ∥ θ - θ^{'} ∥_{2}^{2} / (2 σ^{2})$ (KL divergence between equal-variance Gaussian location laws, Additivity of KL divergence for finite product laws).

[F3]

For $M$ separated hypotheses and a reference law $Q$ , every randomized estimator has uniform average squared-error risk at least $\frac{Δ^{2}}{4} (1 - \frac{M^{- 1} \sum_{j} D (P_{j} ∥ Q) + \log 2}{\log M})$ (Fano’s packing bound with a reference-distribution KL bound).

[F4]

Under the event-supremum convention, $∥ P - Q ∥_{T V} \leq \sqrt{D (P ∥ Q) / 2}$ (Pinsker’s inequality with event-supremum total variation).

[F5]

For scalar targets separated by $b > 0$ , every randomized scalar estimator has maximum squared-error risk at least $\frac{b^{2}}{8} (1 - ∥ P_{0} - P_{1} ∥_{T V})$ (Two-point Le Cam lower bound for squared-error risk).

[F6]

Risk is the expected nonnegative loss under the sampling and action laws (Loss functions and risk).

[F7]

A Borel estimator induces a measurable point-mass probability kernel (Randomized procedures as probability kernels, A statistic induces a deterministic probability kernel).

[F8]

The natural logarithm is strictly increasing and has the product law; $\log x = \int_{1}^{x} d t / t$ , the integral is monotone, squaring is strictly increasing on nonnegative reals, and nonnegative square roots are unique (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The integral logarithm $L (x) : = \int_{1}^{x} \frac{d t}{t}$ for $x > 0$ , The integral logarithm $L$ is the published natural logarithm, If $f \leq g$ on $[a, b]$ and both are integrable then $\int_{a}^{b} f \leq \int_{a}^{b} g$ ; and $m (b - a) \leq \int_{a}^{b} f \leq M (b - a)$ , Squaring is monotone on the nonnegatives, Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ ).

[F9]

$e = \exp (1) > 2$ , since the defining series for $e$ has initial terms $1 + 1 + 1 / 2$ and positive remaining terms; $\exp$ is strictly increasing (The real exponential function and the number $e$ by a power series, The exponential function is strictly increasing).

Proof

1.1F1F8F9givenalgebra

Choose the code $C$ from [F1], with cardinality $M$ . Since $e d / s \geq 2 e > 1$ by [F9], [F8] gives $\log (e d / s) > 0$ ; hence $M \geq 2$ . Put $a : = \sqrt{\frac{σ^{2} \log M}{4 n s}} > 0, θ^{ω} = a u^{ω} (ω \in C) .$ Every $θ^{ω}$ belongs to $Θ_{s, d}$ , and distinct code targets have squared distance greater than $a^{2} s / 2$ .

1.2A1F1F2F4F5F7F8givenalgebra

Now suppose $M = 2$ . By [F8], $\log 2 = \int_{1}^{2} d t / t \leq 1$ , because $1 / t \leq 1$ on $[1, 2]$ . Hence [F1] gives $s \log (e d / s) \leq 1024$ . Consider the two parameters $0$ and $b e_{1}$ , where $b = σ / (2 \sqrt{n})$ ; both belong to $Θ_{s, d}$ . By [F2], their sequence laws have KL divergence $n b^{2} / (2 σ^{2}) = 1 / 8$ , so [F4] gives total variation at most $1 / 4$ . For the Borel vector estimator $T$ , its first coordinate $T_{1}$ is Borel, and [F7] makes it an admissible scalar kernel. Pointwise, $∥ T (z) - θ ∥_{2}^{2} \geq ∣ T_{1} (z) - θ_{1} ∣^{2}$ for both parameters. Applying [F5] to this scalar kernel shows the maximum vector risk is at least $\frac{b^{2}}{8} (1 - \frac{1}{4}) = \frac{3 σ^{2}}{128 n} > \frac{1024 σ^{2}}{200000 n} \geq \frac{σ^{2} s \log (e d / s)}{200000 n} .$

2.1A1F1F2step 1.1algebra

Take the reference law $Q = P_{0}$ of the zero-mean sequence. By [F2], $D (P_{θ^{ω}} ∥ P_{0}) = \frac{n}{2 σ^{2}} ∥ a u^{ω} ∥_{2}^{2} = \frac{n a^{2} s}{2 σ^{2}} = \frac{\log M}{8}$ for every $ω$ , since $u^{ω}$ has exactly $s$ ones.

3.1A1F3F7F8step 1.1step 2.1algebra

First suppose $M \geq 3$ . Since $3 > 2 \sqrt{2}$ (squaring gives $9 > 8$ ), [F8] implies $\log 3 > \log (2 \sqrt{2}) = \frac{3}{2} \log 2$ . Thus $\log 2 / \log M < 2 / 3$ . The average reference KL ratio in [F3] is $1 / 8$ by step 2.1, so the Fano factor is greater than $1 - 1 / 8 - 2 / 3 = 5 / 24 > 1 / 5$ . With separation $Δ = a \sqrt{s / 2}$ , [F3] gives uniform average risk greater than $\frac{Δ^{2}}{20} = \frac{a^{2} s}{40} = \frac{σ^{2} \log M}{160 n} \geq \frac{σ^{2} s \log (e d / s)}{163840 n} > \frac{σ^{2} s \log (e d / s)}{200000 n} .$ The maximum risk dominates this finite-code average; the Borel estimator is an admissible kernel by [F7]. Thus its supremum risk satisfies the same lower bound.

4.1F6step 1.1step 1.2step 3.1∎

The cases $M \geq 3$ and $M = 2$ exhaust the possibilities by step 1.1. Step 3.1 proves the $M \geq 3$ case, and step 1.2 proves the $M = 2$ case. Thus the claimed lower bound holds for the arbitrary Borel estimator $T$ , with risk understood as in [F6].

Depends on

Used by

Matching minimax rate in a Gaussian orthogonal sequence model Corollary

Dependency tree · two levels

108 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Philippe Rigollet and Jan-Christian Hütter, High-Dimensional Statistics: Lecture Notes, Chapter 4, §§18–19.2 (standard reference, not scraped)