Fetching the paper…

Reading the bibliography…

Sharp optimal recovery in the two-component Gaussian Mixture Model · Around

2018

Sharp optimal recovery in the two-component Gaussian Mixture Model

Ndaoud, Mohamed

Original
PDF
Post on X

Understand

This paper studies the problem of clustering in the two-component Gaussian mixture model where the centers are separated by $2\Delta$ for some $\Delta>0$.

We characterize the exact phase transition threshold, given by $$ \bar{\Delta}_n^{2} = \sigma^{2}\left(1 + \sqrt{1+\frac{2p}{n\log{n}}} \right)\log{n}, $$ such that perfect recovery of the communities is possible with high probability if $\Delta\ge(1+\varepsilon)\bar \Delta_n$, and impossible if $\Delta\le (1-\varepsilon)\bar \Delta_n$ for any constant $\varepsilon>0$.
This implies an elbow effect at a critical dimension $p^{*}=n\log{n}$.
We present a non-asymptotic lower bound for the corresponding minimax Hamming risk improving on existing results.

Built on

[author] Wu, YihongY. and Zhou, Harrison HH. H. (2019). Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O ⁡ ( n ) O(\sqrt{n}) iterations. arXiv preprint arXiv:1908.10935
Original
1908
Earlier work this paper cites.
[author] Löffler, MatthiasM., Zhang, Anderson YA. Y. and Zhou, Harrison HH. H. (2019). Optimality of spectral clustering for gaussian mixture model. arXiv preprint arXiv:1911.00538
Original
1911
Earlier work this paper cites.
[author] Ndaoud, MohamedM., Sigalla, SuzanneS. and Tsybakov, Alexandre BA. B. (2019). Improved clustering algorithms for the Bipartite Stochastic Block Model. arXiv preprint arXiv:1911.07987
Original
1911
Earlier work this paper cites.
[author] Lloyd, StuartS. (1982). Least squares quantization in PCM. IEEE transactions on information theory 28 129–137
1982
Earlier work this paper cites.
[author] Holland, Paul WP. W., Laskey, Kathryn BlackmondK. B. and Leinhardt, SamuelS. (1983). Stochastic blockmodels: First steps. Social networks 5 109–137
1983
Earlier work this paper cites.
[author] Chen, XiaohuiX. and Yang, YunY. (2020). Cutoff for exact recovery of Gaussian mixture models. arXiv preprint arXiv:2001.01194
Original
2001
Earlier work this paper cites.
[author] Vempala, SantoshS. and Wang, GrantG. (2004). A spectral algorithm for learning mixture models. Journal of Computer and System Sciences 68 841–860
2004
Earlier work this paper cites.
[author] Abbe, EmmanuelE., Fan, JianqingJ. and Wang, KaizhengK. (2020). An ℓ p \ell_{p} theory of PCA and spectral clustering. arXiv preprint arXiv:2006.14062
Original
2006
Earlier work this paper cites.
[author] Lehmann, Erich LE. L. and Casella, GeorgeG. (2006). Theory of point estimation. Springer Science & Business Media
2006
Earlier work this paper cites.
[author] Benaych-Georges, FlorentF. and Nadakuditi, Raj RaoR. R. (2012). The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis 111 120–135
2012
Earlier work this paper cites.

Similar

[author] Hsu, DanielD., Kakade, ShamS., Zhang, TongT. et al. (2012). A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability 17
2012
Cited alongside, same era.
[author] Abbe, EmmanuelE., Bandeira, Afonso SA. S. and Hall, GeorginaG. (2014). Exact recovery in the stochastic block model. arXiv preprint arXiv:1405.3267
Original
2014
Cited alongside, same era.
Feldman, V
2015
Cited alongside, same era.
Florescu, L
2016
Cited alongside, same era.
[author] Klusowski, Jason MJ. M. and Brinda, WDW. (2016). Statistical guarantees for estimating the centers of a two-component gaussian mixture by EM. arXiv preprint arXiv:1608.02280
Original
2016
Cited alongside, same era.

Then

[author] Xia, DongD. and Zhou, FanF. (2017). The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising. arXiv preprint arXiv:1707.01207
Original
2017
Later among the works it cites.
[author] Banks, JessJ., Moore, CristopherC., Vershynin, RomanR., Verzelen, NicolasN. and Xu, JiamingJ. (2018). Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization. IEEE Transactions on Information Theory
2018
Closest in time.
[author] Butucea, CristinaC., Ndaoud, MohamedM., Stepanova, Natalia AN. A. and Tsybakov, Alexandre BA. B. (2018). Variable selection with Hamming loss. The Annals of Statistics 46 1837–1875
2018
Closest in time.
[author] Fei, YingjieY. and Chen, YudongY. (2018). Hidden integrality of sdp relaxation for sub-gaussian mixture models. arXiv preprint arXiv:1803.06510
Original
2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

[author] Lu, YuY. and Zhou, Harrison HH. H. (2016). Statistical and Computational Guarantees of Lloyd’s Algorithm and its Variants. arXiv preprint arXiv:1612.02099

2016

Cited alongside, same era.

[author] Mixon, Dustin GD. G., Villar, SoledadS. and Ward, RachelR. (2016). Clustering subgaussian mixtures by semidefinite programming. arXiv preprint arXiv:1602.06612

2016

Cited alongside, same era.

[author] Abbe, EmmanuelE. (2017). Community detection and stochastic block models: recent developments. arXiv preprint arXiv:1703.10146

2017

Cited alongside, same era.

[author] Abbe, EmmanuelE., Fan, JianqingJ., Wang, KaizhengK. and Zhong, YiqiaoY. (2017). Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank. arXiv preprint arXiv:1709.09565

2017

Cited alongside, same era.

Royer, M

2017

Cited alongside, same era.

[author] Gao, ChaoC., Ma, ZongmingZ., Zhang, Anderson YA. Y., Zhou, Harrison HH. H. et al. (2018). Community detection in degree-corrected block models. The Annals of Statistics 46 2153–2185

2018

Closest in time.

[author] Giraud, ChristopheC. and Verzelen, NicolasN. (2018). Partial recovery bounds for clustering with the relaxed K K means. arXiv preprint arXiv:1807.07547

2018

Closest in time.

[author] Ndaoud, MohamedM. (2018). Interplay of minimax estimation and minimax support recovery under sparsity. arXiv preprint arXiv:1810.05478

2018

Closest in time.

[author] Vershynin, RomanR. (2018). High-dimensional probability: An introduction with applications in data science 47. Cambridge University Press

2018

Closest in time.

[author] Zhang, AnruA., Cai, T TonyT. T. and Wu, YihongY. (2018). Heteroskedastic PCA: Algorithm, Optimality, and Applications. arXiv preprint arXiv:1810.08316

2018

Closest in time.