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.
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 |
Archive Staff Only
 |
View Item |
