Lemma 7, p. 13 — with q = 1/(p+1), E[|O_u ∖ S| · f(u | S_u)] ≤ p/(p+1) · E[X_u f(u | S_u)] (5)
ProvedSubsampleSubmod.SampleGreedy.lemma_7p-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 , and let indicate that is considered. Then for every element ,
This is where the choice balances the elements of OPT that may be lost against the gains of the considered elements.
Formalization Note is a natural number cast to ; the expectations are exact sums over the coin outcomes.
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- Lemma 7 (p. 13), inequality (5). With sampling probability `q = 1/(p+1)`, for every element `u`:
`E[|O_u \ S| · f(u | S_u)] ≤ p/(p+1) · E[X_u f(u | S_u)]`, where `X_u` indicates that `u` is
considered by Algorithm 2 (run from an independent `T`, over a `p`-extendible system). -/
theorem lemma_7 {α : 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 : ℝ) + 1)) f I T
(fun st => ((st.Ou u \ st.S).card : ℝ) * marg f u (st.Su u)) ≤
((p : ℝ) / ((p : ℝ) + 1)) *
E2 (1 / ((p : ℝ) + 1)) f I T
(fun st => (if u ∈ st.considered then (1 : ℝ) else 0) * marg f u (st.Su u)) := by sorry
end SubsampleSubmod.SampleGreedy
Source
Harshaw et al., arXiv:2104.02772v1, p. 13, Lemma 7, inequality (5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.