Topic: Speeding Up Paulson’s Procedure for Large-Scale Problem Using Parallel Computing

Speaker: Prof. Jun LUO, Shanghai Jiao Tong University

Time: 10:30 am - 11:30 am, November 11, 2020

Venue：Room 207, Cheng Dao Building

Abstract：

With the rapid development of computing technology, using parallel computing to solve large-scale ranking-and-selection (R&S) problems has emerged as an important research topic. However, direct implementation of traditionally fully sequential procedures in parallel computing environments may encounter various problems. First, the scheme of all-pairwise comparisons, which is commonly used in fully sequential procedures, has an O(k^2) computational complexity, and significantly slows down the selection process. Second, traditional fully sequential procedures require frequent communication and coordination among processors, which are also not efficient in parallel computing environments. In this talk, we propose three modifications on one classical fully sequential procedure, Paulson’s procedure, to speed up its selection process in parallel computing environments. First, we show that if no common random numbers (CRNs) are used, we can reduce the computational complexity of the all-pairwise comparisons at each round to O(k). Second, by batching different alternatives, we show that we can reduce the communication cost among the processors, leading the procedure to achieve better performance. Third, to boost the procedure’s final-stage selection, when the number of surviving alternatives is less than the number of processors, we suggest to sample all surviving alternatives to the maximal number of observations they should take. We show that after these modifications, the procedure remains statistically valid, and is more efficient compared with existing parallel procedures in the literature. This is a joint work with Ying Zhong, Shaoxuan Liu and Jeff Hong.

Biography：

Jun LUO is a tenured associate professor of Antai College of Economics and Management at Shanghai Jiao Tong University. He received his PhD degree in Industrial Engineering and Logistics Management (IELM) at Hong Kong University of Science and Technology (HKUST) in 2013 and a B.S. degree in Statistics at Nanjing University in 2009. His research interests include stochastic modeling, simulation optimization, and data analytics, with their applications in service operations management, healthcare management and risk management. His work has been published in journals such as Operations Research, INFORMS Journal on Computing, Naval Research Logistics and so on. He is the principle investigator for several projects, including the National Science Fund of China (NSFC) for Young Scientists (2014), NSFC for Excellent Young Scientists (2017) and Key Program of NSFC (2020).