Pipeline-generated

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.

Minimax Lower Bounds

1 · Prerequisites

2 · Summary

This page builds finite-sample minimax lower bounds from KL divergence and the event-supremum total-variation convention defined on the stationary Markov-chain page. It defines directional KL and finite uniform-hypothesis mutual information, proves Pinsker’s inequality with the matching factor of $1 / 2$ , and proves finite-product KL additivity under independence. Two-point testing, Fano packing, and Assouad’s hypercube arguments cover arbitrary randomized kernels and reduce squared loss to testing error explicitly. A local Gaussian KL formula and sparse block-code packing supply the calculations used by the companion examples. AC is stated at the Radon–Nikodym and Gaussian-construction steps; the finite testing and coding arguments add no choice. The plan also lists the concentration page as a prerequisite; no concentration inequality is used by these lower-bound proofs.

3 · Logical flowchart

4 · Definitions, theorems and proofs

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

A sparse Hamming packing for every $1 \leq k \leq d / 2$

Statement

Let $d, k$ be natural numbers with $1 \leq k \leq d / 2$ . Let $m$ and $r$ be the natural quotients determined by $m k \leq d < (m + 1) k, 4 r \leq k < 4 (r + 1) .$ Thus $m \geq 2$ . Write $[m] = {0, 1, \dots, m - 1}$ and give $[m]^{k}$ the Hamming distance $d_{H} (ω, ω^{'}) = # {j < k : ω_{j} \neq ω_{j}^{'}}$ . There is a set $C \subseteq [m]^{k}$ such that distinct $ω, ω^{'} \in C$ satisfy $d_{H} (ω, ω^{'}) > r$ and $\log ∣ C ∣ \geq \frac{k}{1024} \log ⁣ (\frac{e d}{k}) .$ For each $ω \in C$ , place one $1$ in each of the first $k$ disjoint coordinate blocks of size $m$ , at position $ω_{j}$ in block $j$ , and put $0$ in all remaining coordinates of $R^{d}$ . The resulting vectors $u^{ω} \in {0, 1}^{d}$ have exactly $k$ nonzero coordinates and satisfy $∥ u^{ω} - u^{ω^{'}} ∥_{2}^{2} > k / 2 (ω \neq ω^{'}) .$

Facts & Assumptions

Given: Natural numbers $1 \leq k \leq d / 2$ and the conventions in the Statement.

[F1]

The naturals embed in the integers gives an order-preserving and order-reflecting arithmetic embedding $ι_{Z} : N \to Z$ whose image is exactly the nonnegative integers. By Discreteness: $σ (n)$ is the immediate successor, a positive integer $x = ι_{Z} (n)$ has $n \geq 1$ , hence $x \geq 1$ . Identify $d, k$ with their integer images. Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ gives integers $q, s, p, t$ with $d = q k + s$ , $0 \leq s < k$ , and $k = 4 p + t$ , $0 \leq t < 4$ . In the ordered ring of The integers form a totally ordered ring, $q < 0$ would imply $q \leq - 1$ , so $d = q k + s \leq - k + s < 0$ , contrary to $d \geq 0$ ; likewise $p < 0$ would imply $k = 4 p + t \leq - 4 + t < 0$ . Thus the quotients and remainders are nonnegative integers. The embedding lemma therefore supplies unique naturals $m, r, s_{0}, t_{0}$ with these integer images, and transfers the identities and inequalities to $d = m k + s_{0}$ , $0 \leq s_{0} < k$ , $k = 4 r + t_{0}$ , and $0 \leq t_{0} < 4$ . The real-embedding bridge in [F2] transfers $k \leq d / 2$ to $2 k \leq d$ in $N$ . If $m = 0$ or $m = 1$ , the first division identity gives $d < k$ or $d < 2 k$ , contradicting $2 k \leq d$ . Thus $m \geq 2$ .

[F2]

The natural numbers $N$ (von Neumann), The cardinality $∣ A ∣$ of a finite set, The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ , Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ , and The binomial theorem in $R$ : $(x + y)^{n} = \sum_{k < n + 1} ι ⁣ (\binom{n}{k}) x^{k} y^{n - k}$ : $[m]^{k}$ is finite with natural cardinality $m^{k}$ , and a finite set admits a bijection with its cardinality. Let $ι_{R} : N \to R$ be the canonical natural embedding used by the binomial theorem and natural-power bridge; Clauses 0, 6, and 7 of Laws of finite sums and products in $N$ , and $ι (\sum_{k < n} a_{k}) = \sum_{k < n} ι (a_{k})$ establish that it preserves addition and multiplication (including zero arguments), carries finite natural sums and products to the corresponding real sums and products, and is an order-embedding. Applying its finite-product bridge to the constant list of $k$ copies of $m$ , with the natural-power definition, gives $ι_{R} (m^{k}) = ι_{R} (m)^{k}$ . Throughout the Statement and proof, a natural number or finite cardinality in a real expression means its image under $ι_{R}$ ; in particular, the displayed logarithmic bound means $\log ι_{R} (∣ C ∣) \geq (ι_{R} (k) / 1024) \log (e ι_{R} (d) / ι_{R} (k))$ .

[F3]

The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ , and The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition: $(\binom{k}{j})$ counts $j$ -element subsets of $[k]$ ; finite products multiply cardinalities and disjoint finite unions add them.

[F4]

The binomial theorem in $R$ : $(x + y)^{n} = \sum_{k < n + 1} ι ⁣ (\binom{n}{k}) x^{k} y^{n - k}$ : for real $q \in [0, 1]$ , the binomial theorem is the real identity $\sum_{j = 0}^{k} ι_{R} ⁣ (\binom{k}{j}) q^{j} (1 - q)^{k - j} = 1$ ; each natural binomial coefficient is carried into $R$ by $ι_{R}$ .

[F5]

