Prof. Andreas Krause receives ICML Test of Time Award

The ICML is next to the Conference on Neural Information Processing Systems (NeurIPS) one of the two most important conferences on machine learning. The prize is awarded annually to one of the papers published 10 years ago. The paper, published at ICML 2010, was recognized in particular for the depth and breadth of the impact it has had over the past ten years.

Andreas Krause, Niranjan Srinivas (10x Genomics), Matthias Seeger (Amazon) and Sham Kakade (University of Washington) authored the award-winning paper.

About the paper

Should we go to our favorite restaurant, or try a new one? This question is an instance of the so-called "exploration-exploitation" dilemma and arises in numerous applications, where one needs to optimize an unknown, noisy function that is expensive to evaluate. Examples range from recommender systems to automatic hyperparameter tuning and neural architecture search to learning optimal control strategies for robots. 

One important approach to this problem is Bayesian optimisation: A Bayesian model – typically a Gaussian Process (GP) – is used to model the unknown function. Its predictive uncertainty can then be used to not only make predictions about alternatives that have not been explored yet, but also reason about the informativeness of an experiment. While this approach is very flexible and has been used in various applications, prior to the ICML paper, Bayesian optimisation has been primarily heuristic in nature. The explore-exploit tradeoff has also been extensively studied in the multi-armed bandit (MAB) paradigm. The resulting approaches are associated with an elegant theory, but have been more limited in modeling flexibility.

As a central contribution, the ICML paper established a novel link between these two previously largely separate bodies of literature. It proposes a practical algorithm, GP-UCB, which builds on classical ideas from multi-armed bandits, in particular, the "optimism in the face of uncertainty" principle, and extends them to Gaussian process models. GP-UCB exploits carefully calibrated nonparametric confidence bounds for Gaussian processes, lifting techniques from linear bandits to infinite dimensional Hilbert spaces. It enjoys rigorous bounds on its regret, implying the first convergence rates for Bayesian optimisation. These bounds come in terms of a natural "maximum information gain" quantity developed and analysed in the paper, which is intimately connected to ideas from optimal experimental design.

The established connection between these fields has enabled subsequent work to naturally translate ideas between them. This has enabled the development of principled algorithms for, e.g., more efficiently solving many related optimisation tasks by taking into account context; planning batches of experiments to be carried out in parallel; incorporating safety constraints and many more. These algorithms have in turn have been deployed in a wide range of practical applications.

Prof. Krause and his co-authors will be awarded at a virtual award presentation, which is scheduled for Monday, 13 July 2020. 

About Prof. Andreas Krause

Andreas Krause is a professor of computer science at ETH Zurich and leads the Learning & Adaptive Systems group. Furthermore, he serves as academic co-director of the Swiss Data Science Center. His research focuses on machine learning, data mining, optimization, learning systems, sensing, and network analysis. He received his doctoral thesis in computer science from Carnegie Mellon University (2008) and his diploma in computer science and mathematics from the Technical University of Munich, Germany (2004). After that he was an assistant professor of computer science at Caltech. Prof. Krause is a Microsoft Research Faculty Fellow and a Kavli Frontiers Fellow of the US National Academy of Sciences. He served as program co-chair for ICML 2018 and is regularly serving as area chair or senior program committee member for ICML, NeurIPS, AAAI and IJCAI, and as action editor for the Journal of Machine Learning Research.