Towards optimal estimation of bivariate isotonic matrices with unknown permutations
未知排列下双变量保序矩阵的最优估计探索AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要主要研究通用矩阵估计；虽提及graphon应用，但不足以归入经济网络与干扰研究。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
未知排列下双变量保序矩阵的最优估计探索
- 研究问题
- 当矩阵行列的排序未知，且只能获得带噪声的部分或全部元素时，如何兼顾估计误差与计算效率来恢复双变量保序矩阵？
- 方法与思路
- 作者设计并分析多项式时间算法，在两种度量下研究估计表现，同时通过锥检验问题的极小极大半径上下界刻画统计难度。
- 材料陈述的贡献
- 摘要称，算法在两种度量下改进已有结果，并在某些设定中实现计算高效的极小极大最优估计，还给出部分锥检验的匹配上下界。
- 阅读关注点
- 应核对两种误差度量、观测与噪声设定、允许的未知排列范围，以及实现极小极大最优性的具体场景和计算复杂度。
- 阅读边界
- 所给OpenAlex索引摘要未注明稿件版本；最优性仅限摘要所称的某些设定，具体速率、条件及与会议结果的关系需查全文。
原文摘要
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. (A corollary of Theorem 3.5 of this paper was presented at the Conference on Learning Theory (COLT) 2018, and a statement of this result appears in the abstract (In Proceedings of the 31st Conference On Learning Theory (2018) 2037–2042 PMLR).)