Better Agnostic Clustering Via Relaxed Tensor Norms

Abstract

We develop a new family of convex relaxations for $k$-means clustering based on sum-of-squares norms, a relaxation of the injective tensor norm that is efficiently computable using the Sum-of-Squares algorithm. We give an algorithm based on this relaxation that recovers a faithful approximation to the true means in the given data whenever the low-degree moments of the points in each cluster have bounded sum-of-squares norms. We then prove a sharp upper bound on the sum-of-squares norms for moment tensors of any distribution that satisfies the \emph{Poincare inequality}. The Poincare inequality is a central inequality in probability theory, and a large class of distributions satisfy it including Gaussians, product distributions, strongly log-concave distributions, and any sum or uniformly continuous transformation of such distributions. As an immediate corollary, for any $\gamma >0$, we obtain an efficient algorithm for learning the means of a mixture of $k$ arbitrary \Poincare distributions in ${\mathbb{R}}^d$ in time $d^{O(1/\gamma )}$ so long as the means have separation $\Omega (k^{\gamma })$. This in particular yields an algorithm for learning Gaussian mixtures with separation $\Omega (k^{\gamma })$, thus partially resolving an open problem of Regev and Vijayaraghavan \citet{regev2017learning}. Our algorithm works even in the outlier-robust setting where an $\epsilon$ fraction of arbitrary outliers are added to the data, as long as the fraction of outliers is smaller than the smallest cluster. We, therefore, obtain results in the strong agnostic setting where, in addition to not knowing the distribution family, the data itself may be arbitrarily corrupted.

References in corpus (3)

• A Spectral Algorithm for Learning Hidden Markov Models
• Estimates of moments and tails of Gaussian chaoses
• Functional inequalities for Gaussian convolutions of compactly supported measures: explicit bounds and dimension dependence

Cited by in corpus (13)

• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• An Analysis of the t-SNE Algorithm for Data Visualization
• Efficient Algorithms for Outlier-Robust Regression
• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• Robust regression with covariate filtering: Heavy tails and adversarial contamination
• Outlier-Robust Clustering of Non-Spherical Mixtures
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Adversarially Robust Low Dimensional Representations
• Robustly Clustering a Mixture of Gaussians
• Low Rank Approximation in the Presence of Outliers
• List-Decodable Mean Estimation via Iterative Multi-Filtering
• Learning RUMs: Reducing Mixture to Single Component via PCA