Pipeline-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.

Adversarial robustness and robust risk

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Measurable threat correspondences and robust risk

Definition

Let $(X, Σ_{X})$ and $(Y, Σ_{Y})$ be measurable spaces, let $A$ be a measurable action space, and let $P$ be a probability measure on $(X \times Y, Σ_{X} \otimes Σ_{Y})$ . A threat correspondence is a map $Δ : X \to P (X)$ with $Δ (x) \neq \emptyset$ for every $x$ . It is measurable when its graph ${(x, x^{'}) \in X^{2} : x^{'} \in Δ (x)}$ belongs to $Σ_{X} \otimes Σ_{X}$ . For a measurable predictor $f : X \to A$ and a nonnegative measurable loss $ℓ : A \times Y \to [0, + \infty]$ , the pointwise robust loss is $L_{Δ, f} (x, y) = \sup_{x^{'} \in Δ (x)} ℓ (f (x^{'}), y) .$ Its robust risk is the outer expectation $R_{P, Δ}^{r o b} (f) = E_{P}^{*} [L_{Δ, f} (X, Y)] : = \inf {E_{P} [g (X, Y)] : g \geq L_{Δ, f} and g is nonnegative measurable} .$ If $L_{Δ, f}$ is measurable, this is its ordinary expectation. The supremum need not be attained. For a metric $ρ$ on $X$ and a radius $ϵ \geq 0$ , the closed-ball threat is $Δ_{ϵ} (x) = {x^{'} \in X : ρ (x, x^{'}) \leq ϵ}$ . On $R^{d}$ , $∥ u ∥_{\infty} : = \max_{1 \leq j \leq d} ∣ u_{j} ∣$ and the $ℓ_{\infty}$ threat is $Δ_{ϵ} (x) = {x + δ : ∥ δ ∥_{\infty} \leq ϵ}$ . When $A = Y = {- 1, + 1}$ with their discrete sigma-algebras and $ℓ (a, y) = 1_{{a \neq y}}$ , the robust zero-one loss of a measurable classifier $f : X \to {- 1, + 1}$ is $1 {\exists x^{'} \in Δ_{ϵ} (x) : f (x^{'}) \neq y}$ .

Definition references

Measurable spaces and measurable sets: a measurable space is a set equipped with a sigma-algebra.

A measurable function between measurable spaces: measurability means every measurable target set has measurable preimage.

A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain: a function is single-valued on its domain.

The product sigma-algebra and its finite iterates: $Σ_{X} \otimes Σ_{Y}$ is generated by measurable rectangles.

Probability measures and probability spaces: a probability measure has total mass one.

Expectation of a nonnegative or integrable random variable: expectation is the corresponding extended or finite Lebesgue integral.

Pydi, Chapter 2 §§2.2–2.3: expected-supremum risk and the measurability caveat.

Kolter–Madry, Chapter 1: input-dependent perturbation sets and expected worst-case loss.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Two-class spherical Gaussian model

Definition

Assume the Axiom of Choice. For an integer $d \geq 1$ , a vector $θ \in R^{d}$ , and $σ > 0$ , the two-class spherical Gaussian model is the Borel probability law $P_{θ, σ}$ on $R^{d} \times {- 1, + 1}$ defined by $P_{θ, σ} (C) = \frac{1}{2} \sum_{y \in {- 1, + 1}} N_{d} (y θ, σ^{2} I_{d}) (C_{y}), C_{y} : = {x \in R^{d} : (x, y) \in C},$ for every Borel set $C \subseteq R^{d} \times {- 1, + 1}$ . Thus $Y$ is uniform on ${- 1, + 1}$ and, conditional on $Y = y$ , $X$ has law $N_{d} (y θ, σ^{2} I_{d})$ . In the normalized model used below, $∥ θ ∥_{2} = \sqrt{d}$ . Independent training and test observations are drawn from the corresponding finite product law.

Definition references

Multivariate normal law, including singular covariance: $N_{d} (m, Σ)$ is the Borel law whose linear projections have the corresponding scalar normal laws; its construction assumes AC.

The Axiom of Choice: AC asserts that every family of nonempty sets has a choice function.

Probability measures and probability spaces: a probability measure is a measure of total mass one.

Schmidt et al., Definition 1 and the Gaussian-model setup.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Binary-feature Bernoulli model

Definition

Let $d \geq 1$ be an integer, let $θ \in {- 1, + 1}^{d}$ , and let $0 < τ \leq 1 / 2$ . The $(θ, τ)$ binary-feature Bernoulli model is the probability law $P_{θ, τ}$ on ${- 1, + 1}^{d} \times {- 1, + 1}$ defined by $P_{θ, τ} ({(x, y)}) = \frac{1}{2} \prod_{j = 1}^{d} [(\frac{1}{2} + τ) 1_{{x_{j} = y θ_{j}}} + (\frac{1}{2} - τ) 1_{{x_{j} = - y θ_{j}}}] .$ Thus $Y$ is uniform on ${- 1, + 1}$ and, conditional on $Y = y$ , the feature coordinates are independent, with $X_{j} = y θ_{j}$ with probability $1 / 2 + τ$ and $X_{j} = - y θ_{j}$ with probability $1 / 2 - τ$ . The displayed masses sum to one because each coordinate factor sums to one over its two possible signs and the label weights sum to one. The uniform-prior experiment used below draws $Θ$ uniformly from ${- 1, + 1}^{d}$ and then draws observations conditionally independently from $P_{Θ, τ}$ .

Definition references

Probability measures and probability spaces: a probability law has total mass one.

Independent random elements: for each fixed $y$ , coordinate independence is taken under the conditional probability law given $Y = y$ ; in the prior experiment, observation independence is taken under each conditional law given $Θ = θ$ .

Schmidt et al., Definition 7 and the Bernoulli model setup.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Class-weighted mean classifier

Definition

Input: an integer $n \geq 1$ , an integer $d \geq 1$ , and an ordered labeled sample $((x_{1}, y_{1}), \dots, (x_{n}, y_{n}))$ with $x_{i} \in R^{d}$ and $y_{i} \in {- 1, + 1}$ . Compute $w = \frac{1}{n} \sum_{i = 1}^{n} y_{i} x_{i} .$ Output the vector $w$ and the binary linear classifier $f_{w} : R^{d} \to {- 1, + 1}$ defined by $f_{w} (x) = + 1$ when $⟨ w, x ⟩ \geq 0$ and $f_{w} (x) = - 1$ when $⟨ w, x ⟩ < 0$ . The zero-score tie is assigned to $+ 1$ .

