TheoremStatement: AI-adaptedProof: 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.

Lasso prediction and coefficient bounds under incoherence

Statement

Let $n, d, s$ be integers with $n \geq 2$ , $d \geq 1$ , $1 \leq s \leq d$ , and let $σ > 0$ , $δ \in (0, 1)$ . In the model $Y = X θ^{*} + ε$ of Fixed-design regression with sub-Gaussian noise, suppose $∣ {j : θ_{j}^{*} \neq 0} ∣ \leq s$ and the deterministic design satisfies the incoherence condition of Fixed-design incoherence condition. Define $τ = 4 σ (\sqrt{\frac{\log (2 d)}{n}} + \sqrt{\frac{\log (1 / δ)}{n}}) .$ For every response realization the minimizer set in Lasso estimator for fixed design is nonempty by The Lasso objective has a nonempty compact convex minimizer set. The measurable score event has probability at least $1 - δ$ , and on that event every minimizer $\hat{θ}$ in the set satisfies $\frac{∥ X \hat{θ} - X θ^{*} ∥_{2}^{2}}{n} \leq 576 s σ^{2} \frac{\log (2 d / δ)}{n}, ∥ \hat{θ} - θ^{*} ∥_{1} \leq 96 \sqrt{2} s σ \sqrt{\frac{\log (2 d / δ)}{n}} .$ In particular, the prediction and coefficient rates are respectively $O (s σ^{2} \log (2 d / δ) / n)$ and $O (s σ \sqrt{\log (2 d / δ) / n})$ . Incoherence is sufficient for these bounds, but not necessary. Without any design restriction, the coefficient bound can fail.

Facts & Assumptions

Given: The hypotheses in the Statement, the fixed design, response and noise, and an arbitrary minimizer $\hat{θ}$ for each response realization.

[F1]

For every response the Lasso objective has a nonempty minimizer set (Lasso estimator for fixed design, The Lasso objective has a nonempty compact convex minimizer set).

[F2]

On the event $∥ X^{T} ε / n ∥_{\infty} \leq τ / 2$ , the basic inequality gives $a^{2} + τ ∥ Δ_{S^{c}} ∥_{1} \leq 3 τ ∥ Δ_{S} ∥_{1}$ , where $Δ = \hat{θ} - θ^{*}$ and $a = ∥ X Δ ∥_{2} / \sqrt{n}$ (Lasso basic inequality and cone constraint).

[F3]

If $∥ Δ_{S^{c}} ∥_{1} \leq 3 ∥ Δ_{S} ∥_{1}$ , the exact incoherence bound implies $a^{2} \geq \frac{1}{2} ∥ Δ_{S} ∥_{2}^{2}$ for the support $S$ with $∣ S ∣ \leq s$ (The stated incoherence bound implies the Lasso restricted eigenvalue condition).

[F4]

With the displayed $τ$ , the score event in [F2] has probability at least $1 - δ$ (Sub-Gaussian score bound under fixed-design incoherence).

[F5]

For $∣ S ∣ \leq s$ , $∥ Δ_{S} ∥_{1} \leq \sqrt{s} ∥ Δ_{S} ∥_{2}$ (The Cauchy-Schwarz inequality for finite sums).

Proof

1.1givenF1F2F3F4F5cases

Work on the event in [F4], whose probability is at least $1 - δ$ , and choose any minimizer, which exists by [F1]. Let $S = {j : θ_{j}^{*} \neq 0}$ and $Δ = \hat{θ} - θ^{*}$ . Since $a^{2} \geq 0$ and $τ > 0$ , [F2] gives $∥ Δ_{S^{c}} ∥_{1} \leq 3 ∥ Δ_{S} ∥_{1}$ , so [F3] applies. If $a = 0$ , [F3] gives $Δ_{S} = 0$ ; then [F2] gives $Δ_{S^{c}} = 0$ , and both conclusions hold. If $a > 0$ , [F3] and [F5] imply $∥ Δ_{S} ∥_{1} \leq \sqrt{2 s} a$ . From [F2], $a^{2} \leq 3 τ ∥ Δ_{S} ∥_{1} \leq 3 \sqrt{2 s} τ a$ , hence $a^{2} \leq 18 s τ^{2}$ .

2.1F2F3F5step 1.1algebra

The cone inequality from [F2] gives $∥ Δ ∥_{1} \leq 4 ∥ Δ_{S} ∥_{1}$ . Using [F3], [F5] and $a \leq 3 \sqrt{2 s} τ$ from step 1.1 yields $∥ Δ ∥_{1} \leq 4 \sqrt{2 s} a \leq 24 s τ$ .

3.1step 1.1step 2.1algebra

Put $L = \log (2 d / δ) = \log (2 d) + \log (1 / δ)$ . Since $(u + v)^{2} \leq 2 (u^{2} + v^{2})$ , $τ^{2} \leq 32 σ^{2} L / n$ and $τ \leq 4 σ \sqrt{2 L / n}$ . Substitution into steps 1.1 and 2.1 gives the two displayed bounds; the event probability is at least $1 - δ$ .

4.1givenF1F2step 3.1constructalgebra∎

To check the design caveats, take $n = 2$ , $d = s = 1$ and $ε = 0$ , which satisfies the noise condition for every $σ > 0$ and makes the score event certain. Choose $X$ with $X^{T} X / n = 4 / 5$ . Its diagonal deviation $1 / 5 > 1 / 14$ violates incoherence, yet [F2] gives $(4 / 5) ∣ Δ ∣^{2} \leq 3 τ ∣ Δ ∣$ , hence $∣ Δ ∣ \leq 15 τ / 4$ and $∥ X Δ ∥_{2}^{2} / n \leq 45 τ^{2} / 4$ for every minimizer and every $θ^{*}$ . Step 3.1 then gives both displayed bounds with smaller constants. Conversely, for $X = 0$ and $ε = 0$ , the objective is $2 τ ∥ θ ∥_{1}$ , whose unique minimizer is zero. Taking $θ^{*} = M \in R$ with $M > 96 \sqrt{2} σ \sqrt{L / n}$ violates the coefficient bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

28 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, 18.S997 High-Dimensional Statistics, Lemma 2.17 and Theorem 2.18 (standard reference, not scraped)
Philippe Rigollet and Jan-Christian Hütter, High-Dimensional Statistics: Lecture Notes, Lemma 2.17 and Theorem 2.18 (standard reference, not scraped)
Peter J. Bickel, Ya'acov Ritov and Alexandre B. Tsybakov, Simultaneous Analysis of Lasso and Dantzig Selector, Theorem 7.2 (standard reference, not scraped)