TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Robust sample lower bound in the Gaussian model

Statement

Assume AC. Let $d \geq 1$ be an integer, let $n \geq 0$ be an integer, let $σ > 0$ and $ϵ \geq 0$ , draw $Θ \sim N_{d} (0, I_{d})$ , and, conditional on $Θ$ , draw $n$ independent training pairs $S = ((X_{i}, Y_{i}))_{i = 1}^{n}$ from the two-class spherical Gaussian model with parameters $Θ, σ$ . Let $S_{n} = (R^{d} \times {- 1, + 1})^{n}$ , and let $F : S_{n} \times R^{d} \to {- 1, + 1}$ be a Borel learning rule; write $f_{S} (x) = F (S, x)$ . Define $m (S) = (σ^{2} + n)^{- 1} \sum_{i = 1}^{n} Y_{i} X_{i}$ , with the empty sum equal to zero. Define the expected robust risk as the outer expectation over $(Θ, S)$ of $R_{P_{Θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})$ , using the same measurable-majorant convention as robust risk; when this random robust risk is measurable, this is its ordinary expectation. Then $E_{Θ, S}^{*} ⁣ [R_{P_{Θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})] \geq \frac{1}{2} P_{V \sim N_{d} (0, I_{d})} ⁣ (\sqrt{\frac{n}{σ^{2} + n}} ∥ V ∥_{\infty} \leq ϵ) .$ Consequently, if $d \geq 2$ and $n \leq ϵ^{2} σ^{2} / (8 \log d)$ , then $E_{Θ, S}^{*} ⁣ [R_{P_{Θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})] \geq \frac{1}{2} (1 - \frac{1}{d}) .$

Statement references

Schmidt et al., Theorem 11 and Corollary 23, Appendix A.2, PDF pp. 27–30.

Pydi, Chapter 2 §§2.2–2.3, robust risk and outer-expectation convention.

Facts & Assumptions

Given: The hypotheses in the Statement.

[A1]

Assume the Axiom of Choice, used by the Gaussian construction, posterior, normal characteristic-function uniqueness, Cramer–Wold and concentration suppliers. The Axiom of Choice.

[F1]

In the Gaussian model, conditional on $Θ = θ$ and $Y_{i} = y$ , the projection $⟨ u, X_{i} ⟩$ is $N (y ⟨ u, θ ⟩, σ^{2} ∥ u ∥_{2}^{2})$ ; scalar normal characteristic functions and affine maps identify $Y_{i} X_{i} \sim N_{d} (θ, σ^{2} I_{d})$ , independently of the label. Two-class spherical Gaussian model, Multivariate normal law, including singular covariance, Characteristic function of a normal law, Characteristic functions under affine maps and independent sums, Uniqueness of a law from its characteristic function, Cramer wold device.

[F2]

Given the class-weighted observations $Z_{i} = Y_{i} X_{i}$ , the posterior is $N_{d} (m (S), v I_{d})$ with $m (S) = (σ^{2} + n)^{- 1} \sum_{i} Z_{i}$ and $v = σ^{2} / (σ^{2} + n)$ ; for $n = 0$ it is the prior. Gaussian normal-prior posterior.

[F3]

Robust risk is the infimum of expectations of nonnegative measurable majorants of pointwise robust loss, and the $ℓ_{\infty}$ threat admits every shift of norm at most $ϵ$ . Measurable threat correspondences and robust risk.

[F4]

If a nonnegative function dominates a measurable nonnegative function, its outer expectation is at least the ordinary expectation of the latter; this follows because every measurable majorant dominates it and the nonnegative integral is monotone. Monotonicity and nonnegative homogeneity of the nonnegative integral.

[F5]

For product-measurable nonnegative functions, Tonelli's theorem gives measurable parameter integrals and permits exchange of the integration order. Tonelli's theorem for nonnegative measurable functions on a sigma-finite product.

[F6]

A uniform sign independent of a feature vector is misclassified with probability exactly $1 / 2$ by every Borel binary classifier; this is proved by splitting the two disjoint label-error events in the common-shift lemma. Common shifts force binary robust risk at least one half.

[F7]

If $V \sim N_{d} (0, I_{d})$ and $d \geq 2$ , then $P (∥ V ∥_{\infty} \leq 2 \sqrt{2 \log d}) \geq 1 - 1 / d$ . Gaussian vector norm and maximum-coordinate tails.

[F8]

The natural logarithm is increasing and $\log d > 0$ for $d \geq 2$ . The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm.

[F9]

Independent random elements remain independent after coordinatewise measurable maps are applied. Independent random elements, Measurable coordinatewise functions preserve independence.

Proof

1.1A1F1F9

Fix $θ$ . For any $u \in R^{d}$ and label $y$ , the characteristic function of $⟨ u, Y_{i} X_{i} ⟩$ conditional on $Y_{i} = y$ is $\exp (i t ⟨ u, θ ⟩ - t^{2} σ^{2} ∥ u ∥_{2}^{2} / 2)$ : multiplying the conditional normal projection by $y$ multiplies its mean by $y$ and its frequency by $y$ , so $y^{2} = 1$ in both terms. This law is independent of $y$ ; scalar uniqueness [F1] identifies each projection, and Cramer–Wold [F1] gives $Y_{i} X_{i} \sim N_{d} (θ, σ^{2} I_{d})$ independent of $Y_{i}$ . Independence of the training pairs and measurable coordinate transformations preserve independence across $i$ , so the class-weighted observations have the independent Gaussian likelihood and labels required by [F2].

