Fetching the paper…
Reading the bibliography…
We investigate the clustering performances of the relaxed $K$means in the setting of sub-Gaussian Mixture Model (sGMM) and Stochastic Block Model (SBM).
Probability Inequalities for Sums of Bounded Random Variables
Wassily Hoeffding · 1963
Earlier work this paper cites.
Least Squares Quantization in PCM
S. Lloyd · 1982
Earlier work this paper cites.
Stochastic blockmodels: First steps
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt · 1983
Earlier work this paper cites.
A Constant-Factor Approximation Algorithm for the k-Median Problem
Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys · 2002
Earlier work this paper cites.
A spectral algorithm for learning mixture models
Santosh Vempala and Grant Wang · 2002
Earlier work this paper cites.
On Spectral Learning of Mixtures of Distributions
Dimitris Achlioptas and Frank McSherry · 2005
Earlier work this paper cites.
K-means++: The Advantages of Careful Seeding
David Arthur and Sergei Vassilvitskii · 2007
Earlier work this paper cites.
Approximating K-means-type Clustering via Semidefinite Programming
Jiming Peng and Yu Wei · 2007
Earlier work this paper cites.
Minimax theory for high-dimensional gaussian mixtures with sparse mean separation
Martin Azizyan, Aarti Singh, and Larry Wasserman · 2013
Earlier work this paper cites.
Hanson-Wright inequality and sub-gaussian concentration
Mark Rudelson and Roman Vershynin · 2013
Earlier work this paper cites.
On semidefinite relaxations for the block model
A. A. Amini and E. Levina · 2014
Earlier work this paper cites.
Community detection in sparse networks via Grothendieck’s inequality
Olivier Guédon and Roman Vershynin · 2014
Earlier work this paper cites.
Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
Se-Young Yun and Alexandre Proutière · 2014
Earlier work this paper cites.
Relax, no need to round: Integrality of clustering formulations
Pranjal Awasthi, Afonso S Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, and Rachel Ward · 2015
Earlier work this paper cites.
The Hardness of Approximation of Euclidean k-means
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop · 2015
Earlier work this paper cites.
Community Detection in General Stochastic Block Models: Fundamental Limits and Efficient Algorithms for Recovery
Emmanuel Abbe and Colin Sandon · 2015
Earlier work this paper cites.
Model Assisted Variable Clustering: Minimax-optimal Recovery and Algorithms
F. Bunea, C. Giraud, X. Luo, M. Royer, and N. Verzelen · 2015
Cited alongside, same era.
Convexified Modularity Maximization for Degree-corrected Stochastic Block Models
Y. Chen, X. Li, and J. Xu · 2015
Cited alongside, same era.
Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery
Peter Chin, Anup Rao, and Van Vu · 2015
Cited alongside, same era.
Introduction to high-dimensional statistics
Christophe Giraud · 2015
Cited alongside, same era.
On the tightness of an SDP relaxation of k-means
Takayuki Iguchi, Dustin G Mixon, Jesse Peterson, and Soledad Villar · 2015
Cited alongside, same era.
Consistency of spectral clustering in stochastic block models
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart · 2017
Later among the works it cites.
Exponential error rates of SDP for block models: Beyond Grothendieck’s inequality
Y. Fei and Y. Chen · 2017
Later among the works it cites.
Achieving Optimal Misclassification Proportion in Stochastic Block Models
Chao Gao, Zongming Ma, Anderson Y. Zhang, and Harrison H. Zhou · 2017
Later among the works it cites.
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins and Jerry Li · 2017
Later among the works it cites.
Better Agnostic Clustering Via Relaxed Tensor Norms
Pravesh K. Kothari and Jacob Steinhardt · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jing Lei and Alessandro Rinaldo · 2015
Cited alongside, same era.
A semidefinite program for unbalanced multisection in the stochastic block model
A. Perry and A. S. Wein · 2015
Cited alongside, same era.
PECOK: a convex optimization approach to variable clustering
Florentina Bunea, Christophe Giraud, Martin Royer, and Nicolas Verzelen · 2016
Cited alongside, same era.
A Semi-Definite Programming approach to low dimensional embedding for unsupervised clustering
S. Chrétien, C. Dombry, and A. Faivre · 2016
Cited alongside, same era.
Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
Yudong Chen and Jiaming Xu · 2016
Cited alongside, same era.
Asymptotic mutual information for the binary stochastic block model
Y. Deshpande, E. Abbe, and A. Montanari · 2016
Cited alongside, same era.
Semidefinite Programs for Exact Recovery of a Hidden Community
B. Hajek, Y. Wu, and J. Xu · 2016
Cited alongside, same era.
When do birds of a feather flock together? k-means, proximity, and conic programming
Xiaodong Li, Yang Li, Shuyang Ling, Thomas Strohmer, and Ke Wei · 2017
Later among the works it cites.
The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
Cristopher Moore · 2017
Later among the works it cites.
Clustering subgaussian mixtures by semidefinite programming
Dustin G Mixon, Soledad Villar, and Rachel Ward · 2017
Later among the works it cites.
Adaptive Clustering through Semidefinite Programming
M. Royer · 2017
Later among the works it cites.
On Learning Mixtures of Well-Separated Gaussians
O. Regev and A. Vijayaraghavan · 2017
Later among the works it cites.
Exact recovery in the Ising blockmodel
Q. Berthet, P. Rigollet, and P. Srivastava · 2018
Closest in time.
Xiaohui Chen and Yun Yang · 2018
Closest in time.
Hidden Integrality of SDP Relaxation for Sub-Gaussian Mixture Models
Y. Fei and Y. Chen · 2018
Closest in time.
Convex Relaxation Methods for Community Detection
Xiaodong Li, Yudong Chen, and Jiaming Xu · 2018
Closest in time.
Sharp optimal recovery in the Two Component Gaussian Mixture Model
Mohamed Ndaoud · 2018
Closest in time.