Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-Based Models in Polynomial Time
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.
Cite
Text
Mao et al. "Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-Based Models in Polynomial Time." Annual Conference on Computational Learning Theory, 2018.Markdown
[Mao et al. "Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-Based Models in Polynomial Time." Annual Conference on Computational Learning Theory, 2018.](https://mlanthology.org/colt/2018/mao2018colt-breaking/)BibTeX
@inproceedings{mao2018colt-breaking,
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 = {Annual Conference on Computational Learning Theory},
year = {2018},
pages = {2037-2042},
url = {https://mlanthology.org/colt/2018/mao2018colt-breaking/}
}