[YPNG] YPNG Friday 17 October 2014

sekhar sekhar.tatikonda at yale.edu
Tue Oct 14 08:49:48 EDT 2014

Hi Everyone,

This Friday Chao Gao will talk about his recent work on:

Network analysis is becoming one of the most active research areas in 
Significant advances have been made recently on developing theories, 
and algorithms  for analyzing networks. However, there has been little  
study on optimal estimation. In this paper, we establish optimal rate of 
for graphon estimation. For the stochastic block model with k clusters, 
the optimal
rate under the mean squared error is n^{-1}\log k+(k/n)^2. The minimax 
upper bound
improves the existing results in literature through a technique of 
solving a quadratic
equation. When k\leq\sqrt{n\log n}, as the number of the cluster k 
grows, the minimax
rate grows slowly with only a logarithmic rate n^{-1}\log k. A key step 
to establish the
lower bound is to construct a novel subset of the parameter space and 
apply Fano's
lemma, from which we see the distinction of the nonparametric graphon 
problem from classical nonparametric regression, due to the lack of 
of the order of nodes in exchangeable random graph models.  As an immediate
application, we consider nonparametric graphon estimation in a Holder 
class with
smoothness \alpha.  When the smoothness \alpha\geq 1, the optimal rate 
of convergence
is n^{-1}\log n, independent of \alpha, while for \alpha\in (0,1), the 
rate is
n^{-\frac{2\alpha}{\alpha+1}},  which is, to our surprise, identical to 
the classical
nonparametric rate.

See you Friday at 11 in the Stat's classroom.


More information about the YPNG mailing list