Timezone: »
In this paper, we consider optimizing submodular functions that are drawn from some unknown distribution. This setting arises, e.g., in recommender systems, where the utility of a subset of items may depend on a user-specific submodular utility function. In modern applications, the ground set of items is often so large that even the widely used (lazy) greedy algorithm is not efficient enough. As a remedy, we introduce the problem of {\em sublinear time probabilistic submodular maximization}: Given training examples of functions (e.g., via user feature vectors), we seek to reduce the ground set so that optimizing new functions drawn from the same distribution will provide almost as much value when restricted to the reduced ground set as when using the full set.
We cast this problem as a two-stage submodular maximization and develop a novel efficient algorithm for this problem which offers 1/2(1 - 1/e^2) approximation ratio for general monotone submodular functions and general matroid constraints. We demonstrate the effectiveness of our approach on several real-world problem instances where running the maximization problem on the reduced ground set leads to two folds speed-up while incurring almost no loss.
Author Information
Serban A Stan (Yale)
Morteza Zadimoghaddam (Google)
Andreas Krause (ETH Zurich)

Andreas Krause is a Professor of Computer Science at ETH Zurich, where he leads the Learning & Adaptive Systems Group. He also serves as Academic Co-Director of the Swiss Data Science Center and Chair of the ETH AI Center, and co-founded the ETH spin-off LatticeFlow. Before that he was an Assistant Professor of Computer Science at Caltech. He received his Ph.D. in Computer Science from Carnegie Mellon University (2008) and his Diplom in Computer Science and Mathematics from the Technical University of Munich, Germany (2004). He is a Max Planck Fellow at the Max Planck Institute for Intelligent Systems, an ELLIS Fellow, a Microsoft Research Faculty Fellow and a Kavli Frontiers Fellow of the US National Academy of Sciences. He received the Rössler Prize, ERC Starting Investigator and ERC Consolidator grants, the German Pattern Recognition Award, an NSF CAREER award as well as the ETH Golden Owl teaching award. His research has received awards at several premier conferences and journals, including the ACM SIGKDD Test of Time award 2019 and the ICML Test of Time award 2020. Andreas Krause served as Program Co-Chair for ICML 2018, and currently serves as General Chair for ICML 2023 and as Action Editor for the Journal of Machine Learning Research.
Amin Karbasi (Yale)

