Theorem 1, p. 7 — SampleGreedy is a (p+1)²/p-approximation (p+1 monotone, q = 1/(p+1); p linear, q = 1/p) over p-extendible systems
ProvedSubsampleSubmod.SampleGreedy.theorem_1Let be a finite ground set with a fixed linear order (used to break ties), let be a non-negative submodular function, and let be a -extendible independence system with . Write for the expected value of the set returned by SampleGreedy (Algorithm 1) when every element is sampled independently with probability . Then:
- SampleGreedy always returns an independent set: for every sample.
- With , for every independent set ,
- If moreover is monotone, then with , for every .
- If moreover is linear, then with , for every .
Taking to be a maximizer OPT of problem (2), these say that SampleGreedy is, in expectation, a -approximation for non-negative submodular maximization over -extendible systems, a -approximation for monotone objectives, and a -approximation for linear objectives. Since no polynomial-query algorithm beats for this problem, the ratio is nearly tight.
Formalization Note The approximation ratio of a randomized algorithm is read as the paper's proof reads it: . Comparing with every is equivalent to comparing with OPT. Additions relative to the page: is a natural number with (the paper divides by ); ties are broken by a fixed linear order of the ground set, as the paper assumes on p. 10; the expectation is the exact sum over all samples; the while loop runs iterations. "Linear" is the page's definition ((1) with equality) and does not force . Submodularity is the published lattice form, equivalent on finite ground sets to the diminishing-returns form (1). The oracle-count clause "SampleGreedy uses in expectation calls to the evaluation and independence oracles" is not formalized.
import Mathlib import Definitions.Def_SubsampleSubmod_SampleGreedy_Model
namespace SubsampleSubmod.SampleGreedy
/-- Theorem 1 (Harshaw et al., arXiv:2104.02772v1, p. 7). Let `f ≥ 0` be submodular and `ℐ` a
`p`-extendible independence system, `p ≥ 1`. SampleGreedy always returns an independent set, and
1. with `q = 1/(p+1)`: `f(T) ≤ (p+1)²/p · E[f(S)]` for every `T ∈ ℐ`;
2. with `q = 1/(p+1)` and `f` monotone: `f(T) ≤ (p+1) · E[f(S)]` for every `T ∈ ℐ`;
3. with `q = 1/p` and `f` linear: `f(T) ≤ p · E[f(S)]` for every `T ∈ ℐ`.
The oracle-count clause `O(nk/p)` is not formalized. -/
theorem theorem_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) :
(∀ N' : Finset α, I (sampleGreedy f I N')) ∧
(∀ T : Finset α, I T →
f T ≤ (((p : ℝ) + 1) ^ 2 / (p : ℝ)) * expectedValue (1 / ((p : ℝ) + 1)) f I) ∧
(Monotone f → ∀ T : Finset α, I T →
f T ≤ ((p : ℝ) + 1) * expectedValue (1 / ((p : ℝ) + 1)) f I) ∧
(IsLinear f → ∀ T : Finset α, I T →
f T ≤ (p : ℝ) * expectedValue (1 / (p : ℝ)) f I) := by sorry
end SubsampleSubmod.SampleGreedy
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.