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

Architecture-dependent robustness in the Bernoulli model

Statement

For $w \in R^{d}$ , let $f_{w} (x) = + 1$ when $⟨ w, x ⟩ \geq 0$ and $f_{w} (x) = - 1$ otherwise. In the following lower-bound branch, let $d \geq 1$ , $0 < τ \leq 1 / 4$ , $0 < γ < 1 / 2$ , and $0 \leq ϵ < 3 τ$ . Draw $Θ$ uniformly from ${- 1, + 1}^{d}$ and, conditional on $Θ$ , draw $n \geq 0$ independent training observations $S$ from the binary-feature Bernoulli model with parameters $Θ, τ$ . Let $g_{n}$ be any function from the finite sample space to $R^{d}$ , set $w = g_{n} (S)$ , and use $f_{w}$ . If $n \leq \frac{ϵ^{2} γ^{2}}{5000 τ^{4} \log (4 d / γ)},$ then the expected robust risk for the closed threat $Δ_{ϵ} (x) = {x + δ : ∥ δ ∥_{\infty} \leq ϵ}$ of $f_{w}$ , averaged over $Θ, S$ , and a fresh test pair from $P_{Θ, τ}$ , is at least $1 / 2 - γ$ .

In the separate thresholded upper-bound branch, let $d \geq 1$ , $0 < τ \leq 1 / 2$ , $0 < β < 1$ , and let $θ \in {- 1, + 1}^{d}$ satisfy $τ \geq (\log (1 / β) / (2 d))^{1 / 4}$ . Draw one training pair $(X_{0}, Y_{0})$ from $P_{θ, τ}$ , set $W = Y_{0} X_{0}$ , and define $T : R^{d} \to {- 1, + 1}^{d}$ by $T (x)_{j} = + 1$ when $x_{j} \geq 0$ and $T (x)_{j} = - 1$ otherwise. Then for every $0 \leq ϵ < 1$ , with training-sample probability at least $1 - e^{- τ^{2} d / 2}$ , the robust risk for the closed threat $Δ_{ϵ} (x) = {x + δ : ∥ δ ∥_{\infty} \leq ϵ}$ of $f_{W} \circ T$ under $P_{θ, τ}$ is at most $β$ .

Statement references

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

Kolter–Madry, Chapter 2, linear classification and $ℓ_{\infty}$ geometry.

Facts & Assumptions

Given: The hypotheses in the Statement; each branch is proved with its own parameter and probability quantifiers.

[F1]

In the Bernoulli model, conditional on $Θ = θ$ , the signs $Y_{i} X_{i j} θ_{j}$ are independent over observations and coordinates and have mean $2 τ$ . Binary-feature Bernoulli model, Independent random elements.

[F2]

For the uniform hypercube prior, conditional on a sample $S$ the parameter coordinates are independent and their log odds are $L_{j} (S) = \log ((1 + 2 τ) / (1 - 2 τ)) \sum_{i} Y_{i} X_{i j}$ . If $n \leq τ^{- 2}$ , then with probability at least $1 - δ$ , all $∣ L_{j} (S) ∣ \leq 15 τ \sqrt{2 n \log (2 d / δ)}$ . Posterior-odds concentration in the Bernoulli model.

[F3]

A finite independent sign sum with coefficients $c_{j}$ satisfies $P (\sum_{j} c_{j} (ξ_{j} - E ξ_{j}) \leq - t) \leq e^{- t^{2} / (2 \sum_{j} c_{j}^{2})}$ for $t > 0$ . Tail bound for finite sums of independent signs.

[F4]

If $A \geq 0$ and $b > 0$ , then $P (A > b) \leq E [A] / b$ . Markov's inequality for random variables.

[F5]

The natural logarithm is the inverse of $\exp$ , so $\exp (\log r) = r$ for $r > 0$ . It is increasing and $\log (x / y) = \log x - \log y$ ; $\log b - \log a = \int_{a}^{b} d u / u$ for $0 < a \leq b$ . 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.

[F6]

$e^{x} = \sum_{k \geq 0} x^{k} / k!$ for real $x$ . The real exponential function and the number $e$ by a power series.

[F7]

Finite integrable sums have expectation equal to the sum of expectations. The Lebesgue integral is linear on $L^{1} (μ)$ .

[F8]

Under the closed $ℓ_{\infty}$ threat, robust zero-one loss is one exactly when some admissible perturbation changes the label. Measurable threat correspondences and robust risk.

[F9]

The coordinate threshold rule has $T (x)_{j} = + 1$ for $x_{j} \geq 0$ and $- 1$ for $x_{j} < 0$ . Coordinatewise threshold preprocessing.

