Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and 1/e Approximation

Submodular maximization is a general optimization problem with a wide range of applications in machine learning (e.g., active learning, clustering, and feature selection). In large-scale optimization, the parallel running time of an algorithm is governed by its adaptivity, which measures the number of sequential rounds needed if the algorithm can execute polynomially-many independent oracle queries in parallel. While low adaptivity is ideal, it is not sufficient for an algorithm to be efficient in practice-there are many applications of distributed submodular optimization where the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of submodular maximization. In this paper, we give the first constant-factor approximation algorithm for maximizing a non-monotone submodular function subject to a cardinality constraint k that runs in O(log(n)) adaptive rounds and makes O(n log(k)) oracle queries in expectation. In our empirical study, we use three real-world applications to compare our algorithm with several benchmarks for non-monotone submodular maximization. The results demonstrate that our algorithm finds competitive solutions using significantly fewer rounds and queries. Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity Table 1 . Independent and concurrent works for low-adaptivity non-monotone submodular maximization subject to a cardinality constraint. ALGORITHM APPROXIMIATION ADAPTIVITY QUERIES BUCHBINDER ET AL. ( 2016 ) The literature on submodular optimization typically assumes access to an oracle that evaluates the submodular function. In practice, however, oracle queries may take a long time to process. For example, the log-determinant of submatrices of a positive semi-definite matrix is a submodular function that is notoriously expensive to compute (Kazemi et al., 2018) . Therefore, our goal when designing distributed algorithms is to minimize the number of rounds where the algorithm communicates with the oracle. This motivates the notion of the adaptivity complexity of submodular optimization, first investigated in Balkanski & Singer (2018). In this model of computation, the algorithm can ask polynomially-many independent oracle queries all together in each round. In a wide range of machine learning optimization problems, the objective functions can only be estimated through oracle access to the function. In many instances, these oracle evaluations are a new time-consuming optimization problem that we treat as a black box (e.g., hyperparameter optimization). Since our goal is to optimize the objective function using as few rounds of interaction with the oracle as possible, insights and algorithms developed in this adaptivity complexity framework can have a deep impact on distributed computing for machine learning applications in practice. Further motivation for the importance of this computational model is given in Balkanski & Singer (2018). While the number of adaptive rounds is an important quantity to minimize, the computational complexity of evaluating oracle queries also motivates the design of algorithms that are efficient in terms of the total number of oracle queries. An algorithm typically needs to make at least a constant number of queries per element in the ground set to achieve a constant-factor approximation. In this paper, we study the adaptivity complexity and the total number of oracle queries that are needed to guarantee a constant-factor approximation when maximizing a non-monotone submodular function. Results and Techniques. Our main result is a distributed algorithm for maximizing a non-monotone submodular function subject to a cardinality constraint k that achieves an expected (0.039 -ε)-approximation in O(log(n)/ε) adaptive rounds using O(n log(k)/ε 2 ) expected function evaluation queries. To the best of our knowledge, this is the first constant-factor approximation algorithm with nearly-optimal adaptivity for the general problem of maximizing non-monotone submodular functions. The adaptivity complexity of our algorithm is optimal up to a Θ(log log(n)) factor by the lower bound in Balkanski & Singer (2018).