Definition references

Schmidt et al., class-weighted sample mean in Theorem 5 and normalized direction in Theorem 21.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Coordinatewise threshold preprocessing

Definition

Input: an integer $d \geq 1$ and a vector $x \in R^{d}$ . Output $T (x) \in {- 1, + 1}^{d}$ with $T (x)_{i} = {\begin{cases} + 1, & x_{i} \geq 0, \\ - 1, & x_{i} < 0 \end{cases} (1 \leq i \leq d) .$

Definition references

Schmidt et al., thresholding operation and Theorem 10.

Kolter–Madry, Chapter 2, binary linear classifiers.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Gaussian vector norm and maximum-coordinate tails

Statement

Assume AC. Let $d \geq 1$ be an integer, $σ > 0$ , and $G \sim N_{d} (0, σ^{2} I_{d})$ . For every $t \geq 0$ and $s \geq 0$ , $P (∥ G ∥_{2} \geq σ \sqrt{d} + t) \leq \exp ⁣ (- \frac{t^{2}}{2 σ^{2}}), P (∥ G ∥_{\infty} > s) \leq 2 d \exp ⁣ (- \frac{s^{2}}{2 σ^{2}}) .$ For every unit vector $u \in R^{d}$ and $s \geq 0$ , each one-sided projection tail satisfies $P (⟨ u, G ⟩ \geq s) \leq \exp ⁣ (- \frac{s^{2}}{2 σ^{2}}), P (⟨ u, G ⟩ \leq - s) \leq \exp ⁣ (- \frac{s^{2}}{2 σ^{2}}) .$ Consequently, for $d \geq 2$ , $P ⁣ (∥ G ∥_{\infty} \leq 2 σ \sqrt{2 \log d}) \geq 1 - \frac{1}{d} .$

Statement references

Schmidt et al., Appendix A.1, Fact 12, PDF p. 22.

Facts & Assumptions

Given: Assume AC. Let $d \geq 1$ be finite, $σ > 0$ , and $G \sim N_{d} (0, σ^{2} I_{d})$ .

[A1]

Assume the Axiom of Choice, stated as the existence of a choice function for every family of nonempty sets. It is used by the supplied finite-dimensional Gaussian construction. The Axiom of Choice.

[F1]

Under AC, $G$ can be represented in law as $σ (Z_{1}, \dots, Z_{d})$ with independent standard normal coordinates, each having density $(2 π)^{- 1 / 2} e^{- x^{2} / 2}$ . Multivariate normal law, including singular covariance, Standard normal and normal laws.

[F2]

For nonnegative Borel functions of independent real random variables, the expectation of their finite product factors, including when an expectation is extended-valued. Expectations factor over finite products of independent random variables.

[F3]

For a nonnegative random variable $U$ and $a > 0$ , $P (U \geq a) \leq E [U] / a$ . Markov's inequality for random variables.

[F4]

For $0 < u < 1$ , $- \log (1 - u) - u = \int_{0}^{u} v / (1 - v) d v$ . The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t.

[F5]

The probability of a finite union of events is at most the sum of their probabilities. The finite union bound.

Proof

1.1A1F1F2F4algebra

Put $Q = \sum_{j = 1}^{d} Z_{j}^{2}$ for the independent standard normal coordinates in [F1]. For $0 < λ < 1 / 2$ , integrating their scalar density and substituting $u = \sqrt{1 - 2 λ} x$ gives $E e^{λ Z_{j}^{2}} = (1 - 2 λ)^{- 1 / 2}$ . By [F2] and the exponential addition formula, $E e^{λ (Q - d)} = e^{- d λ} (1 - 2 λ)^{- d / 2}$ . With $u = 2 λ$ , [F4] gives $- \log (1 - 2 λ) - 2 λ \leq (2 λ)^{2} / [2 (1 - 2 λ)]$ , so $\log E e^{λ (Q - d)} \leq d λ^{2} / (1 - 2 λ)$ .

1.2A1F1F3algebra

For any unit vector $u$ , [F1] gives $⟨ u, G ⟩ \sim N (0, σ^{2})$ . Completing the square in the scalar normal density gives $E e^{v ⟨ u, G ⟩} = e^{v^{2} σ^{2} / 2}$ . Applying [F3] with $v = s / σ^{2}$ to the upper tail and with $v = - s / σ^{2}$ to the lower tail proves both one-sided projection bounds for $s > 0$ ; for $s = 0$ they hold because each right side is $1$ .

2.1step 1.1F3algebra

For $r > 0$ , apply [F3] to $e^{λ (Q - d)}$ at threshold $e^{λ (2 \sqrt{d r} + 2 r)}$ . Choosing $λ = \sqrt{r} / (\sqrt{d} + 2 \sqrt{r})$ gives $0 < λ < 1 / 2$ and, by step 1.1, the exponent $- λ (2 \sqrt{d r} + 2 r) + d λ^{2} / (1 - 2 λ) = - r$ . Therefore $P (Q \geq d + 2 \sqrt{d r} + 2 r) \leq e^{- r}$ .

3.1step 2.1algebra

For $t > 0$ , set $a = t / σ$ and $r = a^{2} / 2$ . The event $∥ G ∥_{2} \geq σ (\sqrt{d} + a)$ is $Q \geq d + 2 \sqrt{d} a + a^{2}$ , and this threshold is at least $d + 2 \sqrt{d r} + 2 r = d + \sqrt{2 d} a + a^{2}$ . Step 2.1 bounds its probability by $e^{- a^{2} / 2}$ . When $t = 0$ , the claimed upper bound is $1$ and holds directly.

4.1step 1.2F5algebra∎

Apply the two one-sided bounds in step 1.2 to each coordinate unit vector and combine them with [F5]. This gives $P (∥ G ∥_{\infty} > s) \leq 2 d e^{- s^{2} / (2 σ^{2})}$ . For $d \geq 2$ , substitute $s = 2 σ \sqrt{2 \log d}$ ; the failure probability is at most $2 d e^{- 4 \log d} = 2 / d^{3} \leq 1 / d$ .

References

Multivariate normal law, including singular covariance: the Gaussian vector has an independent standard-normal coordinate construction under AC.

Expectations factor over finite products of independent random variables: factors the nonnegative coordinate mgfs.

Markov's inequality for random variables: converts the mgf bounds to one-sided tails.

The finite union bound: combines coordinate tails.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Signal alignment of a Gaussian sample mean

Statement

Assume AC. Let $d, n \geq 1$ be integers, let $σ > 0$ , let $θ \in R^{d}$ satisfy $∥ θ ∥_{2} = \sqrt{d}$ , and draw independent observations $(X_{i}, Y_{i})_{i = 1}^{n}$ from the two-class spherical Gaussian model with parameters $θ, σ$ . Put $W = n^{- 1} \sum_{i = 1}^{n} Y_{i} X_{i}$ , and define $\hat{W} = W / ∥ W ∥_{2}$ when $W \neq 0$ and $\hat{W} = e_{1}$ when $W = 0$ . Then $P ⁣ (⟨ \hat{W}, θ ⟩ \leq \frac{2 \sqrt{n} - 1}{2 \sqrt{n} + 4 σ} \sqrt{d}) \leq 2 \exp ⁣ (- \frac{d}{8 (σ^{2} + 1)}) .$

Statement references

Schmidt et al., Lemma 16 and its proof, Appendix A.1, PDF pp. 22–23.

Facts & Assumptions

Given: The hypotheses in the Statement.

[A1]

Assume the Axiom of Choice. It is used through the Gaussian-law, scalar characteristic-function uniqueness, Cramer–Wold, and Gaussian concentration suppliers. The Axiom of Choice.

[F1]

Under the model, conditional on $Y_{i} = y$ , $X_{i}$ has law $N_{d} (y θ, σ^{2} I_{d})$ ; the sample pairs are independent. Two-class spherical Gaussian model.

[F2]

A multivariate normal law has the stated scalar normal projection laws; scalar normal laws have characteristic function $\exp (i m t - v t^{2} / 2)$ when their mean is $m$ and variance is $v$ . Multivariate normal law, including singular covariance, Characteristic function of a normal law.

[F3]

Equal characteristic functions determine equal scalar Borel probability laws under AC. Uniqueness of a law from its characteristic function.

[F4]

Equal laws of all one-dimensional linear projections determine a Borel probability law on $R^{d}$ under AC. Cramer wold device.

[F5]

Applying a measurable map separately to independent random elements preserves independence. Independent random elements, Measurable coordinatewise functions preserve independence.

[F6]

Characteristic functions transform under affine maps and factor for finite independent sums. Characteristic functions under affine maps and independent sums.

[F7]

If $G \sim N_{d} (0, η^{2} I_{d})$ , then $P (∥ G ∥_{2} \geq η \sqrt{d} + t) \leq e^{- t^{2} / (2 η^{2})}$ , and for every unit $u$ , $P (⟨ u, G ⟩ \leq - s) \leq e^{- s^{2} / (2 η^{2})}$ for $t, s \geq 0$ . Gaussian vector norm and maximum-coordinate tails.

[F8]

The probability of a union of two events is at most the sum of their probabilities. The finite union bound.

Proof

1.1A1F1F2F3F4F5

For each $i$ , the map $(x, y) \mapsto y x$ is Borel, so [F5] makes $Z_{i} : = Y_{i} X_{i}$ independent. For each $u \in R^{d}$ and $y \in {- 1, + 1}$ , [F1]–[F2] give the conditional characteristic function $E [e^{i t ⟨ u, y X_{i} ⟩} ∣ Y_{i} = y] = \exp (i t ⟨ u, θ ⟩ - t^{2} σ^{2} ∥ u ∥_{2}^{2} / 2)$ : the mean term uses $y^{2} = 1$ and the variance term uses $y^{2} = 1$ . This does not depend on $y$ , so the same formula holds after averaging over the two labels. By [F3] each projection has law $N (⟨ u, θ ⟩, σ^{2} ∥ u ∥_{2}^{2})$ , and [F4] identifies $Z_{i} \sim N_{d} (θ, σ^{2} I_{d})$ .

2.1step 1.1A1F2F3F4F5F6

Put $E_{i} = Z_{i} - θ$ . They remain independent by [F5]. For each fixed $u$ , their projections are independent scalar $N (0, σ^{2} ∥ u ∥_{2}^{2})$ variables by step 1.1 and [F2]. By [F6], the characteristic function of $n^{- 1} \sum_{i} ⟨ u, E_{i} ⟩$ is $\exp (- t^{2} σ^{2} ∥ u ∥_{2}^{2} / (2 n))$ ; [F3] identifies this as $N (0, σ^{2} ∥ u ∥_{2}^{2} / n)$ . Since this holds for every $u$ , [F4] gives $\overline{E} : = n^{- 1} \sum_{i} E_{i} \sim N_{d} (0, σ^{2} I_{d} / n)$ . Thus $W = θ + \overline{E}$ .

3.1step 2.1F7

Set $η = σ / \sqrt{n}$ . Apply the norm tail in [F7] to $\overline{E}$ with $t = η \sqrt{d}$ . Except on an event of probability at most $e^{- d / 2}$ , $∥ \overline{E} ∥_{2} < 2 η \sqrt{d}$ , so $∥ W ∥_{2} \leq \sqrt{d} + 2 σ \sqrt{d / n} = (1 + 2 σ / \sqrt{n}) \sqrt{d}$ .

3.2step 2.1F7algebra

Apply the projection tail in [F7] to $u = θ / \sqrt{d}$ and $s = \sqrt{d} / (2 \sqrt{n})$ . Except on an event of probability at most $e^{- d / (8 σ^{2})}$ , $⟨ \overline{E}, θ ⟩ > - d / (2 \sqrt{n})$ , hence $⟨ W, θ ⟩ > d (1 - 1 / (2 \sqrt{n})) > 0$ .

4.1step 3.1step 3.2A1F8algebra∎

On the intersection of the events in steps 3.1 and 3.2, $W \neq 0$ , and division by the positive upper bound for $∥ W ∥_{2}$ yields $⟨ \hat{W}, θ ⟩ \geq \frac{1 - 1 / (2 \sqrt{n})}{1 + 2 σ / \sqrt{n}} \sqrt{d} = \frac{2 \sqrt{n} - 1}{2 \sqrt{n} + 4 σ} \sqrt{d}$ . By [F8], the failure probability is at most $e^{- d / 2} + e^{- d / (8 σ^{2})} \leq 2 e^{- d / (8 (σ^{2} + 1))}$ , since both exponents dominate $d / (8 (σ^{2} + 1))$ .

References

Two-class spherical Gaussian model: the conditional Gaussian law and independent training sample convention.

Gaussian vector norm and maximum-coordinate tails: the Euclidean norm and one-sided projection tails.

CorollaryStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

One-sample natural error in the Gaussian model

Statement

Assume AC. Let $d \geq 1$ be an integer, let $θ \in R^{d}$ satisfy $∥ θ ∥_{2} = \sqrt{d}$ , let $0 < β < 1$ , and let $σ > 0$ satisfy $σ \leq d^{1 / 4} / (5 \sqrt{\log (1 / β)})$ . Draw one training pair $(X_{0}, Y_{0})$ from the two-class spherical Gaussian model with parameters $θ, σ$ . Set $W = Y_{0} X_{0}$ and define the unit vector $\hat{W} = W / ∥ W ∥_{2}$ for $W \neq 0$ and $\hat{W} = e_{1}$ for $W = 0$ . Define $h_{u} (x) = + 1$ when $⟨ u, x ⟩ \geq 0$ and $h_{u} (x) = - 1$ otherwise, and define its natural error by ${err}_{θ, σ} (u) = P_{(X, Y) \sim P_{θ, σ}} (h_{u} (X) \neq Y)$ . Then $P_{(X_{0}, Y_{0}) \sim P_{θ, σ}} ⁣ ({err}_{θ, σ} (\hat{W}) \leq β) \geq 1 - 2 \exp ⁣ (- \frac{d}{8 (σ^{2} + 1)}) .$

Statement references

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

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 a one-sample Gaussian model pair, the class-weighted direction satisfies $⟨ \hat{W}, θ ⟩ \geq \sqrt{d} / (2 + 4 σ)$ except with probability at most $2 e^{- d / (8 (σ^{2} + 1))}$ . Signal alignment of a Gaussian sample mean.

[F2]

For every unit $u$ , $⟨ u, X ⟩$ conditional on $Y = y$ is $N (y ⟨ u, θ ⟩, σ^{2})$ ; scalar normal laws have their stated characteristic functions, affine transformations preserve the characteristic-function formula, and equal characteristic functions determine equal scalar laws under AC. 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]

