Towards optimal estimation of bivariate isotonic matrices with unknown permutations
From MaRDI portal
Publication:1996765
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3152611 (Why is no real title available?)
- scientific article; zbMATH DE number 3073477 (Why is no real title available?)
- Active ranking from pairwise comparisons and when parametric assumptions do not help
- Binary choice probabilities: on the varieties of stochastic transitivity
- Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems
- Community detection and stochastic block models: recent developments
- Computational implications of reducing data to sufficient statistics
- Entropy estimate for high-dimensional monotonic functions
- Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
- Estimation in Tournaments and Graphs Under Monotonicity Constraints
- Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
- Isotonic regression in general dimensions
- Learning from comparisons and choices
- Matrix estimation by universal singular value thresholding
- Minimax rates and efficient algorithms for noisy sorting
- Minimax rates in permutation estimation for feature matching
- Noisy sorting without resampling
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- On matrix estimation under monotonicity constraints
- Optimal rates of statistical seriation
- Oracle inequalities for network models and sparse graphon estimation
- Rank Centrality: Ranking from Pairwise Comparisons
- Rate of convergence of nonparametric estimates of maximum-likelihood type
- Rate-optimal graphon estimation
- Restricted strong convexity and weighted matrix completion: optimal bounds with noise
- Risk bounds in isotonic regression
- Simple, Robust and Optimal Ranking from Pairwise Comparisons
- Spectral methods meet EM: a provably optimal algorithm for crowdsourcing
- 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
- The method of moments and degree distributions for network models
- Topological sorting of large networks
- Worst-case versus average-case design for estimation from partial pairwise comparisons
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
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)
