Oracle Inequalities for Network Models and Sparse Graphon Estimation

• Activity Number: 406
• Type: Invited
• Date/Time: Tuesday, August 2, 2016 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Alexandre Tsybakov and Olga Klopp* and Nicolas Verzelen
• Companies: ENSAE and University Paris 10/CREST and INRA
• Keywords: oracle inequality ; networks ; stochastic block model ; optimal rates ; graphon estimation

Abstract

Inhomogeneous random graph models encompass many network models such as stochastic block models and latent position models. In this paper, we study two estimators - the ordinary block constant least squares estimator, and its restricted version. We show that they satisfy oracle inequalities with respect to the block constant oracle. As a consequence, we derive optimal rates of estimation of the probability matrix. Our results cover the important setting of sparse networks. Nonparametric rates for graphon estimation in the L2 norm are also derived when the probability matrix is sampled according to a graphon model. The results shed light on the differences between estimation under the empirical loss (the probability matrix estimation) and under the integrated loss (the graphon estimation).