TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passjudge 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.

Sub-Gaussian projection risk bounds

Statement

Let $n \geq 1$ , let $V \subseteq R^{n}$ be a fixed subspace of dimension $r$ , and let $μ \in V$ . Suppose $Y = μ + ε$ , where $ε \in R^{n}$ is centered sub-Gaussian with proxy $σ^{2} \geq 0$ in the linear-functional sense of Sub-Gaussian variables and vectors, and sub-exponential variables. Put $\hat{μ} = P_{V} Y$ . Then $\hat{μ} - μ = P_{V} ε$ . If $r = 0$ or $σ^{2} = 0$ , this error is zero almost surely. If $r \geq 1$ and $σ^{2} > 0$ , for every $t > 0$ ,

$P (∥ \hat{μ} - μ ∥_{2}^{2} > t) \leq 2 \cdot 6^{r} \exp ⁣ (- \frac{t}{8 σ^{2}}) .$

Consequently, for every $0 < δ < 1$ ,

$P ⁣ (\frac{1}{n} ∥ \hat{μ} - μ ∥_{2}^{2} \leq \frac{8 σ^{2}}{n} [r \log 6 + \log ⁣ (\frac{2}{δ})]) \geq 1 - δ,$

and

$E [\frac{1}{n} ∥ \hat{μ} - μ ∥_{2}^{2}] \leq \frac{8 σ^{2}}{n} (r \log 6 + \log 2 + \frac{13}{10}) .$ For $r \geq 1$ , both bounds are at most $C σ^{2} (r + \log (1 / δ)) / n$ and $C σ^{2} r / n$ , respectively, for a universal constant $C$ . In the fixed-design model $Y = X θ^{*} + ε$ with $μ = X θ^{*} \in col (X)$ , this is the fitted vector of Fixed-design least squares as orthogonal projection.

Facts & Assumptions

Given: A fixed subspace $V \subseteq R^{n}$ , a mean vector $μ \in V$ , and centered vector noise satisfying the stated proxy inequality.

[F1]

A centered vector $Z \in R^{n}$ is sub-Gaussian with proxy $σ^{2}$ when $E e^{λ ⟨ u, Z ⟩} \leq e^{σ^{2} λ^{2} ∥ u ∥_{2}^{2} / 2}$ for all $u \in R^{n}$ and $λ \in R$ (Sub-Gaussian variables and vectors, and sub-exponential variables).

[F2]

A centered sub-Gaussian vector in $R^{q}$ with proxy $σ^{2}$ obeys $P (∥ Z ∥_{2} \geq a) \leq 2 (1 + 2 / ϵ)^{q} \exp ⁣ (- \frac{(1 - ϵ)^{2} a^{2}}{2 σ^{2}})$ for $a > 0$ , $0 < ϵ < 1$ , and $σ^{2} > 0$ ; proxy zero gives zero tail (Finite sub-Gaussian maxima and epsilon-net reduction).

[F3]

Orthogonal projection has its component in the subspace and its residual orthogonal to that subspace (The orthogonal projection $P_{W} v$ is the $W$ -component in $V = W \oplus W^{⊥}$ ).

[F4]

A finite-dimensional subspace has an orthonormal basis, including the empty basis in dimension zero (Every finite-dimensional real or complex inner product space has an orthonormal basis).

[F5]

The projection is linear and contractive (Finite-dimensional orthogonal projections are linear and contractive).

[F7]

In a fixed-design model, the fitted vector is the projection of the observation onto the design column space (Fixed-design least squares as orthogonal projection).

[F8]

Probability is countably subadditive (Basic identities for a probability measure).

[F9]

Risk is the expected loss of a decision rule under the sampling law (Loss functions and risk).

[F10]

Finite linear combinations of integrable random variables are integrable, and expectation is linear; hence linear combinations of the centered coordinates of $ε$ are centered (Linearity, monotonicity, and the modulus bound for expectation).

[F11]

The natural logarithm is the inverse of $\exp$ , is strictly increasing, and satisfies the product law and $\log 1 = 0$ (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F12]

For $T \geq 0$ , $c > 0$ , $t_{0} \geq 0$ , $h = c / 2$ , and $N \in N$ , $\min (T, t_{0} + N h) \leq t_{0} + h \sum_{j < N} 1_{{T > t_{0} + j h}} .$ If $P (T > t) \leq A \exp (- t / c)$ and $t_{0} = c \log A$ , monotone convergence and expectation linearity, with the Archimedean property giving $t_{0} + N h \to \infty$ , bound $E T$ by $t_{0} + h \sum_{j \geq 0} \exp (- j / 2)$ . The exponential series gives $\exp (1 / 2) \geq 13 / 8$ . Set $q = \exp (- 1 / 2) = 1 / \exp (1 / 2) \leq 8 / 13 < 1$ ; the addition law gives $\exp (- j / 2) = q^{j}$ by induction, and the geometric-series formula gives $\sum_{j \geq 0} \exp (- j / 2) = 1 / (1 - q) \leq 13 / 5$ (Monotone convergence for the integral, Every complete ordered field is Archimedean, The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ , The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , The real exponential function and the number $e$ by a power series, Integer powers $a^{m}$ , For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges).

