A Fourier analytique approach to Gaussian mixture learning

Technical Summary: A Fourier Analytic Approach to Gaussian Mixture Learning

Problem Statement
The paper addresses the problem of learning the parameters of a finite mixture of $k$ spherical Gaussian distributions in $\mathbb{R}^d$. The mixture is defined as $\mu = \sum_{l=1}^{k_0} w_l \mu_l$, where each component $\mu_l$ is a spherical Gaussian with mean $y_l \in \mathbb{R}^d$ and identical, known variance $\sigma^2$ in every coordinate. The weights $w_l$ form a probability vector. The goal is to estimate the centers $\{y_l\}$ and, if unknown, the weights $\{w_l\}$, given independent, identically distributed (i.i.d.) samples from the mixture.

The primary challenge lies in the regime where the dimension $d$ is not constant (specifically $d = \Omega(1)$ and potentially $d = \Theta(\log k)$) and the number of components $k$ is large. Previous works often required separation between centers to scale with $\log(k)$ or $\log(dk/\epsilon)$, or were restricted to constant dimensions. This paper investigates the minimum separation required for polynomial-time learnability in arbitrary dimensions.

Methodology
The authors propose a randomized algorithm that leverages Fourier analysis and deconvolution to recover the underlying atomic mixture. The core technical strategy involves the following steps:

1. Dimensionality Reduction and Preprocessing:

   • Graph Decomposition: Using the concentration of measure, the algorithm constructs a proximity graph on the samples. Connected components of this graph allow the algorithm to isolate clusters of centers, reducing the problem to cases where the centers are well-connected but separated.
   • Johnson-Lindenstrauss (JL) Reduction: The algorithm projects the high-dimensional data into subspaces of dimension $\bar{d} = O(\log k)$ (or $O(1 + \min(\log k, d))$). It is shown that if the Gaussians can be separated in these low-dimensional projections, the original centers can be reconstructed with high accuracy. This reduces the general problem to the regime where $d = O(\log k)$.
   • Localization: The algorithm restricts the search space for centers to a union of balls of radius $O(\sqrt{d})$ centered around the data points.

2. Fourier Deconvolution:

   • The central innovation is the application of deconvolution in the Fourier domain. The mixture density $\mu$ is viewed as the convolution of the atomic measure $\nu = \sum w_l \delta_{y_l}$ with a Gaussian kernel $\gamma$.
   • To recover $\nu$, the algorithm attempts to invert the convolution. However, direct inversion is unstable. The authors introduce a truncated deconvolution technique. They define a function $\hat{s}$ in the Fourier domain which is the reciprocal of a Gaussian (scaled by $\bar{\Delta}$) multiplied by an indicator function of a ball $B$.
   • This truncation ensures the function remains well-behaved. The inverse Fourier transform of $\hat{s}$, denoted $s$, approximates a Gaussian with a smaller variance.
   • The algorithm constructs a "black-box oracle" that provides an additive approximation of the deconvolved mixture $s * \nu$ at any point. This is achieved via a Monte Carlo method, sampling from the support of the truncated Fourier domain.

3. Center Recovery via Optimization:

   • Once the deconvolved density (which approximates the atomic mixture smoothed by a thin Gaussian) is accessible, the algorithm seeks its local maxima.
   • Using a robust, randomized zeroth-order concave optimization method (based on Belloni et al.), the algorithm searches for peaks within the localized search space.
   • These approximate peaks serve as "seeds" for an iterative refinement procedure (from Regev and Vijayaraghavan [16]), which polishes the estimates to the desired accuracy.

4. Weight Estimation:

   • If weights are unknown, they are estimated by integrating the deconvolved mixture density over small balls surrounding the recovered centers.

Key Contributions and Results

The paper establishes polynomial-time learnability under significantly weaker separation assumptions than previously known for non-constant dimensions:

• Separation Requirement: The algorithm succeeds if the minimum $\ell_2$ distance between distinct centers satisfies:
  $$\min_{l \neq j} \|y_l - y_j\|_2 \geq 2\Delta \sigma \min\{\sqrt{d}, \sqrt{k}\}$$
  where $\Delta > C_0$ is a sufficiently large universal constant.
• Uniform Weights Case: If weights are known to be uniform, the algorithm recovers centers to an accuracy of $k^{-\tilde{C}_0}$ in time and sample complexity polynomial in $k$ and $d$, for arbitrary $d$.
• Unknown Weights Case: If weights are unknown, the algorithm recovers centers and weights with high probability provided:
  • $k = \Omega(2^d)$ (i.e., the number of components overwhelms the dimension).
  • The minimum separation is $2c\sigma\sqrt{d}$ for an arbitrary constant $c \in (0, 1)$.
  • The weights lie in the range $[c/k, 1/(ck)]$.
  • The accuracy achieved is $d^{-\tilde{C}_0}$ for centers and $c w_{min}$ for weights.
• Complexity: In both cases, the sample complexity and computational time are bounded by $\text{poly}(k, d)$.

Significance and Claims

The authors claim that this work provides the first polynomial-time algorithm for learning Gaussian mixtures in the regime of non-constant dimension ($d$ not $O(1)$) with separation scaling only as $\sqrt{d}$ (when $k$ is large) or $\min\{\sqrt{d}, \sqrt{k}\}$.

• Tightness: The paper notes that for the specific case where $d = \Theta(\log k)$, the separation requirement of $O(\sqrt{d})$ is tight. This is supported by a lower bound from Regev and Vijayaraghavan [16], which showed that learning random mixtures in a ball of radius $o(\sqrt{d})$ requires super-polynomial sample complexity when $d = \Theta(\log k)$.
• Methodological Novelty: The paper highlights the novel application of Fourier deconvolution with careful truncation to the Gaussian mixture learning problem. Unlike previous approaches relying on local search (EM), $k$-means, or moment-based methods, this approach uses the Fourier transform to convert the convolution into a product, allowing for the recovery of the underlying atomic structure even in high dimensions.
• Limitations: The authors acknowledge that their results currently assume spherical Gaussians with identical known variance and (in the unknown weight case) a specific range for weights. They note that extending this to non-spherical Gaussians or unknown variances presents obstructions in the Fourier domain (non-uniform weighted sums of sinusoids) and remains an open problem.

In summary, the paper demonstrates that with a Fourier analytic approach, the "curse of dimensionality" in Gaussian mixture learning can be mitigated, achieving polynomial learnability with separation requirements that are independent of the number of components $k$ (scaling only with $\sqrt{d}$) when $k$ is exponentially large relative to $d$.