Proof

1.1givenF2F5algebra

For the lower-bound branch put $Λ = \log (4 d / γ)$ . Since $4 d / γ > 8$ and $\log 8 = 3 \log 2 > 3 / 2 > 1$ by [F5], the sample-size hypothesis and $ϵ < 3 τ$ , $γ < 1 / 2$ imply $n < 9 / (20000 τ^{2}) < τ^{- 2}$ . Apply [F2] with $δ = γ / 2$ . With probability at least $1 - γ / 2$ over $(Θ, S)$ , every posterior log odds obeys $∣ L_{j} (S) ∣ \leq B : = 15 τ \sqrt{2 n Λ}$ . Moreover $B \leq (3 / 10) ϵ γ / τ < 9 / 20 < 1$ .

1.2givenF1F3algebra

For the thresholded upper branch, fix $θ$ and a training pair $(X_{0}, Y_{0})$ . The signs $R_{j} = Y_{0} X_{0 j} θ_{j}$ are independent with mean $2 τ$ by [F1]. Apply [F3] with coefficients all one and $t = τ d$ to obtain $P (⟨ W, θ ⟩ \leq τ d) \leq e^{- τ^{2} d / 2}$ . Outside this event, $u = W / \sqrt{d}$ is unit and $⟨ u, θ ⟩ > τ \sqrt{d}$ .

2.1step 1.1F2F5F6algebra

Write $m_{j} (S) = E [Θ_{j} ∣ S]$ . If $r_{j} = e^{L_{j} (S)}$ is the posterior odds, then $m_{j} = (r_{j} - 1) / (r_{j} + 1)$ by the inverse relation in [F5], so on the event in step 1.1, $∣ m_{j} ∣ \leq (e^{B} - 1) / 2$ . For $0 \leq x \leq 1$ , [F6] and $x^{k} \leq x$ give $e^{x} - 1 \leq x \sum_{k \geq 1} 1 / k! = (e - 1) x < 2 x$ : indeed induction using $k + 1 \geq 2$ gives $k! \geq 2^{k - 1}$ for $k \geq 1$ , strictly for some $k$ , so $e < 1 + 1 + \sum_{k \geq 2} 2^{- (k - 1)} = 3$ . Therefore $∣ m_{j} ∣ \leq B$ . Set $a : = 2 τ B = 30 τ^{2} \sqrt{2 n Λ}$ . The sample-size condition yields $a \leq (3 / 5) ϵ γ < 9 τ / 10 \leq 9 / 40 < 1$ and $a / γ \leq 3 ϵ / 5 < ϵ$ when $ϵ > 0$ .

2.2givenF1F2

Fix a sample $S$ in the event of step 1.1 and its learned vector $w$ . Conditional on $S$ , the posterior coordinates $Θ_{j}$ are independent by [F2]. For a fresh pair put $Q_{j} = Y X_{j}$ . Conditional on $Θ_{j} = t$ , $Q_{j} = t$ with probability $1 / 2 + τ$ and $Q_{j} = - t$ with probability $1 / 2 - τ$ , independently across coordinates and independently of the value of $Y$ . Averaging over the product posterior shows that the $Q_{j}$ are independent of one another and of $Y$ , with $E [Q_{j} ∣ S] = 2 τ m_{j} (S)$ .

2.3step 1.2F1F3F5algebra

For a fresh pair, the signs $R_{j} = Y X_{j} θ_{j}$ are independent with mean $2 τ$ . The signed margin of $f_{W}$ is $Y ⟨ u, X ⟩ = \sum_{j} u_{j} θ_{j} R_{j}$ , whose mean is $2 τ ⟨ u, θ ⟩$ and whose centered coefficient square-sum is $\sum_{j} (u_{j} θ_{j})^{2} = 1$ . If $f_{W} (X) \neq Y$ , then this signed margin is at most zero under the stated tie rule. By [F3], its probability is at most $\exp (- 2 τ^{2} ⟨ u, θ ⟩^{2}) \leq e^{- 2 τ^{4} d} \leq β$ , where the last inequality is the assumed lower bound on $τ$ .

3.1step 2.1step 2.2algebra

