UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Uniform estimation in stochastic block models is slow

Castillo, I; Orbanz, P; (2022) Uniform estimation in stochastic block models is slow. Electronic Journal of Statistics , 16 (1) pp. 2947-3000. 10.1214/22-EJS2014. Green open access

[thumbnail of 22-EJS2014.pdf]
Preview
Text
22-EJS2014.pdf - Published Version

Download (635kB) | Preview

Abstract

We explicitly quantify the empirically observed phenomenon that estimation under a stochastic block model (SBM) is hard if the model contains classes that are similar. More precisely, we consider estimation of certain functionals of random graphs generated by a SBM. The SBM may or may not be sparse, and the number of classes may be fixed or grow with the number of vertices. Minimax lower and upper bounds of estimation along specific submodels are derived. The results are nonasymptotic and imply that uniform estimation of a single connectivity parameter is much slower than the expected asymptotic pointwise rate. Specifically, the uniform quadratic rate does not scale as the number of edges, but only as the number of vertices. The lower bounds are local around any possible SBM. An analogous result is derived for functionals of a class of smooth graphons.

Type: Article
Title: Uniform estimation in stochastic block models is slow
Open access status: An open access version is available from UCL Discovery
DOI: 10.1214/22-EJS2014
Publisher version: https://doi.org/10.1214/22-EJS2014
Language: English
Additional information: This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/)
UCL classification: UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Gatsby Computational Neurosci Unit
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences
UCL
URI: https://discovery.ucl.ac.uk/id/eprint/10150325
Downloads since deposit
21Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item