If $G \sim N (0, σ^{2})$ and $s \geq 0$ , then $P (G \leq - s) \leq e^{- s^{2} / (2 σ^{2})}$ ; the centered normal law is symmetric about zero. Gaussian vector norm and maximum-coordinate tails, Characteristic function of a normal law, Uniqueness of a law from its characteristic function.

[F4]

The natural logarithm is increasing, has $\log (a b) = \log a + \log b$ , and $\log 2 = \int_{1}^{2} d x / x > 1 / 2$ . 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.

Proof

1.1givenA1F1

Apply [F1] with $n = 1$ . With probability at least $1 - 2 e^{- d / (8 (σ^{2} + 1))}$ over the training pair, the learned unit vector satisfies $⟨ \hat{W}, θ ⟩ \geq a : = \sqrt{d} / (2 + 4 σ) > 0$ .

1.2givenF2F3algebra

Fix any unit vector $u$ with $c : = ⟨ u, θ ⟩ \geq a$ . Conditional on $Y = y$ , the characteristic function of $Y ⟨ u, X ⟩$ at $t$ is $\exp (i t c - σ^{2} t^{2} / 2)$ by [F2], independently of $y$ . Thus the signed test margin has law $N (c, σ^{2})$ . The tie convention implies ${h_{u} (X) \neq Y} \subseteq {Y ⟨ u, X ⟩ \leq 0}$ , so [F3] gives ${err}_{θ, σ} (u) \leq \exp (- c^{2} / (2 σ^{2})) \leq \exp (- a^{2} / (2 σ^{2}))$ .

