Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
arXiv:1806.09544
Abstract
Many applications, including rank aggregation, crowd-labeling, and graphon estimation, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and/or columns. We consider the problem of estimating an unknown matrix in this class, based on noisy observations of (possibly, a subset of) its entries. We design and analyze polynomial-time algorithms that improve upon the state of the art in two distinct metrics, showing, in particular, that minimax optimal, computationally efficient estimation is achievable in certain settings. Along the way, we prove matching upper and lower bounds on the minimax radii of certain cone testing problems, which may be of independent interest.
arXiv comment60 pages, 1 figure. This paper is a longer version of the paper arXiv:1802.09963 v3, which appeared in part as a 4-page extended abstract at Conference on Learning Theory (COLT) 2018. This paper studies the problem in more general settings and in another error metric. This version corrects a statement in Theorem 2 of v1
References in corpus (17)
- Matrix estimation by Universal Singular Value Thresholding
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Rate-optimal graphon estimation
- Noisy Sorting Without Resampling
- Nonparametric graphon estimation
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- A new perspective on least squares under convex constraint
- Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
- Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels
- A Consistent Histogram Estimator for Exchangeable Graph Models
- A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
- Minimax-optimal Inference from Partial Rankings
- Minimax rates in permutation estimation for feature matching
- Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons
- Exact Exponent in Optimal Rates for Crowdsourcing
- Maximum Selection and Ranking under Noisy Comparisons
- Phase Transitions in Approximate Ranking