Graph Resistance and Learning from Pairwise Comparisons

Julien Hendrickx, Alexander Olshevsky, Venkatesh Saligrama
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:2702-2711, 2019.

Abstract

We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed “comparison graph” and every neighboring pair of items in this graph is compared k times according to the Bradley-Terry-Luce model (where the probability than an item wins a comparison is proportional the item quality). We are interested in how the relative error in quality estimation scales with the comparison graph in the regime where k is large. We show that, asymptotically, the relevant graph-theoretic quantity is the square root of the resistance of the comparison graph. Specifically, we provide an algorithm with relative error decay that scales with the square root of the graph resistance, and provide a lower bound showing that (up to log factors) a better scaling is impossible. The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, significantly outperforms earlier results.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-hendrickx19a, title = {Graph Resistance and Learning from Pairwise Comparisons}, author = {Hendrickx, Julien and Olshevsky, Alexander and Saligrama, Venkatesh}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {2702--2711}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/hendrickx19a/hendrickx19a.pdf}, url = {https://proceedings.mlr.press/v97/hendrickx19a.html}, abstract = {We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed “comparison graph” and every neighboring pair of items in this graph is compared k times according to the Bradley-Terry-Luce model (where the probability than an item wins a comparison is proportional the item quality). We are interested in how the relative error in quality estimation scales with the comparison graph in the regime where k is large. We show that, asymptotically, the relevant graph-theoretic quantity is the square root of the resistance of the comparison graph. Specifically, we provide an algorithm with relative error decay that scales with the square root of the graph resistance, and provide a lower bound showing that (up to log factors) a better scaling is impossible. The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, significantly outperforms earlier results.} }
Endnote
%0 Conference Paper %T Graph Resistance and Learning from Pairwise Comparisons %A Julien Hendrickx %A Alexander Olshevsky %A Venkatesh Saligrama %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-hendrickx19a %I PMLR %P 2702--2711 %U https://proceedings.mlr.press/v97/hendrickx19a.html %V 97 %X We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed “comparison graph” and every neighboring pair of items in this graph is compared k times according to the Bradley-Terry-Luce model (where the probability than an item wins a comparison is proportional the item quality). We are interested in how the relative error in quality estimation scales with the comparison graph in the regime where k is large. We show that, asymptotically, the relevant graph-theoretic quantity is the square root of the resistance of the comparison graph. Specifically, we provide an algorithm with relative error decay that scales with the square root of the graph resistance, and provide a lower bound showing that (up to log factors) a better scaling is impossible. The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, significantly outperforms earlier results.
APA
Hendrickx, J., Olshevsky, A. & Saligrama, V.. (2019). Graph Resistance and Learning from Pairwise Comparisons. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:2702-2711 Available from https://proceedings.mlr.press/v97/hendrickx19a.html.

Related Material