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.

Robust sample upper bound in the Gaussian model

Statement

Assume AC. Let $d, n \geq 1$ be integers, let $θ \in R^{d}$ satisfy $∥ θ ∥_{2} = \sqrt{d}$ , let $σ > 0$ , and draw independent training pairs $(X_{i}, Y_{i})_{i = 1}^{n}$ from the two-class spherical Gaussian model with parameters $θ, σ$ . Set $W = n^{- 1} \sum_{i = 1}^{n} Y_{i} X_{i}$ and let $f_{W} (x) = + 1$ when $⟨ W, x ⟩ \geq 0$ and $f_{W} (x) = - 1$ otherwise. For $0 < β < 1$ , if $0 \leq ϵ \leq \frac{2 \sqrt{n} - 1}{2 \sqrt{n} + 4 σ} - \frac{σ \sqrt{2 \log (1 / β)}}{\sqrt{d}},$ then with probability at least $1 - 2 \exp (- d / (8 (σ^{2} + 1)))$ over the training sample, the $ℓ_{\infty}$ robust risk of $f_{W}$ under $P_{θ, σ}$ at radius $ϵ$ is at most $β$ .

In particular, if $σ \leq d^{1 / 4} / 32$ , then each of the following two conditions is sufficient for $ℓ_{\infty}$ robust risk at most $1 / 100$ with the same training-sample probability:

$0 \leq ϵ \leq (1 / 4) d^{- 1 / 4}$ and $n \geq 1$ ;
$(1 / 4) d^{- 1 / 4} \leq ϵ \leq 1 / 4$ and $n \geq 64 ϵ^{2} \sqrt{d}$ .

Statement references

Schmidt et al., Lemma 20, Theorem 21 and Corollary 22, Appendix A.1, PDF pp. 25–26.

Kolter–Madry, Chapter 2, linear models and dual-norm perturbation calculation.

Facts & Assumptions

Given: The hypotheses in the Statement.

[A1]

Assume the Axiom of Choice, used by the Gaussian-law and concentration suppliers. The Axiom of Choice.

[F1]

For the class-weighted Gaussian sample mean $W$ , the direction $U = W / ∥ W ∥_{2}$ (with any unit fallback at $W = 0$ ) satisfies $⟨ U, θ ⟩ \geq A_{n} \sqrt{d}$ with probability at least $1 - 2 e^{- d / (8 (σ^{2} + 1))}$ , where $A_{n} = (2 \sqrt{n} - 1) / (2 \sqrt{n} + 4 σ)$ . Signal alignment of a Gaussian sample mean.

[F2]

For every unit vector $u$ , conditional on $Y = y$ , $⟨ u, X ⟩ \sim N (y ⟨ u, θ ⟩, σ^{2})$ ; scalar normal characteristic functions and affine transformations identify $Y ⟨ u, X ⟩ \sim N (⟨ u, θ ⟩, σ^{2})$ . Two-class spherical Gaussian model, Multivariate normal law, including singular covariance, Characteristic function of a normal law, Characteristic functions under affine maps and independent sums, Uniqueness of a law from its characteristic function.

[F3]

For $G \sim N (0, σ^{2})$ and $s \geq 0$ , $P (G \leq - s) \leq e^{- s^{2} / (2 σ^{2})}$ . Gaussian vector norm and maximum-coordinate tails.

[F4]

Cauchy–Schwarz gives $∥ u ∥_{1} \leq \sqrt{d}$ for $∥ u ∥_{2} = 1$ . Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation.

[F5]

The $ℓ_{\infty}$ robust loss is the indicator that some perturbation of $ℓ_{\infty}$ norm at most $ϵ$ changes the label, and robust risk is the infimum over measurable nonnegative majorants. Measurable threat correspondences and robust risk.

[F6]

The natural logarithm is increasing and obeys product and integer-power laws; $\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.

[F7]

For $s > 0$ , the scalar law $N (m, s^{2})$ is the image of the standard normal density under $z \mapsto m + s z$ . A singleton has a singleton preimage, whose density integral is zero; hence this law has no atoms. Standard normal and normal laws.

Proof

1.1givenA1F1F2F7

Put $A_{n} = (2 \sqrt{n} - 1) / (2 \sqrt{n} + 4 σ)$ . Conditional on all training labels, the independent training pairs give independent scalar variables $Y_{i} X_{i 1} \sim N (θ_{1}, σ^{2})$ by [F2]. The affine and independent-sum characteristic-function rules in [F2] therefore give $W_{1} \sim N (θ_{1}, σ^{2} / n)$ , a law independent of those labels. Since $σ^{2} / n > 0$ , [F7] implies $P (W = 0) \leq P (W_{1} = 0) = 0$ . Removing this null event from the alignment event in [F1], with probability at least $1 - 2 e^{- d / (8 (σ^{2} + 1))}$ the vector $U : = W / ∥ W ∥_{2}$ is unit with $⟨ U, θ ⟩ \geq A_{n} \sqrt{d}$ . On this event $f_{W} = f_{U}$ , since normalization is by a positive scalar.

