The adaptive complexity of maximizing a submodular function

By Eric Balkanski, Yaron Singer. 2018

136 citations recorded by the source corpus.

In this paper we study the adaptive complexity of submodular optimization. Informally, the adaptive complexity of a problem is the minimal number of sequential rounds required to achieve a constant factor approximation when polynomially-many queries can be executed in parallel at each round. Adaptivity is a fundamental concept that is heavily studied in computer science, largely due to the need for parallelizing computation. Somewhat surprisingly, very little is known about adaptivity in submodular optimization. For the canonical problem of maximizing a monotone submodular function under a cardinality constraint, to the best of our knowledge, all that is known to date is that the adaptive complexity is between 1 and Ω(n). Our main result in this paper is a tight characterization showing that the adaptive complexity of maximizing a monotone submodular function under a cardinality constraint is Θ(log n): - We describe an algorithm which requires O(log n) sequential rounds and achieves an approximation that is arbitrarily close to 1/3; - We show that no algorithm can achieve an approximation better than O(1 / log n) with fewer than O(log n / log log n) rounds. Thus, when allowing for parallelization, our algorithm achieves a constant factor approximation exponentially faster than any known existing algorithm for submodular maximization. Importantly, the approximation algorithm is achieved via adaptive sampling and complements a recent line of work on optimization of functions learned from data. In many cases we do not know the functions we optimize and learn them from labeled samples. Recent results show that no algorithm can obtain a constant factor approximation guarantee using polynomially-many labeled samples as in the PAC and PMAC models, drawn from any distribution. Since learning with non-adaptive samples over any distribution results in a sharp impossibility, we consider learning with adaptive samples where the learner obtains poly(n) samples drawn from a distribution of her choice in every round. Our result implies that in the realizable case, where there is a true underlying function generating the data, Θ(log n) batches of adaptive samples are necessary and sufficient to approximately “learn to optimize” a monotone submodular function under a cardinality constraint.

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

In Computational Theory and Mathematics

In Computer Networks and Communications

In Mathematical Optimization

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 G REEDY for submodular functions under cardinality constraints (Ene and Nguyen, 2019; Fahrbach et al., 2019b; Balkanski and Singer, 2018a,b).”
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity (2018, methodology): “The adaptive optimization framework [BS18] is a realistic model for this type of distributed problem, and the insights from lower bounds and algorithms developed in this framework have a deep impact on distributed computing for machine learning applications in practice.”
Approximation Guarantees for Adaptive Sampling (2018, methodology): “In recent work (Balkanski & Singer, 2018) introduce an adaptive sampling technique for maximizing monotone submodular functions under a cardinality constraint.”
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time (2018, methodology): “…in each round of adaptivity: we sample only a poly-logarithmic number of random sets, and we evaluate the marginal gains only on these random sets, whereas the algorithm of [BS18] uses a polynomial number of random sets and it evaluates the marginal gains with respect to all of these random sets.”
Non-monotone Submodular Maximization in Exponentially Fewer Iterations (2018, methodology): “This is tight in the sense that no algorithm can achieve a constant factor approximation with ˜ o (log n ) rounds [BS18a].”
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.…”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, methodology): “In Balkanski & Singer (2018), the authors show that a (1 / 3 − ε ) -approximation is achievable in O (log( n )) rounds.”
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).”