Lemma 8, p. 14 — q · Σ_{u∈𝒩} E[X_u f(u | S_u)] ≤ E[f(S)]
ProvedSubsampleSubmod.SampleGreedy.lemma_8p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssubmodular-maximization
Let be non-negative, any family of sets, any set, and . Run Algorithm 2 from with every coin showing independently with probability , and let indicate that is considered. Then
Each considered element is kept with probability , and the value of is plus the gains of the kept elements; this lemma converts the right-hand sides of Lemmas 7 and 10 back into the expected value of the output.
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- Lemma 8 (p. 14). For non-negative `f` and sampling probability `q ∈ [0, 1]`:
`q · ∑_{u ∈ 𝒩} E[X_u f(u | S_u)] ≤ E[f(S)]` for Algorithm 2 (any comparison set `T`). -/
theorem lemma_8 {α : Type} [Fintype α] [LinearOrder α] (f : Finset α → ℝ)
(I : Finset α → Prop) (hf0 : ∀ S, 0 ≤ f S) (q : ℝ) (hq0 : 0 ≤ q) (hq1 : q ≤ 1)
(T : Finset α) :
q * ∑ u : α, E2 q f I T
(fun st => (if u ∈ st.considered then (1 : ℝ) else 0) * marg f u (st.Su u)) ≤
E2 q f I T (fun st => f st.S) := by sorry
end SubsampleSubmod.SampleGreedy
Source
Harshaw et al., arXiv:2104.02772v1, p. 14, Lemma 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.