On the Convergence Rates of Expected Improvement Methods

• 成果类型: Article
• 署名作者: Ryzhov, Ilya O.
• 署名单位: University System of Maryland; University of Maryland College Park
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1494
• 发表日期: 2016
• 页码: 1515-1528
• 关键词: EFFICIENT GLOBAL OPTIMIZATION; simulation budget allocation; selection

摘要

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.