CorollaryStatement: 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.

One-sample natural error in the Gaussian model

Statement

Assume AC. Let $d \geq 1$ be an integer, let $θ \in R^{d}$ satisfy $∥ θ ∥_{2} = \sqrt{d}$ , let $0 < β < 1$ , and let $σ > 0$ satisfy $σ \leq d^{1 / 4} / (5 \sqrt{\log (1 / β)})$ . Draw one training pair $(X_{0}, Y_{0})$ from the two-class spherical Gaussian model with parameters $θ, σ$ . Set $W = Y_{0} X_{0}$ and define the unit vector $\hat{W} = W / ∥ W ∥_{2}$ for $W \neq 0$ and $\hat{W} = e_{1}$ for $W = 0$ . Define $h_{u} (x) = + 1$ when $⟨ u, x ⟩ \geq 0$ and $h_{u} (x) = - 1$ otherwise, and define its natural error by ${err}_{θ, σ} (u) = P_{(X, Y) \sim P_{θ, σ}} (h_{u} (X) \neq Y)$ . Then $P_{(X_{0}, Y_{0}) \sim P_{θ, σ}} ⁣ ({err}_{θ, σ} (\hat{W}) \leq β) \geq 1 - 2 \exp ⁣ (- \frac{d}{8 (σ^{2} + 1)}) .$

Statement references

Schmidt et al., Corollary 19 and Appendix A.1, PDF pp. 24–25.

Facts & Assumptions

Given: The hypotheses in the Statement.

[A1]

Assume the Axiom of Choice, used by the Gaussian-law and concentration suppliers. The Axiom of Choice.

[F1]

For a one-sample Gaussian model pair, the class-weighted direction satisfies $⟨ \hat{W}, θ ⟩ \geq \sqrt{d} / (2 + 4 σ)$ except with probability at most $2 e^{- d / (8 (σ^{2} + 1))}$ . Signal alignment of a Gaussian sample mean.

[F2]

For every unit $u$ , $⟨ u, X ⟩$ conditional on $Y = y$ is $N (y ⟨ u, θ ⟩, σ^{2})$ ; scalar normal laws have their stated characteristic functions, affine transformations preserve the characteristic-function formula, and equal characteristic functions determine equal scalar laws under AC. 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.

[F3]

If $G \sim N (0, σ^{2})$ and $s \geq 0$ , then $P (G \leq - s) \leq e^{- s^{2} / (2 σ^{2})}$ ; the centered normal law is symmetric about zero. Gaussian vector norm and maximum-coordinate tails, Characteristic function of a normal law, Uniqueness of a law from its characteristic function.

[F4]

The natural logarithm is increasing, has $\log (a b) = \log a + \log b$ , and $\log 2 = \int_{1}^{2} d x / x > 1 / 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, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t.

Proof

1.1givenA1F1

Apply [F1] with $n = 1$ . With probability at least $1 - 2 e^{- d / (8 (σ^{2} + 1))}$ over the training pair, the learned unit vector satisfies $⟨ \hat{W}, θ ⟩ \geq a : = \sqrt{d} / (2 + 4 σ) > 0$ .

1.2givenF2F3algebra

Fix any unit vector $u$ with $c : = ⟨ u, θ ⟩ \geq a$ . Conditional on $Y = y$ , the characteristic function of $Y ⟨ u, X ⟩$ at $t$ is $\exp (i t c - σ^{2} t^{2} / 2)$ by [F2], independently of $y$ . Thus the signed test margin has law $N (c, σ^{2})$ . The tie convention implies ${h_{u} (X) \neq Y} \subseteq {Y ⟨ u, X ⟩ \leq 0}$ , so [F3] gives ${err}_{θ, σ} (u) \leq \exp (- c^{2} / (2 σ^{2})) \leq \exp (- a^{2} / (2 σ^{2}))$ .

2.1step 1.2F3algebra

If $β \geq 1 / 2$ , then $c > 0$ and symmetry of the centered normal in [F3] gives ${err}_{θ, σ} (u) \leq P (G \leq 0) = 1 / 2 \leq β$ .

2.2givenF4step 1.2algebra

Suppose $β < 1 / 2$ and put $L = \log (1 / β)$ . By [F4], $L > \log 2 > 1 / 2$ . Since $d^{1 / 4} \geq 1$ , the hypothesis gives $2 + 4 σ \leq (2 + 4 \sqrt{2} / 5) d^{1 / 4}$ and $σ^{2} L \leq \sqrt{d} / 25$ . Therefore $2 (2 + 4 σ)^{2} σ^{2} L \leq \frac{2}{25} (2 + 4 \sqrt{2} / 5)^{2} d < d$ , where the final strict inequality follows from $2 + 4 \sqrt{2} / 5 < 5 / \sqrt{2}$ . Hence $a^{2} / (2 σ^{2}) > L$ , and step 1.2 gives ${err}_{θ, σ} (u) \leq e^{- L} = β$ .

3.1step 1.1step 1.2step 2.1step 2.2∎

On the alignment event in step 1.1, the unit vector $u = \hat{W}$ meets the hypothesis of step 1.2. Steps 2.1 and 2.2 cover the two exhaustive cases for $β$ , so its natural error is at most $β$ throughout that event. The event probability from step 1.1 is the asserted lower bound.

References

Signal alignment of a Gaussian sample mean: supplies the one-sample direction bound.

Gaussian vector norm and maximum-coordinate tails: supplies the one-sided Gaussian projection tail used for test error.

Depends on

Used by

Natural and robust risk in the Gaussian model Example

Dependency tree · two levels

58 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, Corollary 19 and Appendix A.1, PDF pp. 24–25 (standard reference, not scraped)