Technical Summary: Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures

1. Problem Statement

The paper addresses the problem of clustering high-dimensional Gaussian Mixture Models (GMMs) where the component covariances are arbitrary (non-spherical). Specifically, given $i.i.d.$ samples from a mixture of $k$ $d$-dimensional Gaussians $P = \sum_{i=1}^k w_i \mathcal{N}(\mu_i, \Sigma_i)$ with $k \ll d$, the goal is to partition the data such that the fraction of misclassified points is small (at most 1%).

The components are assumed to be "well-separated" in Total Variation (TV) distance, specifically $d_{TV}(\mathcal{N}(\mu_i, \Sigma_i), \mathcal{N}(\mu_j, \Sigma_j)) \ge 1 - f(w_{\min})$, where $w_{\min}$ is the minimum mixing weight. The authors focus on two specific settings:

1. Centered Mixtures: All components have zero mean ($\mu_i = 0$), but arbitrary covariances $\Sigma_i$.
2. Identical-Covariance Mixtures: All components share the same unknown covariance $\Sigma$, but have distinct means $\mu_i$.

Prior to this work, the state-of-the-art algorithms for non-spherical mixtures required sample and time complexity of $d^{\Omega(k)}$, even for these structured settings. This stood in contrast to spherical mixtures, which can be clustered in time $d^{O(1)}$. The $d^{\Omega(k)}$ barrier was supported by Statistical Query (SQ) and Sum-of-Squares (SoS) lower bounds [DKS17, DKPP24], which suggested that such costs were necessary for general non-spherical mixtures.

2. Methodology and Key Technical Ideas

The core contribution is a new dimension reduction subroutine based on the Sum-of-Squares (SoS) method. This subroutine identifies a low-dimensional projection of the input data that preserves the separation between at least one pair of components, allowing the algorithm to partially cluster the data and iterate.

2.1 The Bottleneck in Prior Work

Previous approaches (e.g., [BK20, DHKK20]) relied on certifying "anti-concentration" properties of the data in all directions to distinguish components. For non-spherical mixtures, this certification required matching $\Omega(k)$ moments, leading to the $d^{\Omega(k)}$ complexity. The authors observe that for the specific settings of centered components or identical covariances, the "hard" instances used to prove lower bounds (parallel pancakes constructions) do not apply, as these constructions rely on non-zero means and exponentially small weights.

2.2 The SoS Dimension Reduction Approach

The authors develop a technique to find a "direction of separation" without needing to match high-order moments. The approach involves:

1. Formulating Constraints: Constructing a system of polynomial inequalities $A(v)$ over a unit vector $v$ that characterizes "spherical directions" (directions where the variance is close to 1) or directions orthogonal to the separation.

   • For Centered Mixtures: The authors utilize the fourth moment tensor. They observe that while the symmetrized fourth moment tensor is high-rank and difficult to decompose directly, the condition for a vector $v$ to be "spherical" (i.e., $v^\top \Sigma_i v \approx 1$ for all $i$) can be captured by a system involving the Hessian of the fourth moment form. Specifically, if $\langle M_4, v^{\otimes 4} \rangle \approx 0$ and $\nabla^2_v \langle M_4, v^{\otimes 4} \rangle \approx 0$, then $v$ is close to the kernel of the deviation matrices $(\Sigma_i - I)$.
   • For Identical Covariances: The authors leverage a result from [BS23] showing that a mixture with identical covariances cannot match the first $O(\log k)$ moments of a standard Gaussian. They construct constraints based on the first $O(\log k)$ moments to identify directions where the variance is close to 1.

2. SoS Rounding: The system of constraints $A(v)$ defines a set of vectors. The authors use an SoS rounding algorithm (Theorem 4.1 and 4.2) to recover a low-dimensional subspace that contains the solutions to $A(v)$ (or is orthogonal to them).

   • Crucially, the degree of the SoS proofs required is constant for centered mixtures and $O(\log k)$ for identical-covariance mixtures. This low degree is what allows the algorithm to run in time polynomial in $d$ (specifically $d^{O(1)}$ or $d^{O(\log k)}$) rather than $d^{\Omega(k)}$.

