SQ Lower Bounds for Learning Mixtures of Linear Classifiers

Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun

We study the problem of learning mixtures of linear classifiers under Gaussian covariates. Given sample access to a mixture of $r$ distributions on ${\mathbb{R}}^n$ of the form $(\ma…