2022-06-28-bong22a.md

title	booktitle	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model	Proceedings of the 39th International Conference on Machine Learning	Ranking problems based on pairwise comparisons, such as those arising in online gaming, often involve a large pool of items to order. In these situations, the gap in performance between any two items can be significant, and the smallest and largest winning probabilities can be very close to zero or one. Furthermore, each item may be compared only to a subset of all the items, so that not all pairwise comparisons are observed. In this paper, we study the performance of the Bradley-Terry-Luce model for ranking from pairwise comparison data under more realistic settings than those considered in the literature so far. In particular, we allow for near-degenerate winning probabilities and arbitrary comparison designs. We obtain novel results about the existence of the maximum likelihood estimator (MLE) and the corresponding $\ell_2$ estimation error without the bounded winning probability assumption commonly used in the literature and for arbitrary comparison graph topologies. Central to our approach is the reliance on the Fisher information matrix to express the dependence on the graph topologies and the impact of the values of the winning probabilities on the estimation risk and on the conditions for the existence of the MLE. Our bounds recover existing results as special cases but are more broadly applicable.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	bong22a	0	Generalized Results for the Existence and Consistency of the {MLE} in the Bradley-Terry-Luce Model	2160	2177	2160-2177	2160	false	Bong, Heejong and Rinaldo, Alessandro	given family Heejong Bong given family Alessandro Rinaldo	2022-06-28		Proceedings of the 39th International Conference on Machine Learning	162	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v162/bong22a/bong22a.pdf