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.

✓ 10 results · all verified · 8 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Decision-Theoretic Upper Bounds

1 · Prerequisites

2 · Summary

This page studies squared fitted-value loss for fixed-design least squares. Orthogonal projection gives a well-defined fit even when coefficients are not identifiable. It establishes an exact isotropic-noise risk identity, a sub-Gaussian projection bound, a sparse constrained least-squares upper bound, and a penalized support-search bound without design-rank or incoherence assumptions. The sparse bounds concern fitted values; they do not control coefficient error. The BIC statement assumes a nonempty true support and gives no zero right-hand side for the empty model. A matching minimax comparison is proved for the Gaussian sequence submodel with $n = d$ and $X = \sqrt{n} I_{n}$ ; it makes no lower-bound claim for general fixed designs or non-Gaussian noise.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Fixed-design least squares as orthogonal projection

Definition

Let $n, d \in N$ with $n, d \geq 1$ , and let $X \in R^{n \times d}$ be a fixed design matrix, and write $V_{X} : = {X θ : θ \in R^{d}} \subseteq R^{n}$ for its column space. For an observed vector $y \in R^{n}$ , the fixed-design least-squares fitted vector is

${\hat{μ}}_{X} (y) : = P_{V_{X}} y,$

where $P_{V_{X}}$ is the orthogonal projection onto $V_{X}$ , as defined in The orthogonal projection $P_{W} v$ is the $W$ -component in $V = W \oplus W^{⊥}$ . It is uniquely defined even when $X$ is rank deficient. The nearest-point characterization in The orthogonal projection is the unique nearest point in the subspace says that ${\hat{μ}}_{X} (y)$ minimizes $∥ y - v ∥_{2}$ over $v \in V_{X}$ . This item defines the fitted vector; it does not select a coefficient representation $\hat{θ}$ .

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

A binomial support-count bound

Statement

For $d, m \in N$ with $1 \leq m \leq d$ ,

$(\binom{d}{m}) \leq {(\frac{e d}{m})}^{m} .$

Here $(\binom{d}{m})$ is the number of $m$ -element subsets of a $d$ -element set, $m!$ is the factorial, $e = \exp (1)$ , and integer powers have the convention of Integer powers $a^{m}$ .

Facts & Assumptions

Given: Integers $d, m$ with $1 \leq m \leq d$ .

[F1]

For $m \leq d$ , $(\binom{d}{m}) m! (d - m)! = d!$ , equivalently $(\binom{d}{m}) = d^{\underline{m}} / m!$ , and $d^{\underline{m}} = d (d - 1) \dots (d - m + 1)$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ , The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[F2]

$m! = \prod_{j = 1}^{m} j > 0$ ; the real logarithm is continuous and strictly increasing, and obeys $\log (x y) = \log x + \log y$ for positive $x, y$ ; and $\log e = 1$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ , Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm as the inverse of the exponential function, The real exponential function and the number $e$ by a power series).

[F3]

$\log x = \int_{1}^{x} d t / t$ for $x > 0$ , $\log^{'} (x) = 1 / x$ , and the fundamental theorem of calculus applies to continuous integrands (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, The second fundamental theorem: if $G$ is differentiable on $[a, b]$ with $G^{'} = f$ and $f$ is integrable, then $\int_{a}^{b} f = G (b) - G (a)$ ).

[F4]

