(53) — the quadratic part of h1 at α̂ exceeds that at α∗ by at most ½ϵ² + 2ϵ
ProvedL0BnB.DualGap.ineq_53dual-boundsdualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , with , , an optimal solution of (5) and . With , and ,
This compares the smooth part of the dual objective at the constructed and the optimal dual points; together with Lemma 2 it gives the dual-bound guarantee.
Formalization Note The inequality holds for every ; the paper applies it to the output of Algorithm 2, and no property of that output is used. It also 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
/-- (53), Proof of Theorem 3, p. 33: with `‖y‖₂ = 1`, `β*` optimal for (5), `α* = −r*`, `α̂ = −r̂`
and `ϵ = ‖X(β* − β̂)‖₂`: `½‖α̂‖₂² + α̂ᵀy ≤ ½ϵ² + 2ϵ + ½‖α*‖₂² + α*ᵀy`. -/
theorem ineq_53 {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 : Fin p → ℝ) :
(1 / 2) * ∑ r, alphaHat X y βhat r ^ 2 + ∑ r, alphaHat X y βhat r * y r ≤
(1 / 2) * primalGap X βs βhat ^ 2 + 2 * primalGap X βs βhat
+ (1 / 2) * ∑ r, L0BnB.Duality.alphaStar X y βs r ^ 2 + ∑ r, L0BnB.Duality.alphaStar X y βs r * y r := 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, (53) (from (52), p. 32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.