For each $j$ with $w_{j} \neq 0$ , the sign $V_{j} : = sgn (w_{j}) Q_{j}$ has mean at most $a$ and is supported on ${- 1, + 1}$ . Couple independent signs $E_{j}$ of mean $a$ using independent uniform variables so that $V_{j} \leq E_{j}$ coordinatewise: if $p_{j} = P (V_{j} = + 1 ∣ S) \leq (1 + a) / 2$ , use the same uniform variable to set $V_{j} = + 1$ below $p_{j}$ and $E_{j} = + 1$ below $(1 + a) / 2$ . Coordinates with $w_{j} = 0$ contribute zero. Thus the margin $M : = \sum_{j} w_{j} Q_{j}$ is stochastically at most $\tilde{M} : = \sum_{j} ∣ w_{j} ∣ E_{j}$ .

4.1step 3.1F4F7

Represent each $E_{j} = A_{j} + B_{j}$ , where $A_{j}$ is Bernoulli with mean $a$ , $B_{j} = 0$ if $A_{j} = 1$ , and conditional on $A_{j} = 0$ , $B_{j}$ is a uniform sign. Then $E \sum_{j} ∣ w_{j} ∣ A_{j} = a ∥ w ∥_{1}$ . If $w \neq 0$ and $a > 0$ , [F4] gives $P (\sum_{j} ∣ w_{j} ∣ A_{j} > a ∥ w ∥_{1} / γ) \leq γ$ . Conditional on the vector $(A_{j})$ , the sum $\sum_{j} ∣ w_{j} ∣ B_{j}$ is symmetric about zero, so it is nonpositive with probability at least $1 / 2$ . Hence $P (\tilde{M} \leq a ∥ w ∥_{1} / γ) \geq (1 - γ) / 2$ , and step 3.1 gives the same lower bound for $P (M \leq a ∥ w ∥_{1} / γ ∣ S)$ . The same conclusion holds if $a = 0$ by taking $A_{j} = 0$ surely. If $w = 0$ , the constant classifier has robust error $1 / 2$ under the balanced labels.

5.1step 2.1step 4.1F1F8

Suppose $ϵ > 0$ and $w \neq 0$ . On the event in step 4.1, step 2.1 gives $M \leq (a / γ) ∥ w ∥_{1} < ϵ ∥ w ∥_{1}$ . For the fresh label $Y$ , choose $δ_{j} = - ϵ Y$ if $w_{j} > 0$ , choose $δ_{j} = + ϵ Y$ if $w_{j} < 0$ , and choose $δ_{j} = 0$ if $w_{j} = 0$ . By [F8], $∥ δ ∥_{\infty} \leq ϵ$ and $Y ⟨ w, X + δ ⟩ = M - ϵ ∥ w ∥_{1} < 0$ , so this perturbation misclassifies. Thus on every good training sample the posterior-averaged robust risk is at least $(1 - γ) / 2$ . If $ϵ = 0$ , the sample-size hypothesis forces $n = 0$ ; after averaging the uniform prior, $X$ is uniform on the hypercube independently of $Y$ , so every classifier has natural and robust error $1 / 2$ .

6.1step 1.1step 5.1algebra

The good training-sample event has probability at least $1 - γ / 2$ by step 1.1. The expected robust risk is therefore at least $(1 - γ / 2) (1 - γ) / 2 \geq 1 / 2 - γ$ , since the difference is $γ / 4 + γ^{2} / 4 \geq 0$ . The zero-weight and $ϵ = 0$ cases in step 5.1 satisfy the same final bound.

7.1step 1.2step 2.3F9algebra∎

If $x \in {- 1, + 1}^{d}$ and $∥ δ ∥_{\infty} \leq ϵ < 1$ , then $x_{j} + δ_{j} > 0$ when $x_{j} = + 1$ and $x_{j} + δ_{j} < 0$ when $x_{j} = - 1$ . By [F9], $T (x + δ) = x$ coordinatewise. Thus every allowed adversarial perturbation leaves $f_{W} (T (x + δ)) = f_{W} (x)$ , so its robust error equals the natural error bounded in step 2.3. The failure probability is at most $e^{- τ^{2} d / 2}$ by step 1.2.

References

Posterior-odds concentration in the Bernoulli model: supplies exact posterior odds, coordinate posterior independence, and simultaneous concentration.

Tail bound for finite sums of independent signs: supplies the choice-free sign concentration used in both Bernoulli branches.

Coordinatewise threshold preprocessing: supplies the coordinatewise sign threshold with zero mapped to $+ 1$ .

Depends on

Used by

Thresholding removes Bernoulli sign perturbations Example

Dependency tree · two levels

45 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, Theorem 10, Corollary 28, Theorem 31, Appendix B, PDF pp. 7, 31–37 (standard reference, not scraped)
Zico Kolter and Aleksander Madry, Adversarial Robustness: Theory and Practice, NeurIPS 2018 tutorial notes, Chapter 2 (standard reference, not scraped)