Lemma 4: every k-sparse simplex point has duality gap at least 2/k
ProvedJaggiFW.Sparsity.lemma_4duality-gapfrank-wolfelower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplexsparsity
For on the unit simplex , let be a natural number with . Every feasible point with at most nonzero coordinates satisfies
Thus the duality-gap guarantee cannot improve its order in the number of active coordinates for this example.
Formalization Note The gap is the supremum of over , equal to the paper's maximum because makes the compact simplex nonempty. When , no simplex point meets the sparsity condition, so the natural-number division convention has no effect on a feasible case.
Preamble
import Mathlib import Definitions.Def_JaggiFW_Sparsity_Setting
Formal statement
namespace JaggiFW.Sparsity
/-- Sparse duality-gap lower bound (Lemma 4, PDF p. 5). -/
theorem lemma_4 {n : ℕ} (k : ℕ) (hk : k < n) :
∀ x ∈ stdSimplex ℝ (Fin n), card x ≤ k →
2 / (k : ℝ) ≤ dualityGap sqNorm (stdSimplex ℝ (Fin n)) x := by sorry
end JaggiFW.Sparsity
Source
Jaggi, Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, ICML 2013 (JMLR W&CP 28), PDF p. 5, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.