2.1step 1.2F3algebra

If $β \geq 1 / 2$ , then $c > 0$ and symmetry of the centered normal in [F3] gives ${err}_{θ, σ} (u) \leq P (G \leq 0) = 1 / 2 \leq β$ .

2.2givenF4step 1.2algebra

Suppose $β < 1 / 2$ and put $L = \log (1 / β)$ . By [F4], $L > \log 2 > 1 / 2$ . Since $d^{1 / 4} \geq 1$ , the hypothesis gives $2 + 4 σ \leq (2 + 4 \sqrt{2} / 5) d^{1 / 4}$ and $σ^{2} L \leq \sqrt{d} / 25$ . Therefore $2 (2 + 4 σ)^{2} σ^{2} L \leq \frac{2}{25} (2 + 4 \sqrt{2} / 5)^{2} d < d$ , where the final strict inequality follows from $2 + 4 \sqrt{2} / 5 < 5 / \sqrt{2}$ . Hence $a^{2} / (2 σ^{2}) > L$ , and step 1.2 gives ${err}_{θ, σ} (u) \leq e^{- L} = β$ .

3.1step 1.1step 1.2step 2.1step 2.2∎

On the alignment event in step 1.1, the unit vector $u = \hat{W}$ meets the hypothesis of step 1.2. Steps 2.1 and 2.2 cover the two exhaustive cases for $β$ , so its natural error is at most $β$ throughout that event. The event probability from step 1.1 is the asserted lower bound.

References

Signal alignment of a Gaussian sample mean: supplies the one-sample direction bound.

Gaussian vector norm and maximum-coordinate tails: supplies the one-sided Gaussian projection tail used for test error.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

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.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

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.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Gaussian normal-prior posterior

Statement

Assume AC. Let $d \geq 1$ , $σ > 0$ , and $n \geq 1$ . Let $Θ \sim N_{d} (0, I_{d})$ , and, conditional on $Θ$ , let $Z_{1}, \dots, Z_{n}$ be independent with law $N_{d} (Θ, σ^{2} I_{d})$ . Let $Y_{1}, \dots, Y_{n}$ be independent uniform signs, independent of $(Θ, Z_{1}, \dots, Z_{n})$ . Put $\overset{ˉ}{Z} = n^{- 1} \sum_{i = 1}^{n} Z_{i}$ . The conditional law of $Θ$ given $(Z_{1}, \dots, Z_{n}, Y_{1}, \dots, Y_{n})$ is $N_{d} ⁣ (\frac{n}{σ^{2} + n} \overset{ˉ}{Z}, \frac{σ^{2}}{σ^{2} + n} I_{d}) .$ For $n = 0$ , with no observations, the conditional law is the prior $N_{d} (0, I_{d})$ .

Statement references

Multivariate normal law, including singular covariance: the finite-dimensional Gaussian laws and their singular-covariance convention.

