Lemma 1 — on for
ProvedL0BnB.BigMvsPR.lemma_1p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationsparse-regression
Let and let , where is the reverse Huber penalty (4). If , then for every ,
This is the coordinatewise inequality behind (11): for a loose Big-M bound, the penalty dominates the Big-M coordinate penalty on the box.
Preamble
import Mathlib import Definitions.Def_L0BnB_BigMvsPR_Penalties import Definitions.Def_L0BnB_BigMvsPR_Relaxations
Formal statement
namespace L0BnB.BigMvsPR
/-- Lemma 1, p. 29: if `M ≥ √(λ₀/λ₂)`, then `t(b) ≥ 0` for every `b ∈ [−M, M]`. -/
theorem lemma_1 (lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hMlarge : Real.sqrt (lam0 / lam2) ≤ M) :
∀ b : ℝ, -M ≤ b → b ≤ M → 0 ≤ tGap lam0 lam2 M b := by sorry
end L0BnB.BigMvsPR
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 29, App. A, Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.