Grainger College of Engineering, All Events

View Full Calendar

The (Surprising) Rate Optimality of Greedy Algorithms for Large-Scale Ranking and Selection

Event Type
Seminar/Symposium
Sponsor
Industrial and Enterprise Systems Engineering, Dept. Head office
Location
Room 303, Transportation Building (*NOTE: Location change*)
Date
Jan 27, 2023   2:00 - 3:00 pm   *Please note: New time change*
Speaker
Professor L. Jeff Hong
Contact
BuuLinh Quach
E-Mail
bquach@illinois.edu
Phone
217-265-5220
Views
176
Originating Calendar
ISE Seminar Calendar

*Presentation will be recorded.

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 and multi-armed bandit. An ideal large-scale R&S algorithm 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 algorithm 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 algorithm 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 algorithm that harnesses the rate optimality of the greedy algorithm, we propose the explore-first greedy (EFG) algorithm that adds an exploration phase to the greedy algorithm. We show that the new algorithm is simple, rate optimal and consistent. The numerical study demonstrates that the EFG algorithm performs well compared to the existing algorithms.

This is a joint work with Zaile Li (Fudan University) and Weiwei Fan (Tongji University).

Bio: 

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.

link for robots only