Minimax Rates for Robust Community Detection
Minimax Rates for Robust Community Detection
复制标题
用于稳健社区检测的极小极大率
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ankur Moitra
中科院分区：
文献类型：
--
作者：
Allen Liu;Ankur Moitra
在这项工作中，我们研究了具有对抗性节点损坏的随机块模型中的社区检测问题。我们的主要结果是一种有效的算法，可以容忍 $epsilon$ 部分的损坏并实现错误 $O(epsilon)+e^{-frac{C}{2}(1pm o(1))}$，其中 $C=(sqrt{a}-sqrt{b})^{2}$ 是信噪比，$a/n$ 和 $b/n$ 是社区间和社区内连接概率分别。这些界限本质上与 SBM 的极小极大速率相匹配，没有损坏。我们还为 $mathbb{Z}_{2}$ 同步提供了强大的算法。我们算法的核心是一个新的半定程序，它使用全局信息来稳健地提高粗略聚类的准确性。此外，我们表明我们的算法具有双重鲁棒性，因为它们在更具挑战性的噪声模型中工作，该模型将对抗性损坏与来自半随机模型的无限单调变化混合在一起。
In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolerate an $epsilon$-fraction of corruptions and achieves error $O(epsilon)+e^{-frac{C}{2}(1pm o(1))}$ where $C=(sqrt{a}-sqrt{b})^{2}$ is the signal-to-noise ratio and $a/n$ and $b/n$ are the inter-community and intra-community connection probabilities respectively. These bounds essentially match the minimax rates for the SBM without corruptions. We also give robust algorithms for $mathbb{Z}_{2}$-synchronization. At the heart of our algorithm is a new semidefinite program that uses global information to robustly boost the accuracy of a rough clustering. Moreover, we show that our algorithms are doubly-robust in the sense that they work in an even more challenging noise model that mixes adversarial corruptions with unbounded monotone changes, from the semi-random model.
登录
查看更多内容
DOI：
10.1214/15-aap1145
发表时间：
2013-09
期刊：
--
影响因子：
--
作者：
Elchanan Mossel;Joe Neeman;A. Sly
通讯作者：
Elchanan Mossel;Joe Neeman;A. Sly
DOI：
--
发表时间：
2017-03
期刊：
--
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通过 SDP 稳健地实现同步和块模型中的贝叶斯错误率
影响因子：
2.5
作者：
Fei, Yingjie;Chen, Yudong
通讯作者：
Chen, Yudong
DOI：
--
发表时间：
2021-11
期刊：
--
影响因子：
--
作者：
Jayadev Acharya;Ayush Jain;Gautam Kamath;A. Suresh;Huanyu Zhang
通讯作者：
Jayadev Acharya;Ayush Jain;Gautam Kamath;A. Suresh;Huanyu Zhang
鲁棒地学习 k 个任意高斯的混合
DOI：
10.1145/3519935.3519953
发表时间：
2022
期刊：
Symposium on Theory of Computation
影响因子：
--
作者：
Bakshi, Ainesh;Diakonikolas, Ilias;Jia, He;Kane, Daniel M.;Kothari, Pravesh K.;Vempala, Santosh S.
通讯作者：
Vempala, Santosh S.