Timezone: »

 
Poster
Improving the Expected Improvement Algorithm
Chao Qin · Diego Klabjan · Daniel Russo

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #27
in Posters Wed »

The expected improvement (EI) algorithm is a popular strategy for information collection in optimization under uncertainty. The algorithm is widely known to be too greedy, but nevertheless enjoys wide use due to its simplicity and ability to handle uncertainty and noise in a coherent decision theoretic framework. To provide rigorous insight into EI, we study its properties in a simple setting of Bayesian optimization where the domain consists of a finite grid of points. This is the so-called best-arm identification problem, where the goal is to allocate measurement effort wisely to confidently identify the best arm using a small number of measurements. In this framework, one can show formally that EI is far from optimal. To overcome this shortcoming, we introduce a simple modification of the expected improvement algorithm. Surprisingly, this simple change results in an algorithm that is asymptotically optimal for Gaussian best-arm identification problems, and provably outperforms standard EI by an order of magnitude.

Keywords: Bandit Algorithms · Theory
[ Paper] 

Author Information

Chao Qin (Columbia University)

I am a PhD student in Decision, Risk, and Operations at Columbia Business School. My research interests lie in statistical machine learning and sequential decision-making under uncertainty, including multi-armed bandits, (deep) reinforcement learning, Bayesian optimization, and online learning.

Diego Klabjan (Northwestern University)

Diego Klabjan is a professor at Northwestern University, Department of Industrial Engineering and Management Sciences. He is also Founding Director, Master of Science in Analytics. After obtaining his doctorate from the School of Industrial and Systems Engineering of the Georgia Institute of Technology in 1999 in Algorithms, Combinatorics, and Optimization, in the same year he joined the University of Illinois at Urbana-Champaign. In 2007 he became an associate professor at Northwestern and in 2012 he was promoted to a full professor. His research is focused on machine learning, deep learning and analytics with concentration in finance, transportation, sport, and bioinformatics. Professor Klabjan has led projects with large companies such as Intel, Baxter, Allstate, AbbVie, FedEx Express, General Motors, United Continental, and many others, and he is also assisting numerous start-ups with their analytics needs. He is also a founder of Opex Analytics LLC.

Daniel Russo (Columbia University)

More from the Same Authors