(57) — |µ̂i| ≤ ϵ + |µ∗i| on the support of β̂
ProvedL0BnB.DualGap.ineq_57dual-boundsdualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Assume (with ) and that every column of has unit norm; let . Let be an optimal solution of (5), and as in (24). Let , , a maximizer of (27), and . Then for every
This is the per-coordinate step of the bound (30): the loss on the support is at most per coordinate.
Formalization Note is the formula (24); its optimality (Theorem 2) is not assumed. The unit norm of is not needed and is not assumed.
Preamble
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup import Definitions.Def_L0BnB_DualGap_Duals
Formal statement
namespace L0BnB.DualGap
/-- (57), Proof of Theorem 3, p. 33: for `√(λ₀/λ₂) > M`, unit-norm columns of `X`, `β*` optimal for
(5), `µ̂` as in (27) and `i ∈ Supp(β̂)`: `|µ̂ᵢ| ≤ ϵ + |µ*ᵢ|`, with `ϵ = ‖X(β* − β̂)‖₂`. -/
theorem ineq_57 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ)
(lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hreg : M < Real.sqrt (lam0 / lam2)) (hX : ∀ i, ∑ r, X r i ^ 2 = 1)
(βs : Fin p → ℝ) (hβs : IsOptimal X y lam0 lam2 M βs)
(βhat μhat : Fin p → ℝ) (hμ : IsMuHat X y lam0 lam2 M βhat μhat)
(i : Fin p) (hi : βhat i ≠ 0) :
|μhat i| ≤ primalGap X βs βhat + |L0BnB.Duality.muStar X y lam0 lam2 M βs i| := by sorry
end L0BnB.DualGap
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 33, Proof of Theorem 3, (57)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.