The Fourth Lecture of the "series of online forums on deep learning theory and application" hosted by CAAI and CAAI Special Committee on deep learning will be delivered online on March 2, 2022. The series of forums invite front-line researchers from domestic universities and research institutes to give lectures, covering in-depth learning, complex systems, swarm intelligence and intensive learning, and bring all-round communication and sharing under the background of the global anti epidemic era. Jiang Guangxin, Professor of the Department of management science and engineering, School of economics and management, Harbin University of technology and winner of the national youth talent plan, is invited to make a report. The topic of the report is: solving large-scale fixed budget ranking and selection problems.

Topic

Solving Large-Scale Fixed-Budget Ranking and Selection Problems

Abstract

In recent years, with the rapid development of computing technology, developing parallel procedures to solve large-scale ranking and selection (R&S) problems has attracted a lot of research attention. In this paper, we take fixed-budget R&S procedure as an example to investigate potential issues of developing parallel procedures. We argue that to measure the performance of a fixed-budget R&S procedure in solving large- scale problems, it is important to quantify the minimal growth rate of the total sampling budget such that as the number of alternatives increases, the probability of correct selection (PCS) would not decrease to zero. We call such a growth rate of the total sampling budget the rate for maintaining correct selection (RMCS). We show that a tight lower bound for the RMCS of a broad class of existing fixed-budget procedures is in the order of klogk, where k is the number of alternatives. Then, we propose a new type of fixed-budget procedure, namely the fixed-budget knockout-tournament (FBKT) procedure. We prove that, in terms of the RMCS, our procedure outperforms existing fixed-budget procedures and achieves the optimal order, i.e., the order of k. Moreover, we demonstrate that our procedure can be easily implemented in parallel computing environments with almost no non-parallelizable calculations. Lastly, a comprehensive numerical study shows that our procedure is indeed suitable for solving large-scale problems in parallel computing environments.