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

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

60 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Mathematical Optimization, 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 Computer Networks and Communications

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Causal Mediation Analysis for Interpreting Neural NLP: The Case of Gender Bias (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).”
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).”
Fast Parallel Algorithms for Feature Selection (2019, methodology): “…constraints have been introduced using similar techniques Balkanski et al. (2019); Balkanski & Singer (2018b); Chekuri & Quanrud (2019, 2018); Balkanski et al. (2018a); Chen et al. (2018); Ene et al. (2018a); Fahrbach et al. (2019); Balkanski et al. (2018b); Ene & Nguyen (2019); Ene et al. (2018b).”