Timezone: »
The goal of this paper is to characterize Gaussian-Process optimization in the setting where the function domain is large relative to the number of admissible function evaluations, i.e., where it is impossible to find the global optimum. We provide upper bounds on the suboptimality (Bayesian simple regret) of the solution found by optimization strategies that are closely related to the widely used expected improvement (EI) and upper confidence bound (UCB) algorithms. These regret bounds illuminate the relationship between the number of evaluations, the domain size (i.e. cardinality of finite domains / Lipschitz constant of the covariance function in continuous domains), and the optimality of the retrieved function value.In particular, we show that even when the number of evaluations is far too small to find the global optimum, we can find nontrivial function values (e.g. values that achieve a certain ratio with the optimal value).
Author Information
Manuel Wuethrich (Max Planck Institute for Intelligent Systems)
Bernhard Schölkopf (MPI for Intelligent Systems, Tübingen)
Andreas Krause (ETH Zurich)
More from the Same Authors
-
2021 Spotlight: Iterative Teaching by Label Synthesis »
Weiyang Liu · Zhen Liu · Hanchen Wang · Liam Paull · Bernhard Schölkopf · Adrian Weller -
2021 Spotlight: DiBS: Differentiable Bayesian Structure Learning »
Lars Lorch · Jonas Rothfuss · Bernhard Schölkopf · Andreas Krause -
2021 : Transferring Dexterous Manipulation from GPU Simulation to a Remote Real-World Trifinger »
Arthur Allshire · Mayank Mittal · Varun Lodaya · Viktor Makoviychuk · Denys Makoviichuk · Felix Widmaier · Manuel Wuethrich · Stefan Bauer · Ankur Handa · Animesh Garg -
2021 : Towards Safe Global Optimality in Robot Learning with GoSafe »
Bhavya Sukhija · Matteo Turchetta · Andreas Krause · Sebastian Trimpe · Dominik Baumann -
2021 : DiBS: Differentiable Bayesian Structure Learning »
Lars Lorch · Jonas Rothfuss · Bernhard Schölkopf · Andreas Krause -
2021 : Learning Single-Cell Perturbation Responses using Neural Optimal Transport »
Charlotte Bunne · Stefan Stark · Gabriele Gut · Andreas Krause · Gunnar Rätsch · Lucas Pelkmans · Kjong Lehmann -
2022 : Active Bayesian Causal Inference »
Christian Toth · Lars Lorch · Christian Knoll · Andreas Krause · Franz Pernkopf · Robert Peharz · Julius von Kügelgen -
2022 : A Causal Framework to Quantify Robustness of Mathematical Reasoning with Language Models »
Alessandro Stolfo · Zhijing Jin · Kumar Shridhar · Bernhard Schölkopf · Mrinmaya Sachan -
2022 : Active Bayesian Causal inference »
Christian Toth · Lars Lorch · Christian Knoll · Andreas Krause · Franz Pernkopf · Robert Peharz · Julius von Kügelgen -
2022 : Amortized Inference for Causal Structure Learning »
Lars Lorch · Scott Sussex · Jonas Rothfuss · Andreas Krause · Bernhard Schölkopf -
2022 : MARS: Meta-learning as score matching in the function space »
Kruno Lehman · Jonas Rothfuss · Andreas Krause -
2022 : Neural All-Pairs Shortest Path for Reinforcement Learning »
Cristina Pinneri · Georg Martius · Andreas Krause -
2023 Poster: Optimistic Active Exploration of Dynamical Systems »
Bhavya · Lenart Treven · Cansu Sancaktar · Sebastian Blaes · Stelian Coros · Andreas Krause -
2023 Poster: Riemannian stochastic optimization methods avoid strict saddle points »
Ya-Ping Hsieh · Mohammad Reza Karimi Jaghargh · Andreas Krause · Panayotis Mertikopoulos -
2023 Poster: Learning To Dive In Branch And Bound »
Max Paulus · Andreas Krause -
2023 Poster: Implicit Manifold Gaussian Process Regression »
Bernardo Fichera · Viacheslav Borovitskiy · Andreas Krause · Aude G Billard -
2023 Poster: A Dynamical System View of Langevin-Based Non-Convex Sampling »
Mohammad Reza Karimi Jaghargh · Ya-Ping Hsieh · Andreas Krause -
2023 Poster: Anytime Model Selection in Linear Bandits »
Parnian Kassraie · Aldo Pacchiano · Nicolas Emmenegger · Andreas Krause -
2023 Poster: Stochastic Approximation Algorithms for Systems of Interacting Particles »
Mohammad Reza Karimi Jaghargh · Ya-Ping Hsieh · Andreas Krause -
2023 Poster: Efficient Exploration in Continuous-time Model-based Reinforcement Learning »
Lenart Treven · Jonas Hübotter · Bhavya · Florian Dorfler · Andreas Krause -
2023 Poster: Contextual Stochastic Bilevel Optimization »
Yifan Hu · Jie Wang · Yao Xie · Andreas Krause · Daniel Kuhn -
2023 Poster: Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning »
Pier Giuseppe Sessa · Pierre Laforgue · Nicolò Cesa-Bianchi · Andreas Krause -
2023 Poster: Likelihood Ratio Confidence Sets for Sequential Decision Making »
Nicolas Emmenegger · Mojmir Mutny · Andreas Krause -
2023 Workshop: Adaptive Experimental Design and Active Learning in the Real World »
Willie Neiswanger · Mojmir Mutny · Ilija Bogunovic · Ava Soleimany · Zi Wang · Stefano Ermon · Andreas Krause -
2022 Spotlight: Lightning Talks 1A-3 »
Kimia Noorbakhsh · Ronan Perry · Qi Lyu · Jiawei Jiang · Christian Toth · Olivier Jeunen · Xin Liu · Yuan Cheng · Lei Li · Manuel Rodriguez · Julius von Kügelgen · Lars Lorch · Nicolas Donati · Lukas Burkhalter · Xiao Fu · Zhongdao Wang · Songtao Feng · Ciarán Gilligan-Lee · Rishabh Mehrotra · Fangcheng Fu · Jing Yang · Bernhard Schölkopf · Ya-Li Li · Christian Knoll · Maks Ovsjanikov · Andreas Krause · Shengjin Wang · Hong Zhang · Mounia Lalmas · Bolin Ding · Bo Du · Yingbin Liang · Franz Pernkopf · Robert Peharz · Anwar Hithnawi · Julius von Kügelgen · Bo Li · Ce Zhang -
2022 Spotlight: Active Bayesian Causal Inference »
Christian Toth · Lars Lorch · Christian Knoll · Andreas Krause · Franz Pernkopf · Robert Peharz · Julius von Kügelgen -
2022 Poster: Supervised Training of Conditional Monge Maps »
Charlotte Bunne · Andreas Krause · Marco Cuturi -
2022 Poster: Near-Optimal Multi-Agent Learning for Safe Coverage Control »
Manish Prajapat · Matteo Turchetta · Melanie Zeilinger · Andreas Krause -
2022 Poster: Amortized Inference for Causal Structure Learning »
Lars Lorch · Scott Sussex · Jonas Rothfuss · Andreas Krause · Bernhard Schölkopf -
2022 Poster: Movement Penalized Bayesian Optimization with Application to Wind Energy Systems »
Shyam Sundhar Ramesh · Pier Giuseppe Sessa · Andreas Krause · Ilija Bogunovic -
2022 Poster: Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spaces »
Mojmir Mutny · Andreas Krause -
2022 Poster: Graph Neural Network Bandits »
Parnian Kassraie · Andreas Krause · Ilija Bogunovic -
2022 Poster: Active Bayesian Causal Inference »
Christian Toth · Lars Lorch · Christian Knoll · Andreas Krause · Franz Pernkopf · Robert Peharz · Julius von Kügelgen -
2022 Poster: A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits »
Ilija Bogunovic · Zihan Li · Andreas Krause · Jonathan Scarlett -
2022 Poster: Active Exploration for Inverse Reinforcement Learning »
David Lindner · Andreas Krause · Giorgia Ramponi -
2022 Poster: Learning Long-Term Crop Management Strategies with CyclesGym »
Matteo Turchetta · Luca Corinzia · Scott Sussex · Amanda Burton · Juan Herrera · Ioannis Athanasiadis · Joachim M Buhmann · Andreas Krause -
2021 : Boxhead: A Dataset for Learning Hierarchical Representations »
Yukun Chen · Andrea Dittadi · Frederik Träuble · Stefan Bauer · Bernhard Schölkopf -
2021 : Meta-Learning Reliable Priors in the Function Space »
Jonas Rothfuss · Dominique Heyn · jinfan Chen · Andreas Krause -
2021 Poster: Learning Graph Models for Retrosynthesis Prediction »
Vignesh Ram Somnath · Charlotte Bunne · Connor Coley · Andreas Krause · Regina Barzilay -
2021 Poster: Risk-averse Heteroscedastic Bayesian Optimization »
Anastasia Makarova · Ilnura Usmanova · Ilija Bogunovic · Andreas Krause -
2021 Poster: Hierarchical Skills for Efficient Exploration »
Jonas Gehring · Gabriel Synnaeve · Andreas Krause · Nicolas Usunier -
2021 Poster: Dynamic Inference with Neural Interpreters »
Nasim Rahaman · Muhammad Waleed Gondal · Shruti Joshi · Peter Gehler · Yoshua Bengio · Francesco Locatello · Bernhard Schölkopf -
2021 Poster: Multi-Scale Representation Learning on Proteins »
Vignesh Ram Somnath · Charlotte Bunne · Andreas Krause -
2021 Poster: Causal Influence Detection for Improving Efficiency in Reinforcement Learning »
Maximilian Seitzer · Bernhard Schölkopf · Georg Martius -
2021 Poster: Independent mechanism analysis, a new concept? »
Luigi Gresele · Julius von Kügelgen · Vincent Stimper · Bernhard Schölkopf · Michel Besserve -
2021 Poster: Learning Stable Deep Dynamics Models for Partially Observed or Delayed Dynamical Systems »
Andreas Schlaginhaufen · Philippe Wenk · Andreas Krause · Florian Dorfler -
2021 Poster: Information Directed Reward Learning for Reinforcement Learning »
David Lindner · Matteo Turchetta · Sebastian Tschiatschek · Kamil Ciosek · Andreas Krause -
2021 Poster: Robust Generalization despite Distribution Shift via Minimum Discriminating Information »
Tobias Sutter · Andreas Krause · Daniel Kuhn -
2021 Poster: Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning »
Scott Sussex · Caroline Uhler · Andreas Krause -
2021 : Real Robot Challenge II + Q&A »
Stefan Bauer · Joel Akpo · Manuel Wuethrich · Nan Rosemary Ke · Anirudh Goyal · Thomas Steinbrenner · Felix Widmaier · Annika Buchholz · Bernhard Schölkopf · Dieter Büchler · Ludovic Righetti · Franziska Meier -
2021 Poster: Iterative Teaching by Label Synthesis »
Weiyang Liu · Zhen Liu · Hanchen Wang · Liam Paull · Bernhard Schölkopf · Adrian Weller -
2021 Poster: Distributional Gradient Matching for Learning Uncertain Neural Dynamics Models »
Lenart Treven · Philippe Wenk · Florian Dorfler · Andreas Krause -
2021 Poster: Meta-Learning Reliable Priors in the Function Space »
Jonas Rothfuss · Dominique Heyn · jinfan Chen · Andreas Krause -
2021 Poster: The Inductive Bias of Quantum Kernels »
Jonas Kübler · Simon Buchholz · Bernhard Schölkopf -
2021 Poster: Backward-Compatible Prediction Updates: A Probabilistic Approach »
Frederik Träuble · Julius von Kügelgen · Matthäus Kleindessner · Francesco Locatello · Bernhard Schölkopf · Peter Gehler -
2021 Poster: Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style »
Julius von Kügelgen · Yash Sharma · Luigi Gresele · Wieland Brendel · Bernhard Schölkopf · Michel Besserve · Francesco Locatello -
2021 Poster: Misspecified Gaussian Process Bandit Optimization »
Ilija Bogunovic · Andreas Krause -
2021 Poster: DiBS: Differentiable Bayesian Structure Learning »
Lars Lorch · Jonas Rothfuss · Bernhard Schölkopf · Andreas Krause -
2020 : Invited speaker: Adaptive Sampling for Stochastic Risk-Averse Learning, Andreas Krause »
Andreas Krause -
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: Coresets via Bilevel Optimization for Continual Learning and Streaming »
Zalan Borsos · Mojmir Mutny · Andreas Krause -
2020 Poster: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Danny Tarlow · Andreas Krause · Chris Maddison -
2020 Oral: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Danny Tarlow · Andreas Krause · Chris 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 : Bernhard Schölkopf »
Bernhard Schölkopf -
2019 Poster: On the Transfer of Inductive Bias from Simulation to the Real World: a New Disentanglement Dataset »
Muhammad Waleed Gondal · Manuel Wuethrich · Djordje Miladinovic · Francesco Locatello · Martin Breidt · Valentin Volchkov · Joel Akpo · Olivier Bachem · Bernhard Schölkopf · Stefan Bauer -
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 -
2018 : Learning Independent Mechanisms »
Bernhard Schölkopf -
2018 Poster: Provable Variational Inference for Constrained Log-Submodular Models »
Josip Djolonga · Stefanie Jegelka · Andreas Krause -
2018 Poster: Efficient High Dimensional Bayesian Optimization with Additivity and Quadrature Fourier Features »
Mojmir Mutny · Andreas Krause -
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 -
2017 : Invited talk: Towards Safe Bayesian Optimization »
Andreas Krause -
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 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: Stochastic Submodular Maximization: The Case of Coverage Functions »
Mohammad Karimi · Mario Lucic · Hamed Hassani · Andreas Krause -
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 : Safe Exploration for Bayesian Optimization »
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: Efficient Partial Monitoring with Prior Information »
Hastagiri P Vanchinathan · Gábor Bartók · Andreas Krause -
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: Distributed Submodular Maximization: Identifying Representative Elements in Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Rik Sarkar · Andreas Krause -
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: 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