The (Surprising) Rate Optimality of Greedy Procedures for Large-Scale Ranking and Selection
Speakers
L. Jeff Hong
Professor at Fudan University,
Jeff Hong received his bachelor’s and Ph.D. degrees from Tsinghua University and Northwestern University, respectively. He is currently with Fudan University, holding the positions of Fudan Distinguished Professor, Hongyi Chair Professor, Chair of Department of Management Science in School of Management, and Associate Dean of School of Data Science. He was Chair Professor of Management Sciences at City University of Hong Kong, and Professor of Industrial Engineering and Logistics Management at the Hong Kong University of Science and Technology. Prof. Hong’s research interests include stochastic simulation, stochastic optimization, risk management and supply chain management. He is currently the Simulation Area Editor of Operations Research, an Associate Editor of Management Science and ACM Transactions on Modeling and Computer Simulation, and he was the President of INFORMS Simulation Society from 2020 to 2022.
| Date: |
| Wednesday, 14 December 2022 |
| Time: |
| 10:30 am - 11:30 am |
| Venue: |
|
NUS Business School Mochtar Riady Building BIZ1 0509 15 Kent Ridge Drive Singapore 119245 (Map) |
Abstract
Large-scale ranking-and-selection (R&S), which aims to select the best alternative with the largest mean performance from a finite set of alternatives, has emerged as an important research topic in simulation optimization. An ideal large-scale R&S procedure should be rate optimal, i.e., the total sample size required to deliver an asymptotically non-zero probability of correct selection (PCS) grows linearly in the number of alternatives. We discover that the naïve greedy procedure that keeps sampling the alternative with the largest running sample mean performs surprisingly well and appears rate optimal in solving large-scale R&S problems. We develop a boundary-crossing perspective and prove that the greedy procedure is indeed rate optimal, and we further show that the obtained PCS lower bound is tight asymptotically for the slippage configuration with a common variance. To develop a practically competitive procedure that harnesses the rate optimality of the greedy procedure, we propose the explore-first greedy (EFG) procedure that adds an exploration phase to the greedy procedure. We show that the new procedure is simple, rate optimal and consistent. The numerical study demonstrates that the EFG procedure performs well compared to the existing carefully designed rate-optimal R&S procedures. This is a joint work with Zaile Li (Fudan University) and Weiwei Fan (Tongji University).
For General Enquiries:
| WONG Cecilia/TAN Dorothy | |
| 6516 6225/6516 3067 | website |