The integral logarithm $L (x) : = \int_{1}^{x} \frac{d t}{t}$ for $x > 0$ , The natural logarithm as the inverse of the exponential function, Higher derivatives and the classes $C^{k}$ and $C^{\infty}$ , The integral logarithm satisfies $L^{'} (x) = 1 / x$ for $x > 0$ and $L (1) = 0$ , The integral logarithm satisfies $L (x y) = L (x) + L (y)$ for all positive $x$ and $y$ , Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ , The integral logarithm is continuous and strictly increasing on $(0, \infty)$ , $L (1 / x) = - L (x)$ , $L (x^{n}) = n L (x)$ , and in particular $L (2^{n}) = n L (2)$ , and The integral logarithm $L$ is the published natural logarithm: $\log x = \int_{1}^{x} d t / t$ , it is the inverse of $\exp$ with derivative $1 / x$ , is strictly increasing, its derivative obeys the chain and algebra rules, and it satisfies the product and integer-power identities.

[F6]

The real exponential function and the number $e$ by a power series and The exponential function is strictly increasing: $e = \exp (1) > 1$ because $\exp (0) = 1$ and $\exp$ is strictly increasing; the inverse identity $\exp (\log x) = x$ is recorded in [F5].

Proof

1.1F2givenconstruct

Put $W = [m]^{k}$ and fix a bijection from the finite initial segment of size $m^{k}$ onto $W$ , whose existence is [F2]. Scan that finite segment in its natural order, retaining a word exactly when its Hamming distance from every previously retained word is greater than $r$ . The scan terminates; its retained set $C$ has pairwise distances greater than $r$ , and every word not retained lies in a radius- $r$ ball about an earlier retained word.

1.2F3givenalgebra

A Hamming ball of radius $r$ has cardinality $B = \sum_{j = 0}^{r} (\binom{k}{j}) (m - 1)^{j}$ : choose the $j$ coordinates that differ and then one of the other $m - 1$ symbols at each such coordinate; different values of $j$ give disjoint sets, so [F3] counts the union.

2.1F2F4F5F6step 1.2algebra

Regard natural quantities as their real images under $ι_{R}$ as fixed in [F2]. Since $m \geq 2$ and $j \leq r \leq k / 4$ , $\log (ι_{R} (m) - 1) \geq 0$ , and the natural-power bridge in [F2] and the integer-power identity in [F5] give $ι_{R} ((m - 1)^{j}) = \exp (ι_{R} (j) \log (ι_{R} (m) - 1)) \leq \exp ((ι_{R} (k) / 4) \log (ι_{R} (m) - 1))$ . Put $q = 1 / 4$ and $h = - q \log q - (1 - q) \log (1 - q) = \frac{1}{2} \log 2 + \frac{3}{4} \log (4 / 3)$ . The binomial weight $q^{j} (1 - q)^{k - j}$ equals $\exp (ι_{R} (j) \log q + (ι_{R} (k) - ι_{R} (j)) \log (1 - q))$ ; its exponent decreases with $j$ because $\log q - \log (1 - q) = \log (1 / 3) < 0$ . Hence for every $j \leq r \leq k / 4$ this weight is at least $\exp ((ι_{R} (k) / 4) \log q + (3 ι_{R} (k) / 4) \log (1 - q)) = \exp (- ι_{R} (k) h)$ . Applying [F4] and retaining only $j \leq r$ gives $\sum_{j = 0}^{r} ι_{R} ⁣ (\binom{k}{j}) \leq \exp (ι_{R} (k) h)$ . Since $ι_{R}$ preserves finite sums, products and natural powers, the ball count then satisfies $ι_{R} (B) \leq \exp (ι_{R} (k) h + (ι_{R} (k) / 4) \log (ι_{R} (m) - 1))$ .

3.1step 1.1step 2.1F2F3F5algebra

Each greedy selection deletes at most $B$ words and all $m^{k}$ words are eventually deleted. Thus the natural counts satisfy $∣ C ∣ B \geq m^{k}$ . The code is nonempty and $B \geq 1$ , so after applying $ι_{R}$ all logarithms below have positive arguments; [F2] gives $ι_{R} (∣ C ∣) ι_{R} (B) \geq ι_{R} (m)^{k}$ . Combining this with step 2.1 and the logarithm product and integer-power identities in [F5] yields $\log ι_{R} (∣ C ∣) \geq ι_{R} (k) f (ι_{R} (m))$ , where $f (t) = \log t - \frac{1}{4} \log (t - 1) - h$ for real $t \geq 2$ .

4.1F1F2F5F6step 3.1algebra

If $m = 2$ , then $f (2) = \frac{1}{2} \log 2 - \frac{3}{4} \log (4 / 3) > 1 / 24$ : the lower right-endpoint sum on $[1, 2]$ gives $\log 2 > \frac{1}{2} (2 / 3 + 1 / 2) = 7 / 12$ , while $\log (4 / 3) = \int_{1}^{4 / 3} d t / t < 1 / 3$ . By [F1] and [F2], $ι_{R} (d) / ι_{R} (k) < 3$ and $\log (e ι_{R} (d) / ι_{R} (k)) = 1 + \log (ι_{R} (d) / ι_{R} (k)) < 1 + \log 3 < 3$ , since $\log 3 = \int_{1}^{3} d t / t < 2$ ; also $1 / 24 > 3 / 1024$ . Hence $f (ι_{R} (m)) > \frac{1}{1024} \log (e ι_{R} (d) / ι_{R} (k))$ .

5.1F2F5step 4.1algebra

For real $t \geq 3$ , monotonicity of $\log$ gives $f (3) = \log 3 - \frac{3}{4} \log (8 / 3) > \frac{1}{4} \log 3 > 7 / 48$ , since $3 > 8 / 3$ and step 4.1 gives $\log 3 > \log 2 > 7 / 12$ . The chain and algebra rules in [F5] give $f^{'} (t) = 1 / t - 1 / (4 (t - 1)) \geq 1 / (4 t)$ and $\frac{d}{d t} {(1 / 1024) (1 + \log (4 t / 3))} = 1 / (1024 t)$ , so the derivative of their difference is at least $255 / (1024 t) > 0$ . The mean value theorem in [F5] makes $f (t) - (1 / 1024) (1 + \log (4 t / 3))$ increasing for $t \geq 3$ . At $t = 3$ , it exceeds $7 / 48 - 4 / 1024 > 0$ , since $\log 4 = \int_{1}^{4} d t / t < 3$ . Since $m \geq 3$ , take $t = ι_{R} (m)$ . The division identity gives $ι_{R} (d) / ι_{R} (k) < ι_{R} (m) + 1 \leq 4 ι_{R} (m) / 3$ , so $f (ι_{R} (m)) \geq (1 / 1024) \log (e ι_{R} (d) / ι_{R} (k))$ .

6.1step 1.1step 3.1step 4.1step 5.1F1F2algebra∎

Steps 3.1, 4.1, and 5.1 prove the claimed cardinality bound. Index the coordinates by $[d] = {0, 1, \dots, d - 1}$ and map each word to the vector specified in the Statement; the first $k m$ coordinates contain the $k$ blocks because $k m \leq d$ by [F1]. Each word gives one nonzero coordinate in each block, so $u^{ω}$ has exactly $k$ ones. If two words differ in $s$ blocks, their vectors differ in exactly two coordinates per such block. Since $s > r$ , discreteness of $N$ gives $s \geq r + 1$ , and [F1] gives $k < 4 (r + 1)$ ; after applying the order-preserving map in [F2], $ι_{R} (s) \geq ι_{R} (r) + 1 > ι_{R} (k) / 4$ . Therefore $∥ u^{ω} - u^{ω^{'}} ∥_{2}^{2} = 2 ι_{R} (s) > ι_{R} (k) / 2$ .

Remarks

The cited sparse Varshamov–Gilbert lemma in Rigollet–Hütter is stated for $k \leq d / 8$ . The proof above supplies the wider $k \leq d / 2$ range used by the example through a block code; the source citation is context, not a substitute for this local proof.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Kullback–Leibler divergence

Definition

Let $P, Q$ be probability measures on the same measurable space (Probability measures and probability spaces). Absolute continuity $P ≪ Q$ has the convention of Absolute continuity of a signed or complex measure with respect to a positive measure. If $P ≪̸ Q$ , define $D (P ∥ Q) = + \infty$ . If $P ≪ Q$ , assume AC (The Axiom of Choice) as in Likelihood ratio as a Radon–Nikodym derivative and let $r = d P / d Q$ be a finite-valued nonnegative measurable representative of its Radon–Nikodym class; such a representative exists by A sigma-finite positive measure has a nonnegative Radon–Nikodym density version. On ${r = 0}$ set $ℓ = 0$ , and on ${r > 0}$ set $ℓ = \log r$ . This function is measurable: for $a \geq 0$ , ${ℓ > a} = {r > \exp (a)}$ , and for $a < 0$ , ${ℓ > a} = {r = 0} \cup {r > \exp (a)}$ , by the inverse and monotonicity properties of the natural logarithm (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm). These are measurable sets by Extended-real-valued measurable functions. Since $P ({r = 0}) = \int_{{r = 0}} r d Q = 0$ by Likelihood-ratio change of measure, the value chosen there does not affect $\int ℓ d P$ . Define $D (P ∥ Q) : = \int ℓ d P,$ where $\log$ is the natural logarithm (The natural logarithm as the inverse of the exponential function).

The definition is independent of the representative: two representatives agree $Q$ -almost everywhere, hence $P$ -almost everywhere. Put $ψ (0) : = 0, ψ (t) : = t \log t (t > 0) .$ The function $ψ$ is continuous at zero: for $s \geq 1$ , $0 \leq \frac{\log s}{s} = \frac{1}{s} \int_{1}^{s} \frac{d u}{u} \leq \frac{1}{s} \int_{1}^{s} \frac{d u}{\sqrt{u}} \leq \frac{2}{\sqrt{s}} .$ Thus $t \log t \to 0$ as $t ↓ 0$ ; here $L = \log$ by The integral logarithm $L$ is the published natural logarithm and The integral logarithm $L (x) : = \int_{1}^{x} \frac{d t}{t}$ for $x > 0$ . On $(0, \infty)$ , $ψ$ is a product of continuous functions by Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm and Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function, so $ψ$ is continuous on $[0, \infty)$ and $ψ (r)$ is measurable by Extended-real-valued measurable functions. Its signed integral is defined by the positive and negative parts (The positive and negative parts of a function, The nonnegative Lebesgue integral).

For $0 < t \leq 1$ , the function $- t \log t$ has derivative $- \log t - 1$ and maximum $1 / e$ at $t = 1 / e$ : $e = \exp (1) > 1$ by The real exponential function and the number $e$ by a power series and The exponential function is strictly increasing, $1 / e = \exp (- 1)$ by The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , and $\log (1 / e) = - 1$ by Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm and the inverse definition. The mean value theorem gives increase before and decrease after this point (Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , The integral logarithm satisfies $L^{'} (x) = 1 / x$ for $x > 0$ and $L (1) = 0$ , The integral logarithm $L$ is the published natural logarithm, The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ). At $t = 0$ the negative part is zero. Since $Q$ is a probability measure, $\int ψ (r)^{-} d Q \leq \frac{1}{e} .$ The change-of-measure identity of Likelihood-ratio change of measure, applied to $ℓ^{-}$ gives $\int ℓ^{-} d P = \int ψ (r)^{-} d Q \leq 1 / e$ , so $\int ℓ d P$ is well-defined; applying it to both positive and negative parts gives $D (P ∥ Q) = \int ℓ d P = \int ψ (r) d Q = \int r \log r d Q,$ with $0 \log 0 : = 0$ and a finite negative part. Therefore the extended integral is well-defined without an $\infty - \infty$ ambiguity.

This convention is directional: the first argument must be absolutely continuous with respect to the second for the integral formula to apply.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Mutual information for a finite uniform hypothesis experiment

Definition

Let $M \geq 2$ be an integer, let $P_{1}, \dots, P_{M}$ be probability measures on one measurable sample space, and let $J$ be uniform on $[M] = {1, \dots, M}$ . Conditional on $J = j$ , let the observation $X$ have law $P_{j}$ . Define the mixture law $\overset{ˉ}{P} : = \frac{1}{M} \sum_{j = 1}^{M} P_{j}$ and the mutual information of this finite experiment by $I (J; X) : = \frac{1}{M} \sum_{j = 1}^{M} D (P_{j} ∥ \overset{ˉ}{P}) .$ The set function $\overset{ˉ}{P}$ is a probability measure: for disjoint measurable sets $(A_{m})$ , countable additivity of the $P_{j}$ gives $\overset{ˉ}{P} ⁣ (⋃_{m} A_{m}) = \frac{1}{M} \sum_{j = 1}^{M} \sum_{m} P_{j} (A_{m}) .$ The finite sum commutes with the increasing partial-sum limits of these nonnegative series, so $\frac{1}{M} \sum_{j = 1}^{M} \sum_{m} P_{j} (A_{m}) = \sum_{m} \frac{1}{M} \sum_{j = 1}^{M} P_{j} (A_{m}) = \sum_{m} \overset{ˉ}{P} (A_{m}),$ so $\overset{ˉ}{P}$ is countably additive; also $\overset{ˉ}{P} (\emptyset) = 0$ and $\overset{ˉ}{P} (X) = 1$ . Here $D$ is the directional KL divergence of Kullback–Leibler divergence, and logarithms are natural. For every measurable $A$ , $P_{j} (A) \leq M \overset{ˉ}{P} (A)$ , so $P_{j} ≪ \overset{ˉ}{P}$ . Let $r_{j} = d P_{j} / d \overset{ˉ}{P}$ be a finite-valued nonnegative density representative provided by Kullback–Leibler divergence. If $\overset{ˉ}{P} ({r_{j} > M}) > 0$ , then for some integer $q \geq 1$ the set $E_{q} : = {r_{j} \geq M + 1 / q}$ has positive $\overset{ˉ}{P}$ -measure. The change-of-measure identity Likelihood-ratio change of measure would give $P_{j} (E_{q}) = \int_{E_{q}} r_{j} d \overset{ˉ}{P} \geq (M + 1 / q) \overset{ˉ}{P} (E_{q}) > M \overset{ˉ}{P} (E_{q}),$ contradicting $P_{j} (E_{q}) \leq M \overset{ˉ}{P} (E_{q})$ . Hence $r_{j} \leq M$ almost everywhere. The densities also satisfy $M^{- 1} \sum_{j = 1}^{M} r_{j} = 1$ $\overset{ˉ}{P}$ -almost everywhere: for each measurable $A$ , $\overset{ˉ}{P} (A) = \frac{1}{M} \sum_{j = 1}^{M} P_{j} (A) = \int_{A} \frac{1}{M} \sum_{j = 1}^{M} r_{j} d \overset{ˉ}{P},$ so $M^{- 1} \sum_{j} r_{j}$ and the constant function $1$ are both densities of $\overset{ˉ}{P}$ with respect to itself. They agree almost everywhere by A sigma-finite signed measure that is absolutely continuous with respect to a sigma-finite positive measure has a unique almost-everywhere density. For $0 \leq t \leq M$ , the positive part of $t \log t$ is at most $M \log M$ , while its negative part is bounded by $1 / e$ in Kullback–Leibler divergence. Thus every term in the finite sum is well-defined and finite.

The uniform prior is part of this definition. A nonuniform prior requires its own weights in the mixture and in the KL average.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Pinsker’s inequality with event-supremum total variation

Statement

Assume AC. For probability measures $P, Q$ on one measurable space, with $∥ P - Q ∥_{T V} : = \sup_{A} ∣ P (A) - Q (A) ∣,$ the event-supremum convention without a factor $1 / 2$ , $∥ P - Q ∥_{T V} \leq \sqrt{\frac{1}{2} D (P ∥ Q)} .$ If $P ≪̸ Q$ , the right side is $+ \infty$ by the definition of KL divergence.

Facts & Assumptions

Given: AC and probability measures $P, Q$ on the same measurable space.

[A1]

The Axiom of Choice: AC supplies the Radon–Nikodym construction used by the KL divergence.

[F1]

Kullback–Leibler divergence and Likelihood-ratio change of measure: if $P ≪̸ Q$ , then $D (P ∥ Q) = + \infty$ ; if $P ≪ Q$ with $r = d P / d Q$ , then $P (B) = \int_{B} r d Q$ for every measurable $B$ , so $\int r d Q = 1$ , and $D (P ∥ Q) = \int r \log r d Q$ with $0 \log 0 = 0$ and finite negative part.

[F2]

Total variation distance for probability laws: $∥ P - Q ∥_{T V} = \sup_{A} ∣ P (A) - Q (A) ∣ \in [0, 1]$ ; this convention has no factor $1 / 2$ .

[F3]

Jensen's integral inequality for a probability measure: for a probability measure, an integrable real function $f$ , and convex $φ$ with $φ \circ f$ integrable, $φ (\int f) \leq \int φ (f)$ .

[F4]

The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, Higher derivatives and the classes $C^{k}$ and $C^{\infty}$ , The integral logarithm satisfies $L^{'} (x) = 1 / x$ for $x > 0$ and $L (1) = 0$ , The integral logarithm $L$ is the published natural logarithm, Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , and The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : the identity $L = \log$ transfers $L^{'} (x) = 1 / x$ to $\log^{'} (x) = 1 / x$ ; products and compositions obey the derivative rules; and the mean value theorem applies on closed subintervals of $(0, 1)$ . Also $t \log t \to 0$ as $t ↓ 0$ : for $s \geq 1$ , $0 \leq \log (s) / s \leq 2 / \sqrt{s}$ using $\log s = \int_{1}^{s} d u / u$ and $1 / u \leq 1 / \sqrt{u}$ .

Proof

1.1A1F1F3F4given

If $P ≪̸ Q$ or $D (P ∥ Q) = + \infty$ , the inequality is immediate. Otherwise let $r = d P / d Q$ and $φ (t) = t \log t$ for $t > 0$ , with $φ (0) = 0$ . By [F4] and the product rule, $φ^{''} (t) = 1 / t > 0$ for $t > 0$ . The mean value theorem in [F4] makes $φ^{'}$ increasing and hence $φ$ convex on $(0, \infty)$ . The limit in [F4] makes this extension continuous at zero, so $φ$ is convex on $[0, \infty)$ . Since $D (P ∥ Q)$ is finite and its negative part is bounded by [F1], $φ (r)$ is $Q$ -integrable. Jensen [F3] and $\int r d Q = 1$ give $D (P ∥ Q) = \int φ (r) d Q \geq φ (1) = 0$ .

2.1A1F1F3givenstep 1.1algebra

Fix a measurable event $A$ , and put $a = P (A)$ , $b = Q (A)$ . If $b \in {0, 1}$ , absolute continuity gives $a = b$ , so step 1.1 yields $D (P ∥ Q) \geq k (a, b) = 0$ . If $0 < b < 1$ , normalize $Q$ on $A$ and on $A^{c}$ . Their averages of $r$ are $a / b$ and $(1 - a) / (1 - b)$ . Applying [F3] on each normalized probability space and adding yields $D (P ∥ Q) \geq a \log \frac{a}{b} + (1 - a) \log \frac{1 - a}{1 - b} = : k (a, b),$ with $0 \log 0 = 0$ by continuity.

3.1F4step 2.1algebra

For fixed $0 < b < 1$ , define $g (a) = k (a, b) - 2 (a - b)^{2}$ on $[0, 1]$ . Differentiating by [F4] gives $g^{''} (a) = \frac{1}{a (1 - a)} - 4 = \frac{(2 a - 1)^{2}}{a (1 - a)} \geq 0$ on $(0, 1)$ . For $a, b \in (0, 1)$ with $a > b$ , the mean value theorem applied to $g^{'}$ on $[b, a]$ shows $g^{'} (a) \geq g^{'} (b) = 0$ , and applied to $g$ on $[b, a]$ shows $g (a) \geq g (b) = 0$ . For $a, b \in (0, 1)$ with $a < b$ , the same two applications on $[a, b]$ show $g^{'} (a) \leq g^{'} (b) = 0$ and $g (a) \geq g (b) = 0$ . The limit in [F4] makes $g$ continuous at $a = 0, 1$ , so the inequality extends to those endpoints. If $b = 0$ or $b = 1$ , absolute continuity gives $a = b$ and equality. Thus $k (a, b) \geq 2 (a - b)^{2}$ in every case.

4.1F2step 2.1step 3.1algebra∎

Combining steps 2.1 and 3.1 gives $D (P ∥ Q) \geq 2 ∣ P (A) - Q (A) ∣^{2}$ for every measurable $A$ . Since the square is increasing on $[0, 1]$ , its supremum is the square of the supremum; using [F2] yields $D (P ∥ Q) \geq 2 ∥ P - Q ∥_{T V}^{2}$ , which is the claimed inequality.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Additivity of KL divergence for finite product laws

Statement

Assume AC. Let $n \in N$ with $n \geq 1$ . For each $i < n$ , let $(X_{i}, A_{i})$ be a measurable space and let $P_{i}, Q_{i}$ be probability measures on it. On the finite product measurable space set $P = ⨂_{i < n} P_{i}, Q = ⨂_{i < n} Q_{i} .$ With the KL convention of Kullback–Leibler divergence, $D (P ∥ Q) = \sum_{i < n} D (P_{i} ∥ Q_{i}),$ where a sum with an infinite term is $+ \infty$ .

Facts & Assumptions

Given: AC, a natural number $n \geq 1$ , measurable spaces $(X_{i}, A_{i})$ for $i < n$ , probability laws $P_{i}, Q_{i}$ , and their finite product measures $P, Q$ .

[A1]

The Axiom of Choice: AC is assumed by the Radon–Nikodym suppliers in the KL definition.

[F1]

Kullback–Leibler divergence and The Radon-Nikodym derivative as an almost-everywhere equivalence class: if $P_{i} ≪ Q_{i}$ , its density is an almost-everywhere class $r_{i}$ satisfying $P_{i} (A) = \int_{A} r_{i} d Q_{i}$ , and $D (P_{i} ∥ Q_{i}) = \int \log r_{i} d P_{i}$ ; the negative part is finite.

[F2]

The product sigma-algebra and its finite iterates and The product measure of two sigma-finite measure spaces: finite products use the iterated product sigma-algebra and product measures whose rectangle values are the products of factor measures.

[F3]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique and Measures agreeing on a generating pi-system are equal under an increasing finite-measure exhaustion from that pi-system: product measures have the rectangle formula and are determined by it on the generating rectangles.

[F4]

The measure with density $f$ relative to $μ$ and The indefinite integral of a nonnegative measurable function is a measure: a nonnegative measurable density $r$ defines the measure $r d Q$ by $(r d Q) (E) = \int_{E} r d Q$ .

[F5]

Tonelli's theorem for nonnegative measurable functions on a sigma-finite product and Fubini's theorem for L^1 functions on a sigma-finite product: nonnegative product integrals factor by Tonelli, and integrable product functions may be integrated sectionwise by Fubini.

[F6]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: for positive $x_{1}, \dots, x_{n}$ , $\log (\prod_{i} x_{i}) = \sum_{i} \log x_{i}$ .

Proof

1.1A1F2F3given

If $P_{i} ≪̸ Q_{i}$ for some $i < n$ , choose $A_{i} \in A_{i}$ with $Q_{i} (A_{i}) = 0 < P_{i} (A_{i})$ . Let $E = \prod_{j < n} E_{j}$ , where $E_{i} = A_{i}$ and $E_{j} = X_{j}$ for $j \neq i$ . The product rectangle has $Q (E) = 0$ and $P (E) = P_{i} (A_{i}) > 0$ by [F2, F3]. Hence $P ≪̸ Q$ , so the left side is $+ \infty$ ; the corresponding term on the right is also $+ \infty$ and the equality holds.

1.2A1F1F2F3F5given

Now suppose $P_{i} ≪ Q_{i}$ for every $i < n$ , and choose nonnegative representatives $r_{i} = d P_{i} / d Q_{i}$ . Define $r (x_{0}, \dots, x_{n - 1}) = \prod_{i < n} r_{i} (x_{i})$ . Each coordinate function $x \mapsto r_{i} (x_{i})$ is measurable by the finite product sigma-algebra definition: its level-set preimages are measurable rectangles. Hence the vector of coordinate values is measurable, since rectangles generate the Borel sigma-algebra of $R^{n}$ ; composing with the continuous multiplication map gives measurable $r$ . Repeated Tonelli and the rectangle formulas give $\int_{E} r d Q = \prod_{i < n} \int_{A_{i}} r_{i} d Q_{i} = \prod_{i < n} P_{i} (A_{i}) = P (E)$ for every measurable rectangle $E = \prod_{i < n} A_{i}$ ; applying the same calculation to the full space gives $\int r d Q = 1$ .

2.1A1F3F4step 1.2

The measure $r d Q$ is a probability measure by [F4] and step 1.2. The product rectangles form a generating pi-system and the finite product spaces are sigma-finite, so [F3] and the rectangle identity in step 1.2 imply $r d Q = P$ on the entire product sigma-algebra. Therefore $r = d P / d Q$ as a Radon–Nikodym class.

3.1A1F1F5F6step 2.1algebra∎

Each $r_{i}$ is finite $Q_{i}$ -almost everywhere because $\int r_{i} d Q_{i} = 1$ , and $P_{i} ({r_{i} = 0}) = \int_{{r_{i} = 0}} r_{i} d Q_{i} = 0$ ; thus $0 < r_{i} < \infty$ $P_{i}$ -almost everywhere. Therefore [F6] gives $\log r = \sum_{i < n} \log r_{i} (x_{i})$ $P$ -almost everywhere. Each $\log r_{i}$ has integrable negative part by [F1], and the negative part of their finite sum is bounded by the sum of those negative parts. Split each summand into positive and negative parts: Tonelli factors each nonnegative part through the product law, and Fubini applies to the negative parts, which are integrable. Hence, allowing $+ \infty$ for positive parts, $\int \log r d P = \sum_{i < n} \int \log r_{i} d P_{i} = \sum_{i < n} D (P_{i} ∥ Q_{i}) .$ By [F1] and step 2.1 the left side is $D (P ∥ Q)$ , proving the claim.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

KL divergence between equal-variance Gaussian location laws

Statement

Assume AC and let $a, b \in R$ and $τ > 0$ . For the normal location laws with common variance $τ^{2}$ , $D (N (a, τ^{2}) ∥ N (b, τ^{2})) = \frac{(a - b)^{2}}{2 τ^{2}} .$

Facts & Assumptions

Given: AC, real means $a, b$ , and a positive scale $τ$ .

[A1]

The Axiom of Choice: AC supplies the normal-law construction and the Radon–Nikodym assumptions used by the KL definition.

[F1]

Standard normal and normal laws: $N (a, τ^{2})$ is the law of $a + τ Z$ when $Z$ has standard normal law, whose density is $ϕ (z) = (2 π)^{- 1 / 2} e^{- z^{2} / 2}$ .

[F2]

The standard normal density has total mass one: $ϕ$ is a probability density on $R$ .

[F3]

AC supplies countable selections and prescribed serial paths: AC supplies countable choice, the axiom required by the change-of-variables supplier.

[F4]

A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions: for a $C^{1}$ diffeomorphism $T$ and nonnegative measurable $g$ , $\int g (y) d y = \int g (T (x)) ∣ T^{'} (x) ∣ d x$ .

[F5]

Integrating against a density agrees with integrating the product: $\int g d (f d μ) = \int g f d μ$ for nonnegative measurable $f, g$ .

[F6]

The natural logarithm as the inverse of the exponential function: the natural logarithm is the inverse of the real exponential, so $\log (\exp y) = y$ . For positive $u, v$ , $\log (u / v) = \log u - \log v$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F7]

Multivariate normal law, including singular covariance: a normal law with mean $a$ has expectation $a$ ; in dimension one this is the scalar law $N (a, τ^{2})$ .

[F8]

Kullback–Leibler divergence: for $P ≪ Q$ , $D (P ∥ Q) = \int \log (d P / d Q) d P$ .

Proof

1.1A1F1F2F3F4F5givenconstruct

Set $p_{a} (x) = \frac{1}{τ \sqrt{2 π}} \exp (- \frac{(x - a)^{2}}{2 τ^{2}})$ . Apply [F4] to $g p_{a}$ with $T (z) = a + τ z$ ; since $τ p_{a} (a + τ z) = ϕ (z)$ by [F1], for every nonnegative Borel $g$ , $\int g (x) p_{a} (x) d x = \int g (a + τ z) ϕ (z) d z .$ Thus $N (a, τ^{2})$ has Lebesgue density $p_{a}$ ; the same calculation gives $p_{b}$ for $N (b, τ^{2})$ . Both are strictly positive. Let $r = p_{a} / p_{b}$ . By [F5], $\int_{E} r d N (b, τ^{2}) = \int_{E} p_{a} d x = N (a, τ^{2}) (E)$ for every Borel set $E$ , so $r = d N (a, τ^{2}) / d N (b, τ^{2})$ .

1.2F1F6F7algebra

For every $x$ , cancel the common positive prefactor of $p_{a}$ and $p_{b}$ and apply the quotient law and inverse identity in [F6] to obtain $\log \frac{p_{a} (x)}{p_{b} (x)} = \frac{(x - b)^{2} - (x - a)^{2}}{2 τ^{2}} = \frac{(a - b) (2 x - a - b)}{2 τ^{2}} .$ This affine function is integrable under $N (a, τ^{2})$ , whose mean is $a$ by [F7].

2.1A1F8step 1.2algebra∎

By [F8] and step 1.2, $D (N (a, τ^{2}) ∥ N (b, τ^{2})) = \int \frac{(a - b) (2 x - a - b)}{2 τ^{2}} N (a, τ^{2}) (d x) = \frac{(a - b) (2 a - a - b)}{2 τ^{2}} = \frac{(a - b)^{2}}{2 τ^{2}} .$ The identity also covers $a = b$ , when both sides are zero.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Two-point Le Cam lower bound for squared-error risk

Statement

Let an experiment have parameter set ${0, 1}$ , sample space $(X, A)$ , and laws $P_{0}, P_{1}$ . Let the scalar targets satisfy $t_{0} < t_{1}$ and put $Δ = t_{1} - t_{0} > 0$ . An arbitrary randomized estimator is a probability kernel $K$ from $X$ to $R$ with its Borel sigma-algebra, and its loss at parameter $j$ is squared error $(a - t_{j})^{2}$ . For every such $K$ , $\max_{j \in {0, 1}} R_{j} (K) \geq \frac{Δ^{2}}{8} (1 - ∥ P_{0} - P_{1} ∥_{T V}),$ where $∥ P_{0} - P_{1} ∥_{T V} = \sup_{A \in A} ∣ P_{0} (A) - P_{1} (A) ∣$ . Consequently the minimax risk over all randomized estimators obeys the same lower bound.

Facts & Assumptions

Given: The finite-parameter statistical experiment with laws $P_{0}, P_{1}$ , targets $t_{0} < t_{1}$ , and an arbitrary randomized estimator kernel $K$ .

[F1]

Statistical experiments and Parameter-measurable statistical models as kernels: the parameter set ${0, 1}$ has its power-set sigma-algebra and its model assigns the sample law $P_{j}$ to parameter $j$ .

[F2]

Randomized procedures as probability kernels: for every measurable action event $B \subseteq R$ , $x \mapsto K (x, B)$ is measurable and is a probability measure in $B$ for fixed $x$ .

[F3]

Loss functions and risk: for a nonnegative jointly measurable loss $L (j, a)$ , the risk is $R_{j} (K) = \int_{X} \int_{R} L (j, a) K (x, d a) P_{j} (d x)$ , with an extended nonnegative value allowed.

[F4]

Total variation distance for probability laws: with the event-supremum convention, $∥ P_{0} - P_{1} ∥_{T V} = \sup_{A \in A} ∣ P_{0} (A) - P_{1} (A) ∣$ .

[F5]

Bayes risk and minimax risk: the maximum risk of a procedure is $\max_{j \in {0, 1}} R_{j} (K)$ and minimax risk is the infimum of this maximum over all procedures.

Proof

1.1F1F2F3givenalgebra

Put $c = (t_{0} + t_{1}) / 2$ and define the randomized test $ϕ (x) = K (x, [c, \infty))$ . It is measurable and lies in $[0, 1]$ by [F2]. Under parameter $0$ , every action in $[c, \infty)$ has squared error at least $Δ^{2} / 4$ ; under parameter $1$ , every action in $(- \infty, c)$ has squared error at least $Δ^{2} / 4$ . Hence $R_{0} (K) + R_{1} (K) \geq \frac{Δ^{2}}{4} (\int ϕ d P_{0} + \int (1 - ϕ) d P_{1}) .$

2.1F4F5step 1.1algebra∎

For each integer $N \geq 1$ , let $ϕ_{N} = N^{- 1} \sum_{r = 1}^{N} 1_{{ϕ \geq r / N}}$ . Then $0 \leq ϕ - ϕ_{N} \leq 1 / N$ . By [F4], each event term satisfies $P_{0} (ϕ \geq r / N) - P_{1} (ϕ \geq r / N) \geq - ∥ P_{0} - P_{1} ∥_{T V}$ , so $\int ϕ_{N} d P_{0} - \int ϕ_{N} d P_{1} \geq - ∥ P_{0} - P_{1} ∥_{T V}$ . The two integral errors from replacing $ϕ$ by $ϕ_{N}$ have total absolute value at most $2 / N$ ; letting $N \to \infty$ gives $\int ϕ d P_{0} + \int (1 - ϕ) d P_{1} \geq 1 - ∥ P_{0} - P_{1} ∥_{T V} .$ Combining with step 1.1 and using $\max (R_{0}, R_{1}) \geq (R_{0} + R_{1}) / 2$ proves the risk bound. Taking the infimum over $K$ and applying [F5] proves the minimax assertion.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Assouad lower bound for a squared-error hypercube

Statement

Let $d \geq 1$ , $a > 0$ , and consider the finite experiment indexed by $ω \in {0, 1}^{d}$ with sample laws $P_{ω}$ . The target is $t_{ω} = a ω \in R^{d}$ , the action is in $R^{d}$ , and loss is squared Euclidean distance. For each coordinate $i$ , let $ω^{(i)}$ denote the vector with bit $i$ flipped, and set $v : = \max_{ω \in {0, 1}^{d}, 1 \leq i \leq d} ∥ P_{ω} - P_{ω^{(i)}} ∥_{T V} .$ For every randomized estimator kernel $K$ , $\max_{ω} R_{ω} (K) \geq \frac{a^{2} d}{8} (1 - v),$ and the same lower bound holds for the minimax risk. The total variation convention is $∥ P - Q ∥_{T V} = \sup_{A} ∣ P (A) - Q (A) ∣$ .

Facts & Assumptions

Given: A positive integer $d$ , a number $a > 0$ , the finite hypercube experiment, and an arbitrary randomized action kernel $K$ .

[F1]

Statistical experiments and Parameter-measurable statistical models as kernels: the parameter set ${0, 1}^{d}$ is finite with its power-set sigma-algebra and the model assigns $P_{ω}$ to $ω$ .

[F2]

Randomized procedures as probability kernels: action-event probabilities $x \mapsto K (x, B)$ are measurable, and each $K (x, \cdot)$ is a probability measure.

[F3]

Loss functions and risk: the squared-error risk is the nonnegative kernel integral $R_{ω} (K) = \int \int ∥ z - a ω ∥_{2}^{2} K (x, d z) P_{ω} (d x)$ .

[F4]

Total variation distance for probability laws: total variation is the event supremum $\sup_{A} ∣ P (A) - Q (A) ∣$ and lies in $[0, 1]$ .

[F5]

Bayes risk and minimax risk: minimax risk is the infimum over procedures of the supremum of their risks.

Proof

1.1F1F2F3givenalgebra

For each coordinate $i$ , define $ϕ_{i} (x) = K (x, {z \in R^{d} : z_{i} \geq a / 2})$ . This is a measurable $[0, 1]$ -valued function by [F2]. If the true bit is $0$ , an action counted by $ϕ_{i}$ has coordinate squared error at least $a^{2} / 4$ ; if the true bit is $1$ , an action outside that event has coordinate squared error at least $a^{2} / 4$ . Thus $R_{ω} (K) \geq \frac{a^{2}}{4} \sum_{i = 1}^{d} [(1 - ω_{i}) P_{ω} ϕ_{i} + ω_{i} P_{ω} (1 - ϕ_{i})],$ where $P f : = \int f d P$ .

2.1F4step 1.1algebra

For any two probability laws $P, Q$ and measurable $ϕ : X \to [0, 1]$ , the finite approximants $ϕ_{N} = N^{- 1} \sum_{r = 1}^{N} 1_{{ϕ \geq r / N}}$ satisfy $0 \leq ϕ - ϕ_{N} \leq 1 / N$ . By [F4], $\int ϕ_{N} d P - \int ϕ_{N} d Q \leq ∥ P - Q ∥_{T V}$ , and the replacement error is at most $2 / N$ . Letting $N \to \infty$ gives $\int ϕ d P - \int ϕ d Q \leq ∥ P - Q ∥_{T V}$ . Applying the same result to $1 - ϕ$ gives $P ϕ + Q (1 - ϕ) \geq 1 - ∥ P - Q ∥_{T V} .$ For each coordinate, pair every hypercube vertex with bit $i = 0$ to the unique neighbor with bit $i = 1$ . There are $2^{d - 1}$ such pairs, and each pair's two testing errors in step 1.1 sum to at least $1 - v$ . Averaging over all $2^{d}$ vertices therefore gives average coordinate error at least $(1 - v) / 2$ . This establishes the coordinate error bound.

3.1F5step 1.1step 2.1algebra∎

Average the risk bound in step 1.1 over the $2^{d}$ vertices. Step 2.1 shows that the average risk is at least $a^{2} d (1 - v) / 8$ . The supremum of finitely many risks is at least their arithmetic mean, so every $K$ has maximum risk at least this amount. Taking the infimum over procedures using [F5] proves the minimax bound.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Fano’s packing bound with a reference-distribution KL bound

Statement

Assume AC. Let $M \geq 2$ be finite, let $P_{1}, \dots, P_{M}$ be sample laws on one measurable space, and let $t_{1}, \dots, t_{M}$ lie in a metric space $(T, ρ)$ with its Borel sigma-algebra. Suppose $ρ (t_{j}, t_{l}) \geq Δ > 0$ whenever $j \neq l$ . Let $J$ be uniform on $[M] = {1, \dots, M}$ , with conditional observation law $P_{j}$ given $J = j$ . For any probability reference law $Q$ , define $K_{Q} : = \frac{1}{M} \sum_{j = 1}^{M} D (P_{j} ∥ Q) \in [0, + \infty] .$ For every randomized estimator kernel from the observation to $T$ , with squared metric loss $ρ (a, t_{j})^{2}$ , its uniform average risk and its maximum risk are each at least $\frac{Δ^{2}}{4} (1 - \frac{K_{Q} + \log 2}{\log M}) .$ The minimax risk over all randomized estimators obeys this bound as well. When $K_{Q} = + \infty$ , the displayed lower bound is interpreted as $- \infty$ and is vacuous. Logarithms are natural.

Facts & Assumptions

Given: AC; a finite uniform hypothesis experiment, pairwise separated targets, a probability reference law $Q$ , and an arbitrary estimator kernel.

[A1]

The Axiom of Choice: AC supplies the Radon–Nikodym derivatives in the directional KL definition.

[F1]

Mutual information for a finite uniform hypothesis experiment: for the uniform index, $\overset{ˉ}{P} = M^{- 1} \sum_{j} P_{j}$ is a probability measure, $P_{j} ≪ \overset{ˉ}{P}$ , the densities $p_{j} = d P_{j} / d \overset{ˉ}{P}$ satisfy $0 \leq p_{j} / M \leq 1$ and $\sum_{j} p_{j} / M = 1$ almost everywhere, and $I (J; X) = M^{- 1} \sum_{j} D (P_{j} ∥ \overset{ˉ}{P})$ .

[F2]

Kullback–Leibler divergence, The Radon-Nikodym derivative as an almost-everywhere equivalence class, and Likelihood-ratio change of measure: when $P ≪ Q$ , $D (P ∥ Q) = \int (d P / d Q) \log (d P / d Q) d Q$ with $0 \log 0 = 0$ ; otherwise it is $+ \infty$ . The negative part of $u \log u$ is pointwise bounded by $1 / e$ , so its integral under any probability reference law is at most $1 / e$ . Densities can be integrated against their reference laws to recover the original measures.

[F3]

The natural logarithm as the inverse of the exponential function, The integral logarithm $L (x) : = \int_{1}^{x} \frac{d t}{t}$ for $x > 0$ , The integral logarithm $L$ is the published natural logarithm, Higher derivatives and the classes $C^{k}$ and $C^{\infty}$ , Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The integral logarithm satisfies $L^{'} (x) = 1 / x$ for $x > 0$ and $L (1) = 0$ , Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ , The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ , and Jensen's integral inequality for a probability measure: $L = \log$ transfers $L^{'} (x) = 1 / x$ to $\log^{'} (x) = 1 / x$ ; products and compositions obey the derivative rules; and Jensen's inequality applies to an integrable convex transform. The function $ψ (u) = u \log u$ for $u > 0$ , extended by $ψ (0) = 0$ , is continuous at zero: for $s \geq 1$ , $0 \leq \log (s) / s \leq 2 / \sqrt{s}$ by $\log s = \int_{1}^{s} d u / u$ and $1 / u \leq 1 / \sqrt{u}$ . Since $ψ^{''} (u) = 1 / u > 0$ for $u > 0$ , the mean value theorem makes it convex on $(0, \infty)$ ; continuity extends convexity to $[0, \infty)$ .

[F4]

Probability measures and probability spaces and The cardinality $∣ A ∣$ of a finite set: finite probability vectors have entropy $H (q) = - \sum_{j} q_{j} \log q_{j}$ , with $0 \log 0 = 0$ .

[F5]

Randomized procedures as probability kernels: the estimator's action probabilities are measurable in the observation and form a probability measure for each observation.

[F6]

Loss functions and risk: a nonnegative loss with a measurable action section at each parameter has risk given by its iterated integral against the sample law and action kernel. Here each section $a \mapsto ρ (a, t_{j})^{2}$ is continuous, hence Borel measurable.

[F7]

Parameter-measurable statistical models as kernels and Bayes risk and minimax risk: give the finite parameter set $[M]$ its power-set sigma-algebra. The model $j \mapsto P_{j}$ is then a probability kernel. The squared metric loss is jointly measurable: the inverse image of any Borel set $B \subseteq [0, \infty]$ is the finite union $⋃_{j = 1}^{M} {j} \times {a : ρ (a, t_{j})^{2} \in B}$ . Thus the uniform average risk is a Bayes risk, and minimax risk is the infimum of maximum risk over procedures.

Proof

1.1A1F1F2F3F4givenalgebra

Since $\overset{ˉ}{P} \geq P_{j} / M$ , each $P_{j} ≪ \overset{ˉ}{P}$ . Choose densities $p_{j} = d P_{j} / d \overset{ˉ}{P}$ and set $π_{j} = p_{j} / M$ . Then $\sum_{j} π_{j} = 1$ $\overset{ˉ}{P}$ -almost everywhere and $0 \leq π_{j} \leq 1$ by [F1]. The mutual-information definition [F1] and KL formula [F2] give $I (J; X) = \int \sum_{j} π_{j} \log (M π_{j}) d \overset{ˉ}{P} = \log M - \int H (π (x)) \overset{ˉ}{P} (d x) .$ All terms are integrable because $u \log u$ is bounded on $[0, 1]$ and the sum is finite.

2.1F1F3F4F5step 1.1algebra

Let $L$ be any randomized decision in $[M]$ based on $X$ , with $q_{l} (x) = P (L = l ∣ X = x)$ given by its probability kernel. Put $w_{l} = \int q_{l} d \overset{ˉ}{P}$ . When $w_{l} > 0$ , the conditional probability vector of $J$ given $L = l$ has entries $η_{l j} = w_{l}^{- 1} \int q_{l} (x) π_{j} (x) \overset{ˉ}{P} (d x)$ . Apply Jensen to $u \mapsto u \log u$ for each coordinate under the probability measure $q_{l} d \overset{ˉ}{P} / w_{l}$ , sum over $j$ , and use $\sum_{j} π_{j} = \sum_{j} η_{l j} = 1$ . The result is $H (η_{l}) \geq w_{l}^{- 1} \int q_{l} (x) H (π (x)) \overset{ˉ}{P} (d x)$ . Multiplication by $w_{l}$ and summation over positive $w_{l}$ yields $H (J ∣ L) : = \sum_{l} w_{l} H (η_{l}) \geq \int H (π (x)) d \overset{ˉ}{P}$ ; zero-probability outputs contribute zero. Hence $\log M - H (J ∣ L) \leq I (J; X)$ by step 1.1.

2.2A1F1F2F3step 1.1algebra

If some $P_{j} ≪̸ Q$ , then $K_{Q} = + \infty$ and the bound is vacuous. Otherwise write $r_{j} = d P_{j} / d Q$ . If the positive part of $r_{j} \log r_{j}$ has infinite integral, then $D (P_{j} ∥ Q) = + \infty$ ; if it is finite, the negative part is finite by [F2] and Jensen [F3] for the convex function $u \log u$ gives $D (P_{j} ∥ Q) = \int r_{j} \log r_{j} d Q \geq 0$ . Thus every divergence is nonnegative; therefore $K_{Q} < \infty$ implies that every term is finite. Set $\overset{ˉ}{r} = M^{- 1} \sum_{j} r_{j} = d \overset{ˉ}{P} / d Q$ . On ${\overset{ˉ}{r} > 0}$ , $r_{j} = M \overset{ˉ}{r} π_{j}$ $Q$ -almost everywhere: by [F2], for every measurable $A$ , $P_{j} (A) = \int_{A} p_{j} d \overset{ˉ}{P} = \int_{A} p_{j} \overset{ˉ}{r} d Q$ , where $p_{j} = d P_{j} / d \overset{ˉ}{P} = M π_{j}$ from step 1.1; uniqueness of the density gives the identity. Hence $r_{j} \log (r_{j} / \overset{ˉ}{r}) = \overset{ˉ}{r} ψ (M π_{j})$ . This is integrable: $M π_{j} \in [0, M]$ , $∣ u \log u ∣ \leq 1 / e$ for $0 \leq u \leq 1$ by [F2], and $0 \leq u \log u \leq M \log M$ for $1 \leq u \leq M$ by monotonicity in [F3], while $\overset{ˉ}{r}$ has integral one. The identity $r_{j} \log r_{j} = r_{j} \log (r_{j} / \overset{ˉ}{r}) + r_{j} \log \overset{ˉ}{r}$ holds on ${\overset{ˉ}{r} > 0}$ ; on ${\overset{ˉ}{r} = 0}$ all $r_{j} = 0$ and every term is set to zero. Jensen and [F3] give $\overset{ˉ}{r} \log \overset{ˉ}{r} \leq M^{- 1} \sum_{j} r_{j} \log r_{j}$ , so its positive part is integrable; its negative part is bounded by [F2]. Integrating the identity and averaging therefore gives $K_{Q} = I (J; X) + D (\overset{ˉ}{P} ∥ Q) .$ Finally Jensen under the probability law $Q$ yields $D (\overset{ˉ}{P} ∥ Q) = \int \overset{ˉ}{r} \log \overset{ˉ}{r} d Q \geq (\int \overset{ˉ}{r} d Q) \log (\int \overset{ˉ}{r} d Q) = 0$ . Therefore $I (J; X) \leq K_{Q}$ .

3.1F3F4step 2.1step 2.2algebra

For the error event $E = {L \neq J}$ , $E$ is determined by $(J, L)$ , so $H (E, J ∣ L) = H (J ∣ L)$ . Expanding the finite conditional entropy sums and factoring $P (E = e, J = j ∣ L = l) = P (E = e ∣ L = l) P (J = j ∣ E = e, L = l)$ gives $H (J ∣ L) = H (E ∣ L) + H (J ∣ E, L) .$ For each conditional law, entropy on at most $N$ points is at most $\log N$ : if its probabilities are $s_{1}, \dots, s_{N}$ , Jensen for $u \log u$ gives $N^{- 1} \sum_{r} (N s_{r}) \log (N s_{r}) \geq 0$ , which rearranges to $- \sum_{r} s_{r} \log s_{r} \leq \log N$ . Thus $H (E ∣ L) \leq \log 2$ ; when $E = 0$ , $J = L$ has entropy zero, and when $E = 1$ , at most $M - 1$ indices remain, so $H (J ∣ E, L) \leq P (E = 1) \log (M - 1) \leq P (E = 1) \log M$ . Combining this with step 2.1 and $I (J; X) \leq K_{Q}$ from step 2.2 proves $P (L \neq J) \geq 1 - \frac{K_{Q} + \log 2}{\log M}$ when $K_{Q} < \infty$ ; for $K_{Q} = \infty$ the bound is vacuous.

4.1F5F6F7step 2.1step 3.1algebra∎

Given an estimator action $A \in T$ , choose $L$ to be the smallest index minimizing $ρ (A, t_{l})$ . This is a measurable finite-valued decision because each distance to a fixed target is continuous and ties are resolved by the fixed index order; composing the map with the estimator kernel gives the randomized decision kernel of step 2.1 by [F5]. If $L \neq J = j$ , nearest choice and the triangle inequality give $Δ \leq ρ (t_{j}, t_{L}) \leq ρ (t_{j}, A) + ρ (A, t_{L}) \leq 2 ρ (A, t_{j})$ , so squared loss is at least $Δ^{2} / 4$ on the error event. Step 3.1 therefore gives the average risk bound. The maximum risk is at least its uniform average; taking the infimum over procedures using [F6] and [F7] gives the minimax conclusion.

5 · Examples, counterexamples and false statements

None yet.

Minimax Lower Bounds

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

A sparse Hamming packing for every 1≤k≤d/21≤k≤d/2

Statement

Facts & Assumptions

Proof

Remarks

Kullback–Leibler divergence

Definition

Mutual information for a finite uniform hypothesis experiment

Definition

Pinsker’s inequality with event-supremum total variation

Statement

Facts & Assumptions

Proof

Additivity of KL divergence for finite product laws

Statement

Facts & Assumptions

Proof

KL divergence between equal-variance Gaussian location laws

Statement

Facts & Assumptions

Proof

Two-point Le Cam lower bound for squared-error risk

Statement

Facts & Assumptions

Proof

Assouad lower bound for a squared-error hypercube

Statement

Facts & Assumptions

Proof

Fano’s packing bound with a reference-distribution KL bound

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources

A sparse Hamming packing for every $1 \leq k \leq d / 2$