Efficient Clustering for Stretched Mixtures: Landscape and Optimality
This paper considers a canonical clustering problem where one receives unlabeled samples drawn from a balanced mixture of two elliptical distributions and aims for a classifier to estimate the labels. Many popular methods including PCA and k-means require individual components of the mixture to be somewhat spherical, and perform poorly when they are stretched. To overcome this issue, we propose a non-convex program seeking for an affine transform to turn the data into a one-dimensional point cloud concentrating around $-1$ and $1$, after which clustering becomes easy. Our theoretical contributions are two-fold: (1) we show that the non-convex loss function exhibits desirable geometric properties when the sample size exceeds some constant multiple of the dimension, and (2) we leverage this to prove that an efficient first-order algorithm achieves near-optimal statistical precision without good initialization. We also propose a general methodology for clustering with flexible choices of feature transforms and loss objectives.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Clustering a Mixture of Gaussians with Unknown Covariance
We investigate a clustering problem with data from a mixture of Gaussians that share a common but unknown, and potentially ill-conditioned, covariance matrix. We start by considering Gaussian mixtures with two equally-si…
ClusteringMinimax-Optimal Dimension-Reduced Clustering for High-Dimensional Nonspherical Mixtures
In mixture models, nonspherical (anisotropic) noise within each cluster is widely present in real-world data. We study both the minimax rate and optimal statistical procedure for clustering under high-dimensional nonsphe…
ClusteringDimensionality ReductionAdversarially robust clustering with optimality guarantees
We consider the problem of clustering data points coming from sub-Gaussian mixtures. Existing methods that provably achieve the optimal mislabeling error, such as the Lloyd algorithm, are usually vulnerable to outliers. …
ClusteringTransition paths in Potts-like energy landscapes: general properties and application to protein sequence models
We study transition paths in energy landscapes over multi-categorical Potts configurations using the mean-field approach introduced by Mauri et al., {\em Phys Rev Lett 130, 158402 (2023)}. Paths interpolate between two f…
Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation
We study the clustering problem for mixtures of bounded covariance distributions, under a fine-grained separation assumption. Specifically, given samples from a $k$-component mixture distribution $D = \sum_{i =1}^k w_i P…
Clustering