Phase Transitions in Approximate Ranking
Phase Transitions in Approximate Ranking
复制标题
近似排名中的阶段转变
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Chao Gao
中科院分区：
文献类型：
--
作者：
Chao Gao
我们研究了两两相互作用的观测值的近似排序问题。目标是通过比较或协作的交互，从数据中估计$n$个对象的潜在等级。在近似排序模型的一般框架下，我们刻画了估计潜在秩的精确最优统计误差率。我们发现了重要的相变边界的最佳错误率。取决于信噪比（SNR）参数的值，作为SNR的函数的最佳速率是平凡的、多项式的、指数的或零。因此，四个相应的制度具有完全不同的错误行为。据我们所知，这种现象，特别是多项式和指数速率之间的相变，以前没有发现过。
We study the problem of approximate ranking from observations of pairwise interactions. The goal is to estimate the underlying ranks of $n$ objects from data through interactions of comparison or collaboration. Under a general framework of approximate ranking models, we characterize the exact optimal statistical error rates of estimating the underlying ranks. We discover important phase transition boundaries of the optimal error rates. Depending on the value of the signal-to-noise ratio (SNR) parameter, the optimal rate, as a function of SNR, is either trivial, polynomial, exponential or zero. The four corresponding regimes thus have completely different error behaviors. To the best of our knowledge, this phenomenon, especially the phase transition between the polynomial and the exponential rates, has not been discovered before.
用于噪声排序的极小极大率和高效算法
DOI：
--
发表时间：
2018
期刊：
Proceedings of Machine Learning Research
影响因子：
--
作者：
Mao, Cheng;Weed, Jonathan;Rigollet, Philippe
通讯作者：
Rigollet, Philippe