Breaking the 1/√n Barrier: Faster Rates for Permutation-based Models in Polynomial Time

Cheng Mao, Ashwin Pananjady, Martin J. Wainwright
Proceedings of the 31st Conference On Learning Theory, PMLR 75:2037-2042, 2018.

Abstract

Many applications, including rank aggregation and crowd-labeling, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and columns. We consider the problem of estimating such a matrix based on noisy observations of a subset of its entries, and design and analyze a polynomial-time algorithm that improves upon the state of the art. In particular, our results imply that any such n×n matrix can be estimated efficiently in the normalized Frobenius norm at rate ˜O(n−3/4), thus narrowing the gap between ˜O(n−1) and ˜O(n−1/2), which were hitherto the rates of the most statistically and computationally efficient methods, respectively.

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-mao18a, title = {Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time}, author = {Mao, Cheng and Pananjady, Ashwin and Wainwright, Martin J.}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {2037--2042}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/mao18a/mao18a.pdf}, url = {https://proceedings.mlr.press/v75/mao18a.html}, abstract = {Many applications, including rank aggregation and crowd-labeling, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and columns. We consider the problem of estimating such a matrix based on noisy observations of a subset of its entries, and design and analyze a polynomial-time algorithm that improves upon the state of the art. In particular, our results imply that any such $n \times n$ matrix can be estimated efficiently in the normalized Frobenius norm at rate $\widetilde{\mathcal O}(n^{-3/4})$, thus narrowing the gap between $\widetilde{\mathcal O}(n^{-1})$ and $\widetilde{\mathcal O}(n^{-1/2})$, which were hitherto the rates of the most statistically and computationally efficient methods, respectively.} }
Endnote
%0 Conference Paper %T Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time %A Cheng Mao %A Ashwin Pananjady %A Martin J. Wainwright %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-mao18a %I PMLR %P 2037--2042 %U https://proceedings.mlr.press/v75/mao18a.html %V 75 %X Many applications, including rank aggregation and crowd-labeling, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and columns. We consider the problem of estimating such a matrix based on noisy observations of a subset of its entries, and design and analyze a polynomial-time algorithm that improves upon the state of the art. In particular, our results imply that any such $n \times n$ matrix can be estimated efficiently in the normalized Frobenius norm at rate $\widetilde{\mathcal O}(n^{-3/4})$, thus narrowing the gap between $\widetilde{\mathcal O}(n^{-1})$ and $\widetilde{\mathcal O}(n^{-1/2})$, which were hitherto the rates of the most statistically and computationally efficient methods, respectively.
APA
Mao, C., Pananjady, A. & Wainwright, M.J.. (2018). Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:2037-2042 Available from https://proceedings.mlr.press/v75/mao18a.html.

Related Material