Robustly Learning any Clusterable Mixture of Gaussians
  We study the efficient learnability of high-dimensional Gaussian mixtures in
the outlier-robust setting, where a small constant fraction of the data is
adversarially corrupted. We resolve the polynomial learnability of this problem
when the components are pairwise separated in total variation distance.
Specifically, we provide an algorithm that, for any constant number of
components $k$, runs in polynomial time and learns the components of an
$\epsilon$-corrupted $k$-mixture within information theoretically near-optimal
error of $\tilde{O}(\epsilon)$, under the assumption that the overlap between
any pair of components $P_i, P_j$ (i.e., the quantity $1-TV(P_i, P_j)$) is
bounded by $\mathrm{poly}(\epsilon)$.
  Our separation condition is the qualitatively weakest assumption under which
accurate clustering of the samples is possible. In particular, it allows for
components with arbitrary covariances and for components with identical means,
as long as their covariances differ sufficiently. Ours is the first polynomial
time algorithm for this problem, even for $k=2$.
  Our algorithm follows the Sum-of-Squares based proofs to algorithms approach.
Our main technical contribution is a new robust identifiability proof of
clusters from a Gaussian mixture, which can be captured by the constant-degree
Sum of Squares proof system. The key ingredients of this proof are a novel use
of SoS-certifiable anti-concentration and a new characterization of pairs of
Gaussians with small (dimension-independent) overlap in terms of their
parameter distance.