Finite sums obey their recursive product convention (Finite sums and finite products, by recursion, Laws of finite sums and finite products), and the Riemann integral preserves pointwise inequalities between integrable functions (If $f \leq g$ on $[a, b]$ and both are integrable then $\int_{a}^{b} f \leq \int_{a}^{b} g$ ; and $m (b - a) \leq \int_{a}^{b} f \leq M (b - a)$ ). Continuous functions and constant functions on compact intervals are integrable (A continuous function on $[a, b]$ is Riemann integrable, by Heine-Cantor and Riemann's criterion, If $m \leq f \leq M$ on $[a, b]$ then $m (b - a) \leq L (f, P) \leq \underline{\int_{a}^{b}} f \leq \overline{\int_{a}^{b}} f \leq U (f, P) \leq M (b - a)$ for every partition $P$ ; in particular every constant function is integrable, with $\int_{a}^{b} c = c (b - a)$ ).

[F5]

The product rule for derivatives applies to $t \mapsto t \log t - t$ (Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ ).

Proof

1.1F1F2algebra

By [F1], $(\binom{d}{m}) = d^{\underline{m}} / m!$ . Every factor in $d^{\underline{m}} = \prod_{j = 0}^{m - 1} (d - j)$ lies between $0$ and $d$ , so $d^{\underline{m}} \leq d^{m}$ ; since $m! > 0$ by [F2], $(\binom{d}{m}) \leq d^{m} / m!$ .

1.2F2F3F4F5algebra

If $m = 1$ , then $\log (m!) = 0 \geq - 1 = m \log m - m$ by [F2]. If $m \geq 2$ , monotonicity of $\log$ in [F2] gives $\log t \leq \log (j + 1)$ on each interval $[j, j + 1]$ for $1 \leq j < m$ . The logarithm and each comparison constant are integrable there by [F2, F4], so monotonicity of the integral gives $\int_{1}^{m} \log t d t \leq \sum_{j = 2}^{m} \log j = \log (m!)$ . The antiderivative $t \log t - t$ has derivative $\log t$ by [F3, F5], so [F3] evaluates the integral as $m \log m - m + 1$ . Therefore $\log (m!) \geq m \log m - m + 1 \geq m \log m - m$ .

2.1F2step 1.1step 1.2algebra∎

By [F2], $\log ((m / e)^{m}) = m (\log m - \log e) = m \log m - m$ ; the power identity follows by induction from the logarithm product law. Step 1.2 and monotonicity of $\log$ therefore imply $(m / e)^{m} \leq m!$ . Combining this with step 1.1 gives $(\binom{d}{m}) \leq d^{m} (m / e)^{- m} = (e d / m)^{m}$ .

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite-dimensional orthogonal projections are linear and contractive

Statement

Let $V$ be a finite-dimensional real inner-product space, let $W \subseteq V$ be a linear subspace, and let $P_{W} : V \to W$ be the orthogonal projection. Then $P_{W}$ is linear and satisfies $∥ P_{W} x ∥ \leq ∥ x ∥$ for every $x \in V$ . In particular, $P_{W}$ is continuous.

Facts & Assumptions

Given: A finite-dimensional real inner-product space $V$ , a subspace $W$ , its orthogonal projection $P_{W}$ , and vectors $x, y \in V$ .

[F1]

$P_{W} z \in W$ and $z - P_{W} z \in W^{⊥}$ , and this decomposition is unique (The orthogonal projection $P_{W} v$ is the $W$ -component in $V = W \oplus W^{⊥}$ ).

[F2]

$W$ and $W^{⊥}$ are linear subspaces (Linear subspace of a vector space, Orthogonality and the orthogonal complement).

[F3]

If $u ⊥ v$ , then $∥ u + v ∥^{2} = ∥ u ∥^{2} + ∥ v ∥^{2}$ (Pythagoras, the parallelogram identity, and the real and complex polarisation identities).

Proof

1.1F1F2

The vectors $P_{W} x + P_{W} y \in W$ and $(x + y) - (P_{W} x + P_{W} y) = (x - P_{W} x) + (y - P_{W} y) \in W^{⊥}$ form a decomposition of $x + y$ of the type in [F1] by [F2]. Uniqueness in [F1] therefore gives $P_{W} (x + y) = P_{W} x + P_{W} y$ .

2.1F1F2step 1.1

For any scalar $a \in R$ , $a P_{W} x \in W$ and $a x - a P_{W} x = a (x - P_{W} x) \in W^{⊥}$ by [F2]. Uniqueness in [F1] gives $P_{W} (a x) = a P_{W} x$ . Together with step 1.1 this proves linearity.

3.1F1F3step 1.1step 2.1algebra∎

The decomposition $x = P_{W} x + (x - P_{W} x)$ is orthogonal by [F1]. Pythagoras [F3] yields $∥ x ∥^{2} = ∥ P_{W} x ∥^{2} + ∥ x - P_{W} x ∥^{2} \geq ∥ P_{W} x ∥^{2}$ , hence $∥ P_{W} x ∥ \leq ∥ x ∥$ . By linearity, $∥ P_{W} x - P_{W} y ∥ = ∥ P_{W} (x - y) ∥ \leq ∥ x - y ∥$ , so $P_{W}$ is continuous.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Isotropic Gaussian noise has the matching sub-Gaussian proxy

Statement

Assume the Axiom of Choice. Let $n \geq 1$ , $σ \geq 0$ , and let $ε \sim N_{n} (0, σ^{2} I_{n})$ be a centered multivariate normal vector. Then for every $u \in R^{n}$ and $λ \in R$ , $E \exp (λ ⟨ u, ε ⟩) = \exp ⁣ (\frac{σ^{2} λ^{2} ∥ u ∥_{2}^{2}}{2}) .$ In particular, $ε$ is sub-Gaussian with proxy $σ^{2}$ in the linear-functional sense of Sub-Gaussian variables and vectors, and sub-exponential variables.

Facts & Assumptions

Given: The Axiom of Choice, an integer $n \geq 1$ , a parameter $σ \geq 0$ , and a vector $ε \sim N_{n} (0, σ^{2} I_{n})$ .

[A1]

Assume the Axiom of Choice, as required by the multivariate-normal construction (The Axiom of Choice).

[F1]

Under Multivariate normal law, including singular covariance, every linear functional $⟨ u, ε ⟩$ has law $N (0, σ^{2} ∥ u ∥_{2}^{2})$ .

[F2]

A scalar law $N (0, a^{2})$ is the law of $a G$ for a standard normal $G$ ; the standard normal has density $ϕ (x) = (2 π)^{- 1 / 2} e^{- x^{2} / 2}$ (Standard normal and normal laws).

[F3]

Integration against a density gives the corresponding expectation (Integrating against a density agrees with integrating the product).

[F4]

The standard normal density has total integral one (The standard normal density has total mass one).

[F5]

Translation is a $C^{1}$ diffeomorphism and the nonnegative change-of-variables formula applies to its translated Gaussian integrand (A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions).

[F6]

Axiom of Choice supplies the countable-choice hypothesis required by A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions (AC supplies countable selections and prescribed serial paths).

[F7]

A centered vector is sub-Gaussian with proxy $σ^{2}$ when all its linear functionals satisfy the corresponding exponential-moment bound (Sub-Gaussian variables and vectors, and sub-exponential variables).

Proof

1.1A1F1F2F3F4F5F6algebra

Fix $u \in R^{n}$ and $λ \in R$ , and put $a = σ ∥ u ∥_{2}$ . By [F1], $W = ⟨ u, ε ⟩$ has law $N (0, a^{2})$ . If $a = 0$ , then $W = 0$ almost surely by the degenerate-normal clause of [F2], and its exponential moment is $1$ . If $a > 0$ , [F2]–[F4] give $E e^{λ W} = \frac{1}{\sqrt{2 π}} \int_{R} e^{λ a x - x^{2} / 2} d x = e^{λ^{2} a^{2} / 2} \frac{1}{\sqrt{2 π}} \int_{R} e^{- (x - λ a)^{2} / 2} d x .$ Use [F5] for the translation $x \mapsto x - λ a$ and [F6] for its countable-choice hypothesis; the last integral equals the standard normal normalizing integral in [F4]. Thus $E e^{λ W} = e^{λ^{2} a^{2} / 2}$ in both cases.

2.1F1F7step 1.1algebra∎

Since $a^{2} = σ^{2} ∥ u ∥_{2}^{2}$ , step 1.1 is the claimed identity for the arbitrary $u$ and $λ$ . The mean-zero clause follows from [F1]; hence [F7] gives the stated centered sub-Gaussian property.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite tie-broken projection searches are Borel measurable

Statement

Let $n, N \geq 1$ and let $P_{1}, \dots, P_{N}$ be orthogonal projections in $R^{n}$ onto fixed finite-dimensional subspaces $V_{1}, \dots, V_{N}$ . Let $c_{1}, \dots, c_{N} \in R$ be fixed. For $y \in R^{n}$ , define $q_{i} (y) : = n^{- 1} ∥ y - P_{i} y ∥_{2}^{2} + c_{i}$ , choose the least index attaining $\min_{1 \leq i \leq N} q_{i} (y)$ , and return its fitted vector $P_{i} y$ . The resulting map $\hat{m} : R^{n} \to R^{n}$ is Borel measurable. The index map is Borel measurable when ${1, \dots, N}$ has its discrete sigma-algebra.

Facts & Assumptions

Given: A finite ordered list of fixed subspaces and their orthogonal projections, and fixed real penalties.

[F1]

Each finite-dimensional orthogonal projection is linear and continuous (Finite-dimensional orthogonal projections are linear and contractive).

[F2]

The Borel sigma-algebra is the sigma-algebra generated by open sets (The Borel sigma-algebra of a topological space, Topology on a set, open and closed sets, clopen sets, the closed-set axiomatisation, and the coarser/finer comparison).

[F3]

A measurable map is one whose inverse image of every target measurable set is measurable (A measurable function between measurable spaces).

[F4]

Every nonempty finite set of real scores has a minimum (Maximum and minimum of a set, Every nonempty finite set of reals has a maximum and a minimum).

[F5]

A globally continuous map has open inverse images of open sets and closed inverse images of closed sets (For a map of spaces the following agree: continuity at every point, preimages of open sets open, preimages of closed sets closed, preimages of subbasic open sets open, and $f (\overline{A}) \subseteq \overline{f (A)}$ ).

[F6]

The Euclidean inner product satisfies finite-dimensional Cauchy--Schwarz (The Cauchy-Schwarz inequality for finite sums).

[F7]

The Euclidean norm satisfies the triangle inequality, and expansion of squared norms gives $∥ a ∥_{2}^{2} - ∥ b ∥_{2}^{2} = ⟨ a - b, a + b ⟩$ (The inner-product norm is definite, homogeneous, and satisfies the triangle inequality, Pythagoras, the parallelogram identity, and the real and complex polarisation identities).

Proof

1.1F1F6F7algebra

Put $R_{i} = I - P_{i}$ . By [F1] and [F7], $R_{i}$ is linear and $∥ R_{i} z ∥_{2} \leq 2 ∥ z ∥_{2}$ . For $y, z \in R^{n}$ , [F6] and [F7] give $∣ ∥ R_{i} y ∥_{2}^{2} - ∥ R_{i} z ∥_{2}^{2} ∣ \leq ∥ R_{i} (y - z) ∥_{2} ∥ R_{i} (y + z) ∥_{2} \leq 4 ∥ y - z ∥_{2} ∥ y + z ∥_{2} .$ For fixed $z$ , the last factor is bounded when $y$ is near $z$ , so the squared residual and hence $q_{i}$ are continuous.

2.1F2F4F5step 1.1algebra

By [F4], a minimum score exists. Its least minimizing index is $i$ exactly on the set $A_{i} = ⋂_{j < i} {y : q_{i} (y) < q_{j} (y)} \cap ⋂_{j > i} {y : q_{i} (y) \leq q_{j} (y)} .$ Each strict comparison is open and each non-strict comparison is closed because the score differences are continuous and [F5] applies to open and closed sets. Thus every $A_{i}$ is Borel by [F2]; the sets are disjoint and cover $R^{n}$ .

3.1F1F2F3F5step 2.1algebra∎

For any open $O \subseteq R^{n}$ , ${\hat{m}}^{- 1} (O) = ⋃_{i = 1}^{N} (A_{i} \cap P_{i}^{- 1} (O))$ . Each $P_{i}^{- 1} (O)$ is open by [F1, F5], so this finite union is Borel. If $B$ ranges over subsets of $R^{n}$ whose inverse images under $\hat{m}$ are Borel, those subsets form a sigma-algebra containing every open set; [F2] therefore puts every Borel $B$ in this family. By [F3], $\hat{m}$ is Borel measurable. The index-map preimage of any set of indices is a finite union of the corresponding $A_{i}$ , so the index map is measurable as well.

AlgorithmAlgorithm: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Penalized support-search least squares

Definition

Input: naturals $n, d \geq 1$ , a fixed design $X \in R^{n \times d}$ , a data vector $y \in R^{n}$ , and a penalty $τ^{2} \geq 0$ .

List all supports $S \subseteq {1, \dots, d}$ in lexicographic order of their length- $d$ indicator vectors, using $0 < 1$ . For each $S$ , let $V_{S}$ be the span of the corresponding columns of $X$ , compute ${\hat{μ}}_{S} = P_{V_{S}} y$ , and score

$q_{S} : = n^{- 1} ∥ y - {\hat{μ}}_{S} ∥_{2}^{2} + τ^{2} ∣ S ∣ .$

Initialize the incumbent at the first support and scan the rest in order, replacing it exactly when a strictly smaller score is found; on a tie retain the earlier support. Return the selected support $\hat{S}$ and fitted vector ${\hat{μ}}_{B I C} = {\hat{μ}}_{\hat{S}}$ . The candidate family is finite by $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ , and the fitted-vector selection is Borel measurable by Finite tie-broken projection searches are Borel measurable. This is an exhaustive combinatorial procedure, not an efficiency guarantee.

AlgorithmAlgorithm: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Constrained support-search least squares

Definition

Input: naturals $n, d \geq 1$ , a fixed design $X \in R^{n \times d}$ , a data vector $y \in R^{n}$ , and a natural $s$ with $0 \leq s \leq d$ .

Candidate supports: list all subsets $S \subseteq {1, \dots, d}$ with $∣ S ∣ \leq s$ in lexicographic order of their length- $d$ indicator vectors, using $0 < 1$ . This is a finite nonempty list because it contains $\emptyset$ and is contained in the finite power set of ${1, \dots, d}$ .

Procedure: for each candidate $S$ , let $V_{S}$ be the span of the columns of $X$ indexed by $S$ and compute ${\hat{μ}}_{S} = P_{V_{S}} y$ . Compute its residual score $q_{S} = ∥ y - {\hat{μ}}_{S} ∥_{2}^{2}$ . Initialize the incumbent at the first candidate. Scan the remaining candidates in the stated order, replacing the incumbent exactly when a strictly smaller score is found; retain the earlier candidate on a tie. Return the selected support and its fitted vector ${\hat{μ}}_{s}$ .

Each $V_{S}$ is finite-dimensional, so the projections are defined by Fixed-design least squares as orthogonal projection. The fitted-vector selection is Borel measurable by Finite tie-broken projection searches are Borel measurable. The procedure performs a finite exhaustive support search; no computational-efficiency claim is made.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Exact squared-error risk of an isotropic projection fit

Statement

Let $n, d \geq 1$ , let $X \in R^{n \times d}$ be fixed, and put $V = col (X)$ and $r = \dim V$ . Let $P_{V}$ be the orthogonal projection and let $μ \in R^{n}$ be fixed. Let $ε = (ε_{1}, \dots, ε_{n})$ be a centered random vector with square-integrable coordinates satisfying $E [ε_{i} ε_{j}] = σ^{2} 1_{i = j}$ for $σ^{2} \geq 0$ . For $Y = μ + ε$ and $\hat{μ} = {\hat{μ}}_{X} (Y)$ as in Fixed-design least squares as orthogonal projection,

$E ∥ \hat{μ} - μ ∥_{2}^{2} = ∥ P_{V} μ - μ ∥_{2}^{2} + r σ^{2} .$

In particular, when $μ \in V$ , the expected squared fitted-value error is exactly $r σ^{2}$ . The moment assumptions hold for centered Gaussian noise with covariance matrix $σ^{2} I_{n}$ ; Gaussianity is not otherwise needed.

Facts & Assumptions

Given: A fixed design matrix $X$ , its column space $V$ , the projection $P_{V}$ , a fixed $μ \in R^{n}$ , and the centered second-moment assumptions on $ε$ in the statement.

[F1]

The fixed-design fitted vector is the orthogonal projection of the observed vector onto the design column space (Fixed-design least squares as orthogonal projection).

[F2]

The projection is characterized by $P_{V} x \in V$ and $x - P_{V} x \in V^{⊥}$ (The orthogonal projection $P_{W} v$ is the $W$ -component in $V = W \oplus W^{⊥}$ ).

[F3]

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

[F4]

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

[F5]

Orthogonal vectors satisfy Pythagoras (Pythagoras, the parallelogram identity, and the real and complex polarisation identities).

[F6]

For square-integrable real variables, variance and covariance are the expectations of centered products (Moments, variance, and covariance on a probability space).

[F7]

Expectation is additive on finite sums of integrable variables (Linearity, monotonicity, and the modulus bound for expectation).

[F8]

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

Proof

1.1F1F2F3algebra

Put $b = P_{V} μ - μ$ and $z = P_{V} ε$ . By [F2], $b \in V^{⊥}$ and $z \in V$ . Linearity [F3] gives $\hat{μ} - μ = b + z$ .

1.2F2F4algebra

Choose an orthonormal basis $ϕ_{1}, \dots, ϕ_{r}$ of $V$ by [F4]. The vector $\sum_{j = 1}^{r} ⟨ ε, ϕ_{j} ⟩ ϕ_{j}$ lies in $V$ and its residual from $ε$ is orthogonal to every basis vector, hence to $V$ ; uniqueness in [F2] identifies it with $P_{V} ε$ . Orthonormality therefore gives $∥ P_{V} ε ∥_{2}^{2} = \sum_{j = 1}^{r} ⟨ ε, ϕ_{j} ⟩^{2}$ , with the empty sum equal to zero when $r = 0$ .

1.3F4F6F7algebra

Write $ϕ_{j} = (ϕ_{1 j}, \dots, ϕ_{n j})$ . By [F6] and the given coordinate second moments, $E ⟨ ε, ϕ_{j} ⟩^{2} = \sum_{a, b = 1}^{n} ϕ_{a j} ϕ_{b j} E [ε_{a} ε_{b}] = σ^{2} \sum_{a = 1}^{n} ϕ_{a j}^{2} = σ^{2}$ for each $j$ . Summing with [F7] shows $E ∥ P_{V} ε ∥_{2}^{2} = r σ^{2}$ .

2.1step 1.1F5F7

The two summands in step 1.1 are orthogonal, so [F5] gives $∥ \hat{μ} - μ ∥_{2}^{2} = ∥ P_{V} μ - μ ∥_{2}^{2} + ∥ P_{V} ε ∥_{2}^{2}$ pointwise. Taking expectations and using [F7] separates the fixed first term from the noise term.

3.1step 2.1step 1.3F2F8∎

Substitute step 1.3 into step 2.1 to obtain the displayed identity. If $μ \in V$ , then $P_{V} μ = μ$ by [F2], giving the stated special case. By [F8], its left side is the risk under squared fitted-value loss.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

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.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passOpen item page →

BIC fitted-value risk bound

Statement

Let $n, d \geq 1$ , let $X \in R^{n \times d}$ be fixed, and let $θ^{*} \in R^{d}$ have a nonempty support $S^{*} : = {j : θ_{j}^{*} \neq 0}$ of size $s : = ∣ S^{*} ∣ \geq 1$ . Suppose $Y = X θ^{*} + ε$ , 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. Run Penalized support-search least squares with

$τ^{2} = 16 \log (6) \frac{σ^{2}}{n} + 32 \frac{σ^{2} \log (e d)}{n} .$

For every admissible input to Penalized support-search least squares, its finite scan terminates and returns a support minimizing $n^{- 1} ∥ y - P_{V_{S}} y ∥_{2}^{2} + τ^{2} ∣ S ∣$ over all supports. Among tied minimizers, it returns the earliest support in the prescribed order.

Moreover, there is a universal constant $C_{0} : = 64 + 64 \log 6 + 32 \log 4$ such that, for every $0 < δ < 1$ ,

$P ⁣ (\frac{1}{n} ∥ {\hat{μ}}_{B I C} - X θ^{*} ∥_{2}^{2} \leq C_{0} \frac{σ^{2} [s \log (e d) + \log (1 / δ)]}{n}) \geq 1 - δ .$

Since $s \geq 1$ , this also gives $C_{0} σ^{2} s \log (e d / δ) / n$ . The theorem makes no design-rank, incoherence, or column-normalization assumption. It asserts no zero right-hand side when $s = 0$ .

Facts & Assumptions

Given: For the scan assertion, any admissible input listed in the Definition of Penalized support-search least squares. For the risk bound, the fixed-design model, centered sub-Gaussian noise, nonempty true support $S^{*}$ of size $s \geq 1$ , and $0 < δ < 1$ .

[F1]

The support list consists of every subset of the finite $d$ -element coordinate set, so it is finite and nonempty by $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ . The algorithm lists it in the prescribed order and updates its incumbent only when it finds a strictly smaller score (Penalized support-search least squares).

[F2]

For centered sub-Gaussian noise with proxy $σ^{2} > 0$ and a fixed subspace of rank $r$ , $P (∥ P_{V} ε ∥_{2}^{2} > t) \leq 2 \cdot 6^{r} e^{- t / (8 σ^{2})}$ ; proxy zero gives zero projection error (Sub-Gaussian projection risk bounds).

[F3]

For natural $k$ with $1 \leq k \leq d$ , $(\binom{d}{k}) \leq (e d / k)^{k}$ (A binomial support-count bound).

[F4]

Orthogonal projection is the nearest-point map on its subspace (The orthogonal projection is the unique nearest point in the subspace).

[F5]

$e = \exp (1) > 1$ (The real exponential function and the number $e$ by a power series, The exponential function is strictly increasing).

[F6]

The Euclidean inner product satisfies Cauchy--Schwarz (The Cauchy-Schwarz inequality for finite sums).

[F7]

The centered vector MGF convention is the all-directions bound $E e^{λ ⟨ u, ε ⟩} \leq e^{σ^{2} λ^{2} ∥ u ∥_{2}^{2} / 2}$ (Sub-Gaussian variables and vectors, and sub-exponential variables).

[F8]

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^{⊥}$ ).

