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 · 4 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 6 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Linear prediction, shrinkage, and sparse regression

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Fixed-design least-squares, ridge, lasso, group, and fused objectives

Definition

Let $n, p \geq 1$ , let $X \in R^{n \times p}$ be a fixed design matrix, let $y \in R^{n}$ , and let $β \in R^{p}$ . The empirical squared loss is

$ℓ_{n} (β) = \frac{1}{2 n} ∥ y - X β ∥_{2}^{2} .$

Ordinary least squares minimizes $ℓ_{n} (β)$ over $R^{p}$ . For $λ > 0$ , the ridge (Tikhonov) objective is

$J_{λ}^{r i d g e} (β) = ∥ y - X β ∥_{2}^{2} + λ ∥ β ∥_{2}^{2} .$

For $λ > 0$ , the lasso objective in the empirical-loss convention is

$J_{λ}^{l a s s o} (β) = ℓ_{n} (β) + λ ∥ β ∥_{1}, ∥ β ∥_{1} = \sum_{j = 1}^{p} ∣ β_{j} ∣ .$

This lasso has the same minimizers as $n^{- 1} ∥ y - X β ∥_{2}^{2} + 2 λ ∥ β ∥_{1}$ , the fixed-design convention with penalty parameter $τ = λ$ .

For a partition $G_{1}, \dots, G_{m}$ of ${1, \dots, p}$ , fixed weights $w_{g} > 0$ , and $λ \geq 0$ , the group-lasso objective is

$J_{λ}^{g r o u p} (β) = ℓ_{n} (β) + λ \sum_{g = 1}^{m} w_{g} ∥ β_{G_{g}} ∥_{2} .$

For a fixed matrix $D \in R^{q \times p}$ and $λ_{1}, λ_{2} \geq 0$ , a fused-lasso objective is

$J_{λ_{1}, λ_{2}}^{f u s e d} (β) = ℓ_{n} (β) + λ_{1} ∥ β ∥_{1} + λ_{2} ∥ D β ∥_{1} .$

These group and fused formulas define objectives only; no existence, uniqueness, or algorithm guarantee is asserted for them here. The formulas use the displayed feature scales, so rescaling a column changes the penalty unless its coefficient and penalty weight are adjusted. If a separate intercept is included, write $X = [1 X_{0}]$ and $β = (β_{0}, γ)$ , and define the loss by $∥ y - β_{0} 1 - X_{0} γ ∥_{2}^{2} / (2 n)$ . In this convention replace the ridge penalty by $λ ∥ γ ∥_{2}^{2}$ , the lasso penalty by $λ ∥ γ ∥_{1}$ , the group penalty by $λ \sum_{g} w_{g} ∥ γ_{G_{g}} ∥_{2}$ with the groups partitioning only the coordinates of $γ$ , and the fused penalty by $λ_{1} ∥ γ ∥_{1} + λ_{2} ∥ D_{0} γ ∥_{1}$ with $D = [0 D_{0}]$ . The ridge loss remains unaveraged. Each penalty then acts only on $γ$ and the intercept coordinate $β_{0}$ is unpenalized.

Definition references

The published fixed-design Lasso objective convention

The Elements of Statistical Learning, Chapter 3 and §18.4.2

High-Dimensional Statistics lecture notes, Definition 2.12

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

Gaussian sample covariance converges in operator norm when dimension is little-o of sample size

Statement

Assume AC. Let $d_{k}, n_{k} \geq 1$ be integer sequences with $d_{k} / n_{k} \to 0$ . For each $k$ , let $G_{k} \in R^{n_{k} \times d_{k}}$ have mutually independent $N (0, 1)$ entries. Then

${∥ \frac{G_{k}^{T} G_{k}}{n_{k}} - I_{d_{k}} ∥}_{o p} \to_{k \to \infty}^{P} 0.$

Statement references

Wainwright, Appendix K, Gaussian matrix spectral-norm concentration

Facts & Assumptions

Given: AC, integer sequences $d_{k}, n_{k} \geq 1$ with $d_{k} / n_{k} \to 0$ , and matrices $G_{k}$ with independent standard-normal entries.

[A1]

The finite-dimensional Gaussian construction assumes AC and gives standard-normal linear projections with the stated covariance (The Axiom of Choice, Multivariate normal law, including singular covariance).

[F1]

A standard normal has density $(2 π)^{- 1 / 2} e^{- x^{2} / 2}$ (Standard normal and normal laws).

[F2]

