Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model (arxiv.org)
arXiv:2607.22221v1 Announce Type: new
Abstract: Zermelo's algorithm is a classical method for computing the maximum likelihood estimator in the Bradley--Terry (BT) model, but its convergence can be slow in practice. To accelerate computation, Newman introduced a family of Zermelo-type fixed-point iterations parameterized by $\alpha$, with Zermelo's algorithm recovered at $\alpha=1$. Empirical evidence suggests that the choice $\alpha=0$ often converges substantially faster, making it a promising alternative, yet the mechanism underlying this acceleration remains elusive. This paper provides theoretical insight into this phenomenon through a systematic local convergence analysis. We derive closed-form expressions for local convergence factors under synchronous and asynchronous updates and analyze their dependence on $\alpha$ via spectral analysis of the associated Jacobian matrices. For synchronous updates, we show that the algorithm may fail to converge when $\alpha<1$, and its local convergence factor is quasi-convex in $\alpha$ under the population BT model. In contrast, asynchronous updates are always locally convergent, and their local convergence factor is provably monotonically increasing in $\alpha$ under the population BT model of consistently ordered bipartite comparison graphs, establishing the optimality of $\alpha=0$ in this setting. We further establish asymptotic approximation results for the population convergence factors under the BT model, justifying their practical relevance. Numerical experiments on synthetic and real-world datasets confirm the theory. Our analysis complements existing convergence results and shows that the acceleration of $\alpha=0$ arises not only from the parameter choice but, more importantly, from the use of asynchronous updates.
Abstract: Zermelo's algorithm is a classical method for computing the maximum likelihood estimator in the Bradley--Terry (BT) model, but its convergence can be slow in practice. To accelerate computation, Newman introduced a family of Zermelo-type fixed-point iterations parameterized by $\alpha$, with Zermelo's algorithm recovered at $\alpha=1$. Empirical evidence suggests that the choice $\alpha=0$ often converges substantially faster, making it a promising alternative, yet the mechanism underlying this acceleration remains elusive. This paper provides theoretical insight into this phenomenon through a systematic local convergence analysis. We derive closed-form expressions for local convergence factors under synchronous and asynchronous updates and analyze their dependence on $\alpha$ via spectral analysis of the associated Jacobian matrices. For synchronous updates, we show that the algorithm may fail to converge when $\alpha<1$, and its local convergence factor is quasi-convex in $\alpha$ under the population BT model. In contrast, asynchronous updates are always locally convergent, and their local convergence factor is provably monotonically increasing in $\alpha$ under the population BT model of consistently ordered bipartite comparison graphs, establishing the optimality of $\alpha=0$ in this setting. We further establish asymptotic approximation results for the population convergence factors under the BT model, justifying their practical relevance. Numerical experiments on synthetic and real-world datasets confirm the theory. Our analysis complements existing convergence results and shows that the acceleration of $\alpha=0$ arises not only from the parameter choice but, more importantly, from the use of asynchronous updates.
Comments