Network analysis is becoming one of the most active research areas in statistics. Significant advances have been made recently on developing theories, methodologies and algorithms for analyzing networks. However, there has been little fundamental study on optimal estimation. In this paper, we establish optimal rate of convergence for graphon estimation. For the stochastic block model with k clusters, we show that the optimal rate under the mean squared error is n −1 log k + k 2 /n 2 . The minimax upper bound improves the existing results in literature through a technique of solving a quadratic equation. When k ≤ √ n log n, as the number of the cluster k grows, the minimax rate grows slowly with only a logarithmic order n −1 log k. A key step to establish the lower bound is to construct a novel subset of the parameter space and then apply Fano's lemma, from which we see a clear distinction of the nonparametric graphon estimation problem from classical nonparametric regression, due to the lack of identifiability of the order of nodes in exchangeable random graph models. As an immediate application, we consider nonparametric graphon estimation in a Hölder class with smoothness α. When the smoothness α ≥ 1, the optimal rate of convergence is n −1 log n, independent of α, while for α ∈ (0, 1), the rate is n − 2α α+1 , which is, to our surprise, identical to the classical nonparametric rate. 1. Introduction. Network analysis [17] has gained cosiderable research interests in both theories [7] and applications [43, 16] . A lot of recent work has been focusing on studying networks from a nonparametric perspective [7] , following the deep advancement in exchangeable arrays [3, 25, 27, 13] . In this paper, we study the fundamental limits in estimating the underlying generating mechanism of network models, called graphon. Though various algorithms have been proposed and analyzed [10, 38, 44, 2, 9] , it is not clear whether the convergence rates obtained in these works can be improved, and not clear what the differences and connections are between nonparametric graphon estimation and classical nonparametric regression. The results obtained in this paper provide answers to those questions. We found many existing results in literature are not sharp. Nonparametric graphon estima-
This SAS estimator is consistent and reaches the rate of convergence n −1 log n. This rate matches with the optimal rate in general graphon estimation without the assumption of strict monotonicity of degree REF .
Rate-optimal graphon estimation
Annals of Statistics 2015, Vol. 43, No. 6, 2624-2652
Mathematics