Algorithms for Learning a Mixture of Linear Classifiers
Abstract
Linear classifiers are a basic model in supervised learning. We study the problem of learning a mixture of linear classifiers over Gaussian marginals. Despite significant interest in this problem, including in the context of neural networks, basic questions like efficient learnability and identifiability of the model remained open. In this paper, we design algorithms for recovering the parameters of the mixture of $k$ linear classifiers. We obtain two algorithms which both have polynomial dependence on the ambient dimension $n$, and incur an exponential dependence either on the number of the components $k$ or a natural separation parameter $\Delta>0$. These algorithmic results in particular settle the identifiability question under provably minimal assumptions.
Cite
Text
Chen et al. "Algorithms for Learning a Mixture of Linear Classifiers." Proceedings of The 33rd International Conference on Algorithmic Learning Theory, 2022.Markdown
[Chen et al. "Algorithms for Learning a Mixture of Linear Classifiers." Proceedings of The 33rd International Conference on Algorithmic Learning Theory, 2022.](https://mlanthology.org/alt/2022/chen2022alt-algorithms/)BibTeX
@inproceedings{chen2022alt-algorithms,
title = {{Algorithms for Learning a Mixture of Linear Classifiers}},
author = {Chen, Aidao and De, Anindya and Vijayaraghavan, Aravindan},
booktitle = {Proceedings of The 33rd International Conference on Algorithmic Learning Theory},
year = {2022},
pages = {205-226},
volume = {167},
url = {https://mlanthology.org/alt/2022/chen2022alt-algorithms/}
}