(58) — correlation conditions at an optimal β∗ when √(λ0/λ2) > M
ProvedL0BnB.DualGap.eq_58dualityoptimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , , with , and let be an optimal solution of (5), and . Then for every
These conditions identify with , which is the step from (57) to the dual bound (30).
Formalization Note The paper derives (58) from the optimality of for the dual (22) (Theorem 2). Here the hypothesis is the optimality of for the primal (5); Theorem 2 is not assumed. No normalization of or is needed.
Preamble
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup import Definitions.Def_L0BnB_DualGap_Duals
Formal statement
namespace L0BnB.DualGap
/-- (58), p. 34: for `√(λ₀/λ₂) > M` and `β*` optimal for (5), with `ρ* = −r*`:
`|ρ*ᵀXᵢ| ≤ λ₀/M + λ₂M` if `|β*ᵢ| < M` and `|ρ*ᵀXᵢ| ≥ λ₀/M + λ₂M` if `|β*ᵢ| = M`. -/
theorem eq_58 {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))
(βs : Fin p → ℝ) (hβs : IsOptimal X y lam0 lam2 M βs) :
∀ i, (|βs i| < M → |colInner X (L0BnB.Duality.rhoStar X y βs) i| ≤ lam0 / M + lam2 * M) ∧
(|βs i| = M → lam0 / M + lam2 * M ≤ |colInner X (L0BnB.Duality.rhoStar X y β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. 34, (58), Proof of Theorem 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.