The Lagrangian Lasso's -error bound under the restricted eigenvalue condition (Theorem 7.13(a), )
ProvedHighDimStat.SparseLinear.lasso_l2_error_bound_v2Theorem 7.13(a) and final sentence. Under a hard-sparsity assumption on the true parameter and a curvature (restricted eigenvalue) assumption on the design, every solution of the Lagrangian Lasso with a large-enough regularization parameter is within a computable -distance of the truth, and its -error is controlled by that same -error.
Fix , (the noise), , (the support of , with ), and with and . Assume:
- (A1) is supported on ;
- (A2) satisfies the restricted eigenvalue condition over with parameters ;
- ;
- solves the Lagrangian Lasso (7.18), , for .
Then
This is the chapter's title result: a deterministic guarantee that holds for any Lasso solution, any noise vector, and any design matrix satisfying the restricted eigenvalue condition.
Formalization Note. The retired version (lasso_l2_error_bound) did not require the
regularization parameter to be positive, so at (allowed by
when ) the "Lasso" is unpenalized least squares and
the bound fails (accepted disproof with , ). The
new statement adds hlam_pos : 0 < lam: the Lagrangian Lasso program (7.18) is defined with
, and the proof uses to pass from the basic inequality to the cone
condition . Only part (a) of Theorem 7.13 is formalized (as
before); is made explicit as in the retired version; the -bound of the
final sentence is kept as the second conjunct. No other hypothesis changed: and are
arbitrary naturals (at or the statement is vacuous or trivially true).
import Mathlib import Definitions.Def_HighDimStat_SparseLinear_HasSupport import Definitions.Def_HighDimStat_SparseLinear_RestrictedEigenvalue import Definitions.Def_HighDimStat_SparseLinear_IsLagrangianLassoSolution import Definitions.Def_HighDimStat_SparseLinear_L1Norm import Definitions.Def_HighDimStat_SparseLinear_LInftyNorm
namespace HighDimStat.SparseLinear
/-- **Theorem 7.13(a)**, Wainwright, *High-Dimensional Statistics* (2019), Eq. (7.25a) and the
final sentence, p. 210. Under (A1) `θ*` is supported on `S ⊆ {1,...,d}` with `|S| = s`, and
(A2) the design matrix `X` satisfies the restricted eigenvalue condition over `S` with
parameters `(κ, 3)`: any solution `θhat` of the Lagrangian Lasso (7.18) — a program whose
regularization parameter is **positive**, `λₙ > 0` — observing `y = Xθ* + w`, with
`λₙ ≥ 2‖Xᵀw/n‖∞`, satisfies `‖θhat − θ*‖₂ ≤ (3/κ)√s λₙ`; in addition,
`‖θhat − θ*‖₁ ≤ 4√s‖θhat − θ*‖₂`.
Correction relative to the retired version: the positivity `0 < λₙ` of the regularization
parameter (part of the definition of program (7.18), and used in the proof to pass from the
basic inequality to the cone condition `Δ̂ ∈ C₃(S)`) was missing; at `λₙ = 0` the program is
unpenalized least squares and the bound fails. -/
theorem lasso_l2_error_bound_v2 {n d : ℕ} (X : Matrix (Fin n) (Fin d) ℝ) (w : Fin n → ℝ)
(θstar θhat : Fin d → ℝ) (S : Finset (Fin d)) (κ lam : ℝ)
(hSupport : HasSupport θstar S)
(hκ : 0 < κ)
(hRE : RestrictedEigenvalue X S κ 3)
(hlam_pos : 0 < lam)
(hlam : 2 * linfNorm (fun j => X.transpose.mulVec w j / (n : ℝ)) ≤ lam)
(hsol : IsLagrangianLassoSolution X (X.mulVec θstar + w) lam θhat) :
Real.sqrt (∑ j, (θhat j - θstar j) ^ 2) ≤ (3 / κ) * Real.sqrt (S.card : ℝ) * lam ∧
l1Norm (fun j => θhat j - θstar j) ≤
4 * Real.sqrt (S.card : ℝ) * Real.sqrt (∑ j, (θhat j - θstar j) ^ 2) := by sorry
end HighDimStat.SparseLinear