(56) — lower bound on h2(ρ̂, µ̂) in terms of ρ∗, ϵ and ‖µ̂‖1
ProvedL0BnB.DualGap.ineq_56dual-boundsdualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , with , , an optimal solution of (5), , , , and . Then
It is the -regime counterpart of (54), obtained by the argument of (53).
Formalization Note The inequality holds for every and every ; the paper applies it to the output of Algorithm 2 and the maximizer (27), and no property of them is used. It does not depend on the regime of versus .
Preamble
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup import Definitions.Def_L0BnB_DualGap_Duals
Formal statement
namespace L0BnB.DualGap
/-- (56), Proof of Theorem 3, p. 33: with `‖y‖₂ = 1`, `β*` optimal for (5), `ρ* = −r*`, `ρ̂ = −r̂`
and `ϵ = ‖X(β* − β̂)‖₂`: `h₂(ρ̂, µ̂) ≥ −½‖ρ*‖₂² − ρ*ᵀy − 2ϵ − ½ϵ² − M‖µ̂‖₁`. -/
theorem ineq_56 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ)
(lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hy : ∑ r, y r ^ 2 = 1) (βs : Fin p → ℝ) (hβs : IsOptimal X y lam0 lam2 M βs)
(βhat μhat : Fin p → ℝ) :
-(1 / 2) * ∑ r, L0BnB.Duality.rhoStar X y βs r ^ 2 - ∑ r, L0BnB.Duality.rhoStar X y βs r * y r
- 2 * primalGap X βs βhat - (1 / 2) * primalGap X βs βhat ^ 2 - M * ∑ i, |μhat i|
≤ L0BnB.Duality.h2 y M (rhoHat X y βhat) μhat := 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, (56)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.