[F9]

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

[F10]

The nonnegative squared fitted-value error is the loss used here; risk is its expectation (Loss functions and risk).

[F11]

The selected support index and fitted-vector maps are Borel measurable for this finite score family (Finite tie-broken projection searches are Borel measurable).

[F12]

The natural logarithm is the inverse of $\exp$ , is strictly increasing, has the product law and $\log 1 = 0$ , and $e = \exp (1)$ (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 real exponential function and the number $e$ by a power series).

Proof

1.1F1algebra

Let $S_{1}, \dots, S_{M}$ be the finite ordered support list from [F1]. After the first support is processed, the incumbent has least score and earliest index among minimizers in the first one-element list. If this is true after $j < M$ supports, then the next score either is strictly smaller, in which case replacing the incumbent gives the new least score, or is at least the incumbent score, in which case retaining it preserves the minimum and keeps the earlier index in a tie. Induction proves the invariant through $M$ , so the scan terminates and returns the least-scoring support with the stated tie rule.

2.1step 1.1F4givenalgebra

Let $\hat{S}$ be the selected support, $k = ∣ \hat{S} ∣$ , $\hat{μ} = {\hat{μ}}_{B I C}$ , and $Δ = \hat{μ} - X θ^{*}$ . The support $S^{*}$ is a candidate, and $X θ^{*} \in V_{S^{*}}$ . By step 1.1 and [F4], the selected penalized score is no larger than the score of the projection onto $V_{S^{*}}$ , whose residual is no larger than $∥ ε ∥_{2}^{2}$ . Thus $∥ Y - \hat{μ} ∥_{2}^{2} + n τ^{2} k \leq ∥ ε ∥_{2}^{2} + n τ^{2} s .$ Expanding $Y = X θ^{*} + ε$ gives $∥ Δ ∥_{2}^{2} \leq 2 ⟨ ε, Δ ⟩ + n τ^{2} (s - k)$ .

