# Breaking the 1/√n Barrier: Faster Rates for Permutation-based Models in Polynomial Time

arXiv: https://arxiv.org/abs/1802.09963 · HTML: https://mlsanity.com/paper/1802.09963/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2018.

## Built on by (most cited first, 3 of 3)

- [Active Ranking of Experts Based on their Performances in Many Tasks](https://mlsanity.com/paper/2306.02628/) (2023)
- [Computationally efficient reductions between some statistical models](https://mlsanity.com/paper/2402.07717/) (2024)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

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 × n matrix can be estimated efficiently in the normalized Frobenius norm at rate widetildemathcal O(n-3/4), thus narrowing the gap between widetildemathcal O(n-1) and widetildemathcal O(n-1/2), which were hitherto the rates of the most statistically and computationally efficient methods, respectively.