Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation

摘要

Motivated by applications in crowd-sourcing and rank aggregation, a recent line of work has studied the problem of estimating an $n imes n$ bivariate isotonic matrix with an unknown permutation acting on its rows (and possibly another unknown permutation acting on its columns) from partial and noisy observations. There are wide and persistent computational vs. statistical gaps for this problem. It is known that the minimax optimal rate is $widetilde{O}(n^{-1})$ when error is measured in average squared Frobenius norm. However the best known polynomial time computable estimator due to cite{coltpaper} achieves the rate $widetilde{O}(n^{-rac{3}{4}})$, and this is the natural barrier to approaches based on using local statistics to figure out the relative order of pairs of rows without using information from the rest of the matrix. Here we introduce a framework for exploiting global information in shape-constrained estimation problems. In the case when only the rows are permuted, we give an algorithm that achieves error rate $O(n^{-1 + o(1)})$, which essentially closes the computational vs. statistical gap for this problem. When both the rows and columns are permuted, we give an improved algorithm that achieves error rate $O(n^{-rac{5}{6} + o(1)})$. Additionally, all of our algorithms run in nearly linear time.