Paper Info
Title
A lower bound for parallel submodular minimization
Abstract
In this paper, we study submodular function minimization in the adaptive complexity model. Seminal work by Gr'otschel, Lovász, and Schrijver shows that with oracle access to a function f, the problem of submodular minimization can be solved exactly with poly(n) queries to f. A long line of work has since then been dedicated to the acceleration of submodular minimization. In particular, recent work obtains a (strongly) polynomial time algorithm with Õ(n3) query complexity. A natural way to accelerate computation is via parallelization, though very little is known about the extent to which submodular minimization can be parallelized. A natural measure for the parallel runtime of a black-box optimization algorithm is its adaptivity, as recently introduced in the context of submodular maximization. Informally, the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially-many function evaluations in parallel. In the past two years there have been breakthroughs in the study of adaptivity for both submodular maximization and convex minimization, in particular an exponential improvement in the parallel running time of submodular maximization was obtained with a O(logn)-adaptive algorithm. Whether submodular minimization can enjoy, thanks to parallelization, the same dramatic speedups as submodular maximization is unknown. To date, we do not know of any polynomial time algorithm for solving submodular minimization whose adaptivity is subquadratic in n. We initiate the study of the adaptivity of submodular function minimization by giving the first non-trivial lower bound for the parallel runtime of submodular minimization. We show that there is no o(logn/loglogn)-adaptive algorithm with poly(n) queries which solves the problem of submodular minimization. This is the first adaptivity lower bound for unconstrained submodular optimization (whether for maximization or minimization) and the analysis relies on a novel and intricate construction of submodular functions.
Year
DOI
Venue
2020
10.1145/3357713.3384287
STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing Chicago IL USA June, 2020
Keywords
DocType
ISSN
Adaptivity, submodular minimization, parallel algorithms
Conference
0737-8017
ISBN
Citations 
PageRank 
978-1-4503-6979-4
1
0.37
References 
Authors
0
2
Name
Order
Citations
PageRank
eric balkanski1386.13
Yaron Singer251637.15