Towards optimal estimation of bivariate isotonic matrices with unknown permutations

DOI10.1214/19-AOS1925zbMATH Open1490.62129arXiv1806.09544MaRDI QIDQ1996765FDOQ1996765

Authors: Cheng Mao, Ashwin Pananjady, Martin J. Wainwright 

Publication date: 26 February 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1806.09544

Recommendations

• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Optimal rates of statistical seriation
• On matrix estimation under monotonicity constraints
• Estimation of Monge matrices
• Matrix estimation by universal singular value thresholding

zbMATH Keywords

rankingpairwise comparisonscrowd-labelingpermutation-based modelsshape-constrained estimationstatistical-computational gap

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Statistical ranking and selection procedures (62F07) Estimation in multivariate analysis (62H12) Paired and multiple comparisons; multiple testing (62J15)

Cites Work

• Rate-optimal graphon estimation
• Matrix estimation by universal singular value thresholding
• Title not available (Why is that?)
• Community detection and stochastic block models: recent developments
• Title not available (Why is that?)
• The method of moments and degree distributions for network models
• Binary choice probabilities: on the varieties of stochastic transitivity
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Restricted strong convexity and weighted matrix completion: optimal bounds with noise
• Oracle inequalities for network models and sparse graphon estimation
• Entropy estimate for high-dimensional monotonic functions
• Rate of convergence of nonparametric estimates of maximum-likelihood type
• Risk bounds in isotonic regression
• Topological sorting of large networks
• Learning from comparisons and choices
• Noisy sorting without resampling
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
• The geometry of hypothesis testing over convex cones: generalized likelihood ratio tests and minimax radii
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Isotonic regression in general dimensions
• Worst-case versus average-case design for estimation from partial pairwise comparisons
• Computational implications of reducing data to sufficient statistics
• Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
• Rank Centrality: Ranking from Pairwise Comparisons
• Spectral methods meet EM: a provably optimal algorithm for crowdsourcing
• Optimal rates of statistical seriation
• Minimax rates in permutation estimation for feature matching
• Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems
• On matrix estimation under monotonicity constraints
• Estimation in Tournaments and Graphs Under Monotonicity Constraints
• Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
• Active ranking from pairwise comparisons and when parametric assumptions do not help
• Minimax rates and efficient algorithms for noisy sorting

Cited In (7)

• Optimal detection of the feature matching map in presence of noise and outliers
• Optimal permutation estimation in crowdsourcing problems
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Reconstruction of line-embeddings of graphons
• Optimal Permutation Recovery in Permuted Monotone Matrix Model
• Re-thinking high-dimensional mathematical statistics. Abstracts from the workshop held May 15--21, 2022
• Optimal rates of statistical seriation

Uses Software

• AS 206

This page was built for publication: Towards optimal estimation of bivariate isotonic matrices with unknown permutations

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