Robust Estimation for Random Graphs
Robust Estimation for Random Graphs
复制标题
DOI：
--
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Jayadev Acharya;Ayush Jain;Gautam Kamath;A. Suresh;Huanyu Zhang
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;Ayush Jain;Gautam Kamath;A. Suresh;Huanyu Zhang
本文研究了Erd\H{o}s-R\'enyi随机图在n个节点上的参数p的鲁棒估计问题，其中n个节点中有一部分节点可能是不利损坏的.在证明了典型估计量的不足之后，我们设计了一个计算效率高的谱算法，该算法估计$p$的精度为$\tilde O（\sqrt{p（1-p）}/n + \gamma\sqrt{p（1-p）} /\sqrt{n}+ \gamma/n）$，其中$\gamma<1/60$。此外，我们给出了一个低效的算法，具有类似的精度为所有$\gamma<1/2$，信息理论的限制。最后，我们证明了一个近似匹配的统计下界，表明我们的算法的误差是最佳的对数因子。
We study the problem of robustly estimating the parameter $p$ of an Erd\H{o}s-R\'enyi random graph on $n$ nodes, where a $\gamma$ fraction of nodes may be adversarially corrupted. After showing the deficiencies of canonical estimators, we design a computationally-efficient spectral algorithm which estimates $p$ up to accuracy $\tilde O(\sqrt{p(1-p)}/n + \gamma\sqrt{p(1-p)} /\sqrt{n}+ \gamma/n)$ for $\gamma<1/60$. Furthermore, we give an inefficient algorithm with similar accuracy for all $\gamma<1/2$, the information-theoretic limit. Finally, we prove a nearly-matching statistical lower bound, showing that the error of our algorithms is optimal up to logarithmic factors.