1.2givenF2algebra

By [F2], for every realized sample $S$ , the posterior mean is $m (S)$ and the posterior covariance is $v I_{d}$ where $v = σ^{2} / (σ^{2} + n)$ . The formula also gives $m = 0, v = 1$ when $n = 0$ . The map $S \mapsto m (S)$ is Borel because it is a finite sum of coordinate products and division by the positive constant $σ^{2} + n$ .

1.3givenF3algebra

Fix $θ, S$ with $∥ m (S) ∥_{\infty} \leq ϵ$ . For a fresh test pair write $X = Y θ + G$ with $Y$ uniform and $G \sim N_{d} (0, σ^{2} I_{d})$ independent. The perturbation $δ = - Y m (S)$ is admissible by [F3] and sends $X$ to $Y (θ - m (S)) + G$ . Thus the pointwise robust loss is at least $1 {F (S, Y (θ - m (S)) + G) \neq Y}$ . This indicator is measurable in the test pair, so every measurable majorant in [F3] has expectation at least its probability; therefore the fixed-parameter robust risk is at least that probability.

2.1step 1.2step 1.3F4F5

Define $H (S, θ)$ to be zero when $∥ m (S) ∥_{\infty} > ϵ$ , and otherwise to be the probability in step 1.3. The classifier family and $m$ are Borel, so the shifted error indicator is product-measurable in $(S, θ, Y, G)$ ; [F5] makes $H$ measurable. Step 1.3 gives $H (S, θ) \leq R_{P_{θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})$ pointwise. By [F4], taking the outer expectation over $(Θ, S)$ yields a lower bound by $E [H (Θ, S)]$ .

3.1step 1.2step 2.1A1F1F2F5F6

Conditional on $S$ , write $Θ = m (S) + R$ with $R \sim N_{d} (0, v I_{d})$ by [F2]. The fresh label $Y$ and noise $G$ are independent of $R$ . For either sign $y$ , $y R + G$ has law $N_{d} (0, (v + σ^{2}) I_{d})$ : each projection has the product characteristic function of independent centered scalar normals, and [F1] identifies the vector law. This conditional law is the same for both labels, so $U : = Y R + G$ is independent of the uniform label. By [F6], $P (F (S, U) \neq Y ∣ S) = 1 / 2$ . Tonelli and the posterior identity [F2] now give $E [H (Θ, S)] = \frac{1}{2} P_{S} (∥ m (S) ∥_{\infty} \leq ϵ)$ .

4.1step 1.1step 1.2A1F1algebra

If $n \geq 1$ , conditional on $Θ$ , the sample mean $\overset{ˉ}{Z} = n^{- 1} \sum_{i} Y_{i} X_{i}$ has all projections $N (⟨ u, Θ ⟩, σ^{2} ∥ u ∥_{2}^{2} / n)$ by the independent normal laws in step 1.1 and [F1]. Averaging the scalar characteristic function over $Θ \sim N_{d} (0, I_{d})$ shows each projection of $\overset{ˉ}{Z}$ is $N (0, (1 + σ^{2} / n) ∥ u ∥_{2}^{2})$ ; [F1] then gives $\overset{ˉ}{Z} \sim N_{d} (0, (1 + σ^{2} / n) I_{d})$ . Since $m = \frac{n}{σ^{2} + n} \overset{ˉ}{Z}$ , its law is $N_{d} (0, \frac{n}{σ^{2} + n} I_{d})$ . For $n = 0$ , $m = 0$ and the same event probability is one. Therefore $P_{S} (∥ m (S) ∥_{\infty} \leq ϵ) = P_{V \sim N_{d} (0, I_{d})} (\sqrt{n / (σ^{2} + n)} ∥ V ∥_{\infty} \leq ϵ)$ . Combining this with step 3.1 proves the first inequality.

5.1step 4.1F7F8algebra∎

Suppose $d \geq 2$ and $n \leq ϵ^{2} σ^{2} / (8 \log d)$ . If $n = 0$ , the event in step 4.1 has probability one. If $n > 0$ , then $\sqrt{n / (σ^{2} + n)} \leq \sqrt{n} / σ \leq ϵ / \sqrt{8 \log d}$ by [F8] and the sample-size hypothesis. On the event $∥ V ∥_{\infty} \leq 2 \sqrt{2 \log d}$ from [F7], it follows that $\sqrt{n / (σ^{2} + n)} ∥ V ∥_{\infty} \leq ϵ$ . Thus the probability in step 4.1 is at least $1 - 1 / d$ , and the first inequality gives the second assertion.

References

Gaussian normal-prior posterior: supplies the exact posterior mean and covariance, including the empty-sample case.

Common shifts force binary robust risk at least one half: supplies the two-label averaging calculation after the common shift.

Gaussian vector norm and maximum-coordinate tails: supplies the maximum-coordinate Gaussian event used in Corollary 23.

Depends on

Used by

Gaussian robust risk across dimensions and radii Example
Natural and robust risk in the Gaussian model Example

Dependency tree · two levels

89 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, Theorem 11, Corollary 23, Appendix A.2, PDF pp. 27–30 (standard reference, not scraped)
Muni Sreenivas Pydi, Adversarial Robustness in Machine Learning: An Optimal Transport Perspective, Chapter 2 §§2.2–2.3 (standard reference, not scraped)