Abstract
We show tight convergence rate bounds for gradient descent and MM algorithmsfor maximum likelihood estimation and maximum aposteriori probabilityestimation of a popular Bayesian inference method for generalized Bradley-Terrymodels. This class of models includes the Bradley-Terry model of pairedcomparisons, the Rao-Kupper model of paired comparisons with ties, the Lucechoice model, and the Plackett-Luce ranking model. Our results show that MMalgorithms have same convergence rates as gradient descent algorithms up toconstant factors. For the maximum likelihood estimation, the convergence islinear with the rate crucially determined by the algebraic connectivity of thematrix of item pair co-occurrences in observed comparison data. For theBayesian inference, the convergence rate is also linear, with the ratedetermined by a parameter of the prior distribution in a way that can makeconvergence arbitrarily slow for small values of this parameter. We propose asimple, first-order acceleration method that resolves the slow convergenceissue.