Research map / Learning theory and algorithms / Submodular and game algorithms
Streaming Stochastic Submodular Maximization with On-Demand User Requests
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
The paper
Problem
Streaming submodular maximization where users make unpredictable on-demand visits and must receive up to k items per visit from items arriving so far; decisions are irrevocable and memory is limited, while the total number of visits is unknown (only an upper bound T' is available).
Approach
Reduce the multi-visit, stochastic-click coverage objective to streaming submodular maximization under a partition matroid, where each user visit is a partition; adapt a 1/4-approximation matroid streaming algorithm (preemption/threshold style) with a visit counter, and make concurrent guesses of the visit count (multiples of delta) with greedy aggregation across guesses to obtain a 1/(8 delta) co
Key results
- STORM++ achieves a competitive ratio of 1/(8 delta) with space O(T'^2 k/delta) and response time O(T'), while LMGreedy gets 1/2 with Theta(N+kT) memory.
- On Amazon (k=10, T=5, T'=20, delta=10), STORM(T) ran in 4.38 s with 0.72 MB memory versus 88.13 s and 28.99 MB for LMGreedy.
- LMGreedy achieves the best expected coverage across datasets and budgets, with STORM(T) best among proposed methods and outperforming Sieve++ and Preemption adaptations in most settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Storm(T) with the exact visit count instead of Storm(T') with an upper-bound estimate | S3MOR algorithms · Expected coverage across datasets and varying k | expected coverage | Helped |
| Use Storm++ instead of Storm(T') | S3MOR algorithms · Expected coverage across datasets and varying k | expected coverage | Helped |
| Use Storm(T') or Storm++ instead of Sieve++ or Preemption | S3MOR algorithms · Expected coverage across datasets and values of k | expected coverage | Helped |
| Increase Storm++'s δ from 3 to 30 (ablation) | Storm++ · Amazon | expected coverage: 130 to 120 | Hurt |
| Increase Storm(T')'s ΔT (the gap between the upper bound and actual visits) (ablation) | Storm(T') · Expected coverage across datasets | expected coverage | Hurt |
| Increase ΔT from 10 to 100 (ablation) | Storm(T') · S3MOR | competitive ratio: 10-fold decrease | Hurt |
| Increase ΔT (ablation) | Storm++ · Expected coverage across datasets | expected coverage | No clear effect |
| Use a smaller δ and ΔT (ablation) | Storm++ and Storm(T') · Expected coverage across datasets and varying T | expected coverage | Helped |
| Use Storm(T') or Storm++ instead of LMGreedy | S3MOR algorithms · Amazon | memory (MB) | Helped |
| Use Storm(T') or Storm(T) instead of the remaining algorithms | S3MOR algorithms · Amazon | runtime | Helped |
Surprising findings
- STORM(T') and STORM++ can empirically outperform STORM(T) in some settings despite STORM(T) having the strongest theoretical guarantee.
Limitations
- Competitive ratio of STORM degrades as 1/(4(T'-T+1)) when the visit upper bound is loose.
- STORM++ ratio 1/(8 delta) is worse than the 1/2 of LMGreedy and its space/time grow with T'^2.
- Experiments use synthetic click probabilities and a single MacBook setup.
Experimental setup
Datasets: KuaiRec Anime Beer Yahoo RCV1 Amazon
Benchmarks: Yahoo RCV1 Amazon KuaiRec Anime Beer
Metrics: expected topic coverage runtime (s) memory (MB) oracle call counts
Baselines: LMGreedy Sieve++ (adapted) Preemption (adapted) STORM(T) STORM(T')
Builds on: Fisher et al. local greedy Sieve++ preemption streaming algorithm for matchoids streaming matroid submodular algorithm (1/4-approx)
Closest papers by meaning
- Streaming Submodular Maximization under a k-Set System Constraint (ICML 2020 · similarity 0.92)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.91)
- Do Less, Get More: Streaming Submodular Maximization with Subsampling (NeurIPS 2018 · similarity 0.90)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · similarity 0.88)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.86)
- Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.