Timezone: »
Oral
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity
Matthew Fahrbach · Vahab Mirrokni · Morteza Zadimoghaddam
As a general optimization problem, submodular maximization has 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-approximation algorithm for maximizing a non-monotone submodular function subject to a cardinality constraint~$k$ that runs in $O(\log(n))$ adaptive rounds. Additionally, our algorithm makes only $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, and the results show that our algorithm finds competitive solutions using \emph{significantly fewer rounds and queries}.
Author Information
Matthew Fahrbach (Georgia Institute of Technology)
Vahab Mirrokni (Google Research)
Morteza Zadimoghaddam (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity »
Fri. Jun 14th 01:30 -- 04:00 AM Room Pacific Ballroom #141
More from the Same Authors
-
2023 Poster: Fully Dynamic Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Oral: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Oral: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Poster: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2022 Spotlight: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2022 : Closing Remarks »
Vahab Mirrokni -
2022 : Private Algorithms Q/A »
Peilin Zhong · Alessandro Epasto · Vahab Mirrokni -
2022 : Graph Mining Q/A »
Vahab Mirrokni -
2022 : New Challenges in Graph Mining: Scalability, Stability, and Privacy Applications »
Vahab Mirrokni -
2022 Expo Talk Panel: Challenges Of Applying Graph Neural Networks »
Bryan Perozzi · Vahab Mirrokni -
2022 : Graph Mining at Google »
Vahab Mirrokni -
2021 Poster: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time »
Laxman Dhulipala · David Eisenstat · Jakub Łącki · Vahab Mirrokni · Jessica Shi -
2021 Spotlight: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time »
Laxman Dhulipala · David Eisenstat · Jakub Łącki · Vahab Mirrokni · Jessica Shi -
2021 Poster: Regularized Online Allocation Problems: Fairness and Beyond »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2021 Spotlight: Regularized Online Allocation Problems: Fairness and Beyond »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2021 Poster: Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni · Song Zuo -
2021 Spotlight: Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni · Song Zuo -
2020 Poster: Robust Pricing in Dynamic Mechanism Design »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni -
2020 Poster: Dual Mirror Descent for Online Allocation Problems »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2020 Poster: Bandits with Adversarial Scaling »
Thodoris Lykouris · Vahab Mirrokni · Renato Leme -
2020 Poster: Faster Graph Embeddings via Coarsening »
Matthew Fahrbach · Gramoz Goranci · Richard Peng · Sushant Sachdeva · Chi Wang -
2019 Poster: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Poster: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Poster: Distributed Weighted Matching via Randomized Composable Coresets »
Sepehr Assadi · Mohammad Hossein Bateni · Vahab Mirrokni -
2019 Oral: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: Distributed Weighted Matching via Randomized Composable Coresets »
Sepehr Assadi · Mohammad Hossein Bateni · Vahab Mirrokni -
2018 Poster: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Accelerating Greedy Coordinate Descent Methods »
Haihao Lu · Robert Freund · Vahab Mirrokni -
2018 Poster: Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni -
2018 Oral: Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni -
2018 Oral: Accelerating Greedy Coordinate Descent Methods »
Haihao Lu · Robert Freund · Vahab Mirrokni -
2018 Oral: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints »
Ehsan Kazemi · Morteza Zadimoghaddam · Amin Karbasi -
2018 Poster: Data Summarization at Scale: A Two-Stage Submodular Approach »
Marko Mitrovic · Ehsan Kazemi · Morteza Zadimoghaddam · Amin Karbasi -
2018 Poster: Proportional Allocation: Simple, Distributed, and Diverse Matching with High Entropy »
Shipra Agarwal · Morteza Zadimoghaddam · Vahab Mirrokni -
2018 Oral: Proportional Allocation: Simple, Distributed, and Diverse Matching with High Entropy »
Shipra Agarwal · Morteza Zadimoghaddam · Vahab Mirrokni -
2018 Oral: Data Summarization at Scale: A Two-Stage Submodular Approach »
Marko Mitrovic · Ehsan Kazemi · Morteza Zadimoghaddam · Amin Karbasi -
2018 Oral: Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints »
Ehsan Kazemi · Morteza Zadimoghaddam · Amin Karbasi -
2017 Poster: Probabilistic Submodular Maximization in Sub-Linear Time »
Serban A Stan · Morteza Zadimoghaddam · Andreas Krause · Amin Karbasi -
2017 Talk: Probabilistic Submodular Maximization in Sub-Linear Time »
Serban A Stan · Morteza Zadimoghaddam · Andreas Krause · Amin Karbasi -
2017 Poster: Tight Bounds for Approximate Carathéodory and Beyond »
Vahab Mirrokni · Renato Leme · Adrian Vladu · Sam Wong -
2017 Talk: Tight Bounds for Approximate Carathéodory and Beyond »
Vahab Mirrokni · Renato Leme · Adrian Vladu · Sam Wong