Research map / Learning theory and algorithms / Sample complexity
A Near Linear Query Lower Bound for 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.
Proves near-linear query lower bounds for approximating monotone submodular k-subset maximization (even estimating OPT) and a near-tight Õ(n/k) estimator plus matching lower bound for estimating the optimum of additive objectives.
Problem
Whether k-out-of-n subset selection for monotone submodular or additive objectives can be solved (or its optimal value estimated) with sublinear query complexity.
Approach
Reduces query algorithms to communication complexity of distributed set detection (via a blackboard protocol with polylog overhead and distributed SDPI), yielding near-linear query lower bounds; uses a two-level truncated linear function for the decision version, and a multi-scale quantile-estimation algorithm for additive functions achieving Õ(n/k) queries for value estimation.
Key results
- For monotone submodular f and k=o(n), no Õ(n)-query algorithm approximates OPT to any constant factor (Theorem 3.9, Ω(α^11 n/log^2 n) queries).
- For additive functions, an Õ(n/k) query algorithm estimates the optimal k-subset value within (1±ϵ) (Theorem 4.1), matched by an Ω(α^3 n/(k log n)) lower bound (Theorem 4.7).
- Finding an approximately optimal k-subset for additive functions requires Ω(α^5 n/log^2 n) queries (Theorem 3.7), i.e., near-linear.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use two-level truncation of a linear function | Monotone submodular optimal-value estimation · Submodular maximization, cardinality k | query complexity lower bound: eΩ(n) | Helped |
| Use a linear additive objective instead of a general submodular objective | Finding an approximately optimal k-subset · Additive maximization, cardinality k | query complexity lower bound: Ω(α5n/ log2(n)) | No clear effect |
| Estimate the optimum value rather than find an approximately optimal subset | Monotone additive maximization · Additive maximization, cardinality k | query complexity: (n/k) · poly(log(n), ϵ−1) | Helped |
| Estimate the optimum value instead of find an approximately optimal subset | Monotone additive maximization · Additive maximization, cardinality k | query complexity lower bound: Ω(α3n/k log(n)) | Helped |
Surprising findings
- Estimating the optimal value of an additive objective is far easier than finding the optimal subset: Õ(n/k) versus near-linear queries.
Limitations
- Lower bounds hold only for k = o(n) and approximation factor regimes with constant alpha
- Lower bounds are up to polylog factors (Õ(n) rather than exact)
- Query model only; runtime/computation not the focus
Experimental setup
Metrics: query complexity
Baselines: Li et al. 2022 Kuhnle 2021 greedy algorithm stochastic greedy
Builds on: Li et al. 2022 submodular query lower bound Kuhnle 2021 lower bound distributed strong data processing inequality (Braverman et al. 2016)
Closest papers by meaning
- Maximization of Approximately Submodular Functions (NeurIPS 2016 · similarity 0.93)
- Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel (NeurIPS 2021 · similarity 0.91)
- A Dynamic Algorithm for Weighted Submodular Cover Problem (ICML 2024 · similarity 0.89)
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.88)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.88)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.87)
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.