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.

Thresholding removes Bernoulli sign perturbations

Example

Let $d \geq 1$ , $θ \in {- 1, + 1}^{d}$ , $0 < τ \leq 1 / 2$ , $0 \leq ϵ < 1$ , and let $(X, Y) \sim P_{θ, τ}$ be the binary-feature Bernoulli model. Let $T (x)_{j} = + 1$ for $x_{j} \geq 0$ and $T (x)_{j} = - 1$ for $x_{j} < 0$ . For every classifier $g : {- 1, + 1}^{d} \to {- 1, + 1}$ , the classifier $g \circ T$ has exactly the same $ℓ_{\infty}$ robust risk at radius $ϵ$ as $g$ has natural risk: $R_{P_{θ, τ}, Δ_{ϵ}}^{r o b} (g \circ T) = P (g (X) \neq Y) .$ For $w \in R^{d}$ , define $f_{w} (x) = + 1$ when $⟨ w, x ⟩ \geq 0$ and $f_{w} (x) = - 1$ otherwise. In particular, if $0 < β < 1$ and $τ \geq (\log (1 / β) / (2 d))^{1 / 4}$ , then the one-sample classifier $f_{Y_{0} X_{0}} \circ T$ has robust risk at most $β$ with training-sample probability at least $1 - e^{- τ^{2} d / 2}$ .

Example references

Schmidt et al., Theorem 10 and Corollary 28, main text and Appendix B.1, PDF pp. 7, 31–32.

Kolter–Madry, Chapter 2, thresholding and linear models.

Facts & Assumptions

Given: The hypotheses in the Example.

[F1]

The Bernoulli model is supported on ${- 1, + 1}^{d} \times {- 1, + 1}$ . Binary-feature Bernoulli model.

[F2]

$T$ maps a nonnegative coordinate to $+ 1$ and a negative coordinate to $- 1$ . Coordinatewise threshold preprocessing.

[F3]

Robust zero-one loss is one exactly when some admissible perturbation changes the label; robust risk is the expectation of this loss. Measurable threat correspondences and robust risk.

[F4]

Under the stated $τ, β$ condition, the one-sample thresholded Bernoulli classifier has robust risk at most $β$ with the stated training-sample probability. Architecture-dependent robustness in the Bernoulli model.

Proof

1.1givenF1F2algebra

Fix $x \in {- 1, + 1}^{d}$ and any $δ$ with $∥ δ ∥_{\infty} \leq ϵ < 1$ . If $x_{j} = + 1$ , then $x_{j} + δ_{j} \geq 1 - ϵ > 0$ , so [F2] gives $T (x + δ)_{j} = + 1 = x_{j}$ . If $x_{j} = - 1$ , then $x_{j} + δ_{j} \leq - 1 + ϵ < 0$ , so $T (x + δ)_{j} = - 1 = x_{j}$ . Hence $T (x + δ) = x$ for every admissible perturbation.

2.1step 1.1F3

For each support point $(x, y)$ , every allowed perturbation therefore makes $g (T (x + δ)) = g (x)$ . The robust zero-one loss of $g \circ T$ equals $1 {g (x) \neq y}$ pointwise. Taking expectation under $P_{θ, τ}$ proves the displayed equality.

3.1step 2.1F4∎

Under the final $τ, β$ condition, [F4] gives the one-sample risk bound for $f_{Y_{0} X_{0}} \circ T$ with the stated probability. The pointwise identity in step 2.1 explains why every radius $ϵ < 1$ has the same risk.

References

Binary-feature Bernoulli model: the support is exactly the sign hypercube with a binary label.

Architecture-dependent robustness in the Bernoulli model: supplies the one-sample high-probability error guarantee.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

19 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, Theorem 10 and the Bernoulli-model discussion, arXiv:1804.11285v2, PDF pp. 7, 31–32 (standard reference, not scraped)
Zico Kolter and Aleksander Madry, Adversarial Robustness: Theory and Practice, NeurIPS 2018 tutorial notes, Chapter 2 (standard reference, not scraped)