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

arXiv comment30 pages, 1 figure. Accepted for presentation at Conference on Learning Theory (COLT) 2018

References in corpus (16)

• Matrix estimation by Universal Singular Value Thresholding
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Concentration around the mean for maxima of empirical processes
• Noisy Sorting Without Resampling
• Spectral MLE: Top-$K$ Rank Aggregation from Pairwise Comparisons
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
• Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels
• A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
• Minimax rates in permutation estimation for feature matching
• Exact Exponent in Optimal Rates for Crowdsourcing
• Maximum Selection and Ranking under Noisy Comparisons
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Learning from Comparisons and Choices
• Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
• Reducing Crowdsourcing to Graphon Estimation, Statistically
• Phase Transitions in Approximate Ranking

Cited by in corpus (2)

• A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
• Reconstruction of Line-Embeddings of Graphons