Name
Title | ||
|---|---|---|
Breaking the $1/\sqrtn$ 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 polynomial-time algorithms that improve 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 O(n^{-3/4})), thus narrowing the gap between (widetilde O(n^{-1})) and (widetilde O(n^{-1/2})), which were hitherto the rates of the most statistically and computationally efficient methods, respectively. |
Year | Venue | Field |
|---|---|---|
2018 | COLT | Row and column spaces,Mathematical optimization,Combinatorics,Normalization (statistics),Matrix (mathematics),Permutation,Matrix norm,Isotonic,Bivariate analysis,Time complexity,Mathematics |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng Mao | 1 | 6 | 2.47 |
| Ashwin Pananjady | 2 | 40 | 9.69 |
| Martin J. Wainwright | 3 | 7398 | 533.01 |