Processing math: 14%

acharya22a@v178@PMLR

Total: 1

#1 Robust Estimation for Random Graphs [PDF] [Copy] [Kimi] [REL]

Authors: Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, Huanyu Zhang

We study the problem of robustly estimating the parameter p of an Erdős-Rényi 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.

Subject: COLT.2022 - Accept