(14) — closed-form solution of the coordinate problem (13) when √(λ0/λ2) ≤ M
ProvedL0BnB.DualGap.eq_14coordinate-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 update of cyclic coordinate descent (Algorithm 1) in the reverse-Huber 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
/-- (14), p. 10 (derivation App. B.1, p. 34): for `√(λ₀/λ₂) ≤ M`, the solution of (13) is
`T(β̃ᵢ; 2√(λ₀λ₂), M)` if `|β̃ᵢ| ≤ 2√(λ₀λ₂) + √(λ₀/λ₂)` and `T(β̃ᵢ(1 + 2λ₂)⁻¹; 0, M)` otherwise. -/
theorem eq_14 (lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hreg : Real.sqrt (lam0 / lam2) ≤ M) (bt : ℝ) :
IsSolution13 lam0 lam2 M bt
(if |bt| ≤ 2 * Real.sqrt (lam0 * lam2) + Real.sqrt (lam0 / lam2) then
boxedSoftThreshold bt (2 * Real.sqrt (lam0 * lam2)) M
else boxedSoftThreshold (bt * (1 + 2 * lam2)⁻¹) 0 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, (14); derivation in App. B.1, p. 34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.