False statementConstruction: AI-adaptedVerification: AI-generatedPipeline-generatedprecheck pass

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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

46 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

Wainwright, Sharp Thresholds for High-Dimensional and Noisy Recovery of Sparsity, 2006, Theorem 1(a), §3.1, §3.4, and Appendix D.6 (standard reference, not scraped)
Wainwright, Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using L1-Constrained Quadratic Programming (Lasso), 2009, §IV.A (standard reference, not scraped)