11:26arXiv cs.LG@Dongmin Lee, Anuran Makur, Japneet Singh精选本文研究了在Bradley-Terry-Luce (BTL)模型下,当数据受到半随机对抗攻击(即某些边的采样概率被人为提升)时,谱排序算法的逐项误差表现。研究发现,未加权的谱方法性能高度依赖于生成图的谱性质,而通过对观测边进行适当重加权以恢复谱间隙,可以接近均匀采样图下的渐近性能。理论结果通过数值模拟得到了验证。这项工作为对抗环境下的排序算法提供了理论保证。论文谱排序BTL模型对抗鲁棒性逐项误差重加权推荐理由:做排序算法或对抗鲁棒性研究的团队,这篇论文给出了半随机对抗下谱方法的理论误差界,并提出了有效的重加权策略,值得关注。原文