Research map / Learning theory and algorithms / Submodular and game algorithms
Approximation Guarantees for Adaptive Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adding bounded curvature (alpha < 1) to the submodular function | ADAPTIVE-SAMPLING · theory | approximation ratio: from 1/3 to arbitrarily close to max(1-alpha, 1/2) | Helped |
| Assuming mu-homogeneity of the submodular function | ADAPTIVE-SAMPLING with bounded curvature · theory | approximation ratio: approaches 1 as homogeneity improves (1 - mu/(2mu+1)) | Helped |
| Adding the top k/r elements by marginal contribution (M) alongside the best sample | ADAPTIVE-SAMPLING · theory | approximation ratio | Helped |
| Using curvaturing on general submodular functions (unbounded curvature) | ADAPTIVE-SAMPLING · theory | approximation ratio: 1/2 approximation with an additive loss of k/log n terms | Mixed |
| Increasing number of rounds r (curvature tradeoff) (ablation) | ADAPTIVE-SAMPLING on movie recommendation · MovieLens 1M (k=100) | f(S) value | No clear effect |
| Increasing number of rounds r from 1 to 10 (ablation) | ADAPTIVE-SAMPLING on taxi dispatch · NYC taxi (k=30) | f(S) value | Helped |
| Increasing number of samples per round from 10 to 10K (ablation) | ADAPTIVE-SAMPLING · MovieLens 1M | f(S) value | No clear effect |
Closest papers by meaning
- Optimization for Approximate Submodularity (NeurIPS 2018 · similarity 0.93)
- The Power of Optimization from Samples (NeurIPS 2016 · similarity 0.92)
- Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity (ICML 2021 · similarity 0.92)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.90)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.90)
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization (NeurIPS 2024 · similarity 0.89)
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.