Convergence Rates of Gradient Descent and MM Algorithms for Bradley-Terry Models

Milan Vojnovic, Se-Young Yun, Kaifang ZhouAISTATS 2020 · OpenReview

Abstract

We present tight convergence rate bounds for gradient descent (GD) and minorize-maximization (MM) algorithms for maximum likelihood (ML) estimation and maximum a posteriori probability (MAP) estimation of the Bradley-Terry model. By bridging optimization theory and graph theory, we demonstrate that the convergence speed of these algorithms is fundamentally linked to the connectivity of the underlying comparison graph. Our results provide the first tight bounds for these iterative methods, revealing a critical "slow convergence" regime in MAP estimation when the prior is non-informative.

Introduction

Ranking items based on pairwise comparisons is a foundational problem in statistics and machine learning, with applications ranging from sports analytics to recommendation systems. The Bradley-Terry model serves as the standard framework for this task. While iterative algorithms like Gradient Descent (GD) and Minorize-Maximization (MM) are widely used to find the Maximum Likelihood (ML) or Maximum A Posteriori (MAP) estimates, their precise convergence rates have remained largely unquantified. This paper provides a rigorous theoretical analysis of these rates, establishing tight bounds that depend on the structural properties of the data.

Methodology: Graph Theory and Optimization

The authors bridge the gap between optimization theory and graph theory. Their approach involves mapping the Bradley-Terry optimization problem onto the properties of a "comparison graph," where items are nodes and comparisons are edges. We show that the optimization speed is dictated by two key graph metrics:

  1. Algebraic Connectivity ($a(\mathbf{M})$): A measure of how well-connected the graph is.
  2. Maximum Degree ($d(\mathbf{M})$): The maximum number of comparisons involving a single item.

By applying new general convergence theorems for smooth, strongly convex functions, we derive bounds that link these graph properties directly to the number of iterations required for convergence.

Datasets and Empirical Validation

The researchers validated their theoretical bounds using both synthetic simulations and three diverse real-world datasets: GIFGIF (user evaluations of images), Chess (match results), and NASCAR (multi-item racing results). As shown in Table 1, real-world datasets exhibit varying degrees of connectivity, which significantly impacts algorithmic performance.

Table 1: Statistics of real-world datasets, highlighting the connectivity metrics $a(\mathbf{M})$ and $d(\mathbf{M})$ that drive convergence rates.

Key Results and Discussion

MM as "Optimal" Gradient Descent

A significant insight from our work is that MM algorithms effectively behave like GD with an optimal constant step size. This explains the practical robustness of MM: it achieves the best possible linear convergence rate without the need for manual hyperparameter tuning.

The Connectivity Bottleneck and MAP Discontinuity

For ML estimation, the convergence time is proportional to the ratio $d(\mathbf{M})/a(\mathbf{M})$. In scenarios where data is poorly connected—such as two groups of items that rarely compete—the algorithm's progress is critically slowed.

Perhaps most surprisingly, we identify a "MAP Discontinuity." While a Bayesian prior (parameterized by $\beta$) ensures a solution exists even for disconnected graphs, the convergence rate becomes $O(d(\mathbf{M})/\beta)$. As the prior becomes less informative (small $\beta$), the number of iterations required can increase by orders of magnitude, as observed in the GIFGIF dataset where iterations jumped from a few hundred to over 26,000.

Figure 2: Log-log plot of the number of iterations required for MM MAP and MM MLE as a function of the prior parameter $\beta$. The results confirm the $O(1/\beta)$ scaling predicted by our theory.

Conclusion

This work provides the first tight convergence rate bounds for GD and MM in the context of Bradley-Terry models. Our findings highlight the importance of graph connectivity in ranking problems and reveal potential pitfalls in Bayesian estimation with non-informative priors. Future work will extend this analysis to accelerated optimization methods and alternative prior structures.

Summary updated

Abstract

We present tight convergence rate bounds for gradient descent and MM algorithms for maximum likelihood (ML) estimation and maximum a posteriori probability (MAP) estimation of a popular Bayesian in...
BibTeX
@inproceedings{vojnovic2020convergence,
  author = {Milan Vojnovic and Se-Young Yun and Kaifang Zhou},
  title = {{Convergence Rates of Gradient Descent and MM Algorithms for Bradley-Terry Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=Oeo2MWocB8},
}
Figure