[YPNG] YPNG Friday 17 October 2014

[sekhar]

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 
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, 
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 
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 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.

Regards,
sekhar