Accelerated MM Algorithms for Inference of Ranking Scores from Comparison Data

References

• Agarwal A, Patil P, Agarwal S (2018) Accelerated spectral ranking. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., vol. 80 (PMLR, Stockholm, Sweden), 70–79.Google Scholar
• Agresti A (2002) Categorical Data Analysis, 2nd ed. (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Balduzzi D, Tuyls K, Pérolat J, Graepel T (2018) Re-evaluating evaluation. Bengio S, Wallach HM, Larochelle H, Grauman K, Cesa-Bianchi N, eds. Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 3272–3283.Google Scholar
• Bollobás B (2001) Random Graphs, 2nd ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Borkar VS, Karamchandani N, Mirani S (2016) Randomized Kaczmarz for rank aggregation from pairwise comparisons. 2016 IEEE Inform. Theory Workshop (IEEE, Piscataway, NJ), 389–393.Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bradley RA (1954) Rank analysis of incomplete block designs: II. Additional tables for the method of paired comparisons. Biometrika 41(3/4):502–537.Crossref, Google Scholar
• Bradley RA, Terry ME (1952) Rank analysis of incomplete block designs: I. Method of paired comparisons. Biometrika 39(3/4):324–345.Crossref, Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Google Scholar
• Burges CJ, Ragno R, Le QV (2006) Learning to rank with nonsmooth cost functions. Schölkopf B, Platt J, Hoffman T, eds. Proc. 19th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 193–200.Google Scholar
• Caron F, Doucet A (2012) Efficient Bayesian inference for generalized Bradley-Terry models. J. Comput. Graph. Statist. 21(1):174–196.Crossref, Google Scholar
• Chen Y, Suh C (2015) Spectral MLE: Top-K rank aggregation from pairwise comparisons. Bach F, Blei D, eds. Proc. 32nd Internat. Conf. Machine Learn., 371–380.Google Scholar
• Chen Y, Fan J, Ma C, Wang K (2019) Spectral method and regularized MLE are both optimal for top-K ranking. Ann. Statist. (Institute of Mathematical Statistics), 47(4):2204–2235.Google Scholar
• Coja-Oghlan A (2007) On the Laplacian eigenvalues of Gn,p. Combin. Probab. Comput. 16:923–946.Crossref, Google Scholar
• Dykstra O Jr (1956) A note on the rank analysis of incomplete block designs—Applications beyond the scope of existing tables. Biometrics 12(3):301–306.Crossref, Google Scholar
• Dykstra O Jr (1960) Rank analysis of incomplete block designs: A method of paired comparisons employing unequal repetitions on pairs. Biometrics 16(2):176–188.Crossref, Google Scholar
• Elo AE (1978) The Rating of Chessplayers, Past and Present (Ishi Press International, Bronx, NY).Google Scholar
• Fiedler M (1973) Algebraic connectivity of graphs. Czechoslovak Math. J. 23(98):298–305.Crossref, Google Scholar
• Ford LR (1957) Solution of a ranking problem from binary comparisons. Amer. Math. Monthly 64(8):28–33.Crossref, Google Scholar
• Golub GH, Loan CFV (2013) Matrix Computations, 4th ed. (Johns Hopkins University Press, Baltimore).Crossref, Google Scholar
• Grone R, Merris R, Sunder V (1990) The Laplacian spectrum of a graph. SIAM J. Matrix Anal. Appl. 11(2):218–238.Crossref, Google Scholar
• Guiver J, Snelson E (2009) Bayesian inference for Plackett-Luce ranking models. Proc. 26th Internat. Conf. Machine Learning (ACM, New York), 377–384.Google Scholar
• Hajek B, Oh S, Xu J (2014) Minimax-optimal inference from partial rankings. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Proc. 27th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 1475–1483.Google Scholar
• Herbrich R, Minka T, Graepel T (2006) TrueskillTM: A Bayesian skill rating system. Schölkopf B, Platt J, Hoffman T, eds. Proc. 19th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 569–576.Google Scholar
• Huang T-K, Lin C-J, Weng RC (2008) Ranking individuals by group comparisons. J. Machine Learn. Res. 9(72):2187–2216.Google Scholar
• Huang T-K, Weng RC, Lin C-J (2006) Generalized Bradley-Terry models and multi-class probability estimates. J. Machine Learn. Res. 7(4):85–115.Google Scholar
• Hunter DR (2003) MATLAB code for Bradley-Terry models. Accessed March 1, 2020, http://personal.psu.edu/drh20/code/btmatlab/.Google Scholar
• Hunter DR (2004) MM algorithms for generalized Bradley-Terry models. Ann. Statist. 32(1):384–406.Crossref, Google Scholar
• Hunter DR, Lange K (2004) A tutorial on MM algorithms. Amer. Statist. 58(1):30–37.Crossref, Google Scholar
• Kaye E, Firth D (2020) BradleyTerryScalable. Accessed March 1, 2020, https://github.com/EllaKaye/BradleyTerryScalable.Google Scholar
• Khetan A, Oh S (2016a) Computational and statistical tradeoffs in learning to rank. Lee DD, Sugiyama M, Luxburg UV, Guyon I, Garnett R, eds. Advances in Neural Information Processing Systems, Vol. 29 (Curran Associates, Red Hook, NY), 739–747.Google Scholar
• Khetan A, Oh S (2016b) Data-driven rank breaking for efficient rank aggregation. J. Machine Learn. Res. 17(193):1–54.Google Scholar
• Lange K (2016) MM Optimization Algorithms (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Lange K, Hunter DR, Yang I (2000) Optimization transfer using surrogate objective functions. J. Comput. Graph. Statist. 9(1):1–20.Google Scholar
• Li H (2015) Learning to Rank for Information Retrieval and Natural Language Processing, Synthesis Lectures on Human Language Technologies, 2nd ed. (Morgan & Claypool, Williston, VT).Crossref, Google Scholar
• Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (John Wiley & Sons, New York).Google Scholar
• Mairal J (2015) Incremental majorization-minimization optimization with application to large-scale machine learning. SIAM J. Optim. 25(2):829–855.Crossref, Google Scholar
• Maystre L (2018) Choix: Inference algorithms for models based on Luce’s choice axiom. Accessed March 1, 2020, https://github.com/lucasmaystre/choix.Google Scholar
• Maystre L, Grossglauser M (2015) Fast and accurate inference of Plackett–Luce models. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems, Vol. 28 (Curran Associates, Red Hook, NY), 172–180.Google Scholar
• Merris R (1994) Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197–198(January–February):143–176.Crossref, Google Scholar
• Negahban S, Oh S, Shah D (2017) Rank centrality: Ranking from pairwise comparisons. Oper. Res. 65(1):266–287.Link, Google Scholar
• Nesterov Y (2013) Gradient methods for minimizing composite objective functions. Math. Programming 140(1):125–161.Crossref, Google Scholar
• Plackett RL (1975) The analysis of permutations. J. Roy. Statist. Soc. 24(2):193–202.Google Scholar
• Polyak B (1963) Gradient methods for the minimisation of functionals. USSR Comput. Math. Math. Phys. 3(4):864–878.Crossref, Google Scholar
• Rajkumar A, Agarwal S (2014) A statistical convergence perspective of algorithms for rank aggregation from pairwise data. Xing EP, Jebara T, eds. Proc. 31st Internat. Conf. Machine Learn., (PMLR, Bejing), 32(1):118–126.Google Scholar
• Rao PV, Kupper LL (1967) Ties in paired-comparison experiments: A generalization of the Bradley-Terry model. J. Amer. Statist. Assoc. 62(317):194–204.Crossref, Google Scholar
• Rich T, Hu K, Tome B (2018) GIFGIF—Mapping the emotional language of gifs. Accessed March 1, 2020, http://gifgif.media.mit.edu.Google Scholar
• Shah NB, Balakrishnan S, Bradley J, Parekh A, Ramchandran K, Wainwright MJ (2016) Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. J. Machine Learn. Res. 17(1):2049–2095.Google Scholar
• Simons G, Yao YC (1999) Asymptotics when the number of parameters tends to infinity in the Bradley-Terry model for paired comparisons. Ann. Statist. 27(3):1041–1060.Crossref, Google Scholar
• Sonas J (2010) Kaggle competition: Chess ratings—Elo vs. the rest of the world. Accessed March 1, 2020, https://www.kaggle.com/c/chess.Google Scholar
• Thurstone LL (1927) A law of comparative judgment. Psych. Rev. 34(4):273–286.Crossref, Google Scholar
• Turner H, Firth D (2012) Bradley-Terry models in R: The BradleyTerry2 package. J. Statist. Software 48(9):1–21.Crossref, Google Scholar
• Vojnović M, Yun S-Y (2016) Parameter estimation for generalized Thurstone choice models. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Internat. Conf. Machine Learn., vol. 48 (PMLR, New York), 498–506.Google Scholar
• Vojnović M, Yun S-Y, Zhou K (2020) Convergence rates of gradient descent and MM algorithms for Bradley-Terry models. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., vol. 108 (PMLR), 1254–1264.Google Scholar
• Wauthier F, Jordan M, Jojic N (2013) Efficient ranking from pairwise comparisons. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. Machine Learn. (PMLR, Atlanta, Georgia), 28(3):109–117.Google Scholar
• Zermelo E (1929) Die berechnung der Turnier-Ergebnisse als ein maximumproblem der wahrscheinlichkeitsrechnung. Math. Zeitschrift 29:436–460.Crossref, Google Scholar