On the Convergence Rates of Expected Improvement Methods

Ilya O. Ryzhov ()
Additional contact information
Ilya O. Ryzhov: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742

Operations Research, 2016, vol. 64, issue 6, 1515-1528

Abstract: We consider a ranking and selection problem with independent normal observations, and we analyze the asymptotic sampling rates of expected improvement (EI) methods in this setting. Such methods often perform well in practice, but a tractable analysis of their convergence rates is difficult because of the nonlinearity and nonconvexity of the EI calculations. We present new results indicating that, for known sampling noise, variants of EI produce asymptotic simulation allocations that are essentially identical to those chosen by the optimal computing budget allocation (OCBA) methodology, which is known to yield near-optimal asymptotic performance in ranking and selection. This is the first general equivalence result between EI and OCBA, and it provides insight into the good practical performance of EI. We also derive the limiting allocation for EI under unknown sampling variance.

Keywords: optimal learning; ranking and selection; expected improvement; optimal computing budget allocation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1494 (application/pdf)

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:inm:oropre:v:64:y:2016:i:6:p:1515-1528

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().