Breaking the $1/\sqrtn$ Barrier: Faster Rates for Permutationbased Models in Polynomial Time
[edit]
Proceedings of the 31st Conference On Learning Theory, PMLR 75:20372042, 2018.
Abstract
Many applications, including rank aggregation and crowdlabeling, 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 polynomialtime 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.
Related Material


