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.

Natural and robust risk in the Gaussian model

Example

Assume AC and set $d = 10^{14}$ , $σ = d^{1 / 4} / 32$ , $β = 1 / 100$ , and $ϵ = 1 / 4$ . In the fixed-parameter experiment with $∥ θ ∥_{2} = \sqrt{d}$ , one class-weighted training sample yields natural test error at most $1 / 100$ with probability at least $1 - 2 e^{- d / (8 (σ^{2} + 1))}$ . In the distinct Gaussian-prior experiment $Θ \sim N_{d} (0, I_{d})$ , at the same $n = 1$ and $ϵ$ , every Borel learning rule $F : (R^{d} \times {- 1, + 1})^{n} \times R^{d} \to {- 1, + 1}$ has expected robust risk at least $(1 - 1 / d) / 2$ . The first assertion fixes a normalized parameter; the second averages over the stated Gaussian prior. Expected robust risk in the prior experiment uses outer expectation over the parameter and training sample.

Example references

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

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

Facts & Assumptions

Given: The Example's parameters and the two separate Gaussian experiments in its Statement.

[A1]

Assume AC as required by the Gaussian model and both risk bounds. The Axiom of Choice.

[F1]

For $0 < β < 1$ , if $σ \leq d^{1 / 4} / (5 \sqrt{\log (1 / β)})$ , then the one-sample class-weighted classifier has natural test error at most $β$ with probability at least $1 - 2 e^{- d / (8 (σ^{2} + 1))}$ . One-sample natural error 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.

[F3]

The natural logarithm is increasing, obeys $\log (2^{k}) = k \log 2$ , 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.

Proof

1.1givenA1F1F3algebra

Since $100 < 256 = 2^{8}$ and $\log 2 = \int_{1}^{2} d x / x < 1$ , [F3] gives $\log 100 < 8$ . Hence $5 \sqrt{\log 100} < 5 \sqrt{8} < 32$ , so $σ = d^{1 / 4} / 32 \leq d^{1 / 4} / (5 \sqrt{\log 100})$ . Apply [F1] with $β = 1 / 100$ to get the fixed-parameter natural-risk assertion.

2.1givenA1F2F3algebra∎

We have $2^{10} = 1024 > 10^{3}$ , hence $2^{47} = 2^{7} (2^{10})^{4} > 128 \cdot 10^{12} > 10^{14} = d$ . Since $\log 2 < 1$ , [F3] gives $\log d < \log (2^{47}) = 47 \log 2 < 47$ . Therefore $\frac{ϵ^{2} σ^{2}}{8 \log d} = \frac{\sqrt{d}}{131072 \log d} > \frac{10^{7}}{131072 \cdot 47} > 1 = n$ , where $131072 \cdot 47 = 6,160,384 < 10,000,000$ . Since $d \geq 2$ , [F2] applies and proves the Gaussian-prior robust-risk lower bound.

References

One-sample natural error in the Gaussian model: supplies the fixed-parameter one-sample natural-error guarantee.

Robust sample lower bound in the Gaussian model: supplies the Gaussian-prior robust-risk lower bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

39 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, Corollary 19, Corollary 23, arXiv:1804.11285v2, PDF pp. 24–25, 30 (standard reference, not scraped)