Theorem 3 — dual bounds from the active-set primal solution lose only O(kϵ), independent of p
ProvedL0BnB.DualGap.theorem_3Let and , where the columns of and have unit norm, and . Let be an optimal solution of the reduced relaxation (5), with and the dual variables (23)–(24) of Theorem 2. Let be an inexact solution obtained by Algorithm 2, i.e. and the violation set of Step 2 is empty. Define the primal gap and . Let be the dual solution (25) and the dual solution (27).
- If , then
with if and if . The sum has terms, so this is the paper's (29). 2. If , then
which is the paper's (30).
The constants depend only on and , and the number of features does not appear: the dual bounds computed from the cheap primal iterate lose an amount governed by the sparsity of the iterate.
Formalization Note The paper writes ; the proof yields (55) for (29) and (59) for (30), and these explicit forms are stated. "An inexact solution obtained using Algorithm 2" is modelled by box feasibility and (Remark 1), not by the iterations. , are the formulas (23)–(24); their optimality for the duals is not assumed. , are arbitrary maximizers as in (25), (27). sign is Real.sign with .
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup import Definitions.Def_L0BnB_DualGap_Duals
namespace L0BnB.DualGap
/-- Theorem 3, p. 15, with the constants of its proof (pp. 32–34). Assume the columns of `X` and `y`
have unit ℓ₂ norm (standing assumption of Section 3, p. 9). Let `β*` be optimal for (5), `β̂` an output of
Algorithm 2 (box-feasible with `V = ∅`), `ϵ = ‖X(β* − β̂)‖₂`, `k = ‖β̂‖₀`, `γ̂` as in (25) and `µ̂` as in (27).
If `√(λ₀/λ₂) ≤ M`, (55):
`h₁(α̂, γ̂) ≥ h₁(α*, γ*) − 2ϵ − ½ϵ² − ∑_{i ∈ Supp(β̂)} (cᵢϵ + (4λ₂)⁻¹ϵ²)`, the explicit form of (29).
If `√(λ₀/λ₂) > M`, (59): `h₂(ρ̂, µ̂) ≥ h₂(ρ*, µ*) − ϵ(2 + Mk) − ϵ²/2`, the explicit form of (30). -/
theorem theorem_3 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ)
(lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < 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)
(μhat : Fin p → ℝ) (hμ : IsMuHat X y lam0 lam2 M βhat μhat) :
(Real.sqrt (lam0 / lam2) ≤ M →
h1 X y lam0 lam2 M (L0BnB.Duality.alphaStar X y βs) (L0BnB.Duality.gammaStar X y lam2 M βs)
- 2 * primalGap X βs βhat - (1 / 2) * primalGap X βs βhat ^ 2
- ∑ i ∈ supp βhat,
(cLemma2 lam2 M βs i * primalGap X βs βhat + (4 * lam2)⁻¹ * primalGap X βs βhat ^ 2)
≤ h1 X y lam0 lam2 M (alphaHat X y βhat) γhat) ∧
(M < Real.sqrt (lam0 / lam2) →
L0BnB.Duality.h2 y M (L0BnB.Duality.rhoStar X y βs) (L0BnB.Duality.muStar X y lam0 lam2 M βs)
- primalGap X βs βhat * (2 + M * ((supp βhat).card : ℝ)) - primalGap X βs βhat ^ 2 / 2
≤ L0BnB.Duality.h2 y M (rhoHat X y βhat) μhat) := by sorry
end L0BnB.DualGap
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.