Non-monotone Submodular Maximization in Exponentially Fewer Iterations

By Eric Balkanski, Adam Breuer, Yaron Singer. 2018

61 citations recorded by the source corpus.

In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily close to 1/2e in O(log^2 n) adaptive rounds, where n is the size of the ground set. This is an exponential speedup in parallel running time over any previously studied algorithm for constrained non-monotone submodular maximization. Beyond its provable guarantees, the algorithm performs well in practice. Specifically, experiments on traffic monitoring and personalized data summarization applications show that the algorithm finds solutions whose values are competitive with state-of-the-art algorithms while running in exponentially fewer parallel iterations.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Mathematical Optimization

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

1. Yonatan Belinkov
2. Sebastian Gehrmann
3. Jesse Vig
4. Sharon Qian
5. Stuart M. Shieber
6. Yaron Singer
7. Daniel Nevo
8. Vahab S. Mirrokni

In Computational Theory and Mathematics

1. Sharon Qian
2. Yaron Singer
3. Stuart M. Shieber
4. Jesse Vig
5. Yonatan Belinkov
6. Sebastian Gehrmann
7. Daniel Nevo
8. Morteza Zadimoghaddam

In Mathematical Optimization

1. Sharon Qian
2. Yaron Singer
3. Morteza Zadimoghaddam
4. Vahab S. Mirrokni
5. Matthew Fahrbach
6. Stuart M. Shieber
7. Jesse Vig
8. Yonatan Belinkov

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).”
• Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, methodology): “The BLITS algorithm (Balkanski et al., 2018) constructs a solution by randomly choosing blocks of high-valued elements, giving a (1/(2e)−ε)-approximation in O(log(2)(n)) rounds.”
• 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): “…been used for submodular maximization under varying constraints 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.…”