3.1step 2.1F11algebra

On the event $∥ Δ ∥_{2} > 0$ , set $v = Δ / ∥ Δ ∥_{2}$ . Then $v \in W_{\hat{S}} : = span {X_{j} : j \in \hat{S} \cup S^{*}}$ , whose dimension is at most $k + s$ . Young's inequality $2 a b \leq 2 a^{2} + b^{2} / 2$ applied to $a = ∣ ⟨ ε, v ⟩ ∣$ and $b = ∥ Δ ∥_{2}$ yields $∥ Δ ∥_{2}^{2} \leq 2 n τ^{2} s + 4 ⟨ ε, v ⟩^{2} - 2 n τ^{2} k .$ If $Δ = 0$ , no tail event with a positive threshold can occur.

4.1F2F6F8F11step 3.1algebra

Assume $σ^{2} > 0$ and fix $t > 0$ . First consider $k = 0$ . On the event $∥ Δ ∥_{2}^{2} > 2 n τ^{2} s + t$ , step 3.1 implies $⟨ ε, v ⟩^{2} > t / 4$ for a unit vector in $V_{S^{*}}$ . By [F6] and [F8], this forces $∥ P_{V_{S^{*}}} ε ∥_{2}^{2} > t / 4$ . Since $\dim V_{S^{*}} \leq s$ , [F2] gives, for $σ^{2} > 0$ , $P (k = 0, ∥ Δ ∥_{2}^{2} > 2 n τ^{2} s + t) \leq 2 \cdot 6^{s} e^{- t / (32 σ^{2})} .$