Amin Karbasi is currently an assistant professor of Electrical Engineering, Computer Science, and Statistics at Yale University. He has been the recipient of the National Science Foundation (NSF) Career Award 2019, Office of Naval Research (ONR) Young Investigator Award 2019, Air Force Office of Scientific Research (AFOSR) Young Investigator Award 2018, DARPA Young Faculty Award 2016, National Academy of Engineering Grainger Award 2017, Amazon Research Award 2018, Google Faculty Research Award 2016, Microsoft Azure Research Award 2016, Simons Research Fellowship 2017, and ETH Research Fellowship 2013. His work has also been recognized with a number of paper awards, including Medical Image Computing and Computer Assisted Interventions Conference (MICCAI) 2017, International Conference on Artificial Intelligence and Statistics (AISTAT) 2015, IEEE ComSoc Data Storage 2013, International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2011, ACM SIGMETRICS 2010, and IEEE International Symposium on Information Theory (ISIT) 2010 (runner-up). His Ph.D. thesis received the Patrick Denantes Memorial Prize 2013 from the School of Computer and Communication Sciences at EPFL, Switzerland.
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: Probabilistic Submodular Maximization in Sub-Linear Time »
Wed. Aug 9th 04:24 -- 04:42 AM Room Parkside 2
More from the Same Authors
-
2022 : Recovering Stochastic Dynamics via Gaussian Schrödinger Bridges »
Ya-Ping Hsieh · Charlotte Bunne · Marco Cuturi · Andreas Krause -
2022 : Recovering Stochastic Dynamics via Gaussian Schrödinger Bridges »
Charlotte Bunne · Ya-Ping Hsieh · Marco Cuturi · Andreas Krause -
2023 : Anytime Model Selection in Linear Bandits »
Parnian Kassraie · Aldo Pacchiano · Nicolas Emmenegger · Andreas Krause -
2023 : Unbalanced Diffusion Schrödinger Bridge »
Matteo Pariset · Ya-Ping Hsieh · Charlotte Bunne · Andreas Krause · Valentin De Bortoli -
2023 : Aligned Diffusion Schrödinger Bridges »
Vignesh Ram Somnath · Matteo Pariset · Ya-Ping Hsieh · Maria Rodriguez Martinez · Andreas Krause · Charlotte Bunne -
2023 : Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning »
Patrik Okanovic · Roger Waleffe · Vasileios Mageirakos · Konstantinos Nikolakakis · Amin Karbasi · Dionysios Kalogerias · Nezihe Merve Gürel · Theodoros Rekatsinas -
2023 : Graph Neural Network Powered Bayesian Optimization for Large Molecular Spaces »
Miles Wang-Henderson · Bartu Soyuer · Parnian Kassraie · Andreas Krause · Ilija Bogunovic -
2023 : Anytime Model Selection in Linear Bandits »
Parnian Kassraie · Aldo Pacchiano · Nicolas Emmenegger · Andreas Krause -
2023 Poster: Fully Dynamic Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2023 Panel: ICML Education Outreach Panel »
Andreas Krause · Barbara Engelhardt · Emma Brunskill · Kyunghyun Cho -
2022 Workshop: Adaptive Experimental Design and Active Learning in the Real World »
Mojmir Mutny · Willie Neiswanger · Ilija Bogunovic · Stefano Ermon · Yisong Yue · Andreas Krause -
2022 Poster: Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning »
Max Paulus · Giulia Zarpellon · Andreas Krause · Laurent Charlin · Chris Maddison -
2022 Poster: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Spotlight: Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning »
Max Paulus · Giulia Zarpellon · Andreas Krause · Laurent Charlin · Chris Maddison -
2022 Oral: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Interactively Learning Preference Constraints in Linear Bandits »
David Lindner · Sebastian Tschiatschek · Katja Hofmann · Andreas Krause -
2022 Spotlight: Interactively Learning Preference Constraints in Linear Bandits »
David Lindner · Sebastian Tschiatschek · Katja Hofmann · Andreas Krause -
2022 Poster: Adaptive Gaussian Process Change Point Detection »
Edoardo Caldarelli · Philippe Wenk · Stefan Bauer · Andreas Krause -
2022 Poster: Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation »
Pier Giuseppe Sessa · Maryam Kamgarpour · Andreas Krause -
2022 Poster: Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes »
Insu Han · Mike Gartrell · Elvis Dohmatob · Amin Karbasi -
2022 Poster: Meta-Learning Hypothesis Spaces for Sequential Decision-making »
Parnian Kassraie · Jonas Rothfuss · Andreas Krause -
2022 Spotlight: Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation »
Pier Giuseppe Sessa · Maryam Kamgarpour · Andreas Krause -
2022 Oral: Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes »
Insu Han · Mike Gartrell · Elvis Dohmatob · Amin Karbasi -
2022 Spotlight: Meta-Learning Hypothesis Spaces for Sequential Decision-making »
Parnian Kassraie · Jonas Rothfuss · Andreas Krause -
2022 Spotlight: Adaptive Gaussian Process Change Point Detection »
Edoardo Caldarelli · Philippe Wenk · Stefan Bauer · Andreas Krause -
2021 Workshop: Over-parameterization: Pitfalls and Opportunities »
Yasaman Bahri · Quanquan Gu · Amin Karbasi · Hanie Sedghi -
2021 : Greedy and Its Friends »
Amin Karbasi -
2021 : Data Summarization via Bilevel Coresets »
Andreas Krause -
2021 Poster: PopSkipJump: Decision-Based Attack for Probabilistic Classifiers »
Carl-Johann Simon-Gabriel · Noman Ahmed Sheikh · Andreas Krause -
2021 Spotlight: PopSkipJump: Decision-Based Attack for Probabilistic Classifiers »
Carl-Johann Simon-Gabriel · Noman Ahmed Sheikh · Andreas Krause -
2021 Poster: PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees »
Jonas Rothfuss · Vincent Fortuin · Martin Josifoski · Andreas Krause -
2021 Spotlight: PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees »
Jonas Rothfuss · Vincent Fortuin · Martin Josifoski · Andreas Krause -
2021 Poster: Online Submodular Resource Allocation with Applications to Rebalancing Shared Mobility Systems »
Pier Giuseppe Sessa · Ilija Bogunovic · Andreas Krause · Maryam Kamgarpour -
2021 Spotlight: Online Submodular Resource Allocation with Applications to Rebalancing Shared Mobility Systems »
Pier Giuseppe Sessa · Ilija Bogunovic · Andreas Krause · Maryam Kamgarpour -
2021 Poster: No-regret Algorithms for Capturing Events in Poisson Point Processes »
Mojmir Mutny · Andreas Krause -
2021 Poster: Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning »
Sebastian Curi · Ilija Bogunovic · Andreas Krause -
2021 Spotlight: No-regret Algorithms for Capturing Events in Poisson Point Processes »
Mojmir Mutny · Andreas Krause -
2021 Spotlight: Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning »
Sebastian Curi · Ilija Bogunovic · Andreas Krause -
2021 Poster: Regularized Submodular Maximization at Scale »
Ehsan Kazemi · shervin minaee · Moran Feldman · Amin Karbasi -
2021 Spotlight: Regularized Submodular Maximization at Scale »
Ehsan Kazemi · shervin minaee · Moran Feldman · Amin Karbasi -
2021 Poster: Bias-Robust Bayesian Optimization via Dueling Bandits »
Johannes Kirschner · Andreas Krause -
2021 Poster: Fast Projection Onto Convex Smooth Constraints »
Ilnura Usmanova · Maryam Kamgarpour · Andreas Krause · Kfir Levy -
2021 Spotlight: Fast Projection Onto Convex Smooth Constraints »
Ilnura Usmanova · Maryam Kamgarpour · Andreas Krause · Kfir Levy -
2021 Spotlight: Bias-Robust Bayesian Optimization via Dueling Bandits »
Johannes Kirschner · Andreas Krause -
2020 : Constrained Maximization of Lattice Submodular Functions »
Aytunc Sahin · Joachim Buhmann · Andreas Krause -
2020 : Mode Finding for SLC Distributions via Regularized Submodular Maximization »
Ehsan Kazemi · Amin Karbasi · Moran Feldman -
2020 Poster: From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models »
Aytunc Sahin · Yatao Bian · Joachim Buhmann · Andreas Krause -
2020 Poster: More Data Can Expand The Generalization Gap Between Adversarially Robust and Standard Models »
Lin Chen · Yifei Min · Mingrui Zhang · Amin Karbasi -
2020 Poster: Streaming Submodular Maximization under a k-Set System Constraint »
Ran Haba · Ehsan Kazemi · Moran Feldman · Amin Karbasi -
2020 Tutorial: Submodular Optimization: From Discrete to Continuous and Back »
Hamed Hassani · Amin Karbasi -
2020 Test Of Time: Test of Time: Gaussian Process Optimization in the Bandit Settings: No Regret and Experimental Design »
Niranjan Srinivas · Andreas Krause · Sham Kakade · Matthias Seeger -
2019 Poster: Online Variance Reduction with Mixtures »
Zalán Borsos · Sebastian Curi · Yehuda Levy · Andreas Krause -
2019 Poster: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity »
Matthew Fahrbach · Vahab Mirrokni · Morteza Zadimoghaddam -
2019 Poster: Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces »
Johannes Kirschner · Mojmir Mutny · Nicole Hiller · Rasmus Ischebeck · Andreas Krause -
2019 Poster: Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications »
Christopher Harshaw · Moran Feldman · Justin Ward · Amin Karbasi -
2019 Oral: Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces »
Johannes Kirschner · Mojmir Mutny · Nicole Hiller · Rasmus Ischebeck · Andreas Krause -
2019 Oral: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity »
Matthew Fahrbach · Vahab Mirrokni · Morteza Zadimoghaddam -
2019 Oral: Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications »
Christopher Harshaw · Moran Feldman · Justin Ward · Amin Karbasi -
2019 Oral: Online Variance Reduction with Mixtures »
Zalán Borsos · Sebastian Curi · Yehuda Levy · Andreas Krause -
2019 Poster: Learning Generative Models across Incomparable Spaces »
Charlotte Bunne · David Alvarez-Melis · Andreas Krause · Stefanie Jegelka -
2019 Poster: AReS and MaRS - Adversarial and MMD-Minimizing Regression for SDEs »
Gabriele Abbati · Philippe Wenk · Michael A Osborne · Andreas Krause · Bernhard Schölkopf · Stefan Bauer -
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 Oral: Learning Generative Models across Incomparable Spaces »
Charlotte Bunne · David Alvarez-Melis · Andreas Krause · Stefanie Jegelka -
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: AReS and MaRS - Adversarial and MMD-Minimizing Regression for SDEs »
Gabriele Abbati · Philippe Wenk · Michael A Osborne · Andreas Krause · Bernhard Schölkopf · Stefan Bauer -
2019 Poster: Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference »
Yatao Bian · Joachim Buhmann · Andreas Krause -
2019 Oral: Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference »
Yatao Bian · Joachim Buhmann · Andreas Krause -
2018 Poster: Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings »
Aryan Mokhtari · Hamed Hassani · Amin Karbasi -
2018 Poster: Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity »
Lin Chen · Christopher Harshaw · Hamed Hassani · Amin Karbasi -
2018 Oral: Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity »
Lin Chen · Christopher Harshaw · Hamed Hassani · Amin Karbasi -
2018 Oral: Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings »
Aryan Mokhtari · Hamed Hassani · Amin Karbasi -
2018 Poster: Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints »
Ehsan Kazemi · Morteza Zadimoghaddam · Amin Karbasi -
2018 Poster: Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy? »
Lin Chen · Moran Feldman · 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 -
2018 Oral: Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy? »
Lin Chen · Moran Feldman · Amin Karbasi -
2017 Poster: Guarantees for Greedy Maximization of Non-submodular Functions with Applications »
Yatao Bian · Joachim Buhmann · Andreas Krause · Sebastian Tschiatschek -
2017 Poster: Differentially Private Submodular Maximization: Data Summarization in Disguise »
Marko Mitrovic · Mark Bun · Andreas Krause · Amin Karbasi -
2017 Poster: Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten" »
Baharan Mirzasoleiman · Amin Karbasi · Andreas Krause -
2017 Talk: Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten" »
Baharan Mirzasoleiman · Amin Karbasi · Andreas Krause -
2017 Talk: Guarantees for Greedy Maximization of Non-submodular Functions with Applications »
Yatao Bian · Joachim Buhmann · Andreas Krause · Sebastian Tschiatschek -
2017 Talk: Differentially Private Submodular Maximization: Data Summarization in Disguise »
Marko Mitrovic · Mark Bun · Andreas Krause · Amin Karbasi -
2017 Poster: Distributed and Provably Good Seedings for k-Means in Constant Rounds »
Olivier Bachem · Mario Lucic · Andreas Krause -
2017 Poster: Uniform Deviation Bounds for k-Means Clustering »
Olivier Bachem · Mario Lucic · Hamed Hassani · Andreas Krause -
2017 Talk: Uniform Deviation Bounds for k-Means Clustering »
Olivier Bachem · Mario Lucic · Hamed Hassani · Andreas Krause -
2017 Talk: Distributed and Provably Good Seedings for k-Means in Constant Rounds »
Olivier Bachem · Mario Lucic · Andreas Krause