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

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 widetildemathcal O(n-3/4), thus narrowing the gap between widetildemathcal O(n-1) and widetildemathcal O(n-1/2), which were hitherto the rates of the most statistically and computationally efficient methods, respectively.