Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

By Alina Ene, Huy L. Nguyen. 2018

79 citations recorded by the source corpus.

In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds of queries it makes to the evaluation oracle of the function, where in every round the algorithm is allowed to make polynomially-many parallel queries. Adaptivity is an important consideration in settings where the objective function is estimated using samples and in applications where adaptivity is the main running time bottleneck. Previous algorithms achieving a nearly-optimal $1 - 1/e - \epsilon$ approximation require $\Omega(n)$ rounds of adaptivity. In this work, we give the first algorithm that achieves a $1 - 1/e - \epsilon$ approximation using $O(\ln{n} / \epsilon^2)$ rounds of adaptivity. The number of function evaluations and additional running time of the algorithm are $O(n \mathrm{poly}(\log{n}, 1/\epsilon))$.

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

Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity (2018, methodology): “While writing this paper, another related work (on arXiv) was brought to our attention [EN19].”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, background): “)) rounds [BRS18] for the monotone submodular functions. However, this algorithm requires O(nk2) queries. While writing this paper, another recent related work (on arXiv) was brought to our attention [EN18], which achieves the same approximation factor in O(log(n)) adaptive rounds with O(poly(log(n)”
Fast Parallel Algorithms for Feature Selection (2019, background): “…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. (2018b).”
Investigating Gender Bias in Language Models Using Causal Mediation Analysis (2020, methodology): “Alternative methods using adaptive sampling techniques have been proposed to speed-up G REEDY for submodular functions under cardinality constraints (Ene and Nguyen, 2019; Fahrbach et al., 2019b; Balkanski and Singer, 2018a,b).”
Non-monotone Submodular Maximization in Exponentially Fewer Iterations (2018, methodology): “…new techniques for maximizing monotone submodular functions under a cardinality constraint that produce algorithms that are O (log n )-adaptive and achieve strong constant factor approximation guarantees [BS18a, BS18b] and even optimal approximation guarantees in O (log n ) rounds [BRS18, EN18].”