Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — dual bounds from the active-set primal solution lose only O(kϵ), independent of p

Proved
L0BnB.DualGap.theorem_3

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

branch-and-bounddual-boundsdualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression

Let X∈Rn×pX\in\mathbb R^{n\times p}X∈Rn×p and y∈Rny\in\mathbb R^ny∈Rn, where the columns of XXX and yyy have unit ℓ2\ell_2ℓ2​ norm, and λ0,λ2,M>0\lambda_0,\lambda_2,M>0λ0​,λ2​,M>0. Let β∗\beta^*β∗ be an optimal solution of the reduced relaxation (5), with (α∗,γ∗)(\alpha^*,\gamma^*)(α∗,γ∗) and (ρ∗,μ∗)(\rho^*,\mu^*)(ρ∗,μ∗) the dual variables (23)–(24) of Theorem 2. Let β^\hat\betaβ^​ be an inexact solution obtained by Algorithm 2, i.e. ∥β^∥∞≤M\|\hat\beta\|_\infty\le M∥β^​∥∞​≤M and the violation set VVV of Step 2 is empty. Define the primal gap ϵ=∥X(β∗−β^)∥2\epsilon=\|X(\beta^*-\hat\beta)\|_2ϵ=∥X(β∗−β^​)∥2​ and k=∥β^∥0k=\|\hat\beta\|_0k=∥β^​∥0​. Let (α^,γ^)(\hat\alpha,\hat\gamma)(α^,γ^​) be the dual solution (25) and (ρ^,μ^)(\hat\rho,\hat\mu)(ρ^​,μ^​) the dual solution (27).

  1. If λ0/λ2≤M\sqrt{\lambda_0/\lambda_2}\le Mλ0​/λ2​​≤M, then
h1(α^,γ^)≥h1(α∗,γ∗)−2ϵ−12ϵ2−∑i∈Supp⁡(β^)(ciϵ+(4λ2)−1ϵ2),(55)h_1(\hat\alpha,\hat\gamma)\ge h_1(\alpha^*,\gamma^*)-2\epsilon-\tfrac12\epsilon^2-\sum_{i\in\operatorname{Supp}(\hat\beta)}\big(c_i\epsilon+(4\lambda_2)^{-1}\epsilon^2\big),\qquad(55)h1​(α^,γ^​)≥h1​(α∗,γ∗)−2ϵ−21​ϵ2−i∈Supp(β^​)∑​(ci​ϵ+(4λ2​)−1ϵ2),(55)

with ci=(2λ2)−1c_i=(2\lambda_2)^{-1}ci​=(2λ2​)−1 if ∣βi∗∣<M|\beta^*_i|<M∣βi∗​∣<M and ci=Mc_i=Mci​=M if ∣βi∗∣=M|\beta^*_i|=M∣βi∗​∣=M. The sum has kkk terms, so this is the paper's h1(α^,γ^)≥h1(α∗,γ∗)−kO(ϵ)−kO(ϵ2)h_1(\hat\alpha,\hat\gamma)\ge h_1(\alpha^*,\gamma^*)-kO(\epsilon)-kO(\epsilon^2)h1​(α^,γ^​)≥h1​(α∗,γ∗)−kO(ϵ)−kO(ϵ2) (29). 2. If λ0/λ2>M\sqrt{\lambda_0/\lambda_2}>Mλ0​/λ2​​>M, then

h2(ρ^,μ^)≥h2(ρ∗,μ∗)−ϵ(2+Mk)−ϵ2/2,(59)h_2(\hat\rho,\hat\mu)\ge h_2(\rho^*,\mu^*)-\epsilon(2+Mk)-\epsilon^2/2,\qquad(59)h2​(ρ^​,μ^​)≥h2​(ρ∗,μ∗)−ϵ(2+Mk)−ϵ2/2,(59)

which is the paper's h2(ρ^,μ^)≥h2(ρ∗,μ∗)−kO(ϵ)−O(ϵ2)h_2(\hat\rho,\hat\mu)\ge h_2(\rho^*,\mu^*)-kO(\epsilon)-O(\epsilon^2)h2​(ρ^​,μ^​)≥h2​(ρ∗,μ∗)−kO(ϵ)−O(ϵ2) (30).

The constants depend only on MMM and λ2\lambda_2λ2​, and the number of features ppp does not appear: the dual bounds computed from the cheap primal iterate lose an amount governed by the sparsity kkk of the iterate.

Formalization Note The paper writes O(⋅)O(\cdot)O(⋅); 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 V=∅V=\emptysetV=∅ (Remark 1), not by the iterations. (α∗,γ∗)(\alpha^*,\gamma^*)(α∗,γ∗), (ρ∗,μ∗)(\rho^*,\mu^*)(ρ∗,μ∗) are the formulas (23)–(24); their optimality for the duals is not assumed. γ^\hat\gammaγ^​, μ^\hat\muμ^​ are arbitrary maximizers as in (25), (27). sign is Real.sign with sign⁡(0)=0\operatorname{sign}(0)=0sign(0)=0.

Preamble
import Mathlib
import Definitions.Def_L0BnB_DualGap_Setup
import Definitions.Def_L0BnB_DualGap_Duals
Formal statement
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
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 15, Theorem 3, (29), (30); explicit constants from the proof, pp. 32–34, (55), (59)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me