Lemma 2 — per-coordinate perturbation bound for the dual term v
ProvedL0BnB.DualGap.lemma_2dual-boundsdualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Assume (with ), that every column of has unit norm and that . Let be an optimal solution of (5), with , and the dual variables (23). Let be a solution from Algorithm 2: and the set of Step 2 is empty. Let be the dual solution (25): and maximizes . Put . Then
- for every , ;
- for every ,
where if and if .
The lemma localizes the loss of the dual bound to the support of : outside it, the emptiness of makes the dual term vanish.
Formalization Note "A solution from Algorithm 2" is modelled by the two properties the paper uses: box feasibility and (Remark 1). is the formula (23); its optimality (Theorem 2) is not assumed.
Preamble
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup import Definitions.Def_L0BnB_DualGap_Duals
Formal statement
namespace L0BnB.DualGap
/-- Lemma 2, p. 31: for `√(λ₀/λ₂) ≤ M`, unit-norm columns of `X` and `‖y‖₂ = 1`, `β*` optimal for (5),
`β̂` an output of Algorithm 2 (box-feasible with `V = ∅`), `α̂ = −r̂` and `γ̂ ∈ argmax h₁(α̂, ·)` (25),
and `ϵ = ‖X(β* − β̂)‖₂`: `v(α̂, γ̂ᵢ) = 0` for `i ∉ Supp(β̂)`, and
`v(α̂, γ̂ᵢ) ≤ cᵢϵ + (4λ₂)⁻¹ϵ² + v(α*, γ*ᵢ)` (50) for `i ∈ Supp(β̂)`. -/
theorem lemma_2 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ)
(lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hreg : Real.sqrt (lam0 / lam2) ≤ M)
(hX : ∀ i, ∑ r, X r i ^ 2 = 1) (hy : ∑ r, y r ^ 2 = 1)
(βs : Fin p → ℝ) (hβs : IsOptimal X y lam0 lam2 M βs)
(βhat : Fin p → ℝ) (hbox : βhat ∈ L0BnB.Reduced.box p M) (hV : Vset X y lam0 lam2 M βhat = ∅)
(γhat : Fin p → ℝ) (hγ : IsGammaHat X y lam0 lam2 M βhat γhat) :
(∀ i, βhat i = 0 → v X lam0 lam2 M (alphaHat X y βhat) (γhat i) i = 0) ∧
(∀ i, βhat i ≠ 0 →
v X lam0 lam2 M (alphaHat X y βhat) (γhat i) i ≤
cLemma2 lam2 M βs i * primalGap X βs βhat + (4 * lam2)⁻¹ * primalGap X βs βhat ^ 2
+ v X lam0 lam2 M (L0BnB.Duality.alphaStar X y βs) (L0BnB.Duality.gammaStar X y lam2 M βs i) 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. 31, Lemma 2, (50); proof p. 32
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.