Organizers of the 37th International Conference on Machine Learning (ICML) have announced this year’s Test of Time award, which goes to a team from the California Institute of Technology, University of Pennsylvania, Saarland University. The ICML Test of Time award recognizes an ICML paper from ten years ago that has proven influential, with significant impacts in the field, “including both research and practice.”
Test of Time Award:
Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design


Authors: Niranjan Srinivas, Andreas Krause, Sham Kakade, Matthias Seeger
Institutions: California Institute of Technology, University of Pennsylvania, Saarland University
Abstract: Many applications require optimizing an unknown, noisy function that is expensive to evaluate. We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low RKHS norm. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze GP-UCB, an intuitive upper-confidence based algorithm, and bound its cumulative regret in terms of maximal information gain, establishing a novel connection between GP optimization and experimental design. Moreover, by bounding the latter in terms of operator spectra, we obtain explicit sublinear regret bounds for many commonly used covariance functions. In some important cases, our bounds have surprisingly weak dependence on the dimensionality. In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches.
ICML comments: This paper brought together the fields of Bayesian optimization, bandits and experimental design by analyzing Gaussian process bandit optimization, giving a novel approach to derive finite-sample regret bounds in terms of a mutual information gain quantity. This paper has had profound impact over the past ten years, including the method itself, the proof techniques used, and the practical results. These have all enriched our community by sparking creativity in myriad subsequent works, ranging from theory to practice.
The recipients of the Test of Time award will give a plenary talk on Monday July 13:
- Live talk & Q/A @ 11:00-12:00 UTC (4:00 PDT, 7:00 EDT, 13:00 CEST, 16:30 IST, 19:00 CST)
- Recorded talk & Live Q/A @ 21:00-22:00 UTC (14:00 PDT, 17:00 EDT, 23:00 CEST; Tuesday July 14, 2:30 IST, 5:00 CST)
ICML 2020 will be a virtual conference running from July 12 to 18, and the Best Paper awards will be announced at the presentation of the Test of Time award during the conference. Synced will update readers when additional information becomes available.
Journalist: Fangyu Cai | Editor: Michael Sarazen
Pingback: [N] ICML 2020 Announces Test of Time Award – tensor.io