Bad local minima exist in the stochastic block model
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914886624215040 |
|---|---|
| author | Coja-Oghlan, Amin Krieg, Lena Lawnik, Johannes Christian Scheftelowitsch, Olga |
| author_facet | Coja-Oghlan, Amin Krieg, Lena Lawnik, Johannes Christian Scheftelowitsch, Olga |
| contents | We study the disassortative stochastic block model with three communities, a well-studied model of graph partitioning and Bayesian inference for which detailed predictions based on the cavity method exist [Decelle et al. (2011)]. We provide strong evidence that for a part of the phase where efficient algorithms exist that approximately reconstruct the communities, inference based on maximum a posteriori (MAP) fails. In other words, we show that there exist modes of the posterior distribution that have a vanishing agreement with the ground truth. The proof is based on the analysis of a graph colouring algorithm from [Achlioptas and Moore (2003)]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17851 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bad local minima exist in the stochastic block model Coja-Oghlan, Amin Krieg, Lena Lawnik, Johannes Christian Scheftelowitsch, Olga Statistics Theory Discrete Mathematics Information Theory Mathematical Physics Probability 05C80 (Primary) 62B10, 68R10 (Secondary) We study the disassortative stochastic block model with three communities, a well-studied model of graph partitioning and Bayesian inference for which detailed predictions based on the cavity method exist [Decelle et al. (2011)]. We provide strong evidence that for a part of the phase where efficient algorithms exist that approximately reconstruct the communities, inference based on maximum a posteriori (MAP) fails. In other words, we show that there exist modes of the posterior distribution that have a vanishing agreement with the ground truth. The proof is based on the analysis of a graph colouring algorithm from [Achlioptas and Moore (2003)]. |
| title | Bad local minima exist in the stochastic block model |
| topic | Statistics Theory Discrete Mathematics Information Theory Mathematical Physics Probability 05C80 (Primary) 62B10, 68R10 (Secondary) |
| url | https://arxiv.org/abs/2407.17851 |