The Adaptive Complexity of Submodular Optimization

Abstract

In this thesis, we develop a new optimization technique that leads to exponentially faster algorithms for solving submodular optimization problems. For the canonical problem of maximizing a non-decreasing submodular function under a cardinality constraint, it is well known that the celebrated greedy algorithm which iteratively adds elements whose marginal contribution is largest achieves a 1-1/e approximation, which is optimal. The optimal approximation guarantee of the greedy algorithm comes at a price of high adaptivity. The adaptivity of an algorithm is the number of sequential rounds it makes when polynomially-many function evaluations can be executed in parallel in each round. Since submodular optimization is regularly applied on very large datasets, adaptivity is crucial as algorithms with low adaptivity enable dramatic speedups in parallel computing time. Submodular optimization has been studied for well over forty years now, and somewhat surprisingly, there was no known constant-factor approximation algorithm for submodular maximization whose adaptivity is sublinear in the size of the ground set n. Our main contribution is a novel optimization technique called adaptive sampling which leads to constant factor approximation algorithms for submodular maximization in only logarithmically many adaptive rounds. This is an exponential speedup in the parallel runtime for submodular maximization compared to previous constant factor approximation algorithms. Furthermore, we show that no algorithm can achieve a constant factor approximation in \tilde{o}(log n) rounds. Thus, the adaptive complexity of submodular maximization, i.e., the minimum number of rounds r such that there exists an r-adaptive algorithm which achieves a constant factor approximation, is logarithmic up to lower order terms.