ExampleConstruction: Literature-sourcedVerification: 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.

Gaussian robust risk across dimensions and radii

Example

Assume AC. For an integer $d \geq 2$ , set $σ = d^{1 / 4} / 32$ and $ϵ = 1 / 4$ . For the fixed-parameter Gaussian model with $∥ θ ∥_{2} = \sqrt{d}$ , the class-weighted sample-mean classifier has $ℓ_{\infty}$ robust risk at most $1 / 100$ with training-sample probability at least $1 - 2 e^{- d / (8 (σ^{2} + 1))}$ whenever the integer sample size satisfies $n \geq 4 \sqrt{d}$ . In the separate Gaussian-prior experiment $Θ \sim N_{d} (0, I_{d})$ , every Borel learning rule $F : (R^{d} \times {- 1, + 1})^{n} \times R^{d} \to {- 1, + 1}$ has expected $ℓ_{\infty}$ robust risk at least $(1 - 1 / d) / 2$ whenever $n \leq \sqrt{d} / (131072 \log d)$ . The first assertion concerns a fixed normalized parameter and an upper bound for one classifier; the second averages over a Gaussian prior and lower-bounds every such Borel learning rule. Expected robust risk in the prior experiment uses outer expectation over the parameter and training sample.

Example references

Schmidt et al., Corollary 22, Appendix A.1, PDF p. 26.

Schmidt et al., Corollary 23, Appendix A.2, PDF p. 30.

Facts & Assumptions

Given: The Example's Gaussian parameter, radius, and dimension.

[A1]

Assume AC as required by both Gaussian robust-risk bounds. The Axiom of Choice.

[F1]

If $σ \leq d^{1 / 4} / 32$ , $d \geq 1$ , and $1 / (4 d^{1 / 4}) \leq ϵ \leq 1 / 4$ , then $n \geq 64 ϵ^{2} \sqrt{d}$ suffices for the class-weighted mean classifier to have robust risk at most $1 / 100$ with failure probability at most $2 e^{- d / (8 (σ^{2} + 1))}$ . Robust sample upper bound in the Gaussian model.

[F2]

If $d \geq 2$ and $n \leq ϵ^{2} σ^{2} / (8 \log d)$ , every Borel learning rule under prior $Θ \sim N_{d} (0, I_{d})$ has expected robust risk at least $(1 - 1 / d) / 2$ . Robust sample lower bound in the Gaussian model.

Proof

1.1givenA1F1algebra

The chosen variance satisfies $σ = d^{1 / 4} / 32$ , and $d \geq 2$ makes $1 / (4 d^{1 / 4}) \leq 1 / 4 = ϵ$ . The upper-bound condition becomes $n \geq 64 (1 / 4)^{2} \sqrt{d} = 4 \sqrt{d}$ . Apply [F1] to obtain the first assertion.

2.1givenA1F2algebra∎

For the lower bound, $ϵ^{2} σ^{2} / (8 \log d) = (1 / 16) (\sqrt{d} / 1024) / (8 \log d) = \sqrt{d} / (131072 \log d)$ . Thus the stated lower sample-size condition is exactly the premise of [F2], which gives the second assertion.

References

Robust sample upper bound in the Gaussian model: supplies the exact one-percent sufficient sample size.

Robust sample lower bound in the Gaussian model: supplies the learner-independent Gaussian-prior necessary sample size.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

31 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, Corollary 22 and Corollary 23, arXiv:1804.11285v2, PDF pp. 26, 30 (standard reference, not scraped)