5.1F2F6F8F11step 3.1step 4.1algebra

Now fix $1 \leq k \leq d$ and a candidate support $S$ of size $k$ . On the event ${\hat{S} = S, ∥ Δ ∥_{2}^{2} > 2 n τ^{2} s + t}$ , step 3.1 forces $⟨ ε, v ⟩^{2} > t / 4 + n τ^{2} k / 2$ for a unit vector in $W_{S} = span {X_{j} : j \in S \cup S^{*}}$ , whose dimension is at most $k + s$ . By [F6] and [F8], this implies $∥ P_{W_{S}} ε ∥_{2}^{2} > t / 4 + n τ^{2} k / 2$ . By [F2], the probability for this support is at most $2 \cdot 6^{k + s} \exp ⁣ (- \frac{t}{32 σ^{2}} - \frac{n τ^{2} k}{16 σ^{2}}) .$

6.1F3F5F9F11step 5.1algebra

Union bound over the $(\binom{d}{k})$ supports, use [F3], and substitute the specified $τ^{2}$ . Since $n τ^{2} / (16 σ^{2}) = \log 6 + 2 \log (e d)$ , the sum over all $k \geq 1$ is at most $2 e^{s \log 6 - t / (32 σ^{2})} \sum_{k = 1}^{d} (e d)^{- k} \leq 2 e^{s \log 6 - t / (32 σ^{2})} .$ The last inequality follows because each summand is at most $(e d)^{- 1}$ , there are $d$ terms, and $d (e d)^{- 1} = 1 / e < 1$ by [F5].

7.1F5F9F10F12step 4.1step 6.1algebra

Take $t = 32 σ^{2} [s \log 6 + \log (4 / δ)]$ in steps 4.1 and 6.1. Each branch has probability at most $δ / 2$ , so with probability at least $1 - δ$ , $∥ Δ ∥_{2}^{2} \leq 2 n τ^{2} s + t = σ^{2} [64 s \log (e d) + 64 s \log 6 + 32 \log 4 + 32 \log (1 / δ)] .$ By [F5, F12], $\log (e d) = \log e + \log d = 1 + \log d \geq 1$ because $e = \exp (1)$ , $\log e = 1$ , and $d \geq 1$ . Since $s \geq 1$ , the right side is at most $C_{0} σ^{2} [s \log (e d) + \log (1 / δ)]$ . Dividing by $n$ proves the positive-proxy bound. The probability event is for the squared fitted-value loss identified by [F10].

8.1F2F7F9givenstep 1.1algebra∎

The centered vector proxy assumption is [F7], so [F2] applies to the identity subspace. If $σ^{2} = 0$ , for every integer $j \geq 1$ , $P (∥ ε ∥_{2}^{2} > 1 / j) = 0$ . Since ${∥ ε ∥_{2}^{2} > 0} = ⋃_{j \geq 1} {∥ ε ∥_{2}^{2} > 1 / j}$ , [F9] gives $ε = 0$ almost surely. Then $Y = X θ^{*}$ ; the true support has zero residual, and step 1.1 shows that the selected support also has zero residual because $τ^{2} = 0$ . Its fitted vector therefore equals $Y = X θ^{*}$ . Thus the bound also holds in the zero-proxy case.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Sparse constrained least-squares risk bound

Statement

For every admissible input to Constrained support-search least squares, its finite scan terminates and returns a support minimizing $∥ y - P_{V_{S}} y ∥_{2}^{2}$ over all supports of size at most $s$ . Among tied minimizers, it returns the earliest support in the prescribed order.

Moreover, let $n, d$ be positive integers, let $X \in R^{n \times d}$ be fixed, and let $θ^{*} \in R^{d}$ have at most $s$ nonzero coordinates, where $1 \leq s \leq d / 2$ . Suppose $Y = X θ^{*} + ε$ and $ε$ is centered sub-Gaussian with proxy $σ^{2} \geq 0$ in the linear-functional sense of Sub-Gaussian variables and vectors, and sub-exponential variables. Let ${\hat{μ}}_{s}$ be the fitted vector returned by Constrained support-search least squares. For $0 < δ < 1$ , with $C : = 32 (4 + 2 \log 6)$ ,

$E [\frac{1}{n} ∥ {\hat{μ}}_{s} - X θ^{*} ∥_{2}^{2}] \leq C \frac{σ^{2} s \log (e d / s)}{n},$

and

$P ⁣ (\frac{1}{n} ∥ {\hat{μ}}_{s} - X θ^{*} ∥_{2}^{2} \leq C \frac{σ^{2} [s \log (e d / s) + \log (1 / δ)]}{n}) \geq 1 - δ .$ No design-rank, incoherence, or column-normalization condition is assumed. The claim concerns fitted values; it gives no coefficient-error bound.

Facts & Assumptions

Given: For the scan assertion, any admissible input listed in the Definition of Constrained support-search least squares. For the risk bounds, the fixed-design model and noise assumptions in the statement, with $1 \leq s \leq d / 2$ and $0 < δ < 1$ .

[F1]

The procedure enumerates the finite nonempty list of supports of size at most $s$ in its prescribed order and replaces its incumbent only when it finds a strictly smaller residual (Constrained support-search least squares, $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ ).

[F2]

For a fixed subspace of rank $r$ and centered sub-Gaussian noise with proxy $σ^{2} > 0$ , $P (∥ P_{V} ε ∥_{2}^{2} > t) \leq 2 \cdot 6^{r} e^{- t / (8 σ^{2})}$ for $t > 0$ ; proxy zero gives zero projection error (Sub-Gaussian projection risk bounds).

