Asymptotically Optimal Sequential Design for Rank Aggregation

References

• [1] Adler RJ, Blanchet JH, Liu J (2012) Efficient Monte Carlo for high excursions of Gaussian random fields. Ann. Appl. Probab. 22(3):1167–1214.Crossref, Google Scholar
• [2] Albert AE (1961) The sequential design of experiments for infinitely many states of nature. Ann. Math. Statist. 32(3):774–799.Crossref, Google Scholar
• [3] Azuma K (1967) Weighted sums of certain dependent random variables. Tohoku Math. J. (2). 19(3):357–367.Crossref, Google Scholar
• [4] Ballinger TP, Wilcox NT (1997) Decisions, error and heterogeneity. Econom. J. (London). 107(443):1090–1105.Crossref, Google Scholar
• [5] Bartroff J, Lai TL (2008) Efficient adaptive designs with mid-course sample size adjustment in clinical trials. Statist. Medicine 27(10):1593–1611.Crossref, Google Scholar
• [6] Bartroff J, Finkelman M, Lai TL (2008) Modern sequential analysis and its applications to computerized adaptive testing. Psychometrika 73:473–486.Crossref, Google Scholar
• [7] Bartroff J, Lai TL, Shih MC (2013) Sequential Experimentation in Clinical Trials (Springer, New York).Crossref, Google Scholar
• [8] Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3):167–175.Crossref, Google Scholar
• [9] Bertsekas D (1999) Nonlinear Programming (Athena Scientific).Google Scholar
• [10] Blumenthal AL (1977) The Process of Cognition (Prentice Hall/Pearson Education).Google Scholar
• [11] Bradley R, Terry M (1952) Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika. 39(3/4):324–345.Crossref, Google Scholar
• [12] Braverman M, Mossel E (2009) Sorting from noisy information. Preprint, submitted October 7, https://arxiv.org/abs/0910.1191.Google Scholar
• [13] Braverman M, Mao J, Weinberg MS (2016) Parallel algorithms for select and partition with noisy comparisons. Proc. Annual Sympos. Theory Comput.Google Scholar
• [14] Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Crossref, Google Scholar
• [15] Chen X, Jiao K, Lin Q (2016) Bayesian decision process for cost-efficient dynamic ranking via crowdsourcing. J. Machine Learn. Res. 17(217):1–40.Google Scholar
• [16] Chen X, Li Y, Mao J (2018) An instance optimal algorithm for top-K ranking under the multinomial logit model. ACM-SIAM Sympos. Discrete Algorithms.Google Scholar
• [17] Chen X, Bennett PN, Collins-Thompson K, Horvitz E (2013) Pairwise ranking aggregation in a crowdsourced setting. Proc. ACM Internat. Conf. Web Search Data Mining.Google Scholar
• [18] Chen X, Gopi S, Mao J, Schneider J (2018) Optimal instance adaptive algorithm for the top-k ranking problem. IEEE Trans. Inform. Theory 64(9):6139–6160.Crossref, Google Scholar
• [19] Chen Y, Suh C (2015) Spectral MLE: Top-k rank aggregation from pairwise comparisons. Proc. Internat. Conf. Machine Learn.Google Scholar
• [20] Chernoff H (1959) Sequential design of experiments. Ann. Math. Statist. 30(3):755–770.Crossref, Google Scholar
• [21] Dragalin VP, Tartakovsky AG, Veeravalli VV (2000) Multihypothesis sequential probability ratio tests. II. Accurate asymptotic expansions for the expected sample size. IEEE Trans. Inform. Theory 46(4):1366–1383.Crossref, Google Scholar
• [22] Draglia V, Tartakovsky AG, Veeravalli VV (1999) Multihypothesis sequential probability ratio tests. I. Asymptotic optimality. IEEE Trans. Inform. Theory 45(7):2448–2461.Crossref, Google Scholar
• [23] Elo AE (1978) The Rating of Chessplayers, Past, and Present (Arco Publishing).Google Scholar
• [24] Garg N, Johari R (2019) Designing optimal binary rating systems. Proc. 22nd Internat. Conf. Artificial Intelligence Statist.Google Scholar
• [25] Hajek B, Oh S, Xu J (2014) Minimax-optimal inference from partial rankings. Proc. Adv. Neural Inform. Processing Systems.Google Scholar
• [26] Heckel R, Shah NB, Ramchandran K, Wainwright MJ (2019) Active ranking from pairwise comparisons and when parametric assumptions do not help. Ann. Statist. 47(6):3099–3126.Crossref, Google Scholar
• [27] Hoeffding W (1960) Lower bounds for the expected sample size and the average risk of a sequential procedure. Ann. Math. Statist. 31(2):352–368.Crossref, Google Scholar
• [28] Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Crossref, Google Scholar
• [29] Hsiung AC, Ying ZL, Zhang CH, eds. (2004) Random Walk, Sequential Analysis and Related Topics: A Festschrift in Honor of Yuan-Shih Chow (World Scientific).Google Scholar
• [30] Jamieson K, Nowak R (2011) Active ranking using pairwise comparisons. Proc. 24th Internat. Conf. Neural Inform. Processing Systems, 2240–2248Google Scholar
• [31] Kallus N, Udell M (2020) Dynamic assortment personalization in high dimensions. Oper. Res. 68(4):1020–1037.Link, Google Scholar
• [32] Kendall M, Gibbons JD (1990) Rank Correlation Methods, 5th ed. (Charles Griffin).Google Scholar
• [33] Kiefer J, Sacks J (1963) Asymptotically optimum sequential inference and design. Ann. Math. Statist. 34(3):705–750.Crossref, Google Scholar
• [34] Lai TL (1988) Nearly optimal sequential tests of composite hypotheses. Ann. Statist. 16(2):856–886.Crossref, Google Scholar
• [35] Lai TL (2001) Sequential analysis: Some classical problems and new challenges. Statista Sinica 11(2):303–351.Google Scholar
• [36] Lai TL, Shih MC (2004) Power, sample size and adaptation considerations in the design of group sequential clinical trials. Biometrika 91(3):507–528.Crossref, Google Scholar
• [37] Li X, Liu J (2015) Rare-event simulation and efficient discretization for the supremum of Gaussian random fields. Adv. Appl. Probab. 47(3):787–816.Crossref, Google Scholar
• [38] Li X, Liu J, Ying Z (2018) Chernoff index for Cox test of separate parametric families. Ann. Statist. 46(1):1–29.Crossref, Google Scholar
• [39] Lorden G (1976) 2-SPRT’s and the modified Kiefer-Weiss problem of minimizing an expected sample size. Ann. Statist. 4(2):281–291.Crossref, Google Scholar
• [40] Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (Wiley, New York).Google Scholar
• [41] Mao C, Weed J, Rigollet P (2018) Minimax rates and efficient algorithms for noisy sorting. Proc. Algorithmic Learn. Theory.Google Scholar
• [42] Mei Y (2010) Efficient scalable schemes for monitoring a large number of data streams. Biometrika 97(2):419–433.Crossref, Google Scholar
• [43] Morrison HW (1963) Testable conditions for triads of paired comparison choices. Psychometrika 28:369–390.Crossref, Google Scholar
• [44] Naghshvar M, Javidi T (2013) Active sequential hypothesis testing. Ann. Statist. 41(6):2703–2738.Crossref, Google Scholar
• [45] Negahban S, Oh S, Sha D (2017) Rank centrality: Ranking from pair-wise comparisons. Oper. Res. 65(1):266–287.Link, Google Scholar
• [46] Nitinawarat S, Veeravalli VV (2015) Controlled sensing for sequential multihypothesis testing with controlled Markovian observations and non-uniform control cost. Sequential Anal. 34(1):1–24.Crossref, Google Scholar
• [47] Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab.Google Scholar
• [48] Saaty TL, Vargas LG (2012) The possibility of group choice: Pairwise comparisons and merging functions. Soc. Choice Welfare 38(3):481–496.Crossref, Google Scholar
• [49] Schwarz G (1962) Asymptotic shapes of Bayes sequential testing regions. Ann. Math. Statist. 33(1):224–236.Crossref, Google Scholar
• [50] Shah NB, Balakrishnan S, Guntuboyina A, Wainright MJ (2017) Stochastically transitive models for pairwise comparisons: Statistical and computational issues. IEEE Trans. Inform. Theory 63(2):934–959.Crossref, Google Scholar
• [51] Siegmund D (1985) Sequential Analysis: Tests and Confidence Intervals (Springer, New York).Crossref, Google Scholar
• [52] Song Y, Fellouris G (2017) Asymptotically optimal, sequential, multiple testing procedures with prior information on the number of signals. Electronic J. Statist. 11(1):338–363.Crossref, Google Scholar
• [53] Tartakovsky A, Nikiforov I, Basseville M (2014) Sequential Analysis: Hypothesis Testing and Changepoint Detection (Chapman and Hall/CRC).Crossref, Google Scholar
• [54] Thurstone LL (1927) A law of comparative judgement. Psych. Rev. 34(4):273–286.Crossref, Google Scholar
• [55] Train K (2009) Discrete Choice Methods with Simulation (Cambridge University Press).Crossref, Google Scholar
• [56] Tsitovich I (1985) Sequential design of experiments for hypothesis testing. Theory Probab. Appl. 29(4):814–817.Crossref, Google Scholar
• [57] Wald A (1945) Sequential tests of statistical hypotheses. Ann. Math. Statist. 16(2):117–186.Crossref, Google Scholar
• [58] Wald A, Wolfowitz J (1948) Optimum character of the sequential probability ratio test. Ann. Math. Statist. 19(3):326–339.Crossref, Google Scholar
• [59] Wang S, Lin H, Chang HH, Douglas J (2016) Hybrid computerized adaptive testing: From group sequential design to fully sequential design. J. Ed. Measurement 53(1):45–62.Crossref, Google Scholar
• [60] Watkins CJCH (1989) Learning from delayed rewards. Unpublished PhD thesis, Cambridge University, Cambridge, UK.Google Scholar
• [61] Xie Y, Siegmund DO (2013) Sequential multi-sensor change-point detection. Ann. Statist. 41(2):670–692.Crossref, Google Scholar
• [62] Ye S, Fellouris G, Culpepper S, Douglas J (2016) Sequential detection of learning in cognitive diagnosis. British J. Math. Statist. Psych. 69(2):139–158.Crossref, Google Scholar