Clustering mixtures with almost optimal separation in polynomial time

DOI10.1145/3519935.3520012MaRDI QIDQ6083577zbMATH OpenFDO

Authors Allen P. Liu, Jerry Li

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.00706

zbMATH Keywords

clusteringmethod of momentsmixture modelsmixtures of GaussiansPoincaré distribution

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We consider the problem of clustering mixtures of mean-separated Gaussians in high dimensions. We are given samples from a mixture of $k$ identity covariance Gaussians, so that the minimum pairwise distance between any two pairs of means is at least $Delta$, for some parameter $Delta>0$, and the goal is to recover the ground truth clustering of these samples. It is folklore that separation $Delta=Theta(sqrtlogk)$ is both necessary and sufficient to recover a good clustering, at least information theoretically. However, the estimators which achieve this guarantee are inefficient. We give the first algorithm which runs in polynomial time, and which almost matches this guarantee. More precisely, we give an algorithm which takes polynomially many samples and time, and which can successfully recover a good clustering, so long as the separation is $Delta=Omega(lo{g}^{1/2+c}k)$, for any $c>0$. Previously, polynomial time algorithms were only known for this problem when the separation was polynomial in $k$, and all algorithms which could tolerate $extsfpoly(logk)$ separation required quasipolynomial time. We also extend our result to mixtures of translations of a distribution which satisfies the Poincar'{e} inequality, under additional mild assumptions. Our main technical tool, which we believe is of independent interest, is a novel way to implicitly represent and estimate high degree moments of a distribution, which allows us to extract important information about high-degree moments without ever writing down the full moment tensors explicitly.

Recommendations

• Clustering subgaussian mixtures by semidefinite programming
• A polynomial-time algorithm for optimal clustering in a special class of {0, l} -matrices
• On separable clusterings
• Exact and approximation algorithms for clustering
• Almost optimal solutions to k-clustering problems
• Approximation schemes for clustering problems
• Approximation algorithms for stochastic clustering
• Optimal time bounds for approximate clustering
• Near-optimal clustering in the \(k\)-machine model
• scientific article; zbMATH DE number 1629976

Cited in

(3)

• scientific article; zbMATH DE number 1124647 (Why is no real title available?)
• Near-linear time and fixed-parameter tractable algorithms for tensor decompositions
• Mixtures of Gaussians are privately learnable with a polynomial number of samples

This page was built for publication: Clustering mixtures with almost optimal separation in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083577)