[F3]

For natural numbers $1 \leq m \leq d$ , $(\binom{d}{m}) \leq (e d / m)^{m}$ (A binomial support-count bound).

[F5]

The Euclidean inner product satisfies Cauchy--Schwarz (The Cauchy-Schwarz inequality for finite sums).

[F6]

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^{⊥}$ ).

[F7]

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

[F8]

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

[F9]

The selected support index and fitted-vector maps are Borel measurable for this finite score family (Finite tie-broken projection searches are Borel measurable).

[F10]

Orthogonal projection minimizes distance to its subspace (The orthogonal projection is the unique nearest point in the subspace).

[F11]

The natural logarithm is the inverse of $\exp$ , is strictly increasing, has the product, quotient, and reciprocal laws and $\log 1 = 0$ ; repeated application gives its integer-power law, and $e = \exp (1)$ (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 real exponential function and the number $e$ by a power series).

[F12]

For $T \geq 0$ , $c > 0$ , $x_{0} \geq 0$ , $h = c / 2$ , and $N \in N$ , $\min (T, x_{0} + N h) \leq x_{0} + h \sum_{j < N} 1_{{T > x_{0} + j h}} .$ If $P (T > x) \leq A \exp (- x / c)$ and $x_{0} = c \log A$ , monotone convergence and expectation linearity, with the Archimedean property giving $x_{0} + N h \to \infty$ , bound $E T$ by $x_{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, Linearity, monotonicity, and the modulus bound for expectation, 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).

[F13]

Expectation is linear for integrable random variables (Linearity, monotonicity, and the modulus bound for expectation).

Proof

1.1F1algebra

Let $S_{1}, \dots, S_{M}$ be the finite nonempty ordered candidate list from [F1]. After the first support is processed, the incumbent has least residual and earliest index among minimizers in the first one-element list. If this is true after $j < M$ supports, then the next residual either is strictly smaller, in which case replacing the incumbent gives the new least residual, or is at least the incumbent residual, in which case retaining it preserves the minimum and keeps the earlier index in a tie. Induction proves the invariant through $M$ , so the scan terminates and returns a least-residual support with the stated tie rule.

1.2F1F10given

Write $μ = X θ^{*}$ , let $S^{*} = {j : θ_{j}^{*} \neq 0}$ , and put $Δ = {\hat{μ}}_{s} - μ$ . Since $∣ S^{*} ∣ \leq s$ , $S^{*}$ is a candidate support and $μ \in V_{S^{*}}$ . Its candidate fitted vector is $P_{V_{S^{*}}} Y$ . By [F10], $∥ Y - P_{V_{S^{*}}} Y ∥_{2}^{2} \leq ∥ Y - μ ∥_{2}^{2}$ .

2.1step 1.1step 1.2algebra

By the scan-minimizer result in step 1.1, the selected residual is no larger than that of $P_{V_{S^{*}}} Y$ , which step 1.2 bounds by the residual at $μ$ : $∥ Y - {\hat{μ}}_{s} ∥_{2}^{2} \leq ∥ Y - μ ∥_{2}^{2} = ∥ ε ∥_{2}^{2}$ . Expanding $Y = μ + ε$ gives $∥ Δ ∥_{2}^{2} \leq 2 ⟨ ε, Δ ⟩$ .

3.1step 2.1F5F6algebra

If $Δ \neq 0$ , its support difference lies in the span of columns indexed by $S^{*} \cup \hat{S}$ , whose size is at most $2 s$ . Since $2 s \leq d$ , that set is contained in some $T \subseteq {1, \dots, d}$ with $∣ T ∣ = 2 s$ . Thus $Δ \in V_{T}$ , and orthogonality of the projection gives $⟨ ε, Δ ⟩ = ⟨ P_{V_{T}} ε, Δ ⟩$ by [F6]. By [F5] and step 2.1, $∥ Δ ∥_{2}^{2} \leq 2 ∥ P_{V_{T}} ε ∥_{2} ∥ Δ ∥_{2}$ , hence $∥ Δ ∥_{2}^{2} \leq 4 ∥ P_{V_{T}} ε ∥_{2}^{2}$ . If $Δ = 0$ , the last inequality holds for every such $T$ as well.

4.1F1F2F7F9step 1.1step 1.2algebrastep 3.1

There are $(\binom{d}{2 s})$ possible sets $T$ . For each, its projection rank is at most $2 s$ , so [F2] and the finite union bound give, for $t > 0$ and $σ^{2} > 0$ , $P (∥ Δ ∥_{2}^{2} > 4 t) \leq 2 (\binom{d}{2 s}) 6^{2 s} e^{- t / (8 σ^{2})} = : A e^{- t / (8 σ^{2})} .$ If $σ^{2} = 0$ , apply [F2] to the identity subspace: for every integer $j \geq 1$ , $P (∥ ε ∥_{2}^{2} > 1 / j) = 0$ . Since ${∥ ε ∥_{2}^{2} > 0} = ⋃_{j \geq 1} {∥ ε ∥_{2}^{2} > 1 / j}$ , [F7] gives $ε = 0$ almost surely. Then [F1] and the scan result in step 1.1 show that the selected residual is zero, so its fitted vector equals $Y = μ$ ; both claims hold with zero error.

5.1F3F9F11step 4.1algebra

For $σ^{2} > 0$ , take $t = 8 σ^{2} [\log A + \log (1 / δ)]$ in step 4.1. By [F11] the threshold is positive. The resulting tail is at most $δ$ , and $\log A = \log 2 + 2 s \log 6 + \log (\binom{d}{2 s})$ . By [F3] and [F11], $\log (\binom{d}{2 s}) \leq 2 s \log (e d / (2 s)) = 2 s \log (e d / s) - 2 s \log 2$ . Hence $\log A \leq 2 s \log (e d / s) + 2 s \log 6 + (1 - 2 s) \log 2 \leq (2 + 2 \log 6) s \log (e d / s)$ . Dividing the threshold $4 t$ by $n$ and using $C = 32 (4 + 2 \log 6)$ proves the stated high-probability bound.

6.1F3F8F9F11F12F13step 4.1step 5.1algebra∎

Put $Z = ∥ Δ ∥_{2}^{2}$ , $c = 32 σ^{2}$ , $h = c / 2$ , and $x_{0} = c \log A$ . Step 4.1 gives $P (Z > x_{0} + j h) \leq \exp (- j / 2)$ for every $j \geq 0$ . Apply [F12] to $Z$ , using [F13] for expectation linearity and monotone convergence, to get $E Z \leq x_{0} + h \sum_{j \geq 0} \exp (- j / 2) \leq c (\log A + 13 / 10)$ . By step 5.1, $\log A \leq (2 + 2 \log 6) s \log (e d / s)$ ; since $s \log (e d / s) \geq 1$ and $13 / 10 < 2$ , this yields $E Z / n \leq C σ^{2} s \log (e d / s) / n$ . By [F8], this is the expected risk under squared fitted-value loss. The zero-proxy case was settled in step 4.1.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passOpen item page →

