2021/11/09 by Acharya, Jayadev, Jain, Ayush, Kamath, Gautam +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2111.05320
We study the problem of robustly estimating the parameter p of an Erdős-Rényi random graph on n nodes, where a γ 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 O(√(p(1-p))/n + γ√(p(1-p)) /√(n)+ γ/n) for γ< 1/60. Furthermore, we give an inefficient algorithm with similar accuracy for all γ<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.