Timezone: »
Submodular functions have been studied extensively in machine learning and data mining. In particular, the optimization of submodular functions over the integer lattice (integer submodular functions) has recently attracted much interest, because this domain relates naturally to many practical problem settings, such as multilabel graph cut, budget allocation and revenue maximization with discrete assignments. In contrast, the use of these functions for probabilistic modeling has received surprisingly little attention so far. In this work, we firstly propose the Generalized Multilinear Extension, a continuous DR-submodular extension for integer submodular functions. We study central properties of this extension and formulate a new probabilistic model which is defined through integer submodular functions. Then, we introduce a block-coordinate ascent algorithm to perform approximate inference for this class of models and finally, we demonstrate its effectiveness and viability on several real-world social connection graph datasets with integer submodular objectives.
Author Information
Aytunc Sahin (ETH Zurich)
Yatao Bian (Tencent AI Lab)
Joachim Buhmann (ETH Zurich)
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.
More from the Same Authors
-
2022 : Recovering Stochastic Dynamics via Gaussian Schrödinger Bridges »
Ya-Ping Hsieh · Charlotte Bunne · Marco Cuturi · Andreas Krause -
2022 : Invariance Principle Meets Out-of-Distribution Generalization on Graphs »
Yongqiang Chen · Yonggang Zhang · Yatao Bian · Han Yang · Kaili MA · Binghui Xie · Tongliang Liu · Bo Han · James Cheng -
2022 : Recovering Stochastic Dynamics via Gaussian Schrödinger Bridges »
Charlotte Bunne · Ya-Ping Hsieh · Marco Cuturi · Andreas Krause -
2022 : Pareto Invariant Risk Minimization »
Yongqiang Chen · Kaiwen Zhou · Yatao Bian · Binghui Xie · Kaili MA · Yonggang Zhang · Han Yang · Bo Han · James Cheng -
2023 : Anytime Model Selection in Linear Bandits »
Parnian Kassraie · Aldo Pacchiano · Nicolas Emmenegger · Andreas Krause -
2023 : Towards Understanding Feature Learning in Out-of-Distribution Generalization »
Yongqiang Chen · Wei Huang · Kaiwen Zhou · Yatao Bian · Bo Han · James Cheng -
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 : 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 Panel: ICML Education Outreach Panel »
Andreas Krause · Barbara Engelhardt · Emma Brunskill · Kyunghyun Cho -
2022 : DrugOOD: Out-of-Distribution (OOD) Dataset Curator and Benchmark for AI-aided Drug Discovery -- A Focus on Affinity Prediction Problems with Noise Annotations »
Yatao Bian -
2022 : Hypergraph Convolutional Networks via Equivalence Between Hypergraphs and Undirected Graphs »
Jiying Zhang · fuyang li · Xi Xiao · Tingyang Xu · Yu Rong · Junzhou Huang · Yatao Bian -
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 Spotlight: Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning »
Max Paulus · Giulia Zarpellon · Andreas Krause · Laurent Charlin · Chris Maddison -
2022 Poster: $p$-Laplacian Based Graph Neural Networks »
Guoji Fu · Peilin Zhao · Yatao Bian -
2022 Poster: Interactively Learning Preference Constraints in Linear Bandits »
David Lindner · Sebastian Tschiatschek · Katja Hofmann · Andreas Krause -
2022 Spotlight: $p$-Laplacian Based Graph Neural Networks »
Guoji Fu · Peilin Zhao · Yatao Bian -
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: 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 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 : 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: 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 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: Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces »
Johannes Kirschner · Mojmir Mutny · Nicole Hiller · Rasmus Ischebeck · Andreas Krause -
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: 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 Oral: Learning Generative Models across Incomparable Spaces »
Charlotte Bunne · David Alvarez-Melis · Andreas Krause · Stefanie Jegelka -
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: A Distributed Second-Order Algorithm You Can Trust »
Celestine Mendler-Dünner · Aurelien Lucchi · Matilde Gargiani · Yatao Bian · Thomas Hofmann · Martin Jaggi -
2018 Oral: A Distributed Second-Order Algorithm You Can Trust »
Celestine Mendler-Dünner · Aurelien Lucchi · Matilde Gargiani · Yatao Bian · Thomas Hofmann · Martin Jaggi -
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 Poster: Probabilistic Submodular Maximization in Sub-Linear Time »
Serban A Stan · Morteza Zadimoghaddam · Andreas Krause · Amin Karbasi -
2017 Talk: Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten" »
Baharan Mirzasoleiman · Amin Karbasi · Andreas Krause -
2017 Talk: Probabilistic Submodular Maximization in Sub-Linear Time »
Serban A Stan · Morteza Zadimoghaddam · Andreas Krause · Amin Karbasi -
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