Timezone: »
Submodular maximization problems appear in several areas of machine learning and data science, as many useful modelling concepts such as diversity and coverage satisfy this natural diminishing returns property. Because the data defining these functions, as well as the decisions made with the computed solutions, are subject to statistical noise and randomness, it is arguably necessary to go beyond computing a single approximate optimum and quantify its inherent uncertainty. To this end, we define a rich class of probabilistic models associated with constrained submodular maximization problems. These capture log-submodular dependencies of arbitrary order between the variables, but also satisfy hard combinatorial constraints. Namely, the variables are assumed to take on one of — possibly exponentially many — set of states, which form the bases of a matroid. To perform inference in these models we design novel variational inference algorithms, which carefully leverage the combinatorial and probabilistic properties of these objects. In addition to providing completely tractable and well-understood variational approximations, our approach results in the minimization of a convex upper bound on the log-partition function. The bound can be efficiently evaluated using greedy algorithms and optimized using any first-order method. Moreover, for the case of facility location and weighted coverage functions, we prove the first constant factor guarantee in this setting — an efficiently certifiable e/(e-1) approximation of the log-partition function. Finally, we empirically demonstrate the effectiveness of our approach on several instances.
Author Information
Josip Djolonga (Google Brain)
Stefanie Jegelka (MIT)
Stefanie Jegelka is an X-Consortium Career Development Assistant Professor in the Department of EECS at MIT. She is a member of the Computer Science and AI Lab (CSAIL), the Center for Statistics and an affiliate of the Institute for Data, Systems and Society and the Operations Research Center. Before joining MIT, she was a postdoctoral researcher at UC Berkeley, and obtained her PhD from ETH Zurich and the Max Planck Institute for Intelligent Systems. Stefanie has received a Sloan Research Fellowship, an NSF CAREER Award, a DARPA Young Faculty Award, the German Pattern Recognition Award and a Best Paper Award at the International Conference for Machine Learning (ICML). Her research interests span the theory and practice of algorithmic machine learning.
Andreas Krause (ETH Zurich)
More from the Same Authors
-
2020 Poster: Adaptive Sampling for Stochastic Risk-Averse Learning »
Sebastian Curi · Kfir Y. Levy · Stefanie Jegelka · Andreas Krause -
2020 Poster: Contextual Games: Multi-Agent Learning with Side Information »
Pier Giuseppe Sessa · Ilija Bogunovic · Andreas Krause · Maryam Kamgarpour -
2020 Poster: Testing Determinantal Point Processes »
Khashayar Gatmiry · Maryam Aliakbarpour · Stefanie Jegelka -
2020 Spotlight: Testing Determinantal Point Processes »
Khashayar Gatmiry · Maryam Aliakbarpour · Stefanie Jegelka -
2020 Poster: Coresets via Bilevel Optimization for Continual Learning and Streaming »
Zalán Borsos · Mojmir Mutny · Andreas Krause -
2020 Poster: IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method »
Yossi Arjevani · Joan Bruna · Bugra Can · Mert Gurbuzbalaban · Stefanie Jegelka · Hongzhou Lin -
2020 Poster: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Daniel Tarlow · Andreas Krause · Chris J. Maddison -
2020 Spotlight: IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method »
Yossi Arjevani · Joan Bruna · Bugra Can · Mert Gurbuzbalaban · Stefanie Jegelka · Hongzhou Lin -
2020 Oral: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Daniel Tarlow · Andreas Krause · Chris J. Maddison -
2020 Poster: Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning »
Sebastian Curi · Felix Berkenkamp · Andreas Krause -
2020 Poster: Learning to Play Sequential Games versus Unknown Opponents »
Pier Giuseppe Sessa · Ilija Bogunovic · Maryam Kamgarpour · Andreas Krause -
2020 Spotlight: Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning »
Sebastian Curi · Felix Berkenkamp · Andreas Krause -
2020 Poster: Safe Reinforcement Learning via Curriculum Induction »
Matteo Turchetta · Andrey Kolobov · Shital Shah · Andreas Krause · Alekh Agarwal -
2020 Spotlight: Safe Reinforcement Learning via Curriculum Induction »
Matteo Turchetta · Andrey Kolobov · Shital Shah · Andreas Krause · Alekh Agarwal -
2019 Poster: Distributionally Robust Optimization and Generalization in Kernel Methods »
Matthew Staib · Stefanie Jegelka -
2019 Poster: Flexible Modeling of Diversity with Strongly Log-Concave Distributions »
Joshua Robinson · Suvrit Sra · Stefanie Jegelka -
2019 Poster: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2019 Spotlight: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2019 Poster: Stochastic Bandits with Context Distributions »
Johannes Kirschner · Andreas Krause -
2019 Poster: A Domain Agnostic Measure for Monitoring and Evaluating GANs »
Paulina Grnarova · Kfir Y. Levy · Aurelien Lucchi · Nathanael Perraudin · Ian Goodfellow · Thomas Hofmann · Andreas Krause -
2019 Poster: No-Regret Learning in Unknown Games with Correlated Payoffs »
Pier Giuseppe Sessa · Ilija Bogunovic · Maryam Kamgarpour · Andreas Krause -
2019 Poster: Teaching Multiple Concepts to a Forgetful Learner »
Anette Hunziker · Yuxin Chen · Oisin Mac Aodha · Manuel Gomez Rodriguez · Andreas Krause · Pietro Perona · Yisong Yue · Adish Singla -
2019 Poster: Adaptive Sequence Submodularity »
Marko Mitrovic · Ehsan Kazemi · Moran Feldman · Andreas Krause · Amin Karbasi -
2019 Poster: Safe Exploration for Interactive Machine Learning »
Matteo Turchetta · Felix Berkenkamp · Andreas Krause -
2019 Poster: Practical and Consistent Estimation of f-Divergences »
Paul Rubenstein · Olivier Bousquet · Josip Djolonga · Carlos Riquelme · Ilya Tolstikhin -
2018 Poster: ResNet with one-neuron hidden layers is a Universal Approximator »
Hongzhou Lin · Stefanie Jegelka -
2018 Spotlight: ResNet with one-neuron hidden layers is a Universal Approximator »
Hongzhou Lin · Stefanie Jegelka -
2018 Poster: Adversarially Robust Optimization with Gaussian Processes »
Ilija Bogunovic · Jonathan Scarlett · Stefanie Jegelka · Volkan Cevher -
2018 Poster: Efficient High Dimensional Bayesian Optimization with Additivity and Quadrature Fourier Features »
Mojmir Mutny · Andreas Krause -
2018 Spotlight: Adversarially Robust Optimization with Gaussian Processes »
Ilija Bogunovic · Jonathan Scarlett · Stefanie Jegelka · Volkan Cevher -
2018 Spotlight: Efficient High Dimensional Bayesian Optimization with Additivity and Quadrature Fourier Features »
Mojmir Mutny · Andreas Krause -
2018 Poster: Fairness Behind a Veil of Ignorance: A Welfare Analysis for Automated Decision Making »
Hoda Heidari · Claudio Ferrari · Krishna Gummadi · Andreas Krause -
2018 Poster: Exponentiated Strongly Rayleigh Distributions »
Zelda Mariet · Suvrit Sra · Stefanie Jegelka -
2018 Tutorial: Negative Dependence, Stable Polynomials, and All That »
Suvrit Sra · Stefanie Jegelka -
2017 Workshop: Discrete Structures in Machine Learning »
Yaron Singer · Jeff A Bilmes · Andreas Krause · Stefanie Jegelka · Amin Karbasi -
2017 Poster: Interactive Submodular Bandit »
Lin Chen · Andreas Krause · Amin Karbasi -
2017 Poster: Safe Model-based Reinforcement Learning with Stability Guarantees »
Felix Berkenkamp · Matteo Turchetta · Angela Schoellig · Andreas Krause -
2017 Poster: Differentiable Learning of Submodular Functions »
Josip Djolonga · Andreas Krause -
2017 Poster: Parallel Streaming Wasserstein Barycenters »
Matthew Staib · Sebastian Claici · Justin M Solomon · Stefanie Jegelka -
2017 Spotlight: Differentiable Learning of Submodular Functions »
Josip Djolonga · Andreas Krause -
2017 Poster: Non-monotone Continuous DR-submodular Maximization: Structure and Algorithms »
Yatao Bian · Kfir Levy · Andreas Krause · Joachim M Buhmann -
2017 Poster: Polynomial time algorithms for dual volume sampling »
Chengtao Li · Stefanie Jegelka · Suvrit Sra -
2017 Poster: Stochastic Submodular Maximization: The Case of Coverage Functions »
Mohammad Karimi · Mario Lucic · Hamed Hassani · Andreas Krause -
2016 Workshop: Nonconvex Optimization for Machine Learning: Theory and Practice »
Hossein Mobahi · Anima Anandkumar · Percy Liang · Stefanie Jegelka · Anna Choromanska -
2016 Poster: Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling »
Chengtao Li · Suvrit Sra · Stefanie Jegelka -
2016 Poster: Variational Inference in Mixed Probabilistic Submodular Models »
Josip Djolonga · Sebastian Tschiatschek · Andreas Krause -
2016 Poster: Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation »
Ilija Bogunovic · Jonathan Scarlett · Andreas Krause · Volkan Cevher -
2016 Poster: Cooperative Graphical Models »
Josip Djolonga · Stefanie Jegelka · Sebastian Tschiatschek · Andreas Krause -
2016 Poster: Fast and Provably Good Seedings for k-Means »
Olivier Bachem · Mario Lucic · Hamed Hassani · Andreas Krause -
2016 Oral: Fast and Provably Good Seedings for k-Means »
Olivier Bachem · Mario Lucic · Hamed Hassani · Andreas Krause -
2016 Poster: Safe Exploration in Finite Markov Decision Processes with Gaussian Processes »
Matteo Turchetta · Felix Berkenkamp · Andreas Krause -
2015 Poster: Distributed Submodular Cover: Succinctly Summarizing Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Ashwinkumar Badanidiyuru · Andreas Krause -
2015 Poster: Sampling from Probabilistic Submodular Models »
Alkis Gotovos · Hamed Hassani · Andreas Krause -
2015 Spotlight: Distributed Submodular Cover: Succinctly Summarizing Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Ashwinkumar Badanidiyuru · Andreas Krause -
2015 Oral: Sampling from Probabilistic Submodular Models »
Alkis Gotovos · Hamed Hassani · Andreas Krause -
2014 Workshop: NIPS’14 Workshop on Crowdsourcing and Machine Learning »
David Parkes · Denny Zhou · Chien-Ju Ho · Nihar Bhadresh Shah · Adish Singla · Jared Heyman · Edwin Simpson · Andreas Krause · Rafael Frongillo · Jennifer Wortman Vaughan · Panagiotis Papadimitriou · Damien Peters -
2014 Workshop: Discrete Optimization in Machine Learning »
Jeffrey A Bilmes · Andreas Krause · Stefanie Jegelka · S Thomas McCormick · Sebastian Nowozin · Yaron Singer · Dhruv Batra · Volkan Cevher -
2014 Poster: Efficient Sampling for Learning Sparse Additive Models in High Dimensions »
Hemant Tyagi · Bernd Gärtner · Andreas Krause -
2014 Poster: From MAP to Marginals: Variational Inference in Bayesian Submodular Models »
Josip Djolonga · Andreas Krause -
2014 Poster: Parallel Double Greedy Submodular Maximization »
Xinghao Pan · Stefanie Jegelka · Joseph Gonzalez · Joseph K Bradley · Michael Jordan -
2014 Poster: Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets »
Adarsh Prasad · Stefanie Jegelka · Dhruv Batra -
2014 Poster: Efficient Partial Monitoring with Prior Information »
Hastagiri P Vanchinathan · Gábor Bartók · Andreas Krause -
2014 Spotlight: Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets »
Adarsh Prasad · Stefanie Jegelka · Dhruv Batra -
2014 Poster: On the Convergence Rate of Decomposable Submodular Function Minimization »
Robert Nishihara · Stefanie Jegelka · Michael Jordan -
2014 Poster: Weakly-supervised Discovery of Visual Pattern Configurations »
Hyun Oh Song · Yong Jae Lee · Stefanie Jegelka · Trevor Darrell -
2013 Workshop: Machine Learning for Sustainability »
Edwin Bonilla · Thomas Dietterich · Theodoros Damoulas · Andreas Krause · Daniel Sheldon · Iadine Chades · J. Zico Kolter · Bistra Dilkina · Carla Gomes · Hugo P Simao -
2013 Workshop: Bayesian Optimization in Theory and Practice »
Matthew Hoffman · Jasper Snoek · Nando de Freitas · Michael A Osborne · Ryan Adams · Sebastien Bubeck · Philipp Hennig · Remi Munos · Andreas Krause -
2013 Workshop: Discrete Optimization in Machine Learning: Connecting Theory and Practice »
Stefanie Jegelka · Andreas Krause · Pradeep Ravikumar · Kazuo Murota · Jeffrey A Bilmes · Yisong Yue · Michael Jordan -
2013 Poster: High-Dimensional Gaussian Process Bandits »
Josip Djolonga · Andreas Krause · Volkan Cevher -
2013 Poster: Optimistic Concurrency Control for Distributed Unsupervised Learning »
Xinghao Pan · Joseph Gonzalez · Stefanie Jegelka · Tamara Broderick · Michael Jordan -
2013 Poster: Distributed Submodular Maximization: Identifying Representative Elements in Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Rik Sarkar · Andreas Krause -
2013 Poster: Reflection methods for user-friendly submodular optimization »
Stefanie Jegelka · Francis Bach · Suvrit Sra -
2013 Poster: Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions »
Rishabh K Iyer · Stefanie Jegelka · Jeffrey A Bilmes -
2012 Workshop: Discrete Optimization in Machine Learning (DISCML): Structure and Scalability »
Stefanie Jegelka · Andreas Krause · Jeffrey A Bilmes · Pradeep Ravikumar -
2011 Workshop: Discrete Optimization in Machine Learning (DISCML): Uncertainty, Generalization and Feedback »
Andreas Krause · Pradeep Ravikumar · Stefanie S Jegelka · Jeffrey A Bilmes -
2011 Oral: Scalable Training of Mixture Models via Coresets »
Dan Feldman · Matthew Faulkner · Andreas Krause -
2011 Poster: Fast approximate submodular minimization »
Stefanie Jegelka · Hui Lin · Jeffrey A Bilmes -
2011 Poster: Scalable Training of Mixture Models via Coresets »
Dan Feldman · Matthew Faulkner · Andreas Krause -
2011 Poster: Contextual Gaussian Process Bandit Optimization »
Andreas Krause · Cheng Soon Ong -
2011 Poster: Crowdclustering »
Ryan G Gomes · Peter Welinder · Andreas Krause · Pietro Perona -
2010 Workshop: Discrete Optimization in Machine Learning: Structures, Algorithms and Applications »
Andreas Krause · Pradeep Ravikumar · Jeffrey A Bilmes · Stefanie Jegelka -
2010 Spotlight: Efficient Minimization of Decomposable Submodular Functions »
Peter G Stobbe · Andreas Krause -
2010 Poster: Discriminative Clustering by Regularized Information Maximization »
Ryan G Gomes · Andreas Krause · Pietro Perona -
2010 Poster: Efficient Minimization of Decomposable Submodular Functions »
Peter G Stobbe · Andreas Krause -
2010 Poster: Near-Optimal Bayesian Active Learning with Noisy Observations »
Daniel Golovin · Andreas Krause · Debajyoti Ray -
2009 Workshop: Discrete Optimization in Machine Learning: Submodularity, Polyhedra and Sparsity »
Andreas Krause · Pradeep Ravikumar · Jeffrey A Bilmes -
2009 Poster: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause -
2009 Spotlight: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause -
2007 Spotlight: Selecting Observations against Adversarial Objectives »
Andreas Krause · H. Brendan McMahan · Carlos Guestrin · Anupam Gupta -
2007 Poster: Selecting Observations against Adversarial Objectives »
Andreas Krause · H. Brendan McMahan · Carlos Guestrin · Anupam Gupta