LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Posterior-odds concentration in the Bernoulli model

Statement

Let $d \geq 1$ be an integer, $0 < τ \leq 1 / 4$ , and let $n \geq 0$ be an integer with $n \leq τ^{- 2}$ . Draw $Θ$ uniformly from ${- 1, + 1}^{d}$ and, conditionally on $Θ$ , draw $n$ independent observations $S = ((X_{i}, Y_{i}))_{i = 1}^{n}$ from the binary-feature Bernoulli model with parameters $Θ, τ$ . For each coordinate $j$ , define the posterior log odds $L_{j} (S) : = \log (P (Θ_{j} = + 1 ∣ S) / P (Θ_{j} = - 1 ∣ S))$ ; these probabilities are positive for every sample because $τ < 1 / 2$ . Then for every $j$ and every sample $S$ , $L_{j} (S) = \log ⁣ (\frac{1 + 2 τ}{1 - 2 τ}) \sum_{i = 1}^{n} Y_{i} X_{i j} .$ Moreover, the coordinates of $Θ$ are conditionally independent given $S$ . For every $0 < δ < 1$ , with probability at least $1 - δ$ over the joint prior-sample experiment, $\max_{1 \leq j \leq d} ∣ L_{j} (S) ∣ \leq 15 τ \sqrt{2 n \log ⁣ (\frac{2 d}{δ})} .$

Statement references

Schmidt et al., Appendix B.2, Lemma 29 and proof of Theorem 31, PDF pp. 33–38.

Facts & Assumptions

Given: The hypotheses in the Statement.

[F1]

Under fixed $Θ = θ$ , the signs $Y_{i} X_{i j} θ_{j}$ are independent over $i$ and each equals $+ 1$ with probability $1 / 2 + τ$ and $- 1$ with probability $1 / 2 - τ$ . Binary-feature Bernoulli model.

[F2]

The natural logarithm converts finite products to sums and satisfies $\log b - \log a = \int_{a}^{b} d x / x$ for $0 < a \leq b$ . Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t.

[F3]

For independent sign variables and coefficients $c_{i}$ , the centered sum has tails $P (∣ \sum_{i} c_{i} (ξ_{i} - E ξ_{i}) ∣ \geq t) \leq 2 e^{- t^{2} / (2 \sum_{i} c_{i}^{2})}$ . Tail bound for finite sums of independent signs.

[F4]

A union of finitely many events has probability at most the sum of their probabilities. The finite union bound.

Proof

1.1givenF1F2algebra

Fix a sample $S = ((x_{i}, y_{i}))_{i = 1}^{n}$ . The prior mass of each $θ$ is $2^{- d}$ , and the likelihood factors over coordinates because the model's conditional coordinate probabilities do. Write $L_{j} (t) = \prod_{i} [(1 / 2 + τ) 1_{{y_{i} x_{i j} = t}} + (1 / 2 - τ) 1_{{y_{i} x_{i j} = - t}}]$ for $t \in {- 1, + 1}$ . The posterior mass at $θ$ is proportional to $\prod_{j} L_{j} (θ_{j})$ , and its normalizing sum is $\prod_{j} (L_{j} (+ 1) + L_{j} (- 1))$ ; hence it factors as a product of coordinate posterior masses, proving conditional independence. The $j$ th marginal odds are $L_{j} (+ 1) / L_{j} (- 1) = ((1 / 2 + τ) / (1 / 2 - τ))^{\sum_{i} y_{i} x_{i j}}$ . Bayes' finite formula and [F2] give the displayed log identity. Positivity of both coordinate probabilities makes each posterior denominator nonzero.

1.2F2algebra

Put $a_{τ} = \log ((1 + 2 τ) / (1 - 2 τ))$ . With $x = 2 τ \leq 1 / 2$ , [F2] gives $a_{τ} = 2 \int_{0}^{x} (1 - u^{2})^{- 1} d u$ . For $0 \leq u \leq 1 / 2$ , $(1 - u^{2})^{- 1} = 1 + u^{2} / (1 - u^{2}) \leq 1 + 4 u^{2} / 3$ , so $a_{τ} \leq 2 x + 8 x^{3} / 9 = 4 τ + 64 τ^{3} / 9 \leq 40 τ / 9 < 5 τ$ .

1.3givenF1F3F4

Assume $n > 0$ , fix $θ$ and $j$ , and put $ξ_{i} = θ_{j} Y_{i} X_{i j}$ . By [F1], these are independent signs with mean $2 τ$ . Let $t = \sqrt{2 n \log (2 d / δ)}$ . [F3] with all coefficients equal to one gives conditional failure probability at most $2 e^{- t^{2} / (2 n)} = δ / d$ for $∣ \sum_{i} (ξ_{i} - 2 τ) ∣ > t$ . Since $∣ \sum_{i} Y_{i} X_{i j} ∣ = ∣ \sum_{i} ξ_{i} ∣$ , this proves $P (∣ \sum_{i} Y_{i} X_{i j} ∣ > 2 τ n + t ∣ Θ = θ) \leq δ / d$ . By [F4] and averaging over the finite prior, with probability at least $1 - δ$ every coordinate obeys $∣ \sum_{i} Y_{i} X_{i j} ∣ \leq 2 τ n + t$ .

2.1step 1.1step 1.2step 1.3F2algebra∎

Since $n \leq τ^{- 2}$ , $τ n \leq \sqrt{n}$ . Also $2 d / δ \geq 2$ and $\log 2 = \int_{1}^{2} d x / x > 1 / 2$ , so $t \geq \sqrt{n}$ . On the event from step 1.3, step 1.1 and step 1.2 now yield $∣ L_{j} (S) ∣ \leq 5 τ (2 τ n + t) \leq 15 τ t$ for every $j$ , which is the asserted bound. If $n = 0$ , the posterior equals the uniform prior, so every $L_{j} = 0$ and the claimed bound holds with equality.

References

Binary-feature Bernoulli model: conditional sign probabilities and coordinate independence.

Tail bound for finite sums of independent signs: the local, choice-free concentration estimate replacing the source's Hoeffding citation.

Depends on

Used by

Architecture-dependent robustness in the Bernoulli model Theorem

Dependency tree · two levels

26 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

Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry, Adversarially Robust Generalization Requires More Data, arXiv:1804.11285v2, Appendix B.2, Lemma 29 and proof of Theorem 31, PDF pp. 33–38 (standard reference, not scraped)