Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

By Matthew Fahrbach, Vahab S. Mirrokni, Morteza Zadimoghaddam. 2018

70 citations recorded by the source corpus.

Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint $k$ that achieves a $(1-1/e-\varepsilon)$-approximation in expectation. This algorithm runs in $O(\log(n))$ adaptive rounds and makes $O(n)$ calls to the function evaluation oracle in expectation. The approximation guarantee and query complexity are optimal, and the adaptivity is nearly optimal. Moreover, the number of queries is substantially less than in previous works. Last, we extend our results to the submodular cover problem to demonstrate the generality of our algorithm and techniques.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Algorithms & Complexity

Citations in the corpus

Causal Mediation Analysis for Interpreting Neural NLP: The Case of Gender Bias (2020, methodology): “Alternative methods using adaptive sampling techniques have been proposed to speed-up GREEDY for submodular functions under cardinality constraints (Ene and Nguyen, 2019; Fahrbach et al., 2019b; Balkanski and Singer, 2018a,b).”
Investigating Gender Bias in Language Models Using Causal Mediation Analysis (2020, methodology): “For non-monotone or non-submodular functions, there are parallelized algorithms that use similar techniques to select sets (Balkanski et al., 2018; Qian and Singer, 2019; Fahrbach et al., 2019a).”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, methodology): “M EAN estimator subroutine in Fahrbach et al. (2019).”