Gaussian sparse-sequence minimax lower bound

Statement

Assume the Axiom of Choice. Let $n, d \geq 1$ , $σ > 0$ , and let $1 \leq s \leq d / 2$ be integers. Observe $Z \in R^{d}$ with independent coordinates $Z_{j} \sim N (θ_{j}, σ^{2} / n)$ for a parameter $Θ_{s, d} : = {θ \in R^{d} : ∣ {j \in {1, \dots, d} : θ_{j} \neq 0} ∣ \leq s} .$ For every Borel estimator $T : R^{d} \to R^{d}$ , $\sup_{θ \in Θ_{s, d}} E_{θ} ∥ T (Z) - θ ∥_{2}^{2} \geq \frac{σ^{2} s \log (e d / s)}{200000 n} .$

Facts & Assumptions

Given: AC, integers $n, d \geq 1$ , $σ > 0$ , $1 \leq s \leq d / 2$ , the independent-coordinate Gaussian sequence experiment, and a Borel estimator $T : R^{d} \to R^{d}$ .

[A1]

Assume AC, as required by the Fano, KL, and Gaussian-location suppliers (The Axiom of Choice).

[F1]

For $1 \leq s \leq d / 2$ , there is a finite code of binary vectors with exactly $s$ ones, pairwise squared Euclidean distance greater than $s / 2$ , and $\log M \geq (s / 1024) \log (e d / s)$ (A sparse Hamming packing for every $1 \leq k \leq d / 2$ ).

[F2]

