COMPUTATIONAL LOWER BOUNDS FOR GRAPHON ESTIMATION VIA LOW-DEGREE POLYNOMIALS

• 成果类型: Article
• 署名作者: Luo, Yuetian; Gao, Chao
• 署名单位: University of Chicago; University of Chicago
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/24-AOS2437
• 发表日期: 2024
• 页码: 2318-2348
• 关键词: l-p theory; community detection; network models; convergent sequences; sparse submatrix; Minimax Rates; algorithms; barriers; arrays; LIMITS

摘要

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 (Ann. Statist. 43 (2015) 2624-2652) for both stochastic block model (SBM) 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 estimator is based on universal singular value thresholding (USVT), but it can only achieve a much slower estimation error rate than the minimax one. It is natural to wonder if such a gap is essential. The computational optimality of the USVT or the existence of a computational barrier in graphon estimation has been a long-standing open problem. In this work, we take the first step toward it and provide rigorous evidence for the computational barrier in graphon estimation via lowdegree polynomials. Specifically, in SBM graphon estimation, we show that for low-degree polynomial estimators, their estimation error rates cannot be significantly better than that of the USVT under a wide range of parameter regimes and in nonparametric graphon estimation, we show low-degree polynomial estimators achieve estimation error rates strictly slower than the minimax rate. Our results are proved based on the recent development of lowdegree polynomials by (Ann. Statist. 50 (2022) 1833-1858), while we overcome a few key challenges in applying it to the general graphon estimation problem. By leveraging our main results, we also provide a computational lower bound on the clustering error for community detection in SBM with a growing number of communities and this yields a new piece of evidence for the conjectured Kesten-Stigum threshold for efficient community recovery. Finally, we extend our computational lower bounds to sparse graphon estimation and biclustering with additive Gaussian noise, and provide discussion on the optimality of our results.