{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T16:48:07Z","timestamp":1745513287020,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021 175627"],"award-info":[{"award-number":["200021 175627"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012496","name":"nccr - on the move","doi-asserted-by":"publisher","award":["51NF40_180545"],"award-info":[{"award-number":["51NF40_180545"]}],"id":[{"id":"10.13039\/100012496","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Efficient global optimization is a widely used method for optimizing expensive black-box functions. In this paper, we study the worst-case oracle complexity of the efficient global optimization problem. In contrast to existing kernel-specific results, we derive a unified lower bound for the oracle complexity of efficient global optimization in terms of the metric entropy of a ball in its corresponding reproducing kernel Hilbert space. Moreover, we show that this lower bound nearly matches the upper bound attained by non-adaptive search algorithms, for the commonly used squared exponential kernel and the Mat\u00e9rn kernel with a large smoothness parameter <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\nu $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03bd<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This matching is up to a replacement of <jats:italic>d<\/jats:italic>\/2 by <jats:italic>d<\/jats:italic> and a logarithmic term <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\log \\frac{R}{\\epsilon }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mi>R<\/mml:mi>\n                      <mml:mi>\u03f5<\/mml:mi>\n                    <\/mml:mfrac>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>d<\/jats:italic> is the dimension of input space, <jats:italic>R<\/jats:italic> is the upper bound for the norm of the unknown black-box function, and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\epsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03f5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the desired accuracy. That is to say, our lower bound is nearly optimal for these kernels.\n<\/jats:p>","DOI":"10.1007\/s10957-024-02399-1","type":"journal-article","created":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T20:02:34Z","timestamp":1710187354000},"page":"583-608","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds on the Noiseless Worst-Case Complexity of Efficient Global Optimization"],"prefix":"10.1007","volume":"201","author":[{"given":"Wenjie","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7145-0995","authenticated-orcid":false,"given":"Yuning","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emilio T.","family":"Maddalena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Colin N.","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,11]]},"reference":[{"issue":"1","key":"2399_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-018-0139-4","volume":"11","author":"JA Andersson","year":"2019","unstructured":"Andersson, J.A., Gillis, J., Horn, G., Rawlings, J.B., Diehl, M.: CasADi: a software framework for nonlinear optimization and optimal control. Math. Program. Comput. 11(1), 1\u201336 (2019)","journal-title":"Math. Program. Comput."},{"key":"2399_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, S., Calandra, R., Xiao, T., Levine, S., Tomlin, C.J.: Goal-driven dynamics learning via Bayesian optimization. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 5168\u20135173. IEEE (2017)","DOI":"10.1109\/CDC.2017.8264425"},{"key":"2399_CR3","unstructured":"Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. J. Mach. Learn. Res. 13(2) (2012)"},{"key":"2399_CR4","unstructured":"Bull, A.D.: Convergence rates of efficient global optimization algorithms. J. Mach. Learn. Res. 12(10) (2011)"},{"key":"2399_CR5","unstructured":"Cai, X., Scarlett, J.: On lower bounds for standard and robust Gaussian process bandit optimization. In: International Conference on Machine Learning, pp. 1216\u20131226. PMLR (2021)"},{"issue":"1","key":"2399_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-01-00923-5","volume":"39","author":"F Cucker","year":"2002","unstructured":"Cucker, F., Smale, S.: On the mathematical foundations of learning. Bull. Am. Math. Soc. 39(1), 1\u201349 (2002)","journal-title":"Bull. Am. Math. Soc."},{"key":"2399_CR7","unstructured":"De\u00a0Freitas, N., Smola, A.J., Zoghi, M.: Exponential regret bounds for Gaussian process bandits with deterministic observations. In: Proceedings of the 29th International Conference on Machine Learning, pp. 955\u2013962 (2012)"},{"key":"2399_CR8","doi-asserted-by":"crossref","unstructured":"Edmunds, D.E., Triebel, H.: Function Spaces, Entropy Numbers, Differential Operators, vol. 120. Cambridge University Press (1996)","DOI":"10.1017\/CBO9780511662201"},{"issue":"2","key":"2399_CR9","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1137\/090775026","volume":"49","author":"PI Frazier","year":"2011","unstructured":"Frazier, P.I., Powell, W.B.: Consistency of sequential Bayesian sampling policies. SIAM J. Control. Optim. 49(2), 712\u2013731 (2011)","journal-title":"SIAM J. Control. Optim."},{"key":"2399_CR10","doi-asserted-by":"crossref","unstructured":"Frazier, P.I., Wang, J.: Bayesian optimization for materials design. In: Information Science for Materials Discovery and Design, pp. 45\u201375. Springer (2016)","DOI":"10.1007\/978-3-319-23871-5_3"},{"key":"2399_CR11","unstructured":"GPy: GPy: a Gaussian process framework in python. http:\/\/github.com\/SheffieldML\/GPy (since 2012)"},{"key":"2399_CR12","unstructured":"Gr\u00fcnew\u00e4lder, S., Audibert, J.Y., Opper, M., Shawe-Taylor, J.: Regret bounds for Gaussian process bandit problems. In: Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pp. 273\u2013280. JMLR Workshop and Conference Proceedings (2010)"},{"issue":"4","key":"2399_CR13","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1023\/A:1008306431147","volume":"13","author":"DR Jones","year":"1998","unstructured":"Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4), 455\u2013492 (1998)","journal-title":"J. Global Optim."},{"key":"2399_CR14","doi-asserted-by":"crossref","unstructured":"Khemchandani, R., Jayadeva, Chandra, S.: Optimal kernel selection in twin support vector machines. Optim. Lett. 3, 77\u201388 (2009)","DOI":"10.1007\/s11590-008-0092-7"},{"key":"2399_CR15","doi-asserted-by":"crossref","unstructured":"Kim, S.J., Magnani, A., Boyd, S.: Optimal kernel selection in kernel fisher discriminant analysis. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 465\u2013472 (2006)","DOI":"10.1145\/1143844.1143903"},{"issue":"2","key":"2399_CR16","first-page":"3","volume":"14","author":"AN Kolmogorov","year":"1959","unstructured":"Kolmogorov, A.N., Tikhomirov, V.M.: $$\\varepsilon $$-entropy and $$\\varepsilon $$-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk 14(2), 3\u201386 (1959)","journal-title":"Uspekhi Matematicheskikh Nauk"},{"issue":"1","key":"2399_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1023\/A:1008294716304","volume":"10","author":"M Locatelli","year":"1997","unstructured":"Locatelli, M.: Bayesian algorithms for one-dimensional global optimization. J. Global Optim. 10(1), 57\u201376 (1997)","journal-title":"J. Global Optim."},{"issue":"6","key":"2399_CR18","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1090\/S0002-9904-1966-11586-0","volume":"72","author":"G Lorentz","year":"1966","unstructured":"Lorentz, G.: Metric entropy and approximation. Bull. Am. Math. Soc. 72(6), 903\u2013937 (1966)","journal-title":"Bull. Am. Math. Soc."},{"key":"2399_CR19","doi-asserted-by":"crossref","unstructured":"Maddalena, E.T., Scharnhorst, P., Jones, C.N.: Deterministic error bounds for kernel-based learning techniques under bounded noise. Automatica 134, 109896 (2021)","DOI":"10.1016\/j.automatica.2021.109896"},{"key":"2399_CR20","unstructured":"Mairal, J., Vert, J.P.: Machine learning with kernel methods. Lecture Notes 10 (2018)"},{"issue":"3","key":"2399_CR21","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1287\/ijoc.1100.0417","volume":"23","author":"DM Negoescu","year":"2011","unstructured":"Negoescu, D.M., Frazier, P.I., Powell, W.B.: The knowledge-gradient algorithm for sequencing experiments in drug discovery. INFORMS J. Comput. 23(3), 346\u2013363 (2011)","journal-title":"INFORMS J. Comput."},{"key":"2399_CR22","unstructured":"Nemirovskij, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience (1983)"},{"key":"2399_CR23","unstructured":"Novak, E., Wo\u017aniakowski, H.: Tractability of Multivariate Problems: Standard information for functionals, vol.\u00a02. European Mathematical Society (2008)"},{"key":"2399_CR24","unstructured":"Raskutti, G., J Wainwright, M., Yu, B.: Minimax-optimal rates for sparse additive models over kernel classes via convex programming. J. Mach. Learn. Res. 13(2) (2012)"},{"key":"2399_CR25","unstructured":"Ray\u00a0Chowdhury, S., Gopalan, A.: Bayesian optimization under heavy-tailed payoffs. Adv. Neural Inf. Process. Syst. 32 (2019)"},{"issue":"1","key":"2399_CR26","first-page":"2442","volume":"17","author":"D Russo","year":"2016","unstructured":"Russo, D., Van Roy, B.: An information-theoretic analysis of Thompson sampling. J. Mach. Learn. Res. 17(1), 2442\u20132471 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"2399_CR27","unstructured":"Scarlett, J.: Tight regret bounds for Bayesian optimization in one dimension. In: International Conference on Machine Learning, pp. 4500\u20134508. PMLR (2018)"},{"key":"2399_CR28","unstructured":"Scarlett, J., Bogunovic, I., Cevher, V.: Lower bounds on regret for noisy Gaussian process bandit optimization. In: Conference on Learning Theory, pp. 1723\u20131742. PMLR (2017)"},{"issue":"1","key":"2399_CR29","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/JPROC.2015.2494218","volume":"104","author":"B Shahriari","year":"2015","unstructured":"Shahriari, B., Swersky, K., Wang, Z., Adams, R.P., De Freitas, N.: Taking the human out of the loop: a review of Bayesian optimization. Proc. IEEE 104(1), 148\u2013175 (2015)","journal-title":"Proc. IEEE"},{"key":"2399_CR30","unstructured":"Snoek, J., Rippel, O., Swersky, K., Kiros, R., Satish, N., Sundaram, N., Patwary, M., Prabhat, M., Adams, R.: Scalable Bayesian optimization using deep neural networks. In: International Conference on Machine Learning, pp. 2171\u20132180. PMLR (2015)"},{"issue":"5","key":"2399_CR31","doi-asserted-by":"publisher","first-page":"3250","DOI":"10.1109\/TIT.2011.2182033","volume":"58","author":"N Srinivas","year":"2012","unstructured":"Srinivas, N., Krause, A., Kakade, S.M., Seeger, M.W.: Information-theoretic regret bounds for Gaussian process optimization in the bandit setting. IEEE Trans. Inf. Theory 58(5), 3250\u20133265 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2399_CR32","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.jat.2016.11.006","volume":"215","author":"I Steinwart","year":"2017","unstructured":"Steinwart, I.: A short note on the comparison of interpolation widths, entropy numbers, and Kolmogorov widths. J. Approx. Theory 215, 13\u201327 (2017)","journal-title":"J. Approx. Theory"},{"key":"2399_CR33","unstructured":"Vakili, S., Bouziani, N., Jalali, S., Bernacchia, A., Shiu, D.s.: Optimal order simple regret for Gaussian process bandits. Adv. Neural Inf. Process. Syst. 34 (2021)"},{"issue":"11","key":"2399_CR34","doi-asserted-by":"publisher","first-page":"3088","DOI":"10.1016\/j.jspi.2010.04.018","volume":"140","author":"E Vazquez","year":"2010","unstructured":"Vazquez, E., Bect, J.: Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. J. Stat. Plan. Inference 140(11), 3088\u20133095 (2010)","journal-title":"J. Stat. Plan. Inference"},{"issue":"1","key":"2399_CR35","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25\u201357 (2006)","journal-title":"Math. Program."},{"key":"2399_CR36","doi-asserted-by":"crossref","unstructured":"Wahba, G.: Spline Models for Observational Data. SIAM (1990)","DOI":"10.1137\/1.9781611970128"},{"key":"2399_CR37","unstructured":"Wang, Z., de\u00a0Freitas, N.: Theoretical analysis of Bayesian optimisation with unknown Gaussian process hyper-parameters. arXiv preprint arXiv:1406.7758 (2014)"},{"key":"2399_CR38","doi-asserted-by":"crossref","unstructured":"Wendland, H.: Scattered Data Approximation, vol.\u00a017. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511617539"},{"key":"2399_CR39","unstructured":"Wu, Y.: Lecture notes on information-theoretic methods for high-dimensional statistics. Lecture Notes for ECE598YW (UIUC) 16 (2017)"},{"key":"2399_CR40","doi-asserted-by":"crossref","unstructured":"Xu, W., Jones, C.N., Svetozarevic, B., Laughman, C.R., Chakrabarty, A.: VABO: Violation-Aware Bayesian Optimization for closed-loop control performance optimization with unmodeled constraints. arXiv preprint arXiv:2110.07479 (2021)","DOI":"10.23919\/ACC53348.2022.9867298"},{"issue":"3","key":"2399_CR41","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1006\/jcom.2002.0635","volume":"18","author":"DX Zhou","year":"2002","unstructured":"Zhou, D.X.: The covering number in learning theory. J. Complex. 18(3), 739\u2013767 (2002)","journal-title":"J. Complex."},{"issue":"7","key":"2399_CR42","doi-asserted-by":"publisher","first-page":"1743","DOI":"10.1109\/TIT.2003.813564","volume":"49","author":"DX Zhou","year":"2003","unstructured":"Zhou, D.X.: Capacity of reproducing kernel spaces in learning theory. IEEE Trans. Inf. Theory 49(7), 1743\u20131752 (2003)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02399-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-024-02399-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02399-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,9]],"date-time":"2024-05-09T15:14:00Z","timestamp":1715267640000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-024-02399-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,11]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["2399"],"URL":"https:\/\/doi.org\/10.1007\/s10957-024-02399-1","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2024,3,11]]},"assertion":[{"value":"27 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}