SQ Lower Bounds for Learning Bounded Covariance GMMs

We study the complexity of learning mixtures of separated Gaussians with common unknown bounded covariance matrix. Specifically, we focus on learning Gaussian mixture models (GMMs) on \(\mathbb{R}^d\) of the form \(P= \sum_{i=1}^k w_i \mathcal{N}(\boldsymbol \mu_i,\mathbf \Sigma_i)\), where \(\mathb...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-06
Main Authors: Diakonikolas, Ilias, Kane, Daniel M, Pittas, Thanasis, Zarifis, Nikos
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Covariance matrix
Lower bounds
Machine learning
Polynomials
Probabilistic models
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the complexity of learning mixtures of separated Gaussians with common unknown bounded covariance matrix. Specifically, we focus on learning Gaussian mixture models (GMMs) on \(\mathbb{R}^d\) of the form \(P= \sum_{i=1}^k w_i \mathcal{N}(\boldsymbol \mu_i,\mathbf \Sigma_i)\), where \(\mathbf \Sigma_i = \mathbf \Sigma \preceq \mathbf I\) and \(\min_{i \neq j} \| \boldsymbol \mu_i - \boldsymbol \mu_j\|_2 \geq k^\epsilon\) for some \(\epsilon>0\). Known learning algorithms for this family of GMMs have complexity \((dk)^{O(1/\epsilon)}\). In this work, we prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least \(d^{\Omega(1/\epsilon)}\). In the special case where the separation is on the order of \(k^{1/2}\), we additionally obtain fine-grained SQ lower bounds with the correct exponent. Our SQ lower bounds imply similar lower bounds for low-degree polynomial tests. Conceptually, our results provide evidence that known algorithms for this problem are nearly best possible.
ISSN:2331-8422