# Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity

arXiv: https://arxiv.org/abs/1808.06932 · HTML: https://mlsanity.com/paper/1808.06932/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2018.

## Built on by (most cited first, 14 of 14)

- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Sequential Attention for Feature Selection](https://mlsanity.com/paper/2209.14881/) (2022)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](https://mlsanity.com/paper/2111.07917/) (2021)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Adaptive Sampling for Fast Constrained Maximization of Submodular Function](https://mlsanity.com/paper/2102.06486/) (2021)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization](https://mlsanity.com/paper/2304.06048/) (2023)
- [Greedy PIG: Adaptive Integrated Gradients](https://mlsanity.com/paper/2311.06192/) (2023)
- [Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2409.04415/) (2024)
- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)

## Abstract (arXiv)

Submodular maximization is a general optimization problem with a wide range of applications in machine learning (e.g., active learning, clustering, and feature selection). In large-scale optimization, the parallel running time of an algorithm is governed by its adaptivity, which measures the number of sequential rounds needed if the algorithm can execute polynomially-many independent oracle queries in parallel. While low adaptivity is ideal, it is not sufficient for an algorithm to be efficient in practice -- there are many applications of distributed submodular optimization where the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of submodular maximization. In this paper, we give the first constant-factor approximation algorithm for maximizing a non-monotone submodular function subject to a cardinality constraint k that runs in O(log(n)) adaptive rounds and makes O(n log(k)) oracle queries in expectation. In our empirical study, we use three real-world applications to compare our algorithm with several benchmarks for non-monotone submodular maximization. The results demonstrate that our algorithm finds competitive solutions using significantly fewer rounds and queries.