English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the complexity of learning mixtures of separated Gaussians withcommon unknown bounded covariance matrix. Specifically, we focus on learningGaussian mixture models (GMMs) on $\mathbb{R}^d$ of the form $P= \sum_{i=1}^kw_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 learningalgorithms for this family of GMMs have complexity $(dk)^{O(1/\epsilon)}$. Inthis work, we prove that any Statistical Query (SQ) algorithm for this problemrequires complexity at least $d^{\Omega(1/\epsilon)}$. In the special casewhere the separation is on the order of $k^{1/2}$, we additionally obtainfine-grained SQ lower bounds with the correct exponent. Our SQ lower boundsimply similar lower bounds for low-degree polynomial tests. Conceptually, ourresults provide evidence that known algorithms for this problem are nearly bestpossible.

SQ Lower Bounds for Learning Bounded Covariance GMMs