SEQUENTIAL RANKING AND SELECTION PROCEDURES AND SAMPLE .
SEQUENTIAL RANKING AND SELECTIONPROCEDURES AND SAMPLE COMPLEXITYA DissertationPresented to the Faculty of the Graduate Schoolof Cornell Universityin Partial Fulfillment of the Requirements for the Degree ofDoctor of PhilosophybySijia MaSeptember 2018
2018 Sijia MaALL RIGHTS RESERVED
SEQUENTIAL RANKING AND SELECTION PROCEDURES AND SAMPLECOMPLEXITYSijia Ma, Ph.D.Cornell University 2018Ranking and selection (R&S) procedures are widely used for selecting the bestamong a set of candidate systems, where each candidate system is associated witha simulation model. In this thesis, we focus on three aspects on the sample complexity of the R&S problem. First, we develop a method for predicting the samplecomplexity. Second, we present Envelope Procedure (EP), a R&S procedure thatdelivers a probably approximately correct selection guarantee, and we provide ahigh probability upper bound on its sample complexity. We also prove a lowerbound on the sample complexity for general R&S procedures. The performanceof the EP is demonstrated by numerical experiments. Finally, we discuss somespecific aspects and features of the EP in parallel computing environment and thesampling rules.
BIOGRAPHICAL SKETCHSijia Ma grew up in Baoding, an old city in China. He spent the first 18 years ofhis life in that city before he attended Xi’an Jiaotong University, which locates inXi’an, an even older city in China. After graduating with honors in Informationand Computational Sciences, he came to the U.S. for further study. After receivinga M.S. in Scientific Computing from the New York University, he came to Cornellfor PhD study.During the four years spent in Ithaca, Sijia took ski classes every winter andlikes skiing in the Greek Peak a lot. He likes the beautiful scenery in this smalltown, and had a lot of wonderful memories there. He also enjoyed his spring andfall breaks in national parks and skiing resorts. Upon graduating from Cornell, Sijia will move to Bejing, China and begin his career as a machine learning softwareengineer at Google China AI center.iii
To my parents and my fiancé.iv
ACKNOWLEDGEMENTSFirst and foremost, I would like to express my deepest gratitude to my advisor,Shane Henderson, for the patient guidance, consistent encouragement and invaluable advice he has provided throughout my PhD studies. His enthusiasm, humorand immense knowledge have been a great help of my research work. I have beenextremely lucky to have him as my advisor.I would like to extend my sincere thanks to the rest of my committee members:Sidney Resnick and Yudong Chen, for their inspiring comments and insightfulquestions. Besides them, I would also like to thank Pierre Patie and MadeleineUdell, with whom I had a great pleasure to work as a teaching assistant.I am also grateful to my colleagues and friends at Cornell, especially DavidEckman, Pu Yang, Tiandong Wang and Yuhang Ma, who have always been asource of support and help for my research and graduate student life.I thank the School of Operations Research and Information Engineering, notonly for offering me the environment to undertake this research, but also for giving me the opportunity to meet so many outstanding and interesting people here.Special thanks go to my fiancé, Zelin Li. This dissertation would not have beenpossible without her warm love and endless support. Last but not the least, I amvery much indebted to my parents, Xiaoduo Zhao and Shiying Ma, who havebeen offering me unconditionally help throughout my life.This research was supported, in part, by National Science Foundation grantCMMI 1537394 and Army Research Office grant W911NF-17-1-0094.v
TABLE OF CONTENTSBiographical Sketch .Dedication . . . . . .AcknowledgementsTable of Contents . .List of Tables . . . . .List of Figures . . . .iiiivvviviiix1Introduction1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1172Predicting the Sample Complexity in Ranking and Selection Procedures2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Estimating the Total Number of Samples . . . . . . . . . . . . . . . . . .2.2.1 First-order estimate . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.2 Simulation of the simulation process . . . . . . . . . . . . . . . .2.3 Estimation of the Ordered Expectations . . . . . . . . . . . . . . . . . . .2.3.1 Issues with Naive Estimation . . . . . . . . . . . . . . . . . . . .2.3.2 Regression Method for Estimating the Ordered Expectations2.3.3 Convex Combination of Naive and Regression Estimators . .2.3.4 Statistical Properties of The Estimators . . . . . . . . . . . . . .2.4 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.1 Comparison of Naive Estimation and Linear CombinationEstimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.2 An Illustrative Problem . . . . . . . . . . . . . . . . . . . . . . . .2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1014151719202023323544455055A Sequential Selection Procedure Delivering a Probably-ApproximatelyCorrect Selection using Confidence Bands3.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2 Known σ 2 Envelope Procedure . . . . . . . . . . . . . . . . . . . . . . . .3.2.1 The Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.2 Sampling Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.3 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.4 On Computing the Parameter η . . . . . . . . . . . . . . . . . . .3.3 Unknown σ 2 Envelope Procedure . . . . . . . . . . . . . . . . . . . . . .3.3.1 The Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5661636468698083833.vi.
3.43.53.63.3.2 Theoretical Analysis . . . . . . . . . . . . . . . . . . . . .3.3.3 On Computing the Parameter η . . . . . . . . . . . . . .Lower Bound on the Sample Complexity of PAC ProceduresNumerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5.1 Statistical Validity and Efficiency . . . . . . . . . . . . .3.5.2 Empirical PAC and Practical Efficiency . . . . . . . . .Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . 87. 89. 90. 97. 98. 103. 1064Sampling Rules for the Envelope Procedure in a Parallel Computing Environment1094.1 The Envelope Procedure in a Parallel Computing Environment . . . 1094.1.1 Master and Worker Scheme . . . . . . . . . . . . . . . . . . . . . 1094.1.2 Random Completion Times and Vector Filling . . . . . . . . . . 1114.1.3 Sequential Assignment and Information Update . . . . . . . . 1134.1.4 Inferior System Elimination . . . . . . . . . . . . . . . . . . . . . 1154.1.5 The Parallel EP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.2 Sampling Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.2.1 Gap Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 1194.2.2 No-Waste Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 1224.3 Computational Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1264.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1295Conclusions and Future Directions130A Appendix for Chapter 2133A.1 Relaxed Condition in Proposition 2 . . . . . . . . . . . . . . . . . . . . . 133A.2 Supplementary Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135B Appendix for Chapter 3142B.1 Supporting Results for Theorem 3 . . . . . . . . . . . . . . . . . . . . . . 142vii
LIST OF TABLES2.12.22.32.43.13.23.33.43.53.63.7Problem configurations used in numerical experiments. . . . . . . .Means and standard deviations of the ratios of estimation to thetrue value of the sample sizes for the illustrative problem . . . . . .Means and standard deviations of the true sample sizes for theillustrative problem ( 105 , 2 significant figures) . . . . . . . . . . . .Average total running time for the R&S procedure and for the prediction of running time for the illustrative problem (seconds, 2 significant figures) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Partition of the possible cases of rounds. . . . . . . . . . . . . . . . . .Simulated η for different values of k and N . . . . . . . . . . . . . . .Fitted η for different values of k and N . . . . . . . . . . . . . . . . . .Approximated value of η for UEP and UEPu for N 105 . . . . . .Estimated PAC and average sample size of the procedures underdifferent problem configurations for known-variances case. . . . .Estimated PAC and average sample size of the procedures underdifferent problem configurations for unknown-variances case, n0 50. The estimated PAC of UEP and UEPu are all 1.000 and henceomitted. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Estimated PAC and average sample size of the heuristic EPs under different problem configurations for known and unknownvariances cases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44. 51. 51. 52.78828389. 99. 100. 1074.1A Comparison of EP and VKN in Parallel Computing Environment. 128A.1Comparison of naive and linear combination estimators for simulation approach for KN. The values given are the averages over 100replications of the ratio of the estimator to true value . . . . . . . . .Comparison of naive and linear combination estimators for simulation approach for BIZ. The values given are the averages over100 replications of the ratio of the estimator to true value . . . . . .Comparison of naive and linear combination estimators for simulation approach for GSP. The values given are the averages over100 replications of the ratio of the estimator to true value . . . . . .Comparison of naive and linear combination estimators for firstorder approach for KN. The values given are the averages over 100replications of the ratio of the estimator to true value . . . . . . . . .A.2A.3A.4viii. 136. 137. 138. 139
A.5A.6Comparison of naive and linear combination estimators for firstorder approach for BIZ. The values given are the averages over100 replications of the ratio of the estimator to true value . . . . . . . 140Comparison of naive and linear combination estimators for firstorder approach for GSP. The values given are the averages over100 replications of the ratio of the estimator to true value . . . . . . . 141ix
LIST OF FIGURES2.12.22.32.42.52.62.72.8Histograms of expectations and sample means under the followingconfigurations: SC (row 1) and RPI (row 2). k 1000, δ 0.1,σi2 25, n0 50. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Regression method to estimate µ when all µi µ 0 and σi2 σ 2 4are equal. Here k 1000 and n0 50. The estimated µ̂ 0.08. . . . .Regression method to estimate µ(k) when all σi2 4 are equal andµi are independently and normally distributed with standard deviation equal to 0.2. We subtract maxi µi from µi , i 1, 2, . . . , k toensure that µ(k) 0. Here k 1000 and n0 50. Only the last 25data points are used for regression. The estimated µ̂(k) 0.22. . .Regression method to estimate µ(k) when all σi2 4 are equal andµi are normally distributed with standard deviation equal to 0.2,and µ(k) 0. Here k 1000 and n0 50. Only the last 25 data pointsare used for regression. The estimated µ̂(k) 0.14. . . . . . . . . . .Ordered expectations and the values of estimators. The red curveis the true ordered means, the blue curve is the naive estimator mi ,the green curve is the regression estimator µ̂(i) and the black curveis the linear combination estimator µ̃(i) . All σi2 4 are equal and µiare independent and normally distributed with standard deviationequal to 0.2. Here k 10000 and n0 50. The coefficient ρ 0.48. . .Histogram of ratios between estimation and true value of N . Teston BIZ under the following configurations: SC (row 1); SC-INC(row 2) and SC-DEC (row 3) with k 100 (column 1); 500 (column2) and 2000 (column 3). . . . . . . . . . . . . . . . . . . . . . . . . . . .Histogram of ratios between estimation and true value of N . Teston BIZ under the following configurations: MDM (row 1); MDMINC (row 2) and MDM-DEC (row 3) with k 100 (column 1); 500(column 2) and 2000 (column 3). . . . . . . . . . . . . . . . . . . . . . .Histogram of ratios between estimation and true value of N . Teston BIZ under the following configurations: RPI1 (row 1); RPI2(row 2) and RPI-HET (row 3) with k 100 (column 1); 500 (column2) and 2000 (column 3). . . . . . . . . . . . . . . . . . . . . . . . . . . .x. 20. 25. 27. 29. 31. 46. 47. 48
3.13.23.3Illustration of EP. Systems are distinguished by different colors.The solid lines are X̄i (ni )’s and the dashed lines are Ui (ni )’s andLi (ni )’s throughout the procedure. The dotted lines are the finalupper and lower confidence bounds when the procedure stops.The black dashed line indicates termination of the procedure whenthe stopping rule is met. . . . . . . . . . . . . . . . . . . . . . . . . . . . 67Empirical PAC vs. total sample size n for different procedures inSC. Variances are known. . . . . . . . . . . . . . . . . . . . . . . . . . . . 103Empirical PAC vs. total sample size n for different procedures inSC. Variances are unknown. . . . . . . . . . . . . . . . . . . . . . . . . . 104xi
CHAPTER 1INTRODUCTION1.1BackgroundThe simulation optimization (SO) problem integrates stochastic simulation into anonlinear optimization problem whose objective function is not explicitly available but can be measured with error by Monte Carlo simulation. An example ofsuch a problem is ambulance planning [45]. The decision-makers of ambulanceorganizations need to decide the locations and schedules of the ambulances inorder to minimize a quantile of the response times. For any candidate plan, itsperformance over a fixed time horizon is analytically intractable. Stochastic simulation can be used to approximately evaluate the objective function in an effort tosolve this optimization problem. Such problems arise in a wide variety of areas,e.g., supply chain management [31], transportation, and public health [1, part 4].For more examples of SO problems, see [23].Ranking and selection (R&S) problems are a special class of SO problems inwhich: (1) the number of feasible solutions is finite, (2) no structural properties,e.g., convexity, of the objective are assumed, and (3) the computational budgetpermits at least some simulation of every system. The goal is to identify the bestamong a finite set of systems where the performance of each system can only beobserved by simulation. This is an important class of problems, since in many1
practical applications the structural properties are non-existent or very difficult toverify. The main issue in R&S problems is how to allocate computational budgetfor simulation of the systems so that a statistically reliable choice of the best systemcan be determined efficiently. A good R&S procedure achieves a balance betweenthe total running time and the quality of the ultimate selection. For an overviewof this area, see [26, 9] for context, and see [4, 21] for book-level treatment.Many procedures have been proposed for dealing with R&S problems. Theycan be classified into Bayesian approaches and frequentist approaches. Bayesianapproaches usually aim to optimize an objective that penalizes suboptimalchoices, as estimated through the posterior distribution. For example, OCBA(Optimal Computing Budget Allocation) [10] allocates a computational budget tomaximize approximations of the posterior Probability of Correct Selection (PCS).Other Bayesian procedures [13, 12] allocate samples to minimize the expected opportunity cost, or to maximize a measure of the expected value of information[11].Frequentist approaches usually provide a certain statistical guarantee on thequality of the selected system irrespective of the unknown problem configuration.An important class of such procedures are indifference-zone (IZ) procedures. IZprocedures originated with [2] and have been well studied; see, e.g., [49, 52, 36, 24,18]. They guarantee to select the unique best system with at least a prescribed PCS,assuming that the difference between the best and all others is sufficiently large.To be more precise, let µi denote the true performance (usually an expectation)2
of the ith system. For notational simplicity, suppose that, unknown to the R&Sprocedure, the systems are indexed so that µ1 µ2 µk , and System k is thebest. A R&S procedure provides a PCS guarantee at level α ifP(I k) 1 α, if µk µk 1 δ,where I is the (random) index of the selected system, the parameter δ is calledthe IZ parameter, and 1 α is the confidence level. It is natural to require 1 α 1/k, since otherwise the procedure is no better than random guessing. Thereforethroughout the thesis we assume that α 1 1/k, i.e., α is bounded away from1 for fixed k. The IZ guarantee only holds when the difference between the bestand second-best systems is greater than δ; nothing is guaranteed otherwise. Thereare also some recent IZ-free frequentist procedures [17] that deliver PCS withoutimposing an IZ restriction.A stronger form of guarantee that holds for any configuration of means, andthat also implies a PCS guarantee when µk µk 1 δ, is probably approximatelycorrect (PAC) selection, which is also referred to as a probability of good selection(PGS) guarantee in, for example, [46, 47]. It guarantees, with high probability,to select a system whose performance is not too far away from that of the bestsystem, i.e., thatP(µI µk δ) 1 α,irrespective of the gap between the best and the other systems. It is not hard tosee that a procedure that delivers a PAC guarantee automatically delivers a PCSguarantee, but the converse does not necessarily hold. R&S procedures that pro3
vide PAC guarantees are far less prevalent than those providing PCS guarantees,perhaps due to the difficulty in establishing such guarantees; see [15] for a survey.The R&S problem is closely related to the multi-armed bandit (MAB) problem.They both originate from the work of [2] and [49]. An important difference isthat, in MAB problems, one typically considers the cumulative reward collectedby pulling each arm (i.e., obtaining a sample from each system) throughout theexperiment, instead of focusing only on the quality of the final decision as in R&S[50]. In pure-exploration instances of the MAB, the goal is to find the best arm/system at the end of the procedure, which is the same overall objective as inR&S problems, but still, different distributional assumptions are made about theunderlying arms/systems. Algorithms developed for the bandit problem usuallyassume bounded or sub-Gaussian simulation outputs with a known bound on thevariances. In addition, the algorithms for the MAB problem usually simulate onesystem at a time. In comparison, the R&S literature typically assumes Gaussianerror, uses batching to approximately ensure this when needed, and takes samplesfrom a set of systems in each round.A focus of the MAB literature is the analysis of the sample complexity. Themedian elimination procedure of [16] was shown to deliver the PAC guaranteein O(k/δ 2 log(1/α)) arm pulls. Since then, the upper bound on the sample complexity for this problem or the no-relaxation form of this problem, i.e., δ 0, hasbeen successively improved by the work of [33], [27], [34] and [28]. The upperbound on the sample complexity, i.e., how many samples are ne
SEQUENTIAL RANKING AND SELECTION PROCEDURES AND SAMPLE COMPLEXITY Sijia Ma, Ph.D. Cornell University 2018 Ranking and selection (R&S) procedures are widely used for selecting the best among a set of candidate systems, where each candidate system is associated with a simulation model. In this thesis, we focus on three aspects on the sample com-
'Database Ranking'. 3. After selecting an object and then clicking on the 'Add a database ranking' button adds the Database Ranking Filter into the Query Filters pane: For Reference, Web Intelligence uses the SQL-99 Rank function in ranking SQL. NOTE For 'eFashion Oracle' universe, further details and instructions can be found at
Moscow International University Ranking 2020 About the Project Moscow International University Ranking is a fundamentally new academic ranking, the fi rst to evaluate all the three key university missions: education, research, and interaction with society. The ranking uses a number of new criteria calculated on the basis of objective data,
Division of Biostatistics University of Minnesota Week 5. Course Summary So far, we have discussed Group sequential procedures for two-sided tests Group sequential procedures for one-sided tests Group sequential procedure
A rigorous analysis of sequential problems is a large part of this course. Interestingly, most research on sequential prediction (or, onlinelearning) has been algorithmic: given a problem, one would present a method and prove a guarantee for its performance. In this course, we present a thorough study of inherent complexities of sequential .
a sequential pattern; or b) b can be appended to α to form a sequential pattern. 2. For each frequent item b, append it to α to form a sequential pattern α', and output α'; 3. For each α', construct α'-projected database S α', and call PrefixSpan(α', l 1, S α').
The University of Texas at Arlington Sequential Logic - Intro CSE 2340/2140 – Introduction to Digital Logic Dr. Gergely Záruba The Sequential Circuit Model x 1 Combinational z1 x n zm (a) y y Y Y Combinational logic logic x1 z1 x n z m Combinational logic with n inputs and m switching functions: Sequential logic with n inputs, m outputs, r .
complexity is assumed to be independent from the sequen-tial scheduling chosen. Furthermore, different types of se-quential schedules such as sequential check-node updat-ing, sequential variable-node updating and sequential mes-sage updating have very similar performance results [9]. Given their similarities, the different types of sequential
Alex Rider: Never say Die by Anthony Horowitz Below are the complete reviews, written by the Lovereading4kids members. George Hutton - Dormston Secondary School Alex Rider receives a suspicious email from who could be Jack Starbright who was kidnapped on his previous mission. However, whilst trying to locate Jack, he accidentally manages to get tangled up in another MI6 Mission which could put .
