Proof of Proposition 1, p. 29 — when
ProvedL0BnB.Strength.psi1_eq_on_boxp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reverse-hubersparse-regression
Let and let satisfy . If satisfies , then
where and is the reverse Huber penalty (4). This is the first, linear, case of (4): on the box the reverse Huber penalty reduces to a multiple of the absolute value.
The identity turns the difference between the penalties of the relaxations (5) and (6) into a multiple of , coordinate by coordinate.
Preamble
import Mathlib import Definitions.Def_L0BnB_Strength_Penalties import Definitions.Def_L0BnB_Strength_Relaxations
Formal statement
namespace L0BnB.Strength
/-- Proof of Proposition 1, p. 29: if `|b| ≤ M` and `√(λ₀/λ₂) > M`, then
`ψ₁(b; λ₀, λ₂) = 2 |b| √(λ₀ λ₂)` (the first case of (4)). -/
theorem psi1_eq_on_box (lam0 lam2 M b : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2)
(hregime : M < Real.sqrt (lam0 / lam2)) (hb : |b| ≤ M) :
L0BnB.Reduced.psi1 lam0 lam2 b = 2 * |b| * Real.sqrt (lam0 * lam2) := by sorry
end L0BnB.Strength
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 29, App. A, Proof of Proposition 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.