Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
This work addresses a fundamental challenge in applications like rank aggregation and graphon estimation, offering improved computational efficiency and optimality.
The paper tackles the problem of estimating bivariate isotonic matrices with unknown permutations from noisy observations, and presents polynomial-time algorithms that achieve minimax optimal estimation in certain settings.
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.