A positive-definite multivariate normal law has its Gaussian density: the Lebesgue density formula for each positive-definite Gaussian law used here.

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

Facts & Assumptions

Given: Assume AC and the Gaussian prior, conditionally independent observations, and independent labels in the Statement.

[A1]

AC supplies the finite-dimensional multivariate-normal law construction and its positive-definite density formula. The Axiom of Choice, Multivariate normal law, including singular covariance, A positive-definite multivariate normal law has its Gaussian density.

[F1]

Independent random elements have the finite product joint law. Independent random elements, Independent random elements have product joint law.

[F2]

A positive-definite $N_{d} (m, Σ)$ law has density proportional to $\det (Σ)^{- 1 / 2} \exp (- \frac{1}{2} (x - m)^{T} Σ^{- 1} (x - m))$ . A positive-definite multivariate normal law has its Gaussian density.

[F3]

Nonnegative product-measurable densities can be integrated in either order. Tonelli's theorem for nonnegative measurable functions on a sigma-finite product.

Proof

1.1A1F1F2algebra

For $n \geq 1$ , the joint density of $(Θ, Z_{1}, \dots, Z_{n})$ is proportional to $\exp ⁣ (- \frac{1}{2} ∥ θ ∥_{2}^{2} - \frac{1}{2 σ^{2}} \sum_{i = 1}^{n} ∥ z_{i} - θ ∥_{2}^{2})$ . Indeed, the prior density and each conditional Gaussian density are given by [F2], and their product is the joint density by conditional independence and [F1]. The independent labels contribute a constant factor $2^{- n}$ , so conditioning on their observed values does not change the $θ$ -dependent factor.

2.1step 1.1F2algebra

Write $\overset{ˉ}{z} = n^{- 1} \sum_{i} z_{i}$ . Expanding squares gives $\sum_{i} ∥ z_{i} - θ ∥_{2}^{2} = \sum_{i} ∥ z_{i} - \overset{ˉ}{z} ∥_{2}^{2} + n ∥ θ - \overset{ˉ}{z} ∥_{2}^{2}$ . Completing the remaining square in $θ$ yields $∥ θ ∥_{2}^{2} + \frac{n}{σ^{2}} ∥ θ - \overset{ˉ}{z} ∥_{2}^{2} = \frac{σ^{2} + n}{σ^{2}} {∥ θ - \frac{n}{σ^{2} + n} \overset{ˉ}{z} ∥}_{2}^{2} + \frac{n}{σ^{2} + n} ∥ \overset{ˉ}{z} ∥_{2}^{2}$ . The final term is independent of $θ$ . The normalized conditional density is therefore the Gaussian density in the Statement, with positive covariance $\frac{σ^{2}}{σ^{2} + n} I_{d}$ .

3.1step 2.1F1F2F3

The density ratio in step 2.1 defines a measurable probability kernel in the observed vectors because its mean is linear in $\overset{ˉ}{z}$ and its covariance is fixed; [F2] gives unit mass. Applying [F3] to the nonnegative joint density verifies the conditional-law identity on every pair of Borel sets. Since the labels are independent of $(Θ, Z_{1}, \dots, Z_{n})$ , the same kernel is the conditional law after adjoining the labels.

4.1givenF1∎

When $n = 0$ , the observed sigma-algebra contains no data, so conditioning leaves the prior law unchanged; the labels, if supplied, are independent of $Θ$ .

References

The Axiom of Choice: AC is used by the Gaussian construction and density supplier.

Independent random elements have product joint law: finite independent samples have product joint law.

Tonelli's theorem for nonnegative measurable functions on a sigma-finite product: justifies the density integrations defining the conditional kernel.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Robust sample lower bound in the Gaussian model

Statement

Assume AC. Let $d \geq 1$ be an integer, let $n \geq 0$ be an integer, let $σ > 0$ and $ϵ \geq 0$ , draw $Θ \sim N_{d} (0, I_{d})$ , and, conditional on $Θ$ , draw $n$ independent training pairs $S = ((X_{i}, Y_{i}))_{i = 1}^{n}$ from the two-class spherical Gaussian model with parameters $Θ, σ$ . Let $S_{n} = (R^{d} \times {- 1, + 1})^{n}$ , and let $F : S_{n} \times R^{d} \to {- 1, + 1}$ be a Borel learning rule; write $f_{S} (x) = F (S, x)$ . Define $m (S) = (σ^{2} + n)^{- 1} \sum_{i = 1}^{n} Y_{i} X_{i}$ , with the empty sum equal to zero. Define the expected robust risk as the outer expectation over $(Θ, S)$ of $R_{P_{Θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})$ , using the same measurable-majorant convention as robust risk; when this random robust risk is measurable, this is its ordinary expectation. Then $E_{Θ, S}^{*} ⁣ [R_{P_{Θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})] \geq \frac{1}{2} P_{V \sim N_{d} (0, I_{d})} ⁣ (\sqrt{\frac{n}{σ^{2} + n}} ∥ V ∥_{\infty} \leq ϵ) .$ Consequently, if $d \geq 2$ and $n \leq ϵ^{2} σ^{2} / (8 \log d)$ , then $E_{Θ, S}^{*} ⁣ [R_{P_{Θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})] \geq \frac{1}{2} (1 - \frac{1}{d}) .$

Statement references

Schmidt et al., Theorem 11 and Corollary 23, Appendix A.2, PDF pp. 27–30.

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

Facts & Assumptions

Given: The hypotheses in the Statement.

[A1]

Assume the Axiom of Choice, used by the Gaussian construction, posterior, normal characteristic-function uniqueness, Cramer–Wold and concentration suppliers. The Axiom of Choice.

[F1]

In the Gaussian model, conditional on $Θ = θ$ and $Y_{i} = y$ , the projection $⟨ u, X_{i} ⟩$ is $N (y ⟨ u, θ ⟩, σ^{2} ∥ u ∥_{2}^{2})$ ; scalar normal characteristic functions and affine maps identify $Y_{i} X_{i} \sim N_{d} (θ, σ^{2} I_{d})$ , independently of the label. 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, Cramer wold device.

[F2]

Given the class-weighted observations $Z_{i} = Y_{i} X_{i}$ , the posterior is $N_{d} (m (S), v I_{d})$ with $m (S) = (σ^{2} + n)^{- 1} \sum_{i} Z_{i}$ and $v = σ^{2} / (σ^{2} + n)$ ; for $n = 0$ it is the prior. Gaussian normal-prior posterior.

