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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Brochu, E., Cora, V. M., & de Freitas, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.2599 · Cited by 2,011
Interpolation of Spatial Data: Some Theory for Kriging
Rathbun, S. L., & Stein, M. L. (2000) · Journal of the American Statistical Association · doi:10.2307/2669494 · Cited by 1,916
Bayesian Experimental Design: A Review
Chaloner, K., & Verdinelli, I. (1995) · Statistical Science · doi:10.1214/ss/1177009939 · Cited by 1,839
Using confidence bounds for exploitation-exploration trade-offs
Auer, P. L. (2003) · Journal of Machine Learning Research · doi:10.5555/944919.944941 · Cited by 1,229
Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models
Huang, D., Allen, T. T., Notz, W. I., & Zeng, N. (2006) · Journal of Global Optimization · doi:10.1007/s10898-005-2454-3 · Cited by 625
On Tail Probabilities for Martingales
Freedman, D. A. (1975) · The Annals of Probability · doi:10.1214/aop/1176996452 · Cited by 618
(2008) · ScholarlyCommons (University of Pennsylvania) · Cited by 581
Bayesian Approach to Global Optimization: Theory and Applications
Mockus, J. (1989) · Mathematics and Its Applications · doi:10.1007/978-94-009-0909-0 · Cited by 406
Multi-armed bandits in metric spaces
Kleinberg, R., Slivkins, A., & Upfal, E. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374475 · Cited by 396
Near-optimal Nonmyopic Value of Information in Graphical Models
Krause, A., & Guestrin, C. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.1394 · Cited by 349
Self-citationThe Bayesian approach to global optimization
Mockus, J. (2005) · Lecture Notes in Control and Information Sciences · doi:10.1007/bfb0006170 · Cited by 283
Automatic gait optimization with Gaussian process regression
Lizotte, D. J., Wang, T., Bowling, M., & Schuurmans, D. (2007) · Cited by 237
Vazquez, E., & Bect, J. (2010) · Journal of Statistical Planning and Inference · doi:10.1016/j.jspi.2010.04.018 · Cited by 183
The Price of Bandit Information for Online Optimization
Dani, V., Kakade, S. M., & Hayes, T. P. (2007) · ScholarlyCommons (University of Pennsylvania) · Cited by 161
Self-citationOn the Eigenspectrum of the Gram Matrix and the Generalization Error of Kernel-PCA
Shawe-Taylor, J. S., Williams, C. K., Cristianini, N., & Kandola, J. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850052 · Cited by 147
Online Optimization in X-Armed Bandits
Bubeck, S., Stoltz, G., Szepesvári, C., & Munos, R. (2008) · Cited by 132
Information Consistency of Nonparametric Gaussian Process Methods
Seeger, M., Kakade, S. M., & Foster, D. P. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.915707 · Cited by 81
Self-citationHandling Advertisements of Unknown Quality in Search Advertising
Pandey, S., & Olston, C. (2007) · The MIT Press eBooks · doi:10.7551/mitpress/7503.003.0138 · Cited by 65
Regret Bounds for Gaussian Process Bandit Problems
Grünewälder, S., Berlin, T. U., Shawe-Taylor, J. S., Audibert, J.-Y., & Paris-est, U. ́. (2010) · HAL · Cited by 64
Convergence properties of the expected improvement algorithmPreprint
Vázquez, E., & Bect, J. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0712.3744 · Cited by 10
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
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.