3. Iterative Clustering: Once a low-dimensional subspace containing a separation direction is found, the algorithm projects the data, performs a simple thresholding to split the mixture into two parts (partial clustering), and recurses on the resulting subsets.

3. Main Results

The paper presents two main theorems providing efficient algorithms for the two settings described above.

Theorem 1.1: Centered Gaussian Mixtures

For a mixture of $k$ centered Gaussians with minimum weight $w_{\min}$ and pairwise TV separation, there exists an algorithm that:

• Sample Complexity: $n \ge \text{poly}(d) \cdot f(w_{\min}^{-1})$.
• Time Complexity: $\text{poly}(d) \cdot f(w_{\min}^{-1})$.
• Guarantee: Outputs a clustering with misclassification error $O(k w_{\min}^{-1} \max\{\epsilon, k^{-k}\})$, where $\epsilon$ is the fraction of outliers.
• Significance: The dependence on dimension $d$ is a fixed polynomial, completely independent of $k$. This breaks the $d^{\Omega(k)}$ barrier previously thought necessary.

Theorem 1.2: Identical-Covariance Gaussian Mixtures

For a mixture of $k$ Gaussians with identical but unknown covariance $\Sigma$, minimum weight $w_{\min}$, and pairwise TV separation:

• Sample Complexity: $n \ge d^{O(\log w_{\min}^{-1})} \cdot f(w_{\min}^{-1})$.
• Time Complexity: $d^{O(\log^2 w_{\min}^{-1})} \cdot f(w_{\min}^{-1})$.
• Guarantee: Similar misclassification bounds as the centered case.
• Significance: While the dependence on $d$ is slightly higher ($d^{\text{polylog}(k)}$) compared to the centered case, it is still exponentially better than the previous $d^{\Omega(k)}$ bounds.

Corollary: Subspace Clustering

As an immediate application, the authors provide an outlier-robust algorithm for Gaussian subspace clustering (where components are supported on distinct subspaces) with time and sample complexity $\text{poly}(d) \cdot f(w_{\min}^{-1})$.

4. Significance and Claims

The authors claim that their results are surprising in the context of existing hardness results. The $d^{\Omega(k)}$ lower bounds for non-spherical mixtures [DKS17, DKPP24] are based on "parallel pancakes" constructions involving non-zero means and exponentially small weights. By restricting the problem to centered components or identical covariances, the authors demonstrate that these hardness barriers can be circumvented.

• Breaking the Barrier: The work shows that for a "remarkably general class" of non-spherical mixtures (centered or identical-covariance), the cost of clustering can be reduced from $d^{\Omega(k)}$ to $d^{O(1)}$ or $d^{\text{polylog}(k)}$.
• Methodological Advance: The paper introduces a new SoS-based dimension reduction technique that avoids the need for high-degree moment matching. Instead of trying to recover the full structure via high-order tensors, it uses low-degree SoS proofs to identify specific subspaces relevant to the separation.
• Robustness: The algorithms naturally extend to tolerate a dimension-independent fraction of arbitrary outliers.

The authors acknowledge a recent lower bound by [DKK+25] (post-dating the preprint) which shows a $d^{\Omega(\log k)}$ SQ lower bound for the identical-covariance case. This confirms that while the $d^{\Omega(k)}$ barrier is broken, the $d^{O(1)}$ barrier for the identical-covariance case (Theorem 1.2) cannot be improved to $d^{O(1)}$ in the SQ model, highlighting a separation between the centered and identical-covariance settings.

In summary, the paper provides the first efficient algorithms for clustering non-spherical Gaussian mixtures with zero means or identical covariances that run in time polynomial in the dimension $d$ (with a constant or polylogarithmic exponent), significantly improving upon the previous $d^{\Omega(k)}$ state-of-the-art.