1.2givenF2

Fix any unit vector $u$ and write $c = ⟨ u, θ ⟩$ . Conditional on $Y = y$ , [F2] gives the characteristic function $\exp (i t c - σ^{2} t^{2} / 2)$ for $M : = Y ⟨ u, X ⟩$ , independent of $y$ ; hence the same law holds after averaging over $Y$ .

1.3givenF5algebra

For every perturbation $δ$ with $∥ δ ∥_{\infty} \leq ϵ$ , $Y ⟨ u, X + δ ⟩ = M + Y ⟨ u, δ ⟩ \geq M - ϵ ∥ u ∥_{1}$ . Thus if the robust loss is one then $M \leq ϵ ∥ u ∥_{1}$ , including the $+ 1$ tie convention. Consequently the pointwise robust loss is bounded above by the measurable indicator $1_{{M \leq ϵ ∥ u ∥_{1}}}$ , which is an admissible majorant in [F5].

1.4givenF6algebra

For the final assertion put $D = d^{1 / 4} \geq 1$ and $k = \sqrt{2 \log 100}$ . By [F6], $\log 100 < \log 256 = 8 \log 2 < 8$ , so $k < 4$ . Under $σ \leq D / 32$ , this implies $k σ / \sqrt{d} < 1 / (8 D)$ . The robust-radius threshold from the first assertion at $β = 1 / 100$ is $A_{n} - k σ / \sqrt{d}$ .

2.1step 1.2step 1.3F3F4F5algebra

If $c \geq A_{n} \sqrt{d}$ and $ϵ \leq A_{n} - σ \sqrt{2 \log (1 / β)} / \sqrt{d}$ , [F4] gives $c - ϵ ∥ u ∥_{1} \geq σ \sqrt{2 \log (1 / β)} \geq 0$ . By step 1.2, $M - c$ is centered normal with variance $σ^{2}$ ; [F3] and step 1.3 show the robust risk is at most $\exp (- (c - ϵ ∥ u ∥_{1})^{2} / (2 σ^{2})) \leq β$ .

2.2step 1.4givenalgebra

If $0 \leq ϵ \leq 1 / (4 D)$ and $n \geq 1$ , then $A_{n} \geq A_{1} = 1 / (2 + 4 σ) \geq 1 / (2 + D / 8)$ . Since $D \geq 1$ , $2 + D / 8 \leq 17 D / 8$ , so $A_{n} - k σ / \sqrt{d} > 8 / (17 D) - 1 / (8 D) = 47 / (136 D) > 1 / (4 D) \geq ϵ$ .

2.3step 1.4givenalgebra

If $1 / (4 D) \leq ϵ \leq 1 / 4$ and $n \geq 64 ϵ^{2} D^{2}$ , set $q = ϵ D$ . Then $q \geq 1 / 4$ , $q \leq D / 4$ , and $2 \sqrt{n} \geq 16 q$ . The function $s \mapsto (s - 1) / (s + 4 σ)$ is increasing for $s > 0$ , and it decreases as $σ$ increases when $s > 1$ . Hence $A_{n} \geq (16 q - 1) / (16 q + D / 8) \geq 12 q / ((33 / 8) D) = 32 ϵ / 11$ . As $1 / (8 D) \leq ϵ / 2$ , step 1.4 gives $A_{n} - k σ / \sqrt{d} > (32 / 11 - 1 / 2) ϵ = 53 ϵ / 22 \geq ϵ$ .

3.1step 1.1step 2.1

On the event in step 1.1, use $u = U$ in step 2.1. This proves the first assertion with the probability stated there.

4.1step 3.1step 2.2step 2.3∎

Under either sample-size condition in step 2.2 or step 2.3, the first assertion applies with $β = 1 / 100$ . Its training-sample failure probability remains $2 e^{- d / (8 (σ^{2} + 1))}$ , proving the second assertion.

References

Signal alignment of a Gaussian sample mean: supplies the high-probability signal alignment of the learned direction.

Gaussian vector norm and maximum-coordinate tails: supplies the one-sided Gaussian test-margin tail.

Measurable threat correspondences and robust risk: defines the closed $ℓ_{\infty}$ threat and outer robust risk.

Depends on

Used by

Gaussian robust risk across dimensions and radii Example

Dependency tree · two levels

81 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, Lemma 20, Theorem 21, Corollary 22, Appendix A.1, PDF pp. 25–26 (standard reference, not scraped)
Zico Kolter and Aleksander Madry, Adversarial Robustness: Theory and Practice, NeurIPS 2018 tutorial notes, Chapter 2 (standard reference, not scraped)