TOWARDS OPTIMAL ESTIMATION OF BIVARIATE ISOTONIC MATRICES WITH UNKNOWN PERMUTATIONS

• 成果类型: Article
• 署名作者: Mao, Cheng; Pananjady, Ashwin; Wainwright, Martin J.
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of California System; University of California Berkeley; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/19-AOS1925
• 发表日期: 2020
• 页码: 3183-3205
• 关键词: pairwise comparisons; Optimal Rates; probabilities; regression; ranking; models; bounds

摘要

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.(1)