False statementConstruction: AI-adaptedVerification: AI-adaptedPipeline-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 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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

75 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 and §§3.1, 3.3–3.4 (standard reference, not scraped)
Philippe Rigollet and Jan-Christian Hütter, High-Dimensional Statistics: Lecture Notes, §§1.1, 1.4, 2.2–2.4 (standard reference, not scraped)