Better Agnostic Clustering Via Relaxed Tensor Norms

By Pravesh Kothari, Jacob Steinhardt. 2017

62 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

Citations in the corpus

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “Since the dissemination of [DKK + 16, LRV16], there has been a ﬂurry of research activity on algorithmic robust estimation in a variety of high-dimensional settings, including learning graphical models [DKS16], understanding computation-robustness tradeoﬀs [DKS17c, DKK + 18], establishing connection”
A Data Prism: Semi-verified learning in the small-alpha regime (2018, background): “There has been a flurry of very recent works both tightening these results and extending them to more general classes of distribution and other optimization or learning problems (Steinhardt et al., 2018; Kothari and Steinhardt, 2017; Kothari and Steurer, 2017; Diakonikolas et al., 2017a).”
An Analysis of the t-SNE Algorithm for Data Visualization (2018, background): “By now, a sequence of results (Dasgupta et al., 2007, 2006; Arora and Kannan, 2005; Vempala and Wang, 2004; Achlioptas and McSherry, 2005; Kannan et al., 2005; Vempala, 2007; Hsu and Kakade, 2013; Ge et al., 2015b; Kalai et al., 2012; Belkin and Sinha, 2010; Kalai et al., 2010; Kothari and Steinhard”
Outlier-robust moment-estimation via sum-of-squares (2017, methodology): “In a subsequent work, Kothari and Steinhardt [KS17] show that certiﬁable subgaussianity holds for distributions that satisfy a Poincaré inequality (which includes all strongly log-concave distributions).”