We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries.
We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a $11/e\epsilon$ approximation for monotone functions and a $1/e\epsilon$ approximation for nonmonotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is $O(\log^2{n}/\epsilon^3)$, which is an exponential speedup over the existing algorithms.
We obtain the first parallel algorithm for nonmonotone submodular maximization subject to packing constraints. Our algorithm achieves a $1/e\epsilon$ approximation using $O(\log(n/\epsilon) \log(1/\epsilon) \log(n+m)/ \epsilon^2)$ parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a $11/e\epsilon$ approximation in $O(\log(n/\epsilon)\log(m)/\epsilon^2)$ parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016).
Our results apply more generally to the problem of maximizing a diminishing returns submodular (DRsubmodular) function.
more »
« less
The FAST Algorithm for Submodular Maximization
In this paper we describe a new parallel algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint k. This algorithm achieves the optimal 11/e approximation guarantee and is orders of magnitude faster than the stateoftheart on a variety of experiments over realworld data sets. Following recent work by Balkanski & Singer (2018a), there has been a great deal of research on algorithms whose theoretical parallel runtime is exponentially faster than algorithms used for sub modular maximization over the past 40 years. However, while these new algorithms are fast in terms of asymptotic worstcase guarantees, it is computationally infeasible to use them in practice even on small data sets because the number of rounds and queries they require depend on large constants and highdegree polynomials in terms of precision and confidence. The design principles behind the FAST algorithm we present here are a significant departure from those of recent theoretically fast algorithms. Rather than optimize for asymptotic theoretical guarantees, the design of FAST introduces several new techniques that achieve remarkable practical and theoretical parallel runtimes. The approximation guarantee obtained by FAST is arbitrarily close to 11/e, and its asymptotic parallel runtime (adaptivity) is O(log(n) log2(log k)) using O(n log log(k)) total queries. We show that FAST is orders of magnitude faster than any algorithm for submodular maximization we are aware of, including hyperoptimized parallel versions of stateoftheart serial algorithms, by running experiments on large data sets.
more »
« less
 Award ID(s):
 1647325
 NSFPAR ID:
 10220985
 Date Published:
 Journal Name:
 Proceedings of Machine Learning Research
 Volume:
 ICML 2020
 ISSN:
 26403498
 Page Range / eLocation ID:
 11341143
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)In this work, we give a new parallel algorithm for the problem of maximizing a nonmonotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy $\epsilon$, our algorithm achieves a $1/e  \epsilon$ approximation using $O(\log{n} \log(1/\epsilon) / \epsilon^3)$ parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearlyoptimal for any constant $\epsilon$. Previous algorithms achieve worse approximation guarantees using $\Omega(\log^2{n})$ parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality.more » « less

null (Ed.)In this work, we give a new parallel algorithm for the problem of maximizing a nonmonotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy $\epsilon$, our algorithm achieves a $1/e  \epsilon$ approximation using $O(\log{n} \log(1/\epsilon) / \epsilon^3)$ parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearlyoptimal for any constant $\epsilon$. Previous algorithms achieve worse approximation guarantees using $\Omega(\log^2{n})$ parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality.more » « less

null (Ed.)In this work, we give a new parallel algorithm for the problem of maximizing a nonmonotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy epsilon, our algorithm achieves a 1/e−epsilon approximation using O(logn*log(1/epsilon)/epsilon^3) parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearlyoptimal for any constant epsilon. Previous algorithms achieve worse approximation guarantees using Ω(log^2 n) parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality.more » « less

We study the problem of maximizing a nonmonotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a singlepass (semi)streaming algorithm that uses roughly $O(k / \varepsilon^2)$ memory, where $k$ is the size constraint. At the end of the stream, our algorithm postprocesses its data structure using any offline algorithm for submodular maximization, and obtains a solution whose approximation guarantee is $\frac{\alpha}{1+\alpha}\varepsilon$, where $\alpha$ is the approximation of the offline algorithm. If we use an exact (exponential time) postprocessing algorithm, this leads to $\frac{1}{2}\varepsilon$ approximation (which is nearly optimal). If we postprocess with the algorithm of \cite{buchbinder2019constrained}, that achieves the stateoftheart offline approximation guarantee of $\alpha=0.385$, we obtain $0.2779$approximation in polynomial time, improving over the previously best polynomialtime approximation of $0.1715$ due to \cite{feldman2018less}. It is also worth mentioning that our algorithm is combinatorial and deterministic, which is rare for an algorithm for nonmonotone submodular maximization, and enjoys a fast update time of $O(\frac{\log k + \log (1/\alpha {\varepsilon^2})$ per element.more » « less