Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials

arXiv:2308.15728v3 Announce Type: replace-cross
Abstract: Graphon estimation has been one of the most fundamental problems in network analysis and has received considerable attention in the past decade. From the statistical perspective, the minimax error rate of graphon estimation has been established by Gao et al (2015) for both stochastic block model and nonparametric graphon estimation. The statistical optimal estimators are based on constrained least squares and have computational complexity exponential in the dimension. From the computational perspective, the best-known polynomial-time …

abstract analysis arxiv attention block computational cs.cc cs.ds error fundamental low math.st minimax network perspective rate replace statistical stat.ml stat.th stochastic type via