Lemma 3: the minimum squared norm of a k-sparse simplex point is 1/k
ProvedJaggiFW.Sparsity.lemma_3lower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplexsparsity
Let . Among points of the unit simplex with at most nonzero coordinates, the minimum squared Euclidean norm exists and is
This is the sparse primal objective bound used in the paper's lower bound.
Formalization Note The formal statement uses an attained minimum, including an attaining sparse point, so it preserves the paper's “min” rather than merely an infimum.
Preamble
import Mathlib import Definitions.Def_JaggiFW_Sparsity_Setting
Formal statement
namespace JaggiFW.Sparsity
/-- Sparse minimum of the quadratic objective (Lemma 3, PDF p. 5). -/
theorem lemma_3 {n : ℕ} (k : ℕ) (hk1 : 1 ≤ k) (hkn : k ≤ n) :
IsLeast {r : ℝ | ∃ x ∈ stdSimplex ℝ (Fin n), card x ≤ k ∧ r = sqNorm x}
(1 / (k : ℝ)) := 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 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.