[F3]

Robust risk is the infimum of expectations of nonnegative measurable majorants of pointwise robust loss, and the $ℓ_{\infty}$ threat admits every shift of norm at most $ϵ$ . Measurable threat correspondences and robust risk.

[F4]

If a nonnegative function dominates a measurable nonnegative function, its outer expectation is at least the ordinary expectation of the latter; this follows because every measurable majorant dominates it and the nonnegative integral is monotone. Monotonicity and nonnegative homogeneity of the nonnegative integral.

[F5]

For product-measurable nonnegative functions, Tonelli's theorem gives measurable parameter integrals and permits exchange of the integration order. Tonelli's theorem for nonnegative measurable functions on a sigma-finite product.

[F6]

A uniform sign independent of a feature vector is misclassified with probability exactly $1 / 2$ by every Borel binary classifier; this is proved by splitting the two disjoint label-error events in the common-shift lemma. Common shifts force binary robust risk at least one half.

[F7]

If $V \sim N_{d} (0, I_{d})$ and $d \geq 2$ , then $P (∥ V ∥_{\infty} \leq 2 \sqrt{2 \log d}) \geq 1 - 1 / d$ . Gaussian vector norm and maximum-coordinate tails.

[F8]

The natural logarithm is increasing and $\log d > 0$ for $d \geq 2$ . The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm.

[F9]

Independent random elements remain independent after coordinatewise measurable maps are applied. Independent random elements, Measurable coordinatewise functions preserve independence.

Proof

1.1A1F1F9

Fix $θ$ . For any $u \in R^{d}$ and label $y$ , the characteristic function of $⟨ u, Y_{i} X_{i} ⟩$ conditional on $Y_{i} = y$ is $\exp (i t ⟨ u, θ ⟩ - t^{2} σ^{2} ∥ u ∥_{2}^{2} / 2)$ : multiplying the conditional normal projection by $y$ multiplies its mean by $y$ and its frequency by $y$ , so $y^{2} = 1$ in both terms. This law is independent of $y$ ; scalar uniqueness [F1] identifies each projection, and Cramer–Wold [F1] gives $Y_{i} X_{i} \sim N_{d} (θ, σ^{2} I_{d})$ independent of $Y_{i}$ . Independence of the training pairs and measurable coordinate transformations preserve independence across $i$ , so the class-weighted observations have the independent Gaussian likelihood and labels required by [F2].

1.2givenF2algebra

By [F2], for every realized sample $S$ , the posterior mean is $m (S)$ and the posterior covariance is $v I_{d}$ where $v = σ^{2} / (σ^{2} + n)$ . The formula also gives $m = 0, v = 1$ when $n = 0$ . The map $S \mapsto m (S)$ is Borel because it is a finite sum of coordinate products and division by the positive constant $σ^{2} + n$ .

1.3givenF3algebra

Fix $θ, S$ with $∥ m (S) ∥_{\infty} \leq ϵ$ . For a fresh test pair write $X = Y θ + G$ with $Y$ uniform and $G \sim N_{d} (0, σ^{2} I_{d})$ independent. The perturbation $δ = - Y m (S)$ is admissible by [F3] and sends $X$ to $Y (θ - m (S)) + G$ . Thus the pointwise robust loss is at least $1 {F (S, Y (θ - m (S)) + G) \neq Y}$ . This indicator is measurable in the test pair, so every measurable majorant in [F3] has expectation at least its probability; therefore the fixed-parameter robust risk is at least that probability.

2.1step 1.2step 1.3F4F5

Define $H (S, θ)$ to be zero when $∥ m (S) ∥_{\infty} > ϵ$ , and otherwise to be the probability in step 1.3. The classifier family and $m$ are Borel, so the shifted error indicator is product-measurable in $(S, θ, Y, G)$ ; [F5] makes $H$ measurable. Step 1.3 gives $H (S, θ) \leq R_{P_{θ, σ}, Δ_{ϵ}}^{r o b} (f_{S})$ pointwise. By [F4], taking the outer expectation over $(Θ, S)$ yields a lower bound by $E [H (Θ, S)]$ .

3.1step 1.2step 2.1A1F1F2F5F6

Conditional on $S$ , write $Θ = m (S) + R$ with $R \sim N_{d} (0, v I_{d})$ by [F2]. The fresh label $Y$ and noise $G$ are independent of $R$ . For either sign $y$ , $y R + G$ has law $N_{d} (0, (v + σ^{2}) I_{d})$ : each projection has the product characteristic function of independent centered scalar normals, and [F1] identifies the vector law. This conditional law is the same for both labels, so $U : = Y R + G$ is independent of the uniform label. By [F6], $P (F (S, U) \neq Y ∣ S) = 1 / 2$ . Tonelli and the posterior identity [F2] now give $E [H (Θ, S)] = \frac{1}{2} P_{S} (∥ m (S) ∥_{\infty} \leq ϵ)$ .

4.1step 1.1step 1.2A1F1algebra

If $n \geq 1$ , conditional on $Θ$ , the sample mean $\overset{ˉ}{Z} = n^{- 1} \sum_{i} Y_{i} X_{i}$ has all projections $N (⟨ u, Θ ⟩, σ^{2} ∥ u ∥_{2}^{2} / n)$ by the independent normal laws in step 1.1 and [F1]. Averaging the scalar characteristic function over $Θ \sim N_{d} (0, I_{d})$ shows each projection of $\overset{ˉ}{Z}$ is $N (0, (1 + σ^{2} / n) ∥ u ∥_{2}^{2})$ ; [F1] then gives $\overset{ˉ}{Z} \sim N_{d} (0, (1 + σ^{2} / n) I_{d})$ . Since $m = \frac{n}{σ^{2} + n} \overset{ˉ}{Z}$ , its law is $N_{d} (0, \frac{n}{σ^{2} + n} I_{d})$ . For $n = 0$ , $m = 0$ and the same event probability is one. Therefore $P_{S} (∥ m (S) ∥_{\infty} \leq ϵ) = P_{V \sim N_{d} (0, I_{d})} (\sqrt{n / (σ^{2} + n)} ∥ V ∥_{\infty} \leq ϵ)$ . Combining this with step 3.1 proves the first inequality.

5.1step 4.1F7F8algebra∎