Proof

1.1F1F4F10algebra

If $r \geq 1$ , choose an orthonormal basis $ϕ_{1}, \dots, ϕ_{r}$ of $V$ by [F4] and form the coordinate vector $Z = (⟨ ε, ϕ_{j} ⟩)_{j = 1}^{r}$ . Each coordinate is integrable and centered by [F10]. For any $u \in R^{r}$ and $λ \in R$ , $E e^{λ ⟨ u, Z ⟩} = E e^{λ ⟨ \sum_{j} u_{j} ϕ_{j}, ε ⟩} \leq e^{σ^{2} λ^{2} ∥ u ∥_{2}^{2} / 2}$ by [F1], since the basis is orthonormal. Thus $Z$ is a centered sub-Gaussian vector with the same proxy.

2.1F2F3step 1.1algebra

For $σ^{2} > 0$ , apply [F2] with $ϵ = 1 / 2$ to $Z$ . Since $(1 + 2 / ϵ)^{r} = 5^{r} \leq 6^{r}$ and $(1 - ϵ)^{2} / 2 = 1 / 8$ , this gives $P (∥ Z ∥_{2}^{2} > t) \leq 2 \cdot 6^{r} e^{- t / (8 σ^{2})}$ . The basis coordinates identify $∥ Z ∥_{2} = ∥ P_{V} ε ∥_{2}$ by [F3] and uniqueness of projection. If $σ^{2} = 0$ , [F2] gives zero probability that this norm exceeds any positive threshold.

3.1F5F8step 2.1given

By [F5], $\hat{μ} - μ = P_{V} (μ + ε) - μ = P_{V} ε$ , because $P_{V} μ = μ$ . If $r = 0$ , then $V = {0}$ and $μ = 0$ , so the error is zero; if $σ^{2} = 0$ , step 2.1 gives the same conclusion. For $σ^{2} = 0$ , the zero tail in step 2.1 gives $P (∥ P_{V} ε ∥_{2}^{2} > 1 / j) = 0$ for each integer $j \geq 1$ ; this positive-norm event is their countable union, so [F8] gives probability zero. The positive-rank, positive-proxy tail is step 2.1.

3.2F11step 2.1algebra

For $r \geq 1$ and $σ^{2} > 0$ , use step 2.1 with $t = 8 σ^{2} [r \log 6 + \log (2 / δ)]$ ; [F11] makes this threshold positive, and the right side is $δ$ , proving the probability bound after division by $n$ .

4.1F9F10F11F12step 2.1step 3.1algebra

Put $A = 2 \cdot 6^{r}$ , $c = 8 σ^{2}$ , $h = c / 2$ , $t_{0} = c \log A$ , and $T = ∥ \hat{μ} - μ ∥_{2}^{2}$ . In the positive-rank, positive-proxy case, the pointwise bound in [F12], expectation linearity [F10], and monotone convergence give $E T \leq t_{0} + h \sum_{j \geq 0} P (T > t_{0} + j h)$ . Step 2.1 and [F11] bound each probability by $\exp (- j / 2)$ ; [F12] bounds their sum by $13 / 5$ . Hence $E T \leq c (\log A + 13 / 10)$ . By [F11], $\log A = \log 2 + r \log 6$ ; division by $n$ gives the stated expected-error bound. By [F9], it is the expected risk under the squared fitted-value loss. The zero-error cases in step 3.1 also satisfy it.

5.1F7given∎

For a fixed-design model with $μ = X θ^{*} \in col (X)$ , take $V = col (X)$ . [F7] identifies $\hat{μ}$ with the estimator in Fixed-design least squares as orthogonal projection, so the displayed bounds apply to that fitted vector.

Depends on

Used by

BIC fitted-value risk bound Theorem
Sparse constrained least-squares risk bound Theorem

Dependency tree · two levels

96 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

Philippe Rigollet and Jan-Christian Hütter, High-Dimensional Statistics: Lecture Notes, Chapter 2, Theorem 2.2 and proof (standard reference, not scraped)
Sylvain Arlot, Model/estimator selection, Lecture on model selection, §§1–2 (standard reference, not scraped)