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

Common shifts force binary robust risk at least one half

Statement

Let $d \geq 1$ be an integer, let $ϵ \geq 0$ , let $μ \in R^{d}$ satisfy $∥ μ ∥_{\infty} \leq ϵ$ , and let $Y$ be uniform on ${- 1, + 1}$ and independent of an arbitrary Borel random vector $Z \in R^{d}$ . Set $X = Y μ + Z$ , let $P$ be the joint law of $(X, Y)$ , and let $f : R^{d} \to {- 1, + 1}$ be any Borel classifier. For the closed $ℓ_{\infty}$ threat $Δ_{ϵ} (x) = {x + δ : ∥ δ ∥_{\infty} \leq ϵ}$ and robust zero-one risk defined by outer expectation, $R_{P, Δ_{ϵ}}^{r o b} (f) \geq 1 / 2$ .

Statement references

Schmidt et al., Appendix A.2, proof of Theorem 11, PDF pp. 27–30.

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

Facts & Assumptions

Given: The hypotheses in the Statement.

[A1]

The center satisfies $∥ μ ∥_{\infty} \leq ϵ$ .

[F1]

Robust risk is the infimum of expectations of nonnegative measurable majorants of the pointwise robust loss; the $ℓ_{\infty}$ threat includes every $x + δ$ with $∥ δ ∥_{\infty} \leq ϵ$ . Measurable threat correspondences and robust risk.

[F2]

If nonnegative measurable functions $g, h$ satisfy $h \leq g$ , then $E [h] \leq E [g]$ . Monotonicity and nonnegative homogeneity of the nonnegative integral.

[F3]

Independence of $Y$ and $Z$ means their generated sigma-algebras are independent. Independent random elements.

Proof

1.1givenF3algebra

Since $f$ is Borel, the event $A : = {f (Z) = + 1}$ belongs to $σ (Z)$ , which is independent of $σ (Y)$ by [F3]. Thus $P (f (Z) \neq Y) = P (A) P (Y = - 1) + P (A^{c}) P (Y = + 1) = \frac{1}{2} P (A) + \frac{1}{2} P (A^{c}) = 1 / 2$ .

1.2givenA1F1

For each outcome, the perturbation $δ = - Y μ$ satisfies $∥ δ ∥_{\infty} \leq ϵ$ by [A1], and $X + δ = Z$ . Hence the pointwise robust loss is at least $1 {f (Z) \neq Y}$ . This indicator is measurable because $f$ and the coordinate variables are measurable.

2.1step 1.1step 1.2F1F2∎

Every measurable nonnegative majorant $g$ in the definition of robust risk therefore satisfies $g (X, Y) \geq 1 {f (Z) \neq Y}$ . By [F2] and step 1.1, its expectation is at least $1 / 2$ . Taking the infimum over all such majorants gives $R_{P, Δ_{ϵ}}^{r o b} (f) \geq 1 / 2$ .

References

Measurable threat correspondences and robust risk: the robust loss is bounded below pointwise by the loss at any one admissible perturbation, and risk uses outer expectation.

Monotonicity and nonnegative homogeneity of the nonnegative integral: transfers a pointwise measurable lower bound to every measurable majorant's expectation.

Depends on

Used by

Robust sample lower bound in the Gaussian model Theorem

Dependency tree · two levels

15 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, Appendix A.2, proof of Theorem 11, 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)