Research map / Learning theory and algorithms / Submodular and game algorithms
Learning-Augmented Dynamic Submodular Maximization
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.
Gives a dynamic monotone submodular maximization algorithm under cardinality constraint that uses predictions of element insertion/deletion times for preprocessing, achieving polylog-in-prediction-error amortized update time and 1/2-epsilon approximation.
Problem
Dynamic monotone submodular maximization under a cardinality constraint requires fast update time over insertion/deletion streams; the question is whether predictions of update times can reduce amortized update time.
Approach
Framework that splits active elements into predicted and unpredicted ones; precomputes strongly robust sets from a fully dynamic algorithm (Lattanzi et al.) and a deletion-robust algorithm (Kazemi et al.), reusing them across phases so amortized update cost depends on prediction error eta rather than stream length.
Key results
- Main theorem: amortized streaming query complexity O(poly(log eta, log w, log k)) with 1/2 - epsilon approximation in expectation for dynamic monotone submodular maximization under cardinality constraint.
- Precomputation query complexity is tilde-O(n), improved from warm-up tilde-O(n^2 k).
- Warm-up algorithm achieves tilde-O(eta + w + k) amortized update time with 1/4 - epsilon approximation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use insertion and deletion time predictions to guide preprocessing and streaming updates | Dynamic monotone submodular maximization, cardinality k · Dynamic monotone submodular maximization, cardinality k | amortized query complexity per streaming update: \tilde{O}(\eta + w + k) -> O(\ensuremath\textnormal{poly}(\log \eta, \log w, \log k)) | Helped |
| use predictions with the full algorithm instead of the warm-up algorithm | Dynamic monotone submodular maximization, cardinality k · Dynamic monotone submodular maximization, cardinality k | approximation ratio: 1/4 - \epsilon -> 1/2 - \epsilon | Helped |
| use the improved precomputations subroutine instead of independently computing robust solutions for each time step | Dynamic monotone submodular maximization, cardinality k · Dynamic monotone submodular maximization, cardinality k | precomputation query complexity: \tilde{O}(n^2 k) -> \tilde{O}(n) | Helped |
Limitations
- Assumes known or guessed prediction error structure; uses guesses for OPT and eta leading to log factors
- Predicted-deletion model (no preprocessing) remains open
- Results are theoretical with no experiments
Experimental setup
Metrics: amortized query complexity approximation ratio precomputation query complexity
Baselines: Lattanzi et al. dynamic algorithm Monemizadeh dynamic algorithm Banihashem et al. dynamic algorithm Liu and Srinivas predicted-deletion algorithm
Builds on: Lattanzi et al. dynamic submodular maximization Kazemi et al. deletion-robust submodular maximization Liu and Srinivas predicted-deletion model
Closest papers by meaning
- Fully Dynamic Algorithm for Constrained Submodular Optimization (NeurIPS 2020 · similarity 0.92)
- Dynamic Submodular Maximization (NeurIPS 2020 · similarity 0.92)
- Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time (ICML 2023 · similarity 0.92)
- When Streaming Fails: Dynamic Algorithms for Unconstrained Submodular Maximization (NeurIPS 2026 · similarity 0.91)
- Improved Fully Dynamic Submodular Maximization Under Matroid Constraints (AAAI 2026 · similarity 0.91)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.90)
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.