For a nonnegative random variable $U$ and $a > 0$ , $P (U \geq a) \leq E [U] / a$ (Markov's inequality for random variables).

[F3]

For a real symmetric matrix $H$ , $∥ H ∥_{o p} = \sup_{∥ x ∥_{2} = 1} ∣ x^{T} H x ∣$ (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

[F4]

The Euclidean inner product satisfies $∣ x^{T} y ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ (Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors).

Proof

1.1A1F1F2givenalgebra

Fix $k$ , abbreviate $d = d_{k}$ , $n = n_{k}$ , and take a fixed unit $v \in R^{d}$ . The row products $Z_{i} = (G_{k} v)_{i}$ are independent $N (0, 1)$ by [A1]. From [F1], $E e^{t Z_{i}^{2}} = (1 - 2 t)^{- 1 / 2}$ for $t < 1 / 2$ ; applying [F2] at $t = δ / (2 (1 + δ))$ gives $P (n^{- 1} \sum_{i} Z_{i}^{2} \geq 1 + δ) \leq e^{- n [δ - \log (1 + δ)] / 2} \leq e^{- n δ^{2} / 8}$ for $0 < δ \leq 1$ , since $δ - \log (1 + δ) = \int_{0}^{δ} t / (1 + t) d t \geq δ^{2} / 4$ . For $0 < δ < 1$ , applying [F2] at $u = δ / (2 (1 - δ))$ gives $P (n^{- 1} \sum_{i} Z_{i}^{2} \leq 1 - δ) \leq e^{- n [- δ - \log (1 - δ)] / 2} \leq e^{- n δ^{2} / 4}$ , since $- δ - \log (1 - δ) = \int_{0}^{δ} t / (1 - t) d t \geq δ^{2} / 2$ ; at $δ = 1$ this event requires all $Z_{i} = 0$ and has probability zero. Thus $P (∣ v^{T} (G_{k}^{T} G_{k} / n - I_{d}) v ∣ > δ) \leq 2 e^{- n δ^{2} / 8}$ .

2.1step 1.1choosealgebra

Fix $0 < ε < 1$ and greedily add unit vectors at distance greater than $1 / 4$ from those already chosen whenever possible. The open balls of radius $1 / 8$ around a finite separated set are disjoint and lie in the radius- $9 / 8$ ball, so volume comparison gives $∣ N ∣ (1 / 8)^{d} \leq (9 / 8)^{d}$ ; hence the process terminates within $9^{d}$ choices and its maximal set is a $1 / 4$ -net. Applying step 1.1 with $δ = ε / 2$ and taking a union bound yields $P (\max_{v \in N} ∣ v^{T} (G_{k}^{T} G_{k} / n - I_{d}) v ∣ > ε / 2) \leq 2 \exp (d \log 9 - n ε^{2} / 32) \to 0$ because $d / n \to 0$ .

3.1F3F4step 2.1algebra∎

For any symmetric $H$ , [F3] gives $∥ H ∥_{o p} = \sup_{∥ x ∥_{2} = 1} ∣ x^{T} H x ∣$ . For each unit $x$ , choose $v \in N$ with $∥ x - v ∥_{2} \leq 1 / 4$ . By [F4] and the operator-norm definition, $∣ x^{T} H x - v^{T} H v ∣ = ∣ (x - v)^{T} H x + v^{T} H (x - v) ∣ \leq 2 (1 / 4) ∥ H ∥_{o p} .$ Hence $∥ H ∥_{o p} \leq 2 \max_{v \in N} ∣ v^{T} H v ∣$ . On the complementary event in step 2.1, take $H = G_{k}^{T} G_{k} / n - I_{d}$ to obtain $∥ H ∥_{o p} \leq ε$ . Since this holds for every $0 < ε < 1$ , larger tolerances follow by monotonicity, and the claimed convergence in probability follows.

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

A chi-square variable divided by a comparable dimension converges to one

Statement

Assume AC. Let $r_{k}, n_{k}$ be positive integers with $n_{k} \to \infty$ and $r_{k} / n_{k} \to 1$ . For each $k$ , let $Z_{k, 1}, \dots, Z_{k, r_{k}}$ be independent $N (0, 1)$ random variables and set $D_{k} = \sum_{j = 1}^{r_{k}} Z_{k, j}^{2}$ . Then $D_{k} / n_{k} \to 1$ in probability.

Statement references

Wainwright, Appendix K, chi-square concentration

Facts & Assumptions

Given: AC, integer sequences $r_{k}, n_{k}$ with $n_{k} \to \infty$ and $r_{k} / n_{k} \to 1$ , and independent standard-normal variables $Z_{k, j}$ .

[F1]

A standard normal has density $(2 π)^{- 1 / 2} e^{- x^{2} / 2}$ (Standard normal and normal laws).

[F2]

For a nonnegative random variable $U$ and $a > 0$ , $P (U \geq a) \leq E [U] / a$ (Markov's inequality for random variables).

[A1]

AC supplies the finite independent normal coordinates used in the statement (The Axiom of Choice).

Proof

1.1A1F1algebra

Integration by parts against [F1], using $ϕ^{'} (x) = - x ϕ (x)$ and the vanishing Gaussian boundary terms, gives $E Z_{k, j}^{2} = 1$ and $E Z_{k, j}^{4} = 3$ , hence $Var (Z_{k, j}^{2}) = 2$ .

2.1F2step 1.1givenalgebra∎

Independence and step 1.1 give $E D_{k} = r_{k}$ and $E (D_{k} - r_{k})^{2} = 2 r_{k}$ . Fix $η > 0$ ; eventually $∣ r_{k} / n_{k} - 1 ∣ < η / 2$ , so $∣ D_{k} / n_{k} - 1 ∣ > η$ implies $∣ D_{k} - r_{k} ∣ > η n_{k} / 2$ . Applying [F2] to $(D_{k} - r_{k})^{2}$ gives $P (∣ D_{k} / n_{k} - 1 ∣ > η) \leq 8 r_{k} / (η^{2} n_{k}^{2}) \to 0$ , since $r_{k} / n_{k} \to 1$ and $n_{k} \to \infty$ . This is convergence in probability.

Source notes

The cited appendix supplies the Gaussian matrix concentration context. The displayed ratio conclusion is proved here directly from the standard-normal second and fourth moments.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Finite Sudakov–Fernique comparison for Gaussian maxima

Statement

Assume AC. Let $m \geq 2$ , and let $X, Y \in R^{m}$ be independent, centered Gaussian vectors with finite covariance matrices. If

$E [(X_{i} - X_{j})^{2}] \geq E [(Y_{i} - Y_{j})^{2}] (i, j \in {1, \dots, m}),$

then $E [\max_{i} X_{i}] \geq E [\max_{i} Y_{i}]$ .

Statement references

Wainwright 2006, Appendix B, Lemma 10

Wainwright 2009, §VI

Facts & Assumptions

Given: AC and independent centered Gaussian vectors $X, Y \in R^{m}$ satisfying the displayed increment-variance inequalities.

[A1]

Under AC, Multivariate normal law, including singular covariance constructs $C^{1 / 2} Z$ with law $N_{m} (0, C)$ for $C ⪰ 0$ and independent standard-normal coordinates $Z$ . The uniqueness assertion of Characteristic function of a multivariate normal law identifies this law with that of any given centered Gaussian vector of covariance $C$ , including singular $C$ (The Axiom of Choice).

[F1]

A standard normal coordinate has density $ϕ (x) = (2 π)^{- 1 / 2} e^{- x^{2} / 2}$ , with $ϕ^{'} (x) = - x ϕ (x)$ (Standard normal and normal laws).

[F2]

A product of sigma-finite measure spaces has a product measure with the rectangle formula (For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique).

[F3]

Dominated convergence permits passage to limits when the integrands have an integrable common majorant (Dominated convergence).

[F4]

An integrable function on a sigma-finite product can be integrated in either order (Fubini's theorem for L^1 functions on a sigma-finite product).

Proof

1.1givenconstructalgebra

For $a > 0$ define $Φ_{a} (x) = a^{- 1} \log \sum_{i = 1}^{m} e^{a x_{i}}$ and $p_{i} (x) = e^{a x_{i}} / \sum_{j} e^{a x_{j}}$ . Direct differentiation gives $\partial_{i} Φ_{a} = p_{i}$ and $\partial_{i j} Φ_{a} = a (p_{i} 1_{i = j} - p_{i} p_{j})$ , while $\max_{i} x_{i} \leq Φ_{a} (x) \leq \max_{i} x_{i} + \log (m) / a$ .

2.1A1F1F2F3F4step 1.1algebra

Let $C_{X}, C_{Y}$ be the covariance matrices. By [A1], on a product probability space [F2] replace $X, Y$ by copies $X = C_{X}^{1 / 2} ξ$ , $Y = C_{Y}^{1 / 2} η$ with the same respective laws, where all coordinates of $ξ, η$ are independent standard normals. The desired expectations depend only on these laws. Put $Z_{t} = \sqrt{t} X + \sqrt{1 - t} Y$ and $F_{a} (t) = E Φ_{a} (Z_{t})$ . For $0 < t < 1$ , differentiate under the expectation; on every closed subinterval of $(0, 1)$ the derivative is bounded by a constant times $∥ ξ ∥_{2} + ∥ η ∥_{2}$ , which is integrable since $\int_{R} ∣ x ∣ ϕ (x) d x = \sqrt{2 / π}$ . Thus [F3] applies. Using [F4] to integrate one standard-normal coordinate at a time, one-dimensional integration by parts against [F1], with the bounded first and second derivatives from step 1.1, gives $F_{a}^{'} (t) = \frac{1}{2} \sum_{i, j} (C_{X} - C_{Y})_{i j} E [\partial_{i j} Φ_{a} (Z_{t})] .$ The boundary terms vanish because $ϕ (x)$ decays to zero and $\partial_{i} Φ_{a}$ is bounded.

3.1F3step 1.1step 2.1givenalgebra

Substituting the Hessian from step 1.1 into step 2.1 and using $\sum_{i} p_{i} = 1$ rewrites the derivative as $F_{a}^{'} (t) = \frac{a}{4} E [\sum_{i, j} p_{i} (Z_{t}) p_{j} (Z_{t}) (E [(X_{i} - X_{j})^{2}] - E [(Y_{i} - Y_{j})^{2}])] \geq 0.$ Hence $F_{a}$ is nondecreasing on $(0, 1)$ . For all $t \in [0, 1]$ , $∣ Φ_{a} (Z_{t}) ∣ \leq ∥ X ∥_{2} + ∥ Y ∥_{2} + \log (m) / a$ , an integrable bound, so [F3] gives continuity at the endpoints and therefore $F_{a} (1) \geq F_{a} (0)$ .

4.1step 1.1step 3.1algebra∎

The uniform approximation in step 1.1 gives $∣ E Φ_{a} (X) - E \max_{i} X_{i} ∣ \leq \log (m) / a$ and the analogous bound for $Y$ . Letting $a \to \infty$ in step 3.1 proves the asserted comparison.

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

The maximum of independent standard normals has expectation of order at least the square root of log dimension

Statement

Assume AC. There is an integer $m_{0}$ such that for every $m \geq m_{0}$ and independent standard-normal random variables $G_{1}, \dots, G_{m}$ , $E \max_{1 \leq i \leq m} G_{i} \geq \frac{1}{4} \sqrt{\log m} .$

Statement references

Rigollet and Hütter, §1.4, maximal inequalities

Facts & Assumptions

Given: AC and independent standard-normal random variables $G_{1}, \dots, G_{m}$ .

[F1]

A standard normal has density $ϕ (x) = (2 π)^{- 1 / 2} e^{- x^{2} / 2}$ , which is decreasing for $x \geq 0$ (Standard normal and normal laws).

[A1]

AC supplies the finite independent Gaussian family (The Axiom of Choice).

Proof

1.1A1F1algebra

Put $t_{m} = \frac{1}{2} \sqrt{\log m}$ and $q_{m} = P (G_{1} \geq t_{m})$ . Since $ϕ$ decreases on $[0, \infty)$ , $q_{m} \geq ϕ (t_{m} + 1 / (t_{m} + 1)) / (t_{m} + 1) \geq e^{- t_{m}^{2} / 2 - t_{m} - 1 / 2} / (\sqrt{2 π} (t_{m} + 1))$ ; the last inequality follows from $t_{m} / (t_{m} + 1) \leq t_{m}$ and $1 / (2 (t_{m} + 1)^{2}) \leq 1 / 2$ . Hence $m q_{m} \to \infty$ .

2.1F1step 1.1givenalgebra∎

Let $M_{m} = \max_{i} G_{i}$ . Independence gives $P (M_{m} < t_{m}) = (1 - q_{m})^{m} \leq e^{- m q_{m}} \to 0$ and $E [G_{1} 1_{{M_{m} < t_{m}}}] = E [G_{1} 1_{{G_{1} < t_{m}}}] (1 - q_{m})^{m - 1} \geq - (1 - q_{m})^{m - 1} / \sqrt{2 π}$ . Splitting at $M_{m} = t_{m}$ yields $E M_{m} \geq t_{m} (1 - (1 - q_{m})^{m}) - (1 - q_{m})^{m - 1} / \sqrt{2 π} \geq t_{m} / 2 = \frac{1}{4} \sqrt{\log m}$ for all sufficiently large $m$ .

Source notes

The cited notes give maximal-inequality context. The stated lower bound is derived here from a direct Gaussian-tail lower estimate and independence.

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

A unit-diagonal covariance can have conditional covariance below the reciprocal global eigenvalue bound

Statement refuted

For every real symmetric positive-definite covariance matrix $Σ$ with unit diagonal, every coordinate set $S$ for which both $S$ and $S^{c}$ are nonempty and $Σ_{S S}$ is invertible, and constants $C_{\min} > 0$ , $D_{\max} < \infty$ , $C_{\max} < \infty$ , and $0 < ϵ \leq 1$ satisfying $λ_{\min} (Σ_{S S}) \geq C_{\min}, λ_{\max} (Σ) \leq C_{\max}, ∥ (Σ_{S S})^{- 1} ∥_{\infty} \leq D_{\max}, ∥ Σ_{S^{c} S} (Σ_{S S})^{- 1} ∥_{\infty} \leq 1 - ϵ,$ the Schur conditional covariance $Σ_{S^{c} ∣ S} : = Σ_{S^{c} S^{c}} - Σ_{S^{c} S} (Σ_{S S})^{- 1} Σ_{S S^{c}}$ satisfies $λ_{\min} (Σ_{S^{c} ∣ S}) \geq 1 / C_{\max}$ . Here $∥ M ∥_{\infty} = \max_{i} \sum_{j} ∣ M_{i j} ∣$ .

Statement references

Wainwright 2006, Appendix D.6

Wainwright 2009, §IV.A, equations (28)–(30)

Facts & Assumptions

Given: The matrix inequality stated above is proposed for all positive-definite unit-diagonal $Σ$ and admissible $S, C_{\max}$ .

[A1]

For a block matrix with invertible leading block, the expression $Σ_{S^{c} S^{c}} - Σ_{S^{c} S} (Σ_{S S})^{- 1} Σ_{S S^{c}}$ is the Schur complement; here it is defined by the displayed formula.

Counterexample

1.1givenconstructalgebra

Fix any integer $s \geq 1$ , set $p = 2 s$ , $S = {1, \dots, s}$ , and take $Σ = (\begin{array}{cc} I_{s} & \frac{3}{4} I_{s} \\ \frac{3}{4} I_{s} & I_{s} \end{array})$ with $C_{\min} = 1$ , $C_{\max} = 7 / 4$ , $D_{\max} = 1$ , and $ϵ = 1 / 4$ . The vectors $(u, u)$ and $(u, - u)$ have eigenvalues $7 / 4$ and $1 / 4$ for every $u \in R^{s}$ , and these subspaces span $R^{2 s}$ ; hence $Σ$ is positive definite with unit diagonal and maximum eigenvalue $C_{\max}$ . Also $Σ_{S S} = I_{s}$ , so its minimum eigenvalue is $C_{\min}$ and its inverse infinity norm is $D_{\max}$ , while $∥ Σ_{S^{c} S} Σ_{S S}^{- 1} ∥_{\infty} = 3 / 4 = 1 - ϵ$ . Thus all stated covariance hypotheses hold.

2.1A1step 1.1algebra∎

Substitution in [A1] gives $Σ_{S^{c} ∣ S} = I_{s} - (3 I_{s} / 4) I_{s}^{- 1} (3 I_{s} / 4) = 7 I_{s} / 16$ , so $λ_{\min} (Σ_{S^{c} ∣ S}) = 7 / 16 < 4 / 7 = 1 / C_{\max}$ since $49 < 64$ . Direct block multiplication gives $Σ^{- 1} = (16 / 7) (\begin{array}{cc} I_{s} & - 3 I_{s} / 4 \\ - 3 I_{s} / 4 & I_{s} \end{array})$ , whose lower-right block is $16 I_{s} / 7$ , the inverse of the conditional covariance rather than the conditional covariance itself. Thus the proposed bound is false.

Source notes

For this block family, the lower-right block of $Σ^{- 1}$ is $16 I_{s} / 7$ , the inverse of $Σ_{S^{c} ∣ S}$ , not $Σ_{S^{c} ∣ S}$ itself.

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passOpen item page →

The Cmax-only Wainwright lower signed-support threshold can predict failure when Lasso succeeds

Statement

Assume the Axiom of Choice. Wainwright's planned lower-threshold claim is the following: along a sequence of real Gaussian linear models with $S = {j : β_{j}^{*} \neq 0}$ , $s = ∣ S ∣$ , $N = p - s$ , $s, n - s, N \to \infty$ , and independent observations $y_{i} = x_{i}^{T} β^{*} + w_{i}, x_{i} \sim N_{p} (0, Σ), w_{i} \sim N (0, σ^{2}),$ where $X$ has rows $x_{i}^{T}$ , $y = (y_{i})$ , design and noise are independent, there is no separate intercept, and $Σ$ has unit diagonal. Suppose constants $C_{\min} > 0$ , $C_{\max} < \infty$ , $D_{\max} < \infty$ , and $0 < ϵ \leq 1$ satisfy $λ_{\min} (Σ_{S S}) \geq C_{\min}, λ_{\max} (Σ) \leq C_{\max}, ∥ (Σ_{S S})^{- 1} ∥_{\infty} \leq D_{\max}, ∥ Σ_{S^{c} S} (Σ_{S S})^{- 1} ∥_{\infty} \leq 1 - ϵ,$ with $∥ M ∥_{\infty} = \max_{i} \sum_{j} ∣ M_{i j} ∣$ . Define $θ_{ℓ} = \frac{(\sqrt{C_{\max}} - \sqrt{C_{\max} - 1 / C_{\max}})^{2}}{C_{\max} (2 - ϵ)^{2}} .$ For every fixed $ν > 0$ and every positive non-increasing sequence $λ_{n}$ , if $n < 2 (θ_{ℓ} - ν) s \log N + s + 1$ , then the probability that there exists an optimizer with $sgn (\hat{β}) = sgn (β^{*})$ for $∥ y - X β ∥_{2}^{2} / (2 n) + λ_{n} ∥ β ∥_{1}$ tends to zero.

Statement references

Wainwright 2006, Theorem 1(a)

Wainwright 2009, §IV.A, revised lower-threshold interface

Facts & Assumptions

Given: The Gaussian model, covariance hypotheses, exact loss normalization, success event, and claimed lower implication in the Statement.

[F1]

For an iid standard-Gaussian matrix of dimension $d = o (n)$ , its Gram matrix divided by $n$ converges in operator norm to identity (Gaussian sample covariance converges in operator norm when dimension is little-o of sample size).

[F2]

A sum of $q$ independent squared standard normals divided by $n$ converges in probability to one if $q / n \to 1$ and $n \to \infty$ (A chi-square variable divided by a comparable dimension converges to one).

[F3]

Under AC, a centered Gaussian vector with covariance $C ⪰ 0$ can be realized as $C^{1 / 2} G$ for a vector of independent standard normals (Multivariate normal law, including singular covariance).

[F4]

A nondegenerate multivariate normal has its usual Gaussian density; in particular the density with identity covariance factors into independent standard-normal densities (A positive-definite multivariate normal law has its Gaussian density, Independent random elements have product joint law).

[F5]

A standard normal has density $(2 π)^{- 1 / 2} e^{- x^{2} / 2}$ (Standard normal and normal laws). Completing the square gives $E e^{t U} = e^{v t^{2} / 2}$ for $U \sim N (0, v)$ ; applying Markov to $e^{t U}$ with $t = 1 / v$ , and likewise to $e^{- t U}$ , yields $P (∣ U ∣ \geq 1) \leq 2 e^{- 1 / (2 v)}$ when $v > 0$ (Markov's inequality for random variables). For $v = 0$ the probability is zero.

[F6]

The Lasso objective is $F (β) = ∥ y - X β ∥_{2}^{2} / (2 n) + λ ∥ β ∥_{1}$ (Fixed-design least-squares, ridge, lasso, group, and fused objectives).

[A1]

AC is assumed for the finite Gaussian constructions and suppliers (The Axiom of Choice).

Refutation

1.1A1F3F4givenconstruct

Fix $δ = ϵ = 10^{- 6}$ , $c = (1 - ϵ) / 2$ , $a = 1 / 1000$ , and $ν = 1 / 100000$ . For integers $N \geq 2$ tending to infinity set $s = N^{3}, p = s + N, n = s + ⌈ a s \log N ⌉, S = {1, \dots, s}, λ_{n} = 1.$ In each observation let the first $2 N$ active coordinates consist of independent pairs $(U_{j}, V_{j})$ , $1 \leq j \leq N$ , each with covariance $B = (\begin{array}{cc} 1 & - (1 - δ) \\ - (1 - δ) & 1 \end{array}),$ and let the other $s - 2 N$ active coordinates be independent standard normals, independent of these pairs. Take independent standard normals $Z_{j}$ , independent also of all active variables, and define the inactive coordinates by $T_{j} = c (U_{j} - V_{j}) + \sqrt{r} Z_{j}, r = 1 - (1 - ϵ)^{2} (1 - δ / 2) .$ Take independent observations and independent standard-normal noise $w_{i}$ ; set $β_{i}^{*} = n$ on $S$ and zero off $S$ . These finite Gaussian constructions define the model in the Statement, with $σ^{2} = 1$ and no intercept.

2.1step 1.1algebra

The eigenvalues of $B$ are $δ$ and $2 - δ$ , and each row of $B^{- 1}$ has absolute sum $1 / δ$ . Thus $C_{\min} = δ$ and $D_{\max} = 1 / δ$ work. Each inactive coordinate regresses on its pair with coefficients $(c, - c)$ , so $∥ Σ_{S^{c} S} Σ_{S S}^{- 1} ∥_{\infty} = 2 c = 1 - ϵ$ . Its variance is one by the definition of $r$ , and $0 < r < 2 ϵ + δ / 2 < 3 \cdot 10^{- 6}$ . The full covariance, after reordering, is a direct sum of positive-definite three-dimensional covariance blocks and singleton identity blocks: each triple is an invertible linear image of $(U_{j}, V_{j}, Z_{j})$ because $r > 0$ . Every triple has trace three, so every eigenvalue is at most three. Consequently $C_{\max} = 3$ bounds the maximum eigenvalue of the full covariance, and all its diagonal entries are one.

3.1givenstep 1.1step 2.1algebra

For these constants, $\sqrt{3} - \sqrt{8 / 3} = \frac{1 / 3}{\sqrt{3} + \sqrt{8 / 3}} > \frac{1}{12}, 3 (2 - ϵ)^{2} < 12,$ so the precise claimed constant satisfies $θ_{ℓ} > 1 / 1728$ and $2 (θ_{ℓ} - ν) > 2 (1 / 1728 - 1 / 100000) > a$ . Since $⌈ a s \log N ⌉ \leq a s \log N + 1$ , the claimed failure inequality $n < 2 (θ_{ℓ} - ν) s \log N + s + 1$ holds. Also $s, n - s, N \to \infty$ and $s / n \to 0$ . The constant penalty is positive and non-increasing. The lower claim puts no restriction on $ρ_{n} = n$ .

4.1F1F3F5step 2.1step 3.1constructalgebra

Write $X_{S} = Z Σ_{S S}^{1 / 2}$ , with $Z$ an $n \times s$ iid standard-Gaussian matrix, and put $G = X_{S}^{T} X_{S}$ and $A = G / n$ . By [F1] and $s / n \to 0$ , with probability tending to one the minimum eigenvalue of $A$ is at least $δ / 2$ and $∥ A^{- 1} ∥_{o p} \leq 2 / δ$ . On this event define ${\hat{β}}_{S} = n 1 + η - A^{- 1} 1, η = A^{- 1} X_{S}^{T} w / n, {\hat{β}}_{S^{c}} = 0.$ The shrinkage term satisfies $∥ A^{- 1} 1 ∥_{\infty} \leq 2 \sqrt{s} / δ = o (n)$ . Conditional on $X_{S}$ , $η$ is centered Gaussian with covariance $A^{- 1} / n$ , so [F5] and a finite union bound give $P (∥ η ∥_{\infty} \geq 1 ∣ X_{S}) \leq 2 s e^{- n δ / 4} ⟶ 0$ uniformly on the spectral event. Thus every active candidate coordinate is positive with probability tending to one.

4.2A1F2F3F4step 1.1step 2.1step 3.1algebrachoose

Put $b = 1_{s}$ and $T = b^{T} Σ_{S S}^{- 1} b = s - 2 N + 2 N / δ$ , so $T / s \to 1$ . To compute $Q = b^{T} G^{- 1} b$ , put $v = Σ_{S S}^{- 1 / 2} b$ and choose a fixed orthogonal matrix with first column $v / ∥ v ∥_{2}$ . Orthogonal invariance and [F4] make the rotated columns of $Z$ , written $[h, H]$ , mutually independent standard-Gaussian columns. They have full column rank almost surely: condition successively on earlier columns; for each fixed proper column subspace, projection onto any fixed nonzero normal vector has a continuous normal law, so a new standard-Gaussian column belongs to that subspace with probability zero. For full-rank $H$ put $P_{H} = H (H^{T} H)^{- 1} H^{T}, D = h^{T} (I - P_{H}) h .$ Block elimination in the Gram matrix of $[h, H]$ gives exactly $Q = T / D$ . For each fixed full-rank $H$ , the projector $I - P_{H}$ has rank $n - s + 1$ , so orthogonal invariance gives the conditional law $D \sim χ_{n - s + 1}^{2}$ . This conditional law is the same for every such $H$ ; the projector is a measurable function of $H$ , and no random basis is selected. Since $(n - s + 1) / n \to 1$ , [F2] gives $D / n \to 1$ in probability, and therefore $Q / (s / n) \to 1$ in probability.

5.1F2F3F4step 1.1step 4.1step 4.2algebra

Let $P = X_{S} G^{- 1} X_{S}^{T}$ . The candidate residual is $u = y - X_{S} {\hat{β}}_{S} = (I - P) w + n X_{S} G^{- 1} b, X_{S}^{T} u / n = b .$ Its two displayed summands are orthogonal. For inactive column $j$ , the construction gives $X_{j} = X_{S} a_{j} + \sqrt{r} z_{j}$ , where $a_{j}$ has entries $(c, - c)$ on its pair and zero elsewhere, and the $z_{j}$ are mutually independent standard-Gaussian vectors independent of $X_{S}, w$ . Because $a_{j}^{T} b = 0$ , the dual variables $V_{j} = X_{j}^{T} u / n = \sqrt{r} z_{j}^{T} u / n$ are, conditional on $X_{S}, w$ , independent centered normals of common variance $r M, M = ∥ u ∥_{2}^{2} / n^{2} = Q + ∥ (I - P) w ∥_{2}^{2} / n^{2} .$ By [F2], $∥ w ∥_{2}^{2} / n \to 1$ in probability. Since the second term is at most $∥ w ∥_{2}^{2} / n^{2}$ , step 4.2 and $s \to \infty$ show $P (M \leq 4 s / n) \to 1$ . This event depends only on $X_{S}, w$ and is independent of all inactive residual vectors.

6.1F5step 1.1step 2.1step 4.1step 5.1algebra

On the event $M \leq 4 s / n$ , since $n \geq a s \log N$ and $r < 3 \cdot 10^{- 6}$ , $r M \leq \frac{4 r}{a \log N} < \frac{3}{250 \log N} .$ Applying [F5] and a finite union bound conditionally on $X_{S}, w$ yields the uniform bound $P ⁣ (\max_{1 \leq j \leq N} ∣ V_{j} ∣ \geq 1 | X_{S}, w) \leq 2 N \exp ⁣ (- \frac{1}{2 r M}) \leq 2 N^{1 - 125 / 3} ⟶ 0.$ Removing the conditioning and adding the probability of $M > 4 s / n$ proves $\max_{j} ∣ V_{j} ∣ < 1$ with probability tending to one. Intersecting with the event in step 4.1 preserves probability tending to one and gives both active sign correctness and inactive dual feasibility.

7.1F6step 1.1step 3.1step 4.1step 5.1step 6.1algebra∎

On this intersection put $z = X^{T} u / n$ . It equals one on $S$ and satisfies $∣ z_{j} ∣ < 1$ off $S$ . Since the candidate is positive on $S$ and zero off $S$ , the scalar inequality $∣ {\hat{β}}_{i} + h_{i} ∣ - ∣ {\hat{β}}_{i} ∣ \geq z_{i} h_{i}$ holds for every coordinate and every real $h_{i}$ . For every $h \in R^{p}$ , expand [F6], with $λ_{n} = 1$ , to obtain $F (\hat{β} + h) - F (\hat{β}) = \frac{∥ X h ∥_{2}^{2}}{2 n} - h^{T} X^{T} u / n + ∥ \hat{β} + h ∥_{1} - ∥ \hat{β} ∥_{1} \geq 0.$ Thus this candidate is an optimizer with $sgn (\hat{β}) = sgn (β^{*})$ . Its existence has probability tending to one, whereas step 3.1 meets the exact hypotheses that predict probability tending to zero. This refutes the stated lower implication.

Source notes

This refutes the conclusion itself, independently of the erroneous inverse-block identity in the 2006 Appendix D.6. The construction uses $s / (p - s) \to \infty$ , which the stated source and planned hypotheses permit; it does not refute a theorem with an additional dimensional restriction. The 2009 journal article's equation (27) defines $ρ_{ℓ} (C) = \frac{1}{2} \min_{i \neq j} (C_{i i} + C_{j j} - 2 C_{i j})$ , a minimum pairwise increment-variance parameter, not a least eigenvalue. Its revised threshold interface is distinct and is not substituted for the claim refuted here.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

The full ordinary least-squares solution set and the unique ridge solution

Statement

Let $n, p \geq 1$ , $X \in R^{n \times p}$ , and $y \in R^{n}$ . The ordinary least-squares minimizers of $∥ y - X β ∥_{2}^{2}$ are exactly the solutions of $X^{T} X β = X^{T} y$ ; if $β_{0}$ is one such solution, the full minimizer set is $β_{0} + \ker X$ . It is a singleton if and only if the columns of $X$ are linearly independent. For every $λ > 0$ , the ridge objective $∥ y - X β ∥_{2}^{2} + λ ∥ β ∥_{2}^{2}$ has the unique minimizer ${\hat{β}}_{r i d g e} = (X^{T} X + λ I_{p})^{- 1} X^{T} y .$

Statement references

The Elements of Statistical Learning, Chapter 3 §§3.2 and 3.4

Rigollet and Hütter, §2.2, unconstrained least squares

Facts & Assumptions

Given: A finite real design matrix $X$ , a response vector $y$ , and, for the ridge claim, a real $λ > 0$ .

[F1]

Finite-dimensional least-squares minimizers exist, satisfy the normal equations, and form $β_{0} + \ker X$ (For a linear map $T : V \to W$ between finite-dimensional inner-product spaces, $x$ minimises $∥ T x - b ∥$ if and only if $T^{*} (T x - b) = 0$ , equivalently $T^{*} T x = T^{*} b$ ; minimisers exist and any two differ by an element of $\ker T$ ).

[F2]

A finite real matrix has a singular value decomposition with orthonormal left and right bases (Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition).

[F3]

The ridge objective is $∥ X β - y ∥_{2}^{2} + λ ∥ β ∥_{2}^{2}$ for $λ > 0$ (The Tikhonov regularised least-squares objective $∥ A x - b ∥_{2}^{2} + λ ∥ x ∥_{2}^{2}$ for $λ > 0$ ).

[F4]

That objective is strictly convex and has unique minimizer $(X^{T} X + λ I_{p})^{- 1} X^{T} y$ (For every $λ > 0$ , the Tikhonov objective is strictly convex and has the unique minimiser $(A^{*} A + λ I)^{- 1} A^{*} b$ ).

[F5]

The empirical squared-loss convention for OLS and the ridge objective is fixed in Fixed-design least-squares, ridge, lasso, group, and fused objectives.

Proof

1.1F1F5

Apply [F1] to the linear map $β \mapsto X β$ between finite-dimensional Euclidean spaces. It gives existence, the equation $X^{T} (X β - y) = 0$ , and the full set $β_{0} + \ker X$ .

2.1step 1.1algebra

The translate $β_{0} + \ker X$ has exactly one element if and only if $\ker X = {0}$ . By definition this is equivalent to linear independence of the columns, proving the OLS uniqueness assertion.

3.1F2F3F4F5algebra∎

By [F2], there is an orthonormal basis of $R^{p}$ in which $X^{T} X$ is diagonal with entries $σ_{1}^{2}, \dots, σ_{r}^{2}, 0, \dots, 0$ . Thus $X^{T} X + λ I_{p}$ has positive diagonal entries $σ_{j}^{2} + λ$ and $λ$ , so the inverse exists. The objective in [F3] is exactly the ridge objective in [F5], and [F4] gives its unique minimizer in the displayed formula.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Lasso on an orthonormal design is coordinatewise soft-thresholding

Statement

Let $n, p \geq 1$ , $X \in R^{n \times p}$ satisfy $X^{T} X = I_{p}$ , and let $y \in R^{n}$ and $λ > 0$ . The objective $\frac{1}{2 n} ∥ y - X β ∥_{2}^{2} + λ ∥ β ∥_{1}$ has the unique minimizer ${\hat{β}}_{j} = S_{n λ} ((X^{T} y)_{j})$ , where $S_{a} (t) = sgn (t) (∣ t ∣ - a)_{+}$ , $(u)_{+} = \max {u, 0}$ , and $sgn (0) = 0$ . Thus the threshold is $n λ$ under this loss normalization.

Statement references

The Elements of Statistical Learning, §3.4.1 and §18.4

Rigollet and Hütter, §§2.3–2.4, soft thresholding and the Lasso objective

Facts & Assumptions

Given: $n, p \geq 1$ , $X^{T} X = I_{p}$ , $y \in R^{n}$ , and $λ > 0$ .

[F1]

The fixed-design empirical squared loss is $∥ y - X β ∥_{2}^{2} / (2 n)$ and the Lasso penalty is $λ ∥ β ∥_{1}$ (Fixed-design least-squares, ridge, lasso, group, and fused objectives).

Proof

1.1F1givenalgebra

Put $z = X^{T} y$ . Expanding the squared norm and using $X^{T} X = I_{p}$ gives $\frac{1}{2 n} ∥ y - X β ∥_{2}^{2} + λ ∥ β ∥_{1} = \frac{∥ y ∥_{2}^{2} - ∥ z ∥_{2}^{2}}{2 n} + \sum_{j = 1}^{p} (\frac{(β_{j} - z_{j})^{2}}{2 n} + λ ∣ β_{j} ∣)$ . The first term is constant in $β$ , so the minimization separates into scalar strictly convex objectives.

2.1step 1.1algebra

For a scalar $z$ , the derivative of $(t - z)^{2} / (2 n) + λ ∣ t ∣$ on $t > 0$ is $(t - z) / n + λ$ , and on $t < 0$ it is $(t - z) / n - λ$ . The positive stationary point is $t = z - n λ$ exactly when $z > n λ$ ; the negative stationary point is $t = z + n λ$ exactly when $z < - n λ$ . When $∣ z ∣ \leq n λ$ , the one-sided derivatives at zero satisfy $(- z / n - λ) \leq 0 \leq (- z / n + λ)$ , so zero minimizes. Strict convexity makes each minimizer unique, and these cases are precisely $S_{n λ} (z)$ .

3.1step 1.1step 2.1∎

Applying step 2.1 to every coordinate yields the stated vector formula and uniqueness.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

The active coordinates of a signed Lasso optimizer satisfy restricted normal equations

Statement

Let $X \in R^{n \times p}$ , $y \in R^{n}$ , $λ > 0$ , and let $S \subseteq {1, \dots, p}$ be nonempty. Assume the active design $X_{S}$ has full column rank. If an optimizer $\hat{β}$ of $∥ y - X β ∥_{2}^{2} / (2 n) + λ ∥ β ∥_{1}$ has support exactly $S$ and sign vector $b = sgn ({\hat{β}}_{S}) \in {- 1, 1}^{∣ S ∣}$ , then ${\hat{β}}_{S} = (X_{S}^{T} X_{S} / n)^{- 1} (X_{S}^{T} y / n - λ b) .$ This is a necessary active-coordinate condition only; it does not assert that the candidate satisfies any inactive-coordinate condition.

Statement references

Wainwright 2006, §2.3, primal-dual witness construction

Rigollet and Hütter, Definition 2.12

Facts & Assumptions

Given: A finite fixed-design Lasso problem, a nonempty active set $S$ , an optimizer supported on $S$ with nonzero active coordinates, and full column rank of $X_{S}$ .

[F1]

The objective uses loss $∥ y - X β ∥_{2}^{2} / (2 n)$ and penalty $λ ∥ β ∥_{1}$ (Fixed-design least-squares, ridge, lasso, group, and fused objectives).

Proof

1.1F1givenalgebra

Fix an active coordinate $j$ . For $∣ h ∣ < ∣ {\hat{β}}_{j} ∣$ , changing that coefficient by $h$ preserves its sign $b_{j}$ , so the restricted objective is differentiable in $h$ and has a local minimum at $h = 0$ . Its positive difference quotients are nonnegative and its negative difference quotients are nonpositive; since the derivative exists, it is zero. Differentiating the squared loss and the fixed-sign penalty in each active coordinate gives $X_{S}^{T} (X_{S} {\hat{β}}_{S} - y) / n + λ b = 0$ .

2.1step 1.1givenalgebra∎

Full column rank makes $X_{S}^{T} X_{S} / n$ invertible. Rearranging step 1.1 and multiplying by this inverse gives the displayed formula. The argument uses only active stationarity and makes no assertion about inactive coordinates.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passOpen item page →

The unrestricted Wainwright signed-support threshold claim fails without active-dimension control

Statement

Assume the Axiom of Choice, the Axiom of Dependent Choice, and countable choice. Wainwright's 2006 two-sided threshold claim is the following: consider a sequence of real Gaussian linear models with $S = {j : β_{j}^{*} \neq 0}$ , $s = ∣ S ∣$ , $N = p - s$ , $ρ_{n} = \min_{j \in S} ∣ β_{j}^{*} ∣$ , $s, n - s, N \to \infty$ , and $y_{i} = x_{i}^{T} β^{*} + w_{i}, x_{i} \sim N_{p} (0, Σ), w_{i} \sim N (0, σ^{2}),$ where observations are independent, design and noise are independent, there is no separate intercept, and $Σ$ has unit diagonal. Suppose constants $C_{\min} > 0$ , $C_{\max} < \infty$ , $D_{\max} < \infty$ , and $0 < ϵ \leq 1$ satisfy $λ_{\min} (Σ_{S S}) \geq C_{\min}, λ_{\max} (Σ) \leq C_{\max}, ∥ (Σ_{S S})^{- 1} ∥_{\infty} \leq D_{\max}, ∥ Σ_{S^{c} S} (Σ_{S S})^{- 1} ∥_{\infty} \leq 1 - ϵ,$ where $∥ M ∥_{\infty} = \max_{i} \sum_{j} ∣ M_{i j} ∣$ . Define $θ_{ℓ} = \frac{(\sqrt{C_{\max}} - \sqrt{C_{\max} - 1 / C_{\max}})^{2}}{C_{\max} (2 - ϵ)^{2}}, θ_{u} = \frac{C_{\max}}{ϵ^{2} C_{\min}} .$ Let $X$ have rows $x_{i}^{T}$ , $w = (w_{i})$ , and $y = (y_{i})$ . For $λ_{n} > 0$ , let success mean that there exists an optimizer with $sgn (\hat{β}) = sgn (β^{*})$ for the objective $∥ y - X β ∥_{2}^{2} / (2 n) + λ_{n} ∥ β ∥_{1}$ . The threshold claim is that for every fixed $ν > 0$ , success probability tends to zero if $n < 2 (θ_{ℓ} - ν) s \log N + s + 1$ for every non-increasing positive $λ_{n}$ , and tends to one if $n > 2 (θ_{u} + ν) s \log N + s$ , $λ_{n} \to 0$ , $n λ_{n}^{2} / \log N \to \infty$ , and $ρ_{n}^{- 1} (λ_{n} + \sqrt{\log s / n}) \to 0$ .

Statement references

Wainwright 2006, Theorem 1 and its proof

Facts & Assumptions

Given: The model, covariance assumptions, loss normalization, threshold constants, and claimed two-sided conclusion in the Statement refuted.

[F1]

If an optimizer has positive signs on its active coordinates and the active design has full column rank, its active coefficients equal $(X_{S}^{T} X_{S} / n)^{- 1} (X_{S}^{T} y / n - λ 1)$ (The active coordinates of a signed Lasso optimizer satisfy restricted normal equations).

[F2]

For an iid standard-Gaussian matrix with dimension $d = o (n)$ , its Gram matrix divided by $n$ converges in operator norm to the identity (Gaussian sample covariance converges in operator norm when dimension is little-o of sample size).

[F3]

If $r / n \to 1$ , a sum of $r$ independent squared standard normals divided by $n$ converges in probability to one (A chi-square variable divided by a comparable dimension converges to one).

[F4]

For finite centered Gaussian vectors, larger pairwise increment variances imply a larger expected maximum (Finite Sudakov–Fernique comparison for Gaussian maxima).

[F5]

For sufficiently large $m$ , the expected maximum of $m$ independent standard normals is at least $\frac{1}{4} \sqrt{\log m}$ (The maximum of independent standard normals has expectation of order at least the square root of log dimension).

[F6]

An $L$ -Lipschitz function of a standard Gaussian has upper-tail probability at most $e^{- r^{2} / (2 L^{2})}$ above its mean, under AC, DC, and countable choice (Lipschitz concentration for standard Gaussian measure).

[F7]

Under AC, a multivariate normal with covariance $C ⪰ 0$ is realized as $C^{1 / 2} G$ for a standard Gaussian vector $G$ (Multivariate normal law, including singular covariance).

[F8]

A nondegenerate multivariate normal has density proportional to $e^{- (x - m)^{T} Σ^{- 1} (x - m) / 2}$ (A positive-definite multivariate normal law has its Gaussian density).

[F9]

Independent random elements have product joint law (Independent random elements have product joint law).

[F10]

A standard normal has density $(2 π)^{- 1 / 2} e^{- x^{2} / 2}$ (Standard normal and normal laws).

[F11]

For nonnegative $U$ and $a > 0$ , $P (U \geq a) \leq E [U] / a$ (Markov's inequality for random variables).

[F12]

Product measures exist for sigma-finite probability factors and have the rectangle formula (For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique).

[A1]

AC is assumed for the finite Gaussian laws (The Axiom of Choice).

[A2]

DC and countable choice are separately assumed for the Gaussian Lipschitz concentration result (The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain, The Axiom of Countable Choice ( ${A C}_{ω}$ )).

Refutation

1.1givenconstructalgebra

For integers $n \leq ⌈ e^{e} ⌉$ , set $λ_{n} = 1$ , and for $n > ⌈ e^{e} ⌉$ set $λ_{n} = (\log \log n)^{- 1 / 2}$ . Since $\log \log n > 1$ in the latter range and is increasing, this defines a positive non-increasing sequence. For $k \geq 2$ , set $N_{k} = ⌈ e^{k} ⌉$ , $s_{k} = ⌈ e^{k^{2}} ⌉$ , $n_{k} = ⌈ 5 s_{k} k ⌉$ , and $p_{k} = s_{k} + N_{k}$ . Use the model subsequence at sample sizes $n_{k}$ , with $Σ_{k} = I_{p_{k}}$ , $β_{k}^{*} = (1_{s_{k}}, 0_{N_{k}})$ , $σ^{2} = 1$ , and $λ_{k} = λ_{n_{k}}$ . Then $C_{\min} = C_{\max} = D_{\max} = ϵ = 1$ , $ρ_{n_{k}} = 1$ , and $θ_{u} = 1$ , while $\log N_{k} \sim k$ , $\log s_{k} \sim k^{2}$ , $n_{k} / s_{k} \sim 5 k$ , and $\log \log n_{k} \sim 2 \log k$ . For $ν = 1 / 2$ , $n_{k} > 3 s_{k} \log N_{k} + s_{k}$ eventually; also $λ_{k} \to 0$ , $n_{k} λ_{k}^{2} / \log N_{k} \to \infty$ , and $λ_{k} + \sqrt{\log s_{k} / n_{k}} \to 0$ , so the claimed upper hypotheses hold.

2.1A1F7F8F9F10step 1.1algebra

Let $X_{S}$ be the active design, $A = X_{S}^{T} X_{S} / n_{k}$ , and $v = X_{S}^{T} w / n_{k}$ . Choose an orthogonal $R$ with first column $q = 1_{s_{k}} / \sqrt{s_{k}}$ and write $X_{S} R = [h, H]$ . Each row keeps its $N (0, I_{s_{k}})$ projection laws under $R$ ; [F7]–[F10] give its factorized standard-normal density and [F9] gives independent rows, so entries of $h, H$ are mutually independent standard normals. Set $B = H^{T} H$ , $P_{H} = H B^{- 1} H^{T}$ when $B$ is invertible, and $d = h^{T} (I - P_{H}) h$ . Conditional on $H$ , $d$ is chi-square with $n_{k} - s_{k} + 1$ degrees of freedom.

3.1F2F3step 2.1givenalgebra

Since $s_{k} / n_{k} \to 0$ and $(n_{k} - s_{k} + 1) / n_{k} \to 1$ , [F2] applied to $X_{S}$ and $H$ and [F3] applied conditionally to $d$ show that $E_{A, k} = {∥ A - I ∥_{o p} \leq 1 / 2}$ , $E_{B, k} = {∥ B / n_{k} - I ∥_{o p} \leq 1 / 2}$ , and $E_{d, k} = {n_{k} / 2 \leq d \leq 2 n_{k}}$ each have probability tending to one. Their intersection $E_{k} = E_{A, k} \cap E_{B, k} \cap E_{d, k}$ therefore has probability tending to one.

4.1F10F11step 3.1algebra

On $E_{A, k}$ , $∥ A^{- 1} ∥_{o p} \leq 2$ . Given $X_{S}$ , $A^{- 1} v$ is centered Gaussian with covariance $A^{- 1} / n_{k}$ , so each coordinate variance is at most $2 / n_{k}$ . Completing the square in [F10] gives moment-generating function $e^{τ_{i}^{2} t^{2} / 2}$ ; [F11] at $t = n_{k} / 2$ yields $P (∣ (A^{- 1} v)_{i} ∣ \geq 1 ∣ X_{S}) \leq 2 e^{- n_{k} / 4}$ . A union bound gives $P (∥ A^{- 1} v ∥_{\infty} \geq 1 ∣ X_{S}) \leq 2 s_{k} e^{- n_{k} / 4}$ on $E_{A, k}$ , hence $P (E_{A, k} \cap {∥ A^{- 1} v ∥_{\infty} \geq 1}) \leq 2 s_{k} e^{- n_{k} / 4} \to 0$ .

4.2A1F7F8F9F10step 2.1step 3.1algebra

For fixed full-rank $H$ , the Gaussian coordinates of $h$ along $im H$ and its orthogonal complement are independent by the factorized density [F8]–[F10]; hence $H^{T} h \sim N (0, B)$ is independent of $d$ , and $B^{- 1} H^{T} h$ has covariance $B^{- 1}$ . This conditional law is measurable because $B^{- 1}$ and $P_{H}$ are Borel on $\det B > 0$ . Direct multiplication gives $(\begin{array}{cc} h^{T} h & h^{T} H \\ H^{T} h & B \end{array}) (\binom{1}{- B^{- 1} H^{T} h}) = (\binom{d}{0})$ ; since $R^{T} 1 = \sqrt{s_{k}} e_{1}$ , it follows that $A^{- 1} 1 = (n_{k} / d) 1 + Z$ , where $Z = - (n_{k} \sqrt{s_{k}} / d) R (\binom{0}{B^{- 1} H^{T} h})$ is conditionally centered Gaussian with covariance $Γ = (n_{k}^{2} s_{k} / d^{2}) R (\begin{array}{cc} 0 & 0 \\ 0 & B^{- 1} \end{array}) R^{T}$ . On $E_{B, k} \cap E_{d, k}$ , $∥ Γ ∥_{o p} \leq 8 s_{k} / n_{k}$ and, for $i \neq j$ , $E [(Z_{i} - Z_{j})^{2} ∣ H, d] \geq (n_{k}^{2} s_{k} / d^{2}) (1 / (2 n_{k})) ∥ e_{i} - e_{j} ∥_{2}^{2} \geq s_{k} / (4 n_{k})$ .

5.1F4F5F7F10F12step 4.2givenalgebra

Conditional on $H, d$ when $E_{B, k} \cap E_{d, k}$ holds, use [F12] to put the law of $Z$ and an independent standard Gaussian vector $G$ on a product space, and set $Y_{i} = \sqrt{s_{k} / (8 n_{k})} G_{i}$ . By [F4], their increment variances, and [F5], $E [\max_{i} Z_{i} ∣ H, d] \geq E \max_{i} Y_{i} \geq (4 \sqrt{8})^{- 1} \sqrt{s_{k} \log s_{k} / n_{k}}$ .

6.1A1A2F6F7step 4.2step 5.1algebra

The map $z \mapsto - \max_{i} z_{i}$ is 1-Lipschitz. By [F7], represent $Z = Γ^{1 / 2} G$ conditionally and apply [F6] with Lipschitz constant $\sqrt{∥ Γ ∥_{o p}}$ and deviation half the mean bound in step 5.1; uniformly when $E_{B, k} \cap E_{d, k}$ holds, $P (\max_{i} Z_{i} < \frac{1}{2} E [\max_{i} Z_{i} ∣ H, d] ∣ H, d) \leq e^{- c \log s_{k}} \to 0$ for some fixed $c > 0$ . Hence $\max_{i} Z_{i} \geq (8 \sqrt{8})^{- 1} \sqrt{s_{k} \log s_{k} / n_{k}}$ with probability tending to one.

7.1step 1.1step 3.1step 4.2step 6.1algebra

On $E_{d, k}$ , $n_{k} / d \geq 1 / 2$ . Step 6.1 gives $\max_{i} Z_{i} \geq (8 \sqrt{8})^{- 1} \sqrt{s_{k} \log s_{k} / n_{k}}$ with probability tending to one, and $P (E_{B, k} \cap E_{d, k}) \to 1$ . Since $A^{- 1} 1 = (n_{k} / d) 1 + Z$ on this event, and step 1.1 gives $\log s_{k} \sim k^{2}$ , $n_{k} / s_{k} \sim 5 k$ , and $λ_{k} \sim (2 \log k)^{- 1 / 2}$ , it follows that $λ_{k} \max_{i} (A^{- 1} 1)_{i} \geq λ_{k} (1 / 2 + (8 \sqrt{8})^{- 1} \sqrt{s_{k} \log s_{k} / n_{k}}) \to \infty$ in probability; the diverging term has order $\sqrt{k / \log k}$ .

8.1F1step 3.1step 4.1step 7.1givenalgebra∎

By steps 3.1, 4.1, and 7.1 and a union bound, with probability tending to one $E_{A, k}$ holds, $∥ A^{- 1} v ∥_{\infty} < 1$ , and $λ_{k} \max_{i} (A^{- 1} 1)_{i} > 2$ . If an optimizer had the correct signed support, [F1] would force ${\hat{β}}_{S} = A^{- 1} (X_{S}^{T} y / n_{k} - λ_{k} 1) = 1 + A^{- 1} v - λ_{k} A^{- 1} 1$ . At an index attaining the maximum, these events imply ${\hat{β}}_{i} < 0$ , contradicting the required positive sign. Thus exact signed-support success probability tends to zero, refuting the upper implication and the combined threshold statement.

Source notes

The counterexample uses $\log s_{k} / \log (p_{k} - s_{k}) \to \infty$ . It isolates the missing active-coordinate fluctuation term in the claimed upper implication; it makes no prediction-risk claim and does not establish the separate lower-threshold branch.

4 · Examples, counterexamples and false statements

None yet.

Linear prediction, shrinkage, and sparse regression

2 · Logical flowchart

3 · Definitions, theorems and proofs

Fixed-design least-squares, ridge, lasso, group, and fused objectives

Definition

Definition references

Gaussian sample covariance converges in operator norm when dimension is little-o of sample size

Statement

Statement references

Facts & Assumptions

Proof

A chi-square variable divided by a comparable dimension converges to one

Statement

Statement references

Facts & Assumptions

Proof

Source notes

Finite Sudakov–Fernique comparison for Gaussian maxima

Statement

Statement references

Facts & Assumptions

Proof

The maximum of independent standard normals has expectation of order at least the square root of log dimension

Statement

Statement references

Facts & Assumptions

Proof

Source notes

A unit-diagonal covariance can have conditional covariance below the reciprocal global eigenvalue bound

Statement refuted

Statement references

Facts & Assumptions

Counterexample

Source notes

The Cmax-only Wainwright lower signed-support threshold can predict failure when Lasso succeeds

Statement

Statement references

Facts & Assumptions

Refutation

Source notes

The full ordinary least-squares solution set and the unique ridge solution

Statement

Statement references

Facts & Assumptions

Proof

Lasso on an orthonormal design is coordinatewise soft-thresholding

Statement

Statement references

Facts & Assumptions

Proof

The active coordinates of a signed Lasso optimizer satisfy restricted normal equations

Statement

Statement references

Facts & Assumptions

Proof

The unrestricted Wainwright signed-support threshold claim fails without active-dimension control

Statement

Statement references

Facts & Assumptions

Refutation

Source notes

4 · Examples, counterexamples and false statements

Sources