LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

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.

Depends on

Used by

One-sample natural error in the Gaussian model Corollary
Robust sample upper bound in the Gaussian model Theorem

Dependency tree · two levels

68 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 16 and Appendix A.1, PDF pp. 22–23 (standard reference, not scraped)
Rick Durrett, Probability: Theory and Examples, 5th ed., Gaussian laws and characteristic functions (standard reference, not scraped)
S. R. S. Varadhan, Probability Theory, independent random elements and characteristic functions (standard reference, not scraped)