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.

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.

Depends on

Used by

One-sample natural error in the Gaussian model Corollary
Signal alignment of a Gaussian sample mean Lemma
Robust sample lower bound in the Gaussian model Theorem
Robust sample upper bound in the Gaussian model Theorem

Dependency tree · two levels

66 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, Fact 12 (standard reference, not scraped)