Graph Resistance and Learning from Pairwise Comparisons
(2019) 36th International Conference on Machine Learning (ICML2019) — Location: Long Beach, California (10.June.2019)
Files
190200141.pdf
Open Access - Adobe PDF
- 589.02 KB
Details
- Authors
- Abstract
- We consider the problem of learning the qualities of a collection of items by performing noisy comparisonsamongthem. Followingthestandard 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 prove that, after a known transition period, the relevant graph-theoretic quantity is the square root of the resistance of the comparison graph. Specifically, we provide an algorithm that is minimax optimal. The algorithm has a relative error decaythatscaleswiththesquarerootofthegraph resistance, and provide a matching lower bound (up to log factors). The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, outperforms earlier results.
- Affiliations
Citations
Hendrickx, J., Olchevsky, A., & Saligrama, V. (2019). Graph Resistance and Learning from Pairwise Comparisons. PMLR - Proceedings of Machine Learning Research, 97, 2702-2711. https://hdl.handle.net/2078.5/254764 (Original work published 2019)