On Learning Parallel Pancakes with Mostly Uniform Weights

This paper is concerned with learning mixtures of $k$ Guassians, when given i.i.d samples from the mixture. When the mixture weights and covariances of the individual components are unknown and arbitrary, the best-known algorithm from the literature (due to Bakshi et al. 2022) has sample complexity $d^{O(k)}$. A lower bound instance due to Diakonikolas et al. 2017, known as the "parallel pancakes" mixture, comprises of a family of mixtures of $k$ Gaussians having identical covariances. For this family, any SQ based algorithm necessarily requires sample complexity $d^{\Omega(k)}$. However, the weights of the mixture in the family of the lower bound instance end up having to be as small as $2^{-\Omega(k)}$. A natural question here is: can the lower bound be circumvented if the mixture weights are constrained to be at least $1/poly(k)$? Recent results by Anderson et al. 2024, Buhai and Steurer 2023 show that the answer is yes. In particular, they show an algorithm that correctly clusters most points drawn from a $k$-mixture of Gaussians using only $d^{\log(1/w_{min})}$ many samples, where $w_{min}$ is the smallest weight in the mixture.

The first main result in this paper shows that this sample complexity bound is essentially optimal. Theorem 1.3 constructs a family with uniform mixture weights, such that any SQ algorithm must necessarily have sample complexity $d^{\Omega(\log(k))}$.

The algorithms due to Anderson et al. 2024, Buhai and Steurer 2023 have sample complexity $d^k$, even if only a single mixture weight is $2^{-k}$. One can ask if this can be improved. Specifically, consider the setting where $k'$ out of the $k$ mixture weights are allowed to be arbitrary, but the rest are the same. The second main result in the paper (Theorem 1.4) shows that for the task of distinguishing the standard Gaussian from a mixture of this form, there is an algorithm that has sample complexity that scales as $1/{w_{min}}$, which is a better sample complexity that of Anderson et al. 2024, Buhai and Steurer 2023. Note however that the upper bound is only for the testing problem, and not for the learning problem.

For the first result, the authors use a previous construction by Kane 2015, and combine it with a construction from Diakonikolas et al. 2017, to obtain a one-dimensional discrete distribution over $2^{O(t)}$ elements that matches $t$ moments of the standard Gaussian. For the second result, the authors use that their construction for the previous part is essentially optimal. Namely, the uniform distribution on any $k$ points cannot match more that $O(\log k)$ moments of the standard Gaussian. This can be extended to arguing that distributions that are arbitrary on $k'$ out of the $k$ points, but uniform on the rest of $k-k'$ points, cannot match more than $O(\log(k)+k')$ moments of the Gaussian. This fact allows distinguishing between a $k$-mixture from the standard high-dimensional gaussian using higher order tensors that reveal the differences in the higher order moments.

update after rebuttal

I thank the authors for the clarifications. It would be useful to include them appropriately in the revision of the paper. I maintain my evaluation of the paper, and my score.

The paper studies a hypothesis testing problem where the main task is to distinguish (with as few as possible samples) between a standard Gaussian $N(0,I_d)$, and a "parallel pancakes" distribution. This distribution is characterized by k discrete mean points along an unknown line in d dimensions. Now the distribution orthogonal to the line is standard Gaussian, but along the line, the variance is squeezed by a factor $1-\delta$.

The main results are:

1. a $d^{\Omega(\log(k))}$ lower bound against distinguishing a standard normal from a pancake mixture where all mixture weights are equal (resp $> 1/poly(k)$). This matches under the same weight assumptions an upper bound of Anderson 2024, $d^{O(\log(1/w_min))}$.

2. When even one $w$ is not bounded below, the upper bound $d^{O(\log(1/w_{min}))}$ becomes $2^{O(k)}$. As a consequent next step the authors provide a testing algorithm with a dominating factor of $(kd)^{O(\log(k) + k')}$ where $k'$ weights are unbounded and $k-k'$ are bounded below by $1/poly(k)$. The minimum weight still plays a role but is only linear in $1/w_min$, so must be super tiny to dominate.

The analyses are highly technical and are based on the observations that there are discrete distributions that share many but not too many smaller moments with the standard Gaussian. The lower bound comes from the fact that the pancakes with the support set as means and spread along a random directional vector are hard to distinguish from the standard normal in d dimensions. And the upper bounds are shown by showing that only a relatively small number of moments are so close that they are indistinguishable. So the algorithm can check all $i$-th moment tensors up to $i \in O(\log(k) + k')$ and must then find at least one larger deviation.

update after rebuttal:

The authors have addressed my points satisfactorily. Remaining issues are easily resolvable typos. I will therefore retain my initial score "4: Accept".

This paper studies the problem of learning mixtures of Gaussians where each component in the mixture has a shared covariance.

First, an SQ lower bound is proved, matching a recent positive algorithmic result and indicating that it likely cannot be improved. It is shown that even in the case when the mixture is of $k$ equally weighted Gaussians, the problem of distinguishing the $k$-GMM from a spherical Gaussian has SQ complexity $d^{\Omega(\log(k))}$. This indicates that a recent result showing an algorithm with a $d^{O(\log(1/w_{min}))}$ is likely optimal when $w_{min} = \Omega(1/\mathrm{poly}(k)))$.

Next, this paper works on understanding the optimal complexity dependence on $w_{min}$. It is shown that for instances that are close to uniformly-weighted mixtures (but with a small number of arbitrarily-weighted components), the complexity in $k$ and $w_{min}$ can be somewhat decoupled, and solved with $d^{O(\log(k))}$ operations/samples instead of $d^{O(\log(1/w_{min}))}$ complexity.

This paper studies the hypothesis-testing problem of parallel Gaussian pancakes, specifically under structural assumptions on the component weights. The goal is to distinguish between the standard gaussian and the k gaussian pancakes with collinear centers and common covariance. For learning the general mixture of k gaussians, the best known algorithm have sample complexity $d^{O(k)}$, and in the statistical query model, this problem requires sample complexity $d^{\Omega(k)}$. Recent work considers the setting where the minimum weight of component is $w_{\min}$ and components have common covariance. In this case, they provide $d^{O(\log(1/w_{\min}) )}$ time algorithm to learn the GMM.

In this paper, they first provide a SQ lower bound which shows that even when all component weights are uniform, distinguishing between such a mixture and the standard Gaussian requires $d^{\Omega(\log k)}$ complexity. This implies that the algorithm above is essentially best possible in this case. Then they provide an algorithm for the hypothesis testing problem when most of the weights are uniform but a small fraction can be arbitrary. Their algorithm has the complexity $(kd)^{O(k'+\log k)} + \log k/w_{\min}$ where $k'$ components have arbitrary weights and the minimum weight is $w_{\min}$. Their algorithm is more efficient than the previous algorithm even if there is one component has an exponentially small weight, like $2^{-k}$. Their results refine existing complexity bounds and offer new insights into the role of weight distributions in learning Gaussian mixtures.

The paper considers the problem of learning the mixture of k Gaussians with shared unknown covariance and bounded minimum mixture weight. The paper first shows a statistical query lower bound showing that the recent upper bound is tight even when the mixture weights are uniform. The paper also shows an algorithm for testing whether the given distribution is a mixture of mostly uniform weights or the standard gaussian, with query complexity separating the term required for uniform weight and the term depending on the minimum weight. This is an important evident that more efficient algorithms might be possible for smaller mixture weight lower bounds. All reviewers consider the paper to be a timely contribution to a classical problem and might lead to future improvements in the upper bounds. They also suggest that the paper is well-written.