Towards optimal estimation of bivariate isotonic matrices with unknown permutations

DOI10.1214/19-AOS1925zbMath1490.62129arXiv1806.09544MaRDI QIDQ1996765

Cheng Mao, Ashwin Pananjady, Martin J. Wainwright

Publication date: 26 February 2021

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items

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

Uses Software

• AS 206

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rate-optimal graphon estimation
• Oracle inequalities for network models and sparse graphon estimation
• The method of moments and degree distributions for network models
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• The geometry of hypothesis testing over convex cones: generalized likelihood ratio tests and minimax radii
• Computational implications of reducing data to sufficient statistics
• Binary choice probabilities: on the varieties of stochastic transitivity
• Optimal rates of statistical seriation
• Rate of convergence of nonparametric estimates of maximum-likelihood type
• Risk bounds in isotonic regression
• Worst-case versus average-case design for estimation from partial pairwise comparisons
• Active ranking from pairwise comparisons and when parametric assumptions do not help
• Isotonic regression in general dimensions
• Matrix estimation by universal singular value thresholding
• On matrix estimation under monotonicity constraints
• Entropy estimate for high-dimensional monotonic functions
• Minimax rates in permutation estimation for feature matching
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
• Topological sorting of large networks
• Community Detection and Stochastic Block Models
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Minimax Rates and Efficient Algorithms for Noisy Sorting
• Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems
• Estimation in Tournaments and Graphs Under Monotonicity Constraints
• Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Rank Centrality: Ranking from Pairwise Comparisons