# Adaptive Sampling for Fast Constrained Maximization of Submodular Function

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 52 references that are in the map.
- First posted on arXiv 12 Feb 2021.

## Builds on (most cited first, 17 of 17)

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Bayesian experimental design using regularized determinantal point processes](https://mlsanity.com/paper/1906.04133/) (2019)
- [Submodular Maximization Meets Streaming: Matchings, Matroids, and More](https://mlsanity.com/paper/1309.2038/) (2013)
- [Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly](https://mlsanity.com/paper/1706.03583/) (2017)
- [Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity](https://mlsanity.com/paper/1807.07889/) (2018)
- [Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity](https://mlsanity.com/paper/1808.06932/) (2018)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (2018)
- [Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization](https://mlsanity.com/paper/1704.01652/) (2017)
- [Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time](https://mlsanity.com/paper/1804.05379/) (2018)
- [Non-monotone Submodular Maximization in Exponentially Fewer Iterations](https://mlsanity.com/paper/1807.11462/) (2018)
- [Submodular Maximization with Matroid and Packing Constraints in Parallel](https://mlsanity.com/paper/1808.09987/) (2018)
- [Parallelizing greedy for submodular set function maximization in matroids and beyond](https://mlsanity.com/paper/1811.12568/) (2018)
- [An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model](https://mlsanity.com/paper/1811.03093/) (2018)
- [Unconstrained Submodular Maximization with Constant Adaptive Complexity](https://mlsanity.com/paper/1811.06603/) (2018)
- [Streaming Algorithms for Submodular Function Maximization](https://mlsanity.com/paper/1504.08024/) (2015)
- [A polynomial lower bound on adaptive complexity of submodular maximization](https://mlsanity.com/paper/2002.09130/) (2020)

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

- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)

## Abstract (arXiv)

Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a p-system side constraint, and it achieves a (p + O(√p))-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a (p + O(1))-approximation when the given side constraint is a p-extendible system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.