Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model

arXiv:2607.22221v1 Announce Type: cross 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.

Source: arXiv cs.LG | 2026-07-27