Problem 2.7: Lasso ℓ₁ bound

Under sub-Gaussian noise, compatibility conditions, and column normalization, the Lasso estimator satisfies |θ̂^L|₁ ≤ C|θ*|₁.

From Rigollet Chapter 2, Problem 2.7. Under sub-Gaussian noise ε ~ subG_n(σ²), conditions of Theorem 2.2, and column normalization max_j |X_j|₂ ≤ √n, the Lasso estimator with 2τ = 8σ√(2 log(2d)/n) satisfies |θ̂ᴸ|₁ ≤ C|θ*|₁ with probability at least 1 - (2d)⁻¹.

We state a deterministic version: given that the noise event (1/n)‖ε‖² ≤ 2τ‖θ*‖₁ holds (which follows from the sub-Gaussian tail bound and column normalization with high probability), the Lasso minimizer satisfies l1norm θ̂ ≤ 2 · l1norm θ*.

theorem problem_2_7_lasso_l1_bound {n d : ℕ} (hn : 0 < n) (hd : 0 < d) (X : Matrix (Fin n) (Fin d) ℝ) (Y : Fin n → ℝ) (θstar : Fin d → ℝ) (eps : Fin n → ℝ) (hY : Y = X.mulVec θstar + eps) (σ : ℝ) (hσ : 0 < σ) (hcol : ∀ (j : Fin d), √(∑ i : Fin n, X i j ^ 2) ≤ √↑n) (τ : ℝ) (hτ : 0 < τ) (hτ_def : τ = 4 * σ * √(2 * Real.log (2 * ↑d) / ↑n)) (θhat : Fin d → ℝ) (hLasso : Rigollet.IsLassoEstimator X Y τ θhat) (hXeps : ∀ (j : Fin d), |∑ i : Fin n, X i j * eps i| ≤ ↑n * τ) (hresid : 1 / ↑n * Rigollet.sqL2norm eps ≤ 2 * τ * Rigollet.l1norm θstar) : Rigollet.l1norm θhat ≤ 2 * Rigollet.l1norm θstar

Problem 2.7. Under sub-Gaussian noise, the Lasso estimator with 2τ = 8σ√(2 log(2d)/n), column normalization max_j |X_j|₂ ≤ √n, and the conditions of Theorem 2.2 satisfies l1norm θ̂ ≤ C · l1norm θ*.

We state the deterministic version with explicit noise and Lasso conditions. The constant C = 2 arises from: the Lasso optimality at θ* gives 2τ‖θ̂‖₁ ≤ (1/n)‖ε‖² + 2τ‖θ*‖₁, and the residual bound (1/n)‖ε‖² ≤ 2τ‖θ*‖₁ (which holds w.h.p.) yields 2τ‖θ̂‖₁ ≤ 4τ‖θ*‖₁, i.e., ‖θ̂‖₁ ≤ 2‖θ*‖₁.