SCIENCE@home

Robust Estimation for Random Graphs

Jayadev Acharya,Ayush Jain,Gautam Kamath,A. Suresh,Huanyu Zhang

Published 2021 in Annual Conference Computational Learning Theory

ABSTRACT

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.

PUBLICATION RECORD

  • Publication year

    2021

  • Venue

    Annual Conference Computational Learning Theory

  • Publication date

    2021-11-09

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 2111.05320
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-62 of 62 references · Page 1 of 1

CITED BY

Showing 1-9 of 9 citing papers · Page 1 of 1