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.

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.

Depends on

Used by

Cited to discharge well-definedness by Constrained support-search least squares.

Dependency tree · two levels

120 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.6 and Corollaries 2.8–2.9 (standard reference, not scraped)
Sylvain Arlot, Model/estimator selection, Lecture on model selection, §§1–2 (standard reference, not scraped)