Lower Bounds on the Noiseless Worst-Case Complexity of Efficient Global Optimization

Wenjie Xu, Yuning Jiang (), Emilio T. Maddalena and Colin N. Jones
Additional contact information
Wenjie Xu: École Polytechnique Fédérale de Lausanne (EPFL)
Yuning Jiang: École Polytechnique Fédérale de Lausanne (EPFL)
Emilio T. Maddalena: École Polytechnique Fédérale de Lausanne (EPFL)
Colin N. Jones: École Polytechnique Fédérale de Lausanne (EPFL)

Journal of Optimization Theory and Applications, 2024, vol. 201, issue 2, No 4, 583-608

Abstract: Abstract 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érn kernel with a large smoothness parameter $$\nu $$ ν . This matching is up to a replacement of d/2 by d and a logarithmic term $$\log \frac{R}{\epsilon }$$ log R ϵ , where d is the dimension of input space, R is the upper bound for the norm of the unknown black-box function, and $$\epsilon $$ ϵ is the desired accuracy. That is to say, our lower bound is nearly optimal for these kernels.

Keywords: Efficient global optimization; Worst-case complexity; Reproducing Kernel Hilbert space (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-024-02399-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:201:y:2024:i:2:d:10.1007_s10957-024-02399-1

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-024-02399-1

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().