Minimax rates and efficient algorithms for noisy sorting

MaRDI QIDQ4617642zbMATH OpenFDO

Authors Cheng Mao, Jonathan Weed, Philippe Rigollet

Publication date 6 February 2019

Full work available at URL https://arxiv.org/abs/1710.10388, http://proceedings.mlr.press/v83/mao18a/mao18a.pdf

zbMATH Keywords

minimax estimationnoisy sortingpairwise comparisonspermutationsranking

Mathematics Subject Classification ID

Statistical ranking and selection procedures (62F07) Paired and multiple comparisons; multiple testing (62J15) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: There has been a recent surge of interest in studying permutation-based models for ranking from pairwise comparison data. Despite being structurally richer and more robust than parametric ranking models, permutation-based models are less well understood statistically and generally lack efficient learning algorithms. In this work, we study a prototype of permutation-based ranking models, namely, the noisy sorting model. We establish the optimal rates of learning the model under two sampling procedures. Furthermore, we provide a fast algorithm to achieve near-optimal rates if the observations are sampled independently. Along the way, we discover properties of the symmetric group which are of theoretical interest.

Recommendations

• Sorting from Noisier Samples
• Noisy sorting without resampling
• Sorting by swaps with noisy comparisons
• Active ranking from pairwise comparisons and when parametric assumptions do not help
• Worst-case versus average-case design for estimation from partial pairwise comparisons

Cited in

(15)

• Towards optimal estimation of bivariate isotonic matrices with unknown permutations
• Optimal detection of the feature matching map in presence of noise and outliers
• Iterative algorithm for discrete structure recovery
• Optimal full ranking from pairwise comparisons
• Optimal rates for estimation of two-dimensional totally positive distributions
• Worst-case versus average-case design for estimation from partial pairwise comparisons
• Estimation of Monge matrices
• Noisy sorting without resampling
• Efficient computation for the noisy MAX
• Asymptotically Optimal Sequential Design for Rank Aggregation
• Optimal permutation estimation in crowdsourcing problems
• External-memory sorting with comparison errors
• Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems
• Minimax optimal seriation in polynomial time

This page was built for publication: Minimax rates and efficient algorithms for noisy sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4617642)