Lemma 5, p. 11 — throughout Algorithm 2, O is independent, S ⊆ O, and O ∖ S consists of unconsidered elements
ProvedSubsampleSubmod.SampleGreedy.lemma_5greedy-algorithmsindependence-systemsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-maximization
Let be an independence system, , any set function and any outcome of the coins. Run Algorithm 2 from . After every number of iterations the following hold:
- (P1) ;
- (P2) ;
- (P3) every element of has not yet been considered by Algorithm 2.
These invariants are what make the removal step of line 6 well defined and drive the deterministic bound of Lemma 6.
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- Lemma 5 (p. 11). Throughout Algorithm 2 (after every number `j` of iterations), started from an
independent `T`: (P1) `O` is independent; (P2) `S ⊆ O`; (P3) every element of `O \ S` has not yet
been considered. -/
theorem lemma_5 {α : Type} [Fintype α] [LinearOrder α] (f : Finset α → ℝ)
(I : Finset α → Prop) (hI : IsIndepSystem I) (T : Finset α) (hT : I T) (B : Finset α)
(j : ℕ) :
I ((alg2Step f I B)^[j] (alg2Init T)).O ∧
((alg2Step f I B)^[j] (alg2Init T)).S ⊆ ((alg2Step f I B)^[j] (alg2Init T)).O ∧
∀ v ∈ ((alg2Step f I B)^[j] (alg2Init T)).O \ ((alg2Step f I B)^[j] (alg2Init T)).S,
v ∉ ((alg2Step f I B)^[j] (alg2Init T)).considered := by sorry
end SubsampleSubmod.SampleGreedy
Source
Harshaw et al., arXiv:2104.02772v1, p. 11, Lemma 5 (properties P1–P3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.