Lemma 6, p. 12 — f(S) ≥ f(S ∪ OPT) − Σ_{u∈𝒩} |O_u ∖ S| · f(u | S_u) for the final sets of Algorithm 2
ProvedSubsampleSubmod.SampleGreedy.lemma_6greedy-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-maximization
Let be submodular, an independence system, (playing the role of OPT) and any outcome of the coins. For the final sets , and of Algorithm 2 run from ,
This is the deterministic half of the analysis of SampleGreedy: it charges the loss relative to to the marginal gains of considered elements.
Formalization Note No non-negativity of and no -extendibility are assumed; the statement holds for every outcome of the coins.
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- Lemma 6 (p. 12). For the final sets of Algorithm 2 run from an independent `T` (OPT) and any coin
flips `B`: `f(S) ≥ f(S ∪ T) − ∑_{u ∈ 𝒩} |O_u \ S| · f(u | S_u)`, for submodular `f`. -/
theorem lemma_6 {α : Type} [Fintype α] [LinearOrder α] (f : Finset α → ℝ)
(I : Finset α → Prop) (hsub : NonmonotoneSubmod.Shared.Submodular f) (hI : IsIndepSystem I)
(T : Finset α) (hT : I T) (B : Finset α) :
f ((alg2 f I T B).S ∪ T) -
∑ u : α, (((alg2 f I T B).Ou u \ (alg2 f I T B).S).card : ℝ) *
marg f u ((alg2 f I T B).Su u) ≤
f (alg2 f I T B).S := by sorry
end SubsampleSubmod.SampleGreedy
Source
Harshaw et al., arXiv:2104.02772v1, p. 12, Lemma 6 (proof pp. 12–13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.