Robust Estimation for Random Graphs

Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, Huanyu Zhang
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:130-166, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-acharya22a, title = {Robust Estimation for Random Graphs}, author = {Acharya, Jayadev and Jain, Ayush and Kamath, Gautam and Suresh, Ananda Theertha and Zhang, Huanyu}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {130--166}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/acharya22a/acharya22a.pdf}, url = {https://proceedings.mlr.press/v178/acharya22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Robust Estimation for Random Graphs %A Jayadev Acharya %A Ayush Jain %A Gautam Kamath %A Ananda Theertha Suresh %A Huanyu Zhang %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-acharya22a %I PMLR %P 130--166 %U https://proceedings.mlr.press/v178/acharya22a.html %V 178 %X 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.
APA
Acharya, J., Jain, A., Kamath, G., Suresh, A.T. & Zhang, H.. (2022). Robust Estimation for Random Graphs. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:130-166 Available from https://proceedings.mlr.press/v178/acharya22a.html.

Related Material