# [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
statistics.
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
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