Suppose that we are given independent, identically distributed random samples \(x_1,\ldots ,x_n\) from a mixture at most k many d-dimensional spherical Gaussian distributions \(\mu _1,\ldots ,\mu _{k_0}\) of identical and known variance \(\sigma ^2\) in each coordinate, such that the minimum \(\ell ^2\) distance between two distinct centers \(y_l\) and \(y_j\) is greater than \(2\Delta \sigma \min \{\sqrt{d},\sqrt{k}\}\) , where \(\Delta >C_0\) , and \(C_0\) is a sufficiently large universal constant. We develop a randomized algorithm that learns the centers \(y_l\) ’s of the Gaussian components to within an \(\ell ^2\) distance of \(k^{-\tilde{C}_0}\) —in presence of arbitrarily large number of components and in arbitrary dimension, when the weights are known to be uniform. Furthermore, if the number of components is \(k= \Omega (2^d)\) , then for arbitrary universal constant \(c>0\) , even for unknown weights, the algorithm learns the centers to within an \(\ell ^2\) distance of \(d^{-\tilde{C}_0}\) and the weights up to an accuracy of \(cw_{min}\) , with probability greater than \(1 - \exp (-k/c)\) , provided that the weights lie in [c/k, 1/ck], and the minimum separation is just \(2c\sqrt{d}\) . The number of samples and the computational time is bounded above by \(\text {poly}(k, d)\) in either case. Such a bound on the sample and computational complexity was previously unknown in the regime of non-constant dimension, and in particular, when d is not O(1), When \(d = O(1)\) , this complexity bound follows from [16], where it has also been shown that the sample complexity of learning a random mixture of Gaussians in a ball of radius \(o(\sqrt{d})\) in d dimensions, when d is \(\Theta ( \log k)\) , is at least super-polynomial in k, d, showing that our result is tight in this case.

A Fourier Analytic Approach to Gaussian Mixture Learning

章节
发表日期：

2025年

查看全文

Somnath Chakraborty,
Hariharan Narayanan

摘要

Suppose that we are given independent, identically distributed random samples \(x_1,\ldots ,x_n\) from a mixture at most k many d-dimensional spherical Gaussian distributions \(\mu _1,\ldots ,\mu _{k_0}\) of identical and known variance \(\sigma ^2\) in each coordinate, such that the minimum \(\ell ^2\) distance between two distinct centers \(y_l\) and \(y_j\) is greater than \(2\Delta \sigma \min \{\sqrt{d},\sqrt{k}\}\) , where \(\Delta >C_0\) , and \(C_0\) is a sufficiently large universal constant. We develop a randomized algorithm that learns the centers \(y_l\) ’s of the Gaussian components to within an \(\ell ^2\) distance of \(k^{-\tilde{C}_0}\) —in presence of arbitrarily large number of components and in arbitrary dimension, when the weights are known to be uniform. Furthermore, if the number of components is \(k= \Omega (2^d)\) , then for arbitrary universal constant \(c>0\) , even for unknown weights, the algorithm learns the centers to within an \(\ell ^2\) distance of \(d^{-\tilde{C}_0}\) and the weights up to an accuracy of \(cw_{min}\) , with probability greater than \(1 - \exp (-k/c)\) , provided that the weights lie in [c/k, 1/ck], and the minimum separation is just \(2c\sqrt{d}\) . The number of samples and the computational time is bounded above by \(\text {poly}(k, d)\) in either case. Such a bound on the sample and computational complexity was previously unknown in the regime of non-constant dimension, and in particular, when d is not O(1), When \(d = O(1)\) , this complexity bound follows from [16], where it has also been shown that the sample complexity of learning a random mixture of Gaussians in a ball of radius \(o(\sqrt{d})\) in d dimensions, when d is \(\Theta ( \log k)\) , is at least super-polynomial in k, d, showing that our result is tight in this case.