The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection.
Saved in:
| Authors: | Li, Zaile1 (AUTHOR) zaileli21@m.fudan.edu.cn, Fan, Weiwei2 (AUTHOR) wfan@tongji.edu.cn, Hong, L. Jeff1 (AUTHOR) hong_liu@fudan.edu.cn |
|---|---|
| Source: | Management Science (INFORMS). Feb2025, Vol. 71 Issue 2, p1238-1259. 22p. |
| Subject Terms: | *Stochastic models, *Simulation methods & models, Linear orderings, Sampling (Process), Sample size (Statistics) |
| Abstract: | Ranking and selection (R&S) aims to select the best alternative with the largest mean performance from a finite set of alternatives. Recently, considerable attention has turned toward the large-scale R&S problem which involves a large number of alternatives. Ideal large-scale R&S procedures should be sample optimal; that is, the total sample size required to deliver an asymptotically nonzero probability of correct selection (PCS) grows at the minimal order (linear order) in the number of alternatives, k. Surprisingly, we discover that the naïve greedy procedure, which keeps sampling the alternative with the largest running average, performs strikingly well and appears sample optimal. To understand this discovery, we develop a new boundary-crossing perspective and prove that the greedy procedure is sample optimal for the scenarios where the best mean maintains at least a positive constant away from all other means as k increases. We further show that the derived PCS lower bound is asymptotically tight for the slippage configuration of means with a common variance. For other scenarios, we consider the probability of good selection and find that the result depends on the growth behavior of the number of good alternatives: if it remains bounded as k increases, the sample optimality still holds; otherwise, the result may change. Moreover, we propose the explore-first greedy procedures by adding an exploration phase to the greedy procedure. The procedures are proven to be sample optimal and consistent under the same assumptions. Last, we numerically investigate the performance of our greedy procedures in solving large-scale R&S problems. This paper was accepted by Baris Ata, stochastic models and simulation. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72091211, 72071146, 72161160340]. Supplemental Material: The e-companion and data files are available at https://doi.org/10.1287/mnsc.2023.00694. [ABSTRACT FROM AUTHOR] |
| Database: | Entrepreneurial Studies Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: ent DbLabel: Entrepreneurial Studies Source An: 182990763 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Li%2C+Zaile%22">Li, Zaile</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> zaileli21@m.fudan.edu.cn</i><br /><searchLink fieldCode="AR" term="%22Fan%2C+Weiwei%22">Fan, Weiwei</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> wfan@tongji.edu.cn</i><br /><searchLink fieldCode="AR" term="%22Hong%2C+L%2E+Jeff%22">Hong, L. Jeff</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> hong_liu@fudan.edu.cn</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Management+Science+%28INFORMS%29%22">Management Science (INFORMS)</searchLink>. Feb2025, Vol. 71 Issue 2, p1238-1259. 22p. – Name: Subject Label: Subject Terms Group: Su Data: *<searchLink fieldCode="DE" term="%22Stochastic+models%22">Stochastic models</searchLink><br />*<searchLink fieldCode="DE" term="%22Simulation+methods+%26+models%22">Simulation methods & models</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+orderings%22">Linear orderings</searchLink><br /><searchLink fieldCode="DE" term="%22Sampling+%28Process%29%22">Sampling (Process)</searchLink><br /><searchLink fieldCode="DE" term="%22Sample+size+%28Statistics%29%22">Sample size (Statistics)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Ranking and selection (R&S) aims to select the best alternative with the largest mean performance from a finite set of alternatives. Recently, considerable attention has turned toward the large-scale R&S problem which involves a large number of alternatives. Ideal large-scale R&S procedures should be sample optimal; that is, the total sample size required to deliver an asymptotically nonzero probability of correct selection (PCS) grows at the minimal order (linear order) in the number of alternatives, k. Surprisingly, we discover that the naïve greedy procedure, which keeps sampling the alternative with the largest running average, performs strikingly well and appears sample optimal. To understand this discovery, we develop a new boundary-crossing perspective and prove that the greedy procedure is sample optimal for the scenarios where the best mean maintains at least a positive constant away from all other means as k increases. We further show that the derived PCS lower bound is asymptotically tight for the slippage configuration of means with a common variance. For other scenarios, we consider the probability of good selection and find that the result depends on the growth behavior of the number of good alternatives: if it remains bounded as k increases, the sample optimality still holds; otherwise, the result may change. Moreover, we propose the explore-first greedy procedures by adding an exploration phase to the greedy procedure. The procedures are proven to be sample optimal and consistent under the same assumptions. Last, we numerically investigate the performance of our greedy procedures in solving large-scale R&S problems. This paper was accepted by Baris Ata, stochastic models and simulation. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72091211, 72071146, 72161160340]. Supplemental Material: The e-companion and data files are available at https://doi.org/10.1287/mnsc.2023.00694. [ABSTRACT FROM AUTHOR] |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=ent&AN=182990763 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1287/mnsc.2023.00694 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 22 StartPage: 1238 Subjects: – SubjectFull: Stochastic models Type: general – SubjectFull: Simulation methods & models Type: general – SubjectFull: Linear orderings Type: general – SubjectFull: Sampling (Process) Type: general – SubjectFull: Sample size (Statistics) Type: general Titles: – TitleFull: The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Li, Zaile – PersonEntity: Name: NameFull: Fan, Weiwei – PersonEntity: Name: NameFull: Hong, L. Jeff IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 02 Text: Feb2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00251909 Numbering: – Type: volume Value: 71 – Type: issue Value: 2 Titles: – TitleFull: Management Science (INFORMS) Type: main |
| ResultId | 1 |
