Algorithms for learning a mixture of linear classifiers

Aidao Chen, Anindya De, Aravindan Vijayaraghavan
Proceedings of The 33rd International Conference on Algorithmic Learning Theory, PMLR 167:205-226, 2022.

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 this Paper

BibTeX
@InProceedings{pmlr-v167-chen22c, 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}, pages = {205--226}, year = {2022}, editor = {Dasgupta, Sanjoy and Haghtalab, Nika}, volume = {167}, series = {Proceedings of Machine Learning Research}, month = {29 Mar--01 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v167/chen22c/chen22c.pdf}, url = {https://proceedings.mlr.press/v167/chen22c.html}, 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.} }
Endnote
%0 Conference Paper %T Algorithms for learning a mixture of linear classifiers %A Aidao Chen %A Anindya De %A Aravindan Vijayaraghavan %B Proceedings of The 33rd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Sanjoy Dasgupta %E Nika Haghtalab %F pmlr-v167-chen22c %I PMLR %P 205--226 %U https://proceedings.mlr.press/v167/chen22c.html %V 167 %X 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.
APA
Chen, A., De, A. & Vijayaraghavan, A.. (2022). Algorithms for learning a mixture of linear classifiers. Proceedings of The 33rd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 167:205-226 Available from https://proceedings.mlr.press/v167/chen22c.html.

Related Material