Suppose $d \geq 2$ and $n \leq ϵ^{2} σ^{2} / (8 \log d)$ . If $n = 0$ , the event in step 4.1 has probability one. If $n > 0$ , then $\sqrt{n / (σ^{2} + n)} \leq \sqrt{n} / σ \leq ϵ / \sqrt{8 \log d}$ by [F8] and the sample-size hypothesis. On the event $∥ V ∥_{\infty} \leq 2 \sqrt{2 \log d}$ from [F7], it follows that $\sqrt{n / (σ^{2} + n)} ∥ V ∥_{\infty} \leq ϵ$ . Thus the probability in step 4.1 is at least $1 - 1 / d$ , and the first inequality gives the second assertion.

References

Gaussian normal-prior posterior: supplies the exact posterior mean and covariance, including the empty-sample case.

Common shifts force binary robust risk at least one half: supplies the two-label averaging calculation after the common shift.

Gaussian vector norm and maximum-coordinate tails: supplies the maximum-coordinate Gaussian event used in Corollary 23.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Tail bound for finite sums of independent signs

Statement

Let $ξ_{1}, \dots, ξ_{m}$ be independent random variables with values in ${- 1, + 1}$ , let $c_{1}, \dots, c_{m} \in R$ , and put $V = \sum_{i = 1}^{m} c_{i}^{2}$ and $S = \sum_{i = 1}^{m} c_{i} (ξ_{i} - E ξ_{i})$ . For every $t > 0$ , if $V > 0$ then $P (S \geq t) \leq e^{- t^{2} / (2 V)}, P (S \leq - t) \leq e^{- t^{2} / (2 V)}, P (∣ S ∣ \geq t) \leq 2 e^{- t^{2} / (2 V)} .$ If $V = 0$ , then $S = 0$ almost surely and all three tail probabilities are zero. The empty sum $m = 0$ is included with $V = S = 0$ .

Statement references

Schmidt et al., Appendix B.2, Lemma 29 and proof of Theorem 31, PDF pp. 33–38.

Facts & Assumptions

Given: A finite independent family of sign-valued random variables, real coefficients, and $t > 0$ .

[A1]

No choice axiom is used; every construction and product is finite.

[F1]

Independence means independence of the sigma-algebras generated by the random variables. Independent random elements.

[F2]

Expectations are Lebesgue integrals against the probability law. Expectation of a nonnegative or integrable random variable.

[F3]

For a nonnegative random variable $U$ and $a > 0$ , $P (U \geq a) \leq E [U] / a$ . Markov's inequality for random variables.

[F4]

