[theory students] Theory seminar talk this Friday!

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Hi everyone,

Just a reminder that this Friday (tomorrow) on Oct 18 from 2-3pm in CS 3310 we have our very own Thanasis Pittas giving the following talk:

Title: Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation

Abstract: 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_i$, where each $w_i \ge \alpha$ for some known parameter $\alpha$, and each $P_i$ has unknown covariance $\Sigma_i \preceq \sigma^2_i \cdot I_d$ for some unknown $\sigma_i$, the goal is to cluster the samples 

assuming a pairwise mean separation in the order of $(\sigma_i+\sigma_j)/\sqrt{\alpha}$ between every pair of components $P_i$ and $P_j$. Our main contributions are as follows:

1. For the special case of nearly uniform mixtures, we give the first polynomial-time algorithm for this clustering task. Prior work either required separation scaling with the maximum cluster standard deviation (i.e. $\max_i \sigma_i$)[DKKLT22] or required both additional structural assumptions and mean separation scaling as a large degree polynomial in $1/\alpha$ [BKK22]. 

2. For arbitrary (i.e. general-weight) mixtures, we point out that accurate clustering is information-theoretically impossible under our fine-grained mean separation assumptions. We introduce the notion of a *clustering refinement*--- a list of not-too-small subsets satisfying a similar separation, and which can be merged into a clustering approximating the ground truth --- and show that it is possible to efficiently compute an accurate clustering refinement of the samples. Furthermore, under a variant of the "no large sub-cluster" condition introduced in prior work [BKK22], we show that our algorithm will output an accurate clustering, not just a refinement, even for general-weight mixtures. As a corollary, we obtain efficient clustering algorithms for mixtures of well-conditioned high-dimensional log-concave distributions. 

Moreover, our algorithm is robust to a fraction of adversarial outliers comparable to $\alpha$. At the technical level, our algorithm proceeds by first using list-decodable mean estimation to generate a  polynomial-size list of possible cluster means, before successively pruning candidates using a carefully constructed convex program. In particular, the convex program takes as input a candidate mean $\hat{\mu}$ and a scale parameter $\hat{s}$, and determines the existence of a subset of points that could plausibly form a cluster with scale $\hat{s}$ centered around $\hat{\mu}$. While the natural way of designing this program makes it non-convex, we construct a convex relaxation which remains satisfiable by (and only by) not-too-small subsets of true clusters.

See you there!

Sandeep