Lemma 4, p. 10 — SampleGreedy and Algorithm 2 produce output sets with the same probability distribution
ProvedSubsampleSubmod.SampleGreedy.lemma_4greedy-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssubmodular-maximization
Let be a finite ground set with a fixed linear order, any set function, any family of sets, any set and a real number. Let be the output of SampleGreedy with sampling probability and the output of Algorithm 2 run from , whose coins show independently with probability . Then for every set ,
that is,
This lemma transfers every guarantee proved for Algorithm 2 to SampleGreedy.
Formalization Note The identity is stated for every real , every and every , which includes the paper's setting (, ). Both algorithms break ties by the same fixed order of the ground set, as the paper assumes on p. 10.
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- Lemma 4 (p. 10). The output `S¹` of SampleGreedy and the output `S²` of Algorithm 2 (run with any
comparison set `T`) have the same distribution: for every set `R`, `Pr[S¹ = R] = Pr[S² = R]`, both
computed with the independent sampling probability `q`. -/
theorem lemma_4 {α : Type} [Fintype α] [LinearOrder α] (f : Finset α → ℝ)
(I : Finset α → Prop) (q : ℝ) (T R : Finset α) :
∑ N' : Finset α, sampleWeight q N' * (if sampleGreedy f I N' = R then (1 : ℝ) else 0) =
∑ B : Finset α, sampleWeight q B * (if (alg2 f I T B).S = R then (1 : ℝ) else 0) := by sorry
end SubsampleSubmod.SampleGreedy
Source
Harshaw et al., arXiv:2104.02772v1, p. 10, Lemma 4 (proof pp. 10–11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.