§4.1.1, p. 14 — with q = 1/(p+1), E[f(S)] ≥ E[f(S ∪ OPT)] − Σ E[|O_u∖S| f(u|S_u)] ≥ … ≥ E[f(S ∪ OPT)] − p · E[f(S)]
ProvedSubsampleSubmod.SampleGreedy.display_4_1_1approximation-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssubmodular-maximization
Let be non-negative and submodular, a -extendible independence system with , and . Run Algorithm 2 from with sampling probability . Then the chain of the proof of Theorem 1 for submodular objectives holds:
Combined with (monotone case) or (Lemma 3), and with Lemma 4, it yields the ratios and of Theorem 1.
Formalization Note The three inequalities of the display are stated as a conjunction, in the order printed.
Preamble
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Analysis
Formal statement
namespace SubsampleSubmod.SampleGreedy
/-- The display of §4.1.1 (p. 14). With `q = 1/(p+1)`, for Algorithm 2 run from an independent `T`
(OPT), non-negative submodular `f` and a `p`-extendible system:
`E[f(S)] ≥ E[f(S ∪ T)] − ∑_u E[|O_u \ S| · f(u | S_u)]
≥ E[f(S ∪ T)] − p/(p+1) ∑_u E[X_u · f(u | S_u)] ≥ E[f(S ∪ T)] − p · E[f(S)]`. -/
theorem display_4_1_1 {α : Type} [Fintype α] [LinearOrder α] (f : Finset α → ℝ)
(I : Finset α → Prop) (p : ℕ) (hp : 1 ≤ p) (hf0 : ∀ S, 0 ≤ f S)
(hsub : NonmonotoneSubmod.Shared.Submodular f) (hI : IsIndepSystem I)
(hext : IsPExtendible p I) (T : Finset α) (hT : I T) :
E2 (1 / ((p : ℝ) + 1)) f I T (fun st => f (st.S ∪ T)) -
∑ u : α, E2 (1 / ((p : ℝ) + 1)) f I T
(fun st => ((st.Ou u \ st.S).card : ℝ) * marg f u (st.Su u)) ≤
E2 (1 / ((p : ℝ) + 1)) f I T (fun st => f st.S) ∧
E2 (1 / ((p : ℝ) + 1)) f I T (fun st => f (st.S ∪ T)) -
((p : ℝ) / ((p : ℝ) + 1)) * ∑ u : α, E2 (1 / ((p : ℝ) + 1)) f I T
(fun st => (if u ∈ st.considered then (1 : ℝ) else 0) * marg f u (st.Su u)) ≤
E2 (1 / ((p : ℝ) + 1)) f I T (fun st => f (st.S ∪ T)) -
∑ u : α, E2 (1 / ((p : ℝ) + 1)) f I T
(fun st => ((st.Ou u \ st.S).card : ℝ) * marg f u (st.Su u)) ∧
E2 (1 / ((p : ℝ) + 1)) f I T (fun st => f (st.S ∪ T)) -
(p : ℝ) * E2 (1 / ((p : ℝ) + 1)) f I T (fun st => f st.S) ≤
E2 (1 / ((p : ℝ) + 1)) f I T (fun st => f (st.S ∪ T)) -
((p : ℝ) / ((p : ℝ) + 1)) * ∑ u : α, 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. 14, §4.1.1 (unnumbered display in the proof of Theorem 1, submodular objectives)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.