Proof of Theorem 1, Case I — when
ProvedL0BnB.Reduced.case_Ip2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationreverse-hubersparse-regression
Fix with , and with . Let be the minimum of over the pairs with
Then this minimum is attained and equals
where is the reverse Huber penalty (4).
In this regime the Big-M bound does not bind the optimal , and the relaxation of the perspective term produces the reverse Huber penalty: an -type penalty for and beyond.
Formalization Note The statement is IsLeast of the set of values over the feasible pairs, so it asserts both attainment and the lower bound.
Preamble
import Mathlib import Definitions.Def_L0BnB_Reduced_ReverseHuber import Definitions.Def_L0BnB_Reduced_Setup
Formal statement
namespace L0BnB.Reduced
/-- Proof of Theorem 1, Case I, p. 28: if `√(λ₀/λ₂) ≤ M` and `|b| ≤ M`, then
`ω(b; λ₀, λ₂, M) = 2λ₀ B(b √(λ₂/λ₀)) = ψ₁(b; λ₀, λ₂)`. -/
theorem case_I (lam0 lam2 M b : ℝ) (h0 : 0 < lam0) (h2 : 0 < lam2) (hM : 0 < M)
(hreg : Real.sqrt (lam0 / lam2) ≤ M) (hb : |b| ≤ M) :
IsLeast (omegaValues lam0 lam2 M b) (psi1 lam0 lam2 b) := by sorry
end L0BnB.Reduced
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 28, App. A, Proof of Theorem 1, Case I
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.