For independent coordinates $N (θ_{j}, σ^{2} / n)$ , the KL divergence between two sequence laws is $n ∥ θ - θ^{'} ∥_{2}^{2} / (2 σ^{2})$ (KL divergence between equal-variance Gaussian location laws, Additivity of KL divergence for finite product laws).

[F3]

For $M$ separated hypotheses and a reference law $Q$ , every randomized estimator has uniform average squared-error risk at least $\frac{Δ^{2}}{4} (1 - \frac{M^{- 1} \sum_{j} D (P_{j} ∥ Q) + \log 2}{\log M})$ (Fano’s packing bound with a reference-distribution KL bound).

[F4]

Under the event-supremum convention, $∥ P - Q ∥_{T V} \leq \sqrt{D (P ∥ Q) / 2}$ (Pinsker’s inequality with event-supremum total variation).

[F5]

For scalar targets separated by $b > 0$ , every randomized scalar estimator has maximum squared-error risk at least $\frac{b^{2}}{8} (1 - ∥ P_{0} - P_{1} ∥_{T V})$ (Two-point Le Cam lower bound for squared-error risk).

[F6]

Risk is the expected nonnegative loss under the sampling and action laws (Loss functions and risk).

[F7]

A Borel estimator induces a measurable point-mass probability kernel (Randomized procedures as probability kernels, A statistic induces a deterministic probability kernel).

[F8]

The natural logarithm is strictly increasing and has the product law; $\log x = \int_{1}^{x} d t / t$ , the integral is monotone, squaring is strictly increasing on nonnegative reals, and nonnegative square roots are unique (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 integral logarithm $L (x) : = \int_{1}^{x} \frac{d t}{t}$ for $x > 0$ , The integral logarithm $L$ is the published natural logarithm, If $f \leq g$ on $[a, b]$ and both are integrable then $\int_{a}^{b} f \leq \int_{a}^{b} g$ ; and $m (b - a) \leq \int_{a}^{b} f \leq M (b - a)$ , Squaring is monotone on the nonnegatives, Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ ).

[F9]

$e = \exp (1) > 2$ , since the defining series for $e$ has initial terms $1 + 1 + 1 / 2$ and positive remaining terms; $\exp$ is strictly increasing (The real exponential function and the number $e$ by a power series, The exponential function is strictly increasing).

Proof

1.1F1F8F9givenalgebra

Choose the code $C$ from [F1], with cardinality $M$ . Since $e d / s \geq 2 e > 1$ by [F9], [F8] gives $\log (e d / s) > 0$ ; hence $M \geq 2$ . Put $a : = \sqrt{\frac{σ^{2} \log M}{4 n s}} > 0, θ^{ω} = a u^{ω} (ω \in C) .$ Every $θ^{ω}$ belongs to $Θ_{s, d}$ , and distinct code targets have squared distance greater than $a^{2} s / 2$ .

1.2A1F1F2F4F5F7F8givenalgebra

Now suppose $M = 2$ . By [F8], $\log 2 = \int_{1}^{2} d t / t \leq 1$ , because $1 / t \leq 1$ on $[1, 2]$ . Hence [F1] gives $s \log (e d / s) \leq 1024$ . Consider the two parameters $0$ and $b e_{1}$ , where $b = σ / (2 \sqrt{n})$ ; both belong to $Θ_{s, d}$ . By [F2], their sequence laws have KL divergence $n b^{2} / (2 σ^{2}) = 1 / 8$ , so [F4] gives total variation at most $1 / 4$ . For the Borel vector estimator $T$ , its first coordinate $T_{1}$ is Borel, and [F7] makes it an admissible scalar kernel. Pointwise, $∥ T (z) - θ ∥_{2}^{2} \geq ∣ T_{1} (z) - θ_{1} ∣^{2}$ for both parameters. Applying [F5] to this scalar kernel shows the maximum vector risk is at least $\frac{b^{2}}{8} (1 - \frac{1}{4}) = \frac{3 σ^{2}}{128 n} > \frac{1024 σ^{2}}{200000 n} \geq \frac{σ^{2} s \log (e d / s)}{200000 n} .$

2.1A1F1F2step 1.1algebra

Take the reference law $Q = P_{0}$ of the zero-mean sequence. By [F2], $D (P_{θ^{ω}} ∥ P_{0}) = \frac{n}{2 σ^{2}} ∥ a u^{ω} ∥_{2}^{2} = \frac{n a^{2} s}{2 σ^{2}} = \frac{\log M}{8}$ for every $ω$ , since $u^{ω}$ has exactly $s$ ones.

3.1A1F3F7F8step 1.1step 2.1algebra

First suppose $M \geq 3$ . Since $3 > 2 \sqrt{2}$ (squaring gives $9 > 8$ ), [F8] implies $\log 3 > \log (2 \sqrt{2}) = \frac{3}{2} \log 2$ . Thus $\log 2 / \log M < 2 / 3$ . The average reference KL ratio in [F3] is $1 / 8$ by step 2.1, so the Fano factor is greater than $1 - 1 / 8 - 2 / 3 = 5 / 24 > 1 / 5$ . With separation $Δ = a \sqrt{s / 2}$ , [F3] gives uniform average risk greater than $\frac{Δ^{2}}{20} = \frac{a^{2} s}{40} = \frac{σ^{2} \log M}{160 n} \geq \frac{σ^{2} s \log (e d / s)}{163840 n} > \frac{σ^{2} s \log (e d / s)}{200000 n} .$ The maximum risk dominates this finite-code average; the Borel estimator is an admissible kernel by [F7]. Thus its supremum risk satisfies the same lower bound.

4.1F6step 1.1step 1.2step 3.1∎

The cases $M \geq 3$ and $M = 2$ exhaust the possibilities by step 1.1. Step 3.1 proves the $M \geq 3$ case, and step 1.2 proves the $M = 2$ case. Thus the claimed lower bound holds for the arbitrary Borel estimator $T$ , with risk understood as in [F6].

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Matching minimax rate in a Gaussian orthogonal sequence model

Statement

Assume the Axiom of Choice. Let $n = d \geq 2$ , let $1 \leq s \leq n / 2$ , and take the fixed design $X = \sqrt{n} I_{n}$ . For $Θ_{s} : = {θ \in R^{n} : ∣ {j \in {1, \dots, n} : θ_{j} \neq 0} ∣ \leq s},$ observe $Y = X θ + ε$ with one common noise law $ε \sim N_{n} (0, σ^{2} I_{n})$ , where $σ > 0$ . For Borel fitted-vector estimators $T : R^{n} \to R^{n}$ , define $R_{n, s}^{*} : = \inf_{T B o r e l} \sup_{θ \in Θ_{s}} E_{θ} [\frac{1}{n} ∥ T (Y) - X θ ∥_{2}^{2}] .$ Then for $C = 32 (4 + 2 \log 6)$ , $\frac{σ^{2} s \log (e n / s)}{200000 n} \leq R_{n, s}^{*} \leq \sup_{θ \in Θ_{s}} E_{θ} [\frac{1}{n} ∥ {\hat{μ}}_{s} (Y) - X θ ∥_{2}^{2}] \leq C \frac{σ^{2} s \log (e n / s)}{n},$ where ${\hat{μ}}_{s}$ is the constrained support-search fitted vector. Thus this Gaussian orthogonal-sequence model has a matching minimax rate up to universal constants. The sparse upper-bound theorem itself is choice-free; this corollary assumes AC for its Gaussian law and Fano lower-bound suppliers.

Facts & Assumptions

Given: AC; integers $n = d \geq 2$ , $1 \leq s \leq n / 2$ ; $X = \sqrt{n} I_{n}$ ; and a common noise vector $ε \sim N_{n} (0, σ^{2} I_{n})$ with $σ > 0$ .

[A1]

AC is assumed by the multivariate-normal and Fano lower-bound suppliers (The Axiom of Choice).

[F1]

For every fixed design and every truth with at most $s$ nonzero coordinates, the constrained least-squares fitted vector has expected normalized squared error at most $C σ^{2} s \log (e n / s) / n$ (Sparse constrained least-squares risk bound).

[F2]

The finite tie-broken support-search output is Borel measurable (Finite tie-broken projection searches are Borel measurable).

[F3]

Isotropic Gaussian noise is centered sub-Gaussian with proxy $σ^{2}$ (Isotropic Gaussian noise has the matching sub-Gaussian proxy).

[F4]

By Multivariate normal law, including singular covariance, $N_{n} (0, σ^{2} I_{n})$ has the independent-coordinate realization $σ (G_{1}, \dots, G_{n})$ for independent standard-normal $G_{j}$ . Its characteristic-function formula and uniqueness in Characteristic function of a multivariate normal law identify that realization with the stated multivariate-normal law. Since $σ > 0$ , its coordinates are independent $N (0, σ^{2})$ variables.

[F5]

In the Gaussian sequence model $Z_{j} \sim N (θ_{j}, σ^{2} / n)$ with at most $s$ nonzero coordinates, every Borel vector estimator has maximum squared-error risk at least $σ^{2} s \log (e n / s) / (200000 n)$ (Gaussian sparse-sequence minimax lower bound).

[F6]

The general risk definition integrates a nonnegative loss against the sampling law and, for randomized rules, the action kernel (Loss functions and risk).

[F7]

Measurable coordinatewise transformations preserve independence, and an affine image $a + b G$ of a standard normal $G$ has law $N (a, b^{2})$ (Measurable coordinatewise functions preserve independence, Standard normal and normal laws).

[F8]

Continuous affine maps on Euclidean spaces are Borel, and compositions of measurable maps remain measurable (Continuous functions on Euclidean spaces are Borel measurable, Composition with a Borel measurable outer map preserves measurability).

Proof

1.1A1F1F2F3F6algebra

By [F3], the noise satisfies the centered vector proxy condition required by [F1]. The support-search fitted vector is Borel by [F2], so it is an admissible estimator for [F6]. Applying [F1] at each $θ \in Θ_{s}$ and taking the supremum and then the infimum gives the upper bound.

1.2A1F4F5F7F8algebra

Fix any Borel fitted-vector estimator $T$ . Put $Z = Y / \sqrt{n}$ and $S (z) = T (\sqrt{n} z) / \sqrt{n}$ , which is Borel by [F8]. Under the independent realization in [F4], the coordinates of $Z$ are coordinatewise measurable affine transforms of independent standard normals. By [F7], they remain independent and have laws $N (θ_{j}, σ^{2} / n)$ , exactly the sequence experiment in [F5]. Applying [F5] to the Borel estimator $S$ gives $\sup_{θ \in Θ_{s}} E_{θ} ∥ S (Z) - θ ∥_{2}^{2} \geq \frac{σ^{2} s \log (e n / s)}{200000 n} .$

2.1F6step 1.2algebra

Since $X = \sqrt{n} I_{n}$ , pointwise $\frac{1}{n} ∥ T (Y) - X θ ∥_{2}^{2} = {∥ \frac{T (Y)}{\sqrt{n}} - θ ∥}_{2}^{2} = ∥ S (Z) - θ ∥_{2}^{2} .$ By [F6] these pointwise losses define the respective risks. Thus every Borel $T$ has supremum fitted-value risk at least the lower bound in step 1.2. Taking the infimum over $T$ proves the minimax lower bound.

3.1step 1.1step 2.1algebra∎

The upper bound in step 1.1 and the lower bound in step 2.1 give the displayed comparison, with universal constants $1 / 200000$ and $C$ .

5 · Examples, counterexamples and false statements

None yet.

Decision-Theoretic Upper Bounds

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Fixed-design least squares as orthogonal projection

Definition

A binomial support-count bound

Statement

Facts & Assumptions

Proof

Finite-dimensional orthogonal projections are linear and contractive

Statement

Facts & Assumptions

Proof

Isotropic Gaussian noise has the matching sub-Gaussian proxy

Statement

Facts & Assumptions

Proof

Finite tie-broken projection searches are Borel measurable

Statement

Facts & Assumptions

Proof

Penalized support-search least squares

Definition

Constrained support-search least squares

Definition

Exact squared-error risk of an isotropic projection fit

Statement

Facts & Assumptions

Proof

Sub-Gaussian projection risk bounds

Statement

Facts & Assumptions

Proof

BIC fitted-value risk bound

Statement

Facts & Assumptions

Proof

Sparse constrained least-squares risk bound

Statement

Facts & Assumptions

Proof

Gaussian sparse-sequence minimax lower bound

Statement

Facts & Assumptions

Proof

Matching minimax rate in a Gaussian orthogonal sequence model

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources