Lemma 10, p. 16 — with q = 1/p, E[|O_u| − Y_u] ≤ (p−1)/p · E[X_u] (7)
ProvedSubsampleSubmod.SampleGreedy.lemma_10p-extendible-systemsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssubmodular-maximization
Let be a -extendible independence system with , and a set function. Run Algorithm 2 from with every coin showing independently with probability ; let indicate that is considered and that was added to while at the beginning of its iteration. Then for every ,
Together with Lemmas 8 and 9 this gives the -approximation for linear objectives.
Formalization Note is computed in (it can be ). For the sampling probability is and every coin shows .
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- Lemma 10 (p. 16), inequality (7). With sampling probability `q = 1/p`, for every element `u`:
`E[|O_u| − Y_u] ≤ (p − 1)/p · E[X_u]` for Algorithm 2 run from an independent `T` over a
`p`-extendible system. -/
theorem lemma_10 {α : Type} [Fintype α] [LinearOrder α] (f : Finset α → ℝ)
(I : Finset α → Prop) (p : ℕ) (hp : 1 ≤ p) (hI : IsIndepSystem I)
(hext : IsPExtendible p I) (T : Finset α) (hT : I T) (u : α) :
E2 (1 / (p : ℝ)) f I T
(fun st => ((st.Ou u).card : ℝ) - (if u ∈ st.Y then (1 : ℝ) else 0)) ≤
(((p : ℝ) - 1) / (p : ℝ)) *
E2 (1 / (p : ℝ)) f I T (fun st => if u ∈ st.considered then (1 : ℝ) else 0) := by sorry
end SubsampleSubmod.SampleGreedy
Source
Harshaw et al., arXiv:2104.02772v1, p. 16, Lemma 10, inequality (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.