The natural logarithm differentiates as $1 / x$ , and $\exp (x + y) = \exp (x) \exp (y)$ . The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ , The exponential function is smooth and $(\exp)^{'} = \exp$ .

[F5]

A finite union of events has probability at most the sum of its event probabilities. The finite union bound.

[F6]

For independent real random variables and nonnegative Borel functions, the expectation of their finite product factors, including extended-valued expectations. Expectations factor over finite products of independent random variables.

Proof

1.1givenF2F4algebra

For one sign variable $ξ$ with $p = P (ξ = + 1)$ and $μ = E ξ = 2 p - 1$ , put $ψ (s) = \log E e^{s (ξ - μ)}$ . The two-point formula gives $ψ (s) = \log (p e^{s} + (1 - p) e^{- s}) - s μ$ , so $ψ (0) = ψ^{'} (0) = 0$ and $ψ^{''} (s) = \frac{4 p (1 - p)}{(p e^{s} + (1 - p) e^{- s})^{2}} \leq 1$ . The inequality follows from $4 a b \leq (a + b)^{2}$ with $a = p e^{s}$ and $b = (1 - p) e^{- s}$ . Integrating the second-derivative bound twice from $0$ to $s$ , in either direction, gives $ψ (s) \leq s^{2} / 2$ for every real $s$ ; if $p = 0$ or $p = 1$ , $ψ$ is identically zero and the same bound holds.

2.1step 1.1F4F6algebraF1

Apply step 1.1 to each $ξ_{i}$ with $s = λ c_{i}$ . The functions $x \mapsto e^{λ c_{i} (x - E ξ_{i})}$ are nonnegative Borel functions, so [F6] factors their expectations; [F4] combines the exponentials. Thus $E e^{λ S} = \prod_{i = 1}^{m} E e^{λ c_{i} (ξ_{i} - E ξ_{i})} \leq \exp ⁣ (\frac{λ^{2}}{2} \sum_{i = 1}^{m} c_{i}^{2}) = e^{λ^{2} V / 2}$ for every real $λ$ .

3.1F3step 2.1algebra

Suppose $V > 0$ and choose $λ = t / V > 0$ . Markov's inequality [F3] applied to $e^{λ S}$ and the MGF bound in step 2.1 give $P (S \geq t) \leq e^{- λ t + λ^{2} V / 2} = e^{- t^{2} / (2 V)}$ . Applying the same argument to $- S$ gives $P (S \leq - t) \leq e^{- t^{2} / (2 V)}$ .

4.1F5step 3.1algebra∎

By [F5], $P (∣ S ∣ \geq t) \leq P (S \geq t) + P (S \leq - t)$ , which gives the stated two-sided bound from step 3.1. If $V = 0$ , every $c_{i} = 0$ , so $S = 0$ almost surely; the empty-sum case is the same.

References

Markov's inequality for random variables: the MGF bound is converted to a tail by Markov's inequality.

Expectations factor over finite products of independent random variables: factors the expectations of the nonnegative exponential functions of the independent signs.

The finite union bound: combines the two one-sided tails.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Posterior-odds concentration in the Bernoulli model

Statement

Let $d \geq 1$ be an integer, $0 < τ \leq 1 / 4$ , and let $n \geq 0$ be an integer with $n \leq τ^{- 2}$ . Draw $Θ$ uniformly from ${- 1, + 1}^{d}$ and, conditionally on $Θ$ , draw $n$ independent observations $S = ((X_{i}, Y_{i}))_{i = 1}^{n}$ from the binary-feature Bernoulli model with parameters $Θ, τ$ . For each coordinate $j$ , define the posterior log odds $L_{j} (S) : = \log (P (Θ_{j} = + 1 ∣ S) / P (Θ_{j} = - 1 ∣ S))$ ; these probabilities are positive for every sample because $τ < 1 / 2$ . Then for every $j$ and every sample $S$ , $L_{j} (S) = \log ⁣ (\frac{1 + 2 τ}{1 - 2 τ}) \sum_{i = 1}^{n} Y_{i} X_{i j} .$ Moreover, the coordinates of $Θ$ are conditionally independent given $S$ . For every $0 < δ < 1$ , with probability at least $1 - δ$ over the joint prior-sample experiment, $\max_{1 \leq j \leq d} ∣ L_{j} (S) ∣ \leq 15 τ \sqrt{2 n \log ⁣ (\frac{2 d}{δ})} .$

Statement references

Schmidt et al., Appendix B.2, Lemma 29 and proof of Theorem 31, PDF pp. 33–38.

Facts & Assumptions

Given: The hypotheses in the Statement.

[F1]

Under fixed $Θ = θ$ , the signs $Y_{i} X_{i j} θ_{j}$ are independent over $i$ and each equals $+ 1$ with probability $1 / 2 + τ$ and $- 1$ with probability $1 / 2 - τ$ . Binary-feature Bernoulli model.

[F2]

The natural logarithm converts finite products to sums 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.

[F3]

For independent sign variables and coefficients $c_{i}$ , the centered sum has tails $P (∣ \sum_{i} c_{i} (ξ_{i} - E ξ_{i}) ∣ \geq t) \leq 2 e^{- t^{2} / (2 \sum_{i} c_{i}^{2})}$ . Tail bound for finite sums of independent signs.

[F4]

A union of finitely many events has probability at most the sum of their probabilities. The finite union bound.

Proof

1.1givenF1F2algebra

Fix a sample $S = ((x_{i}, y_{i}))_{i = 1}^{n}$ . The prior mass of each $θ$ is $2^{- d}$ , and the likelihood factors over coordinates because the model's conditional coordinate probabilities do. Write $L_{j} (t) = \prod_{i} [(1 / 2 + τ) 1_{{y_{i} x_{i j} = t}} + (1 / 2 - τ) 1_{{y_{i} x_{i j} = - t}}]$ for $t \in {- 1, + 1}$ . The posterior mass at $θ$ is proportional to $\prod_{j} L_{j} (θ_{j})$ , and its normalizing sum is $\prod_{j} (L_{j} (+ 1) + L_{j} (- 1))$ ; hence it factors as a product of coordinate posterior masses, proving conditional independence. The $j$ th marginal odds are $L_{j} (+ 1) / L_{j} (- 1) = ((1 / 2 + τ) / (1 / 2 - τ))^{\sum_{i} y_{i} x_{i j}}$ . Bayes' finite formula and [F2] give the displayed log identity. Positivity of both coordinate probabilities makes each posterior denominator nonzero.

1.2F2algebra

Put $a_{τ} = \log ((1 + 2 τ) / (1 - 2 τ))$ . With $x = 2 τ \leq 1 / 2$ , [F2] gives $a_{τ} = 2 \int_{0}^{x} (1 - u^{2})^{- 1} d u$ . For $0 \leq u \leq 1 / 2$ , $(1 - u^{2})^{- 1} = 1 + u^{2} / (1 - u^{2}) \leq 1 + 4 u^{2} / 3$ , so $a_{τ} \leq 2 x + 8 x^{3} / 9 = 4 τ + 64 τ^{3} / 9 \leq 40 τ / 9 < 5 τ$ .

1.3givenF1F3F4

Assume $n > 0$ , fix $θ$ and $j$ , and put $ξ_{i} = θ_{j} Y_{i} X_{i j}$ . By [F1], these are independent signs with mean $2 τ$ . Let $t = \sqrt{2 n \log (2 d / δ)}$ . [F3] with all coefficients equal to one gives conditional failure probability at most $2 e^{- t^{2} / (2 n)} = δ / d$ for $∣ \sum_{i} (ξ_{i} - 2 τ) ∣ > t$ . Since $∣ \sum_{i} Y_{i} X_{i j} ∣ = ∣ \sum_{i} ξ_{i} ∣$ , this proves $P (∣ \sum_{i} Y_{i} X_{i j} ∣ > 2 τ n + t ∣ Θ = θ) \leq δ / d$ . By [F4] and averaging over the finite prior, with probability at least $1 - δ$ every coordinate obeys $∣ \sum_{i} Y_{i} X_{i j} ∣ \leq 2 τ n + t$ .

2.1step 1.1step 1.2step 1.3F2algebra∎

Since $n \leq τ^{- 2}$ , $τ n \leq \sqrt{n}$ . Also $2 d / δ \geq 2$ and $\log 2 = \int_{1}^{2} d x / x > 1 / 2$ , so $t \geq \sqrt{n}$ . On the event from step 1.3, step 1.1 and step 1.2 now yield $∣ L_{j} (S) ∣ \leq 5 τ (2 τ n + t) \leq 15 τ t$ for every $j$ , which is the asserted bound. If $n = 0$ , the posterior equals the uniform prior, so every $L_{j} = 0$ and the claimed bound holds with equality.

References

Binary-feature Bernoulli model: conditional sign probabilities and coordinate independence.

Tail bound for finite sums of independent signs: the local, choice-free concentration estimate replacing the source's Hoeffding citation.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

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$ .

4 · Examples, counterexamples and false statements

None yet.

Adversarial robustness and robust risk

2 · Logical flowchart

3 · Definitions, theorems and proofs

Measurable threat correspondences and robust risk

Definition

Definition references

Two-class spherical Gaussian model

Definition

Definition references

Binary-feature Bernoulli model

Definition

Definition references

Class-weighted mean classifier

Definition

Definition references

Coordinatewise threshold preprocessing

Definition

Definition references

Gaussian vector norm and maximum-coordinate tails

Statement

Statement references

Facts & Assumptions

Proof

References

Signal alignment of a Gaussian sample mean

Statement

Statement references

Facts & Assumptions

Proof

References

One-sample natural error in the Gaussian model

Statement

Statement references

Facts & Assumptions

Proof

References

Robust sample upper bound in the Gaussian model

Statement

Statement references

Facts & Assumptions

Proof

References

Common shifts force binary robust risk at least one half

Statement

Statement references

Facts & Assumptions

Proof

References

Gaussian normal-prior posterior

Statement

Statement references

Facts & Assumptions

Proof

References

Robust sample lower bound in the Gaussian model

Statement

Statement references

Facts & Assumptions

Proof

References

Tail bound for finite sums of independent signs

Statement

Statement references

Facts & Assumptions

Proof

References

Posterior-odds concentration in the Bernoulli model

Statement

Statement references

Facts & Assumptions

Proof

References

Architecture-dependent robustness in the Bernoulli model

Statement

Statement references

Facts & Assumptions

Proof

References

4 · Examples, counterexamples and false statements

Sources