(15) — closed-form solution of the coordinate problem (13) when √(λ0/λ2) > M
ProvedL0BnB.DualGap.eq_15coordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1soft-thresholdingsparse-regression
Let with , so that the penalty is , and let . Then the problem
has the unique solution
where is the boxed soft-thresholding operator.
This is the closed-form coordinate-descent update in the regime.
Formalization Note "The solution" is stated as: the given value is feasible and every other feasible point has a strictly larger objective.
Preamble
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup
Formal statement
namespace L0BnB.DualGap
/-- (15), p. 10 (derivation App. B.1, p. 34): for `√(λ₀/λ₂) > M`, the solution of (13) is
`T(β̃ᵢ; λ₀/M + λ₂M, M)`. -/
theorem eq_15 (lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hreg : M < Real.sqrt (lam0 / lam2)) (bt : ℝ) :
IsSolution13 lam0 lam2 M bt (boxedSoftThreshold bt (lam0 / M + lam2 * M) M) := 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. 10, (15); derivation in App. B.1, p. 34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.