The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
Open accessAbstract
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 norm in a reproducing kernel Hilbert space. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze an intuitive Gaussian process upper confidence bound (GP-UCB) algorithm, and bound its cumulative regret in terms of maximal in- formation 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Gaussian Processes for Machine Learning
Rasmussen, C. E., & Williams, C. K. I. (2005) · doi:10.7551/mitpress/3206.001.0001 · Cited by 11,705
Efficient Global Optimization of Expensive Black-Box Functions
Jones, D. R., Schonlau, M., & Welch, W. J. (1998) · Journal of Global Optimization · doi:10.1023/a:1008306431147 · Cited by 8,070
Finite-time Analysis of the Multiarmed Bandit Problem
Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002) · Machine Learning · doi:10.1023/a:1013689704352 · Cited by 6,033
Spline Models for Observational Data.
Muller, H.-G., & Wahba, G. (1991) · Journal of the American Statistical Association · doi:10.2307/2290434 · Cited by 4,928
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Spline Models for Observational Data
Wahba, G. (1990) · doi:10.1137/1.9781611970128 · Cited by 4,184
Bandit Based Monte-Carlo Planning
Kocsis, L., & Szepesvári, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11871842_29 · Cited by 2,855
Stein, M. L. (1999) · Springer Series in Statistics · doi:10.1007/978-1-4612-1494-6 · Cited by 2,348
Some aspects of the sequential design of experiments
Robbins, H. (1952) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1952-09620-8 · Cited by 2,184
Cited by
Practical Bayesian Optimization of Machine Learning Algorithms
Snoek, J., Larochelle, H., & Adams, R. P. (2012) · arXiv · doi:10.48550/arxiv.1206.2944 · Cited by 6,691
Taking the Human Out of the Loop: A Review of Bayesian Optimization
Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., & de Freitas, N. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2494218 · Cited by 6,049
(2011) · Cited by 3,939
Brochu, E., Cora, V. M., & de Freitas, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.2599 · Cited by 2,011
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986276 · Cited by 1,404
Auto-WEKA: combined selection and hyperparameter optimization of classification algorithms
Thornton, C., Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487629 · Cited by 1,359
Closed-loop optimization of fast-charging protocols for batteries with machine learning
Attia, P. M., Grover, A., Jin, N., Severson, K. A., Markov, T. M., Liao, Y.-H., Chen, M. H., Cheong, B., Perkins, N., Yang, Z., et al. (2020) · Nature · doi:10.1038/s41586-020-1994-5 · Cited by 1,180
Lattimore, T., & Szepesvári, C. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108571401 · Cited by 976
Hyperparameter optimization: Foundations, algorithms, best practices, and open challenges
Bischl, B., Binder, M., Lang, M., Pielok, T., Richter, J., Coors, S., Thomas, J., Ullmann, T., Becker, M., Boulesteix, A., et al. (2023) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1484 · Cited by 930
Introduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Gaussian Processes for Data-Efficient Learning in Robotics and Control
Deisenroth, M. P., Fox, D., & Rasmussen, C. E. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.218 · Cited by 659
Auto-WEKA: Automatic Model Selection and Hyperparameter Optimization in WEKA
Kotthoff, L., Thornton, C., Hoos, H. H., Hutter, F., & Leyton-Brown, K. (2019) · The Springer Series on Challenges in Machine Learning · doi:10.1007/978-3-030-05318-5_4 · Cited by 650
Scalable Bayesian Optimization Using Deep Neural Networks
Snoek, J., Rippel, O., Swersky, K., Kiros, R., Satish, N., Sundaram, N., Patwary, M. A., Prabhat, & Adams, R. P. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.05700 · Cited by 613
Google Vizier: A Service for Black-Box Optimization
Golovin, D., Solnik, B., Moitra, S., Kochanski, G., Karro, J., & Sculley, D. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098043 · Cited by 571
On-the-fly closed-loop materials discovery via Bayesian active learning
Kusne, A. G., Yu, H., Wu, C., Zhang, H., Hattrick-Simpers, J., DeCost, B., Sarker, S., Oses, C., Toher, C., Curtarolo, S., et al. (2020) · Nature Communications · doi:10.1038/s41467-020-19597-w · Cited by 542
Learning to Optimize via Posterior Sampling
Russo, D., & Van Roy, B. (2014) · Mathematics of Operations Research · doi:10.1287/moor.2014.0650 · Cited by 493
Recent Advances in Bayesian Optimization
Wang, X., Jin, Y., Schmitt, S., & Olhofer, M. (2023) · ACM Computing Surveys · doi:10.1145/3582078 · Cited by 477
Simulation optimization: a review of algorithms and applications
Amaran, S., Sahinidis, N. V., Sharda, B., & Bury, S. J. (2016) · Annals of Operations Research · doi:10.1007/s10479-015-2019-x · Cited by 467
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Golovin, D., & Krause, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1003.3967 · Cited by 461
Self-citationConvergence rates of efficient global optimization algorithms
Bull, A. D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1101.3501 · Cited by 446
Liu, H., Ong, Y.-S., & Cai, J. (2018) · Structural and Multidisciplinary Optimization · doi:10.1007/s00158-017-1739-8 · Cited by 444
Entropy search for information-efficient global optimization
Hennig, P., & Schuler, C. J. (2012) · Journal of Machine Learning Research · doi:10.5555/2188385.2343701 · Cited by 443
Predictive Entropy Search for Efficient Global Optimization of Black-box Functions
Hernández-Lobato, J. M., Hoffman, M. W., & Ghahramani, Z. (2014) · arXiv · doi:10.48550/arxiv.1406.2541 · Cited by 407
Bayesian Optimization in a Billion Dimensions via Random Embeddings
Wang, Z., Hutter, F., Zoghi, M., Matheson, D., & De Feitas, N. (2016) · Journal of Artificial Intelligence Research · doi:10.1613/jair.4806 · Cited by 390
A Tutorial on Thompson Sampling
Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834710 · Cited by 380
Phoenics: A Bayesian Optimizer for Chemistry
Häse, F., Roch, L. M., Kreisbeck, C., & Aspuru-Guzik, A. (2018) · ACS Central Science · doi:10.1021/acscentsci.8b00307 · Cited by 379
Navigating the protein fitness landscape with Gaussian processes
Romero, P. A., Krause, A., & Arnold, F. H. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1215251110 · Cited by 360
Self-citationMahler, J., Pokorny, F. T., Hou, B., Roderick, M., Laskey, M., Aubry, M., Kohlhoff, K., Kroger, T., Kuffner, J., & Goldberg, K. (2016) · 2016 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2016.7487342 · Cited by 359
A benchmark of kriging-based infill criteria for noisy optimization
Picheny, V., Wagner, T., & Ginsbourger, D. (2013) · Structural and Multidisciplinary Optimization · doi:10.1007/s00158-013-0919-4 · Cited by 325
Learning-Based Model Predictive Control for Safe Exploration
Koller, T., Berkenkamp, F., Turchetta, M., & Krause, A. (2018) · 2018 IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619572 · Cited by 318
Self-citationBayesian Optimization with Unknown Constraints
Gelbart, M. A., Snoek, J., & Adams, R. P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1403.5607 · Cited by 299
Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics
Berkenkamp, F., Krause, A., & Schoellig, A. P. (2023) · Machine Learning · doi:10.1007/s10994-021-06019-1 · Cited by 286
Self-citationCalandra, R., Seyfarth, A., Peters, J., & Deisenroth, M. P. (2016) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-015-9463-9 · Cited by 280
Rare Event Estimation Using Polynomial-Chaos Kriging
Schöbi, R., Sudret, B., & Marelli, S. (2017) · ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering · doi:10.1061/ajrua6.0000870 · Cited by 278
Deconstructing the human algorithms for exploration
Gershman, S. J. (2018) · Cognition · doi:10.1016/j.cognition.2017.12.014 · Cited by 267
Safe controller optimization for quadrotors with Gaussian processes
Berkenkamp, F., Schoellig, A. P., & Krause, A. (2016) · 2016 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2016.7487170 · Cited by 264
Self-citationComputational mechanisms of curiosity and goal-directed exploration
Schwartenbeck, P., Passecker, J., Hauser, T. U., FitzGerald, T. H., Kronbichler, M., & Friston, K. J. (2019) · eLife · doi:10.7554/elife.41703 · Cited by 254
SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization
Lindauer, M., Eggensperger, K., Feurer, M., Biedenkapp, A., Deng, D., Benjamins, C., Ruhopf, T., Sass, R., & Hutter, F. (2021) · arXiv · doi:10.48550/arxiv.2109.09831 · Cited by 195
Perrone, V., Donini, M., Zafar, M. B., Schmucker, R., Kenthapadi, K., & Archambeau, C. (2021) · Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society · doi:10.1145/3461702.3462629 · Cited by 66
Bayesian optimization for maximum power point tracking in photovoltaic power plants
Abdelrahman, H., Berkenkamp, F., Poland, J., & Krause, A. (2016) · 2016 European Control Conference (ECC) · doi:10.1109/ecc.2016.7810598 · Cited by 45
Self-citationMulti-objective Bayesian optimization using Pareto-frontier entropy
Suzuki, S., Takeno, S., Tamura, T., Shitara, K., & Karasuyama, M. (2019) · arXiv · doi:10.48550/arxiv.1906.00127 · Cited by 40
PHYRE: A New Benchmark for Physical Reasoning
Bakhtin, A., van der Maaten, L., Johnson, J., Gustafson, L., & Girshick, R. (2019) · arXiv · doi:10.48550/arxiv.1908.05656 · Cited by 37
Learning Periodic Tasks from Human Demonstrations
Yang, J., Zhang, J., Settle, C., Rai, A., Antonova, R., & Bohg, J. (2022) · 2022 International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra46639.2022.9812402 · Cited by 21
What's to Know? Uncertainty as a Guide to Asking Goal-Oriented Questions
Abbasnejad, E., Wu, Q., Shi, Q., & van den Hengel, A. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00428 · Cited by 16
Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism
Li, Z., Yang, Z., & Wang, M. (2023) · arXiv · doi:10.48550/arxiv.2305.18438 · Cited by 19
(2021) · arXiv (Cornell University) · Cited by 11
Koyner, J. L., Martin, J., Carey, K. A., Caskey, J., Edelson, D. P., Mayampurath, A., Dligach, D., Afshar, M., & Churpek, M. M. (2025) · Clinical Journal of the American Society of Nephrology · doi:10.2215/cjn.0000000695 · Cited by 10
Järvenpää, M., Vehtari, A., & Marttinen, P. (2019) · arXiv · doi:10.48550/arxiv.1910.06121 · Cited by 8
Uncertainty Quantification for Bayesian Optimization
Tuo, R., & Wang, W. (2020) · arXiv · doi:10.48550/arxiv.2002.01569 · Cited by 2
Metadata
- Authors
- Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. W.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2012-05
- Volume
- 58
- Issue
- 5
- Pages
- 3250-3265
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2951665052
- Cited by
- 1,850
- References
- 30
- FWCI
- 72.82
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.