Sharp analysis of EM for learning mixtures of pairwise differences

Abhishek Dhawan, Cheng Mao, Ashwin Pananjady
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4384-4428, 2023.

Abstract

We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design, which can be seen as a noisy version of a type of Euclidean distance geometry problem. We analyze the expectation-maximization (EM) algorithm locally around the ground truth and establish that the sequence converges linearly, providing an $\ell_\infty$-norm guarantee on the estimation error of the iterates. Furthermore, we show that the limit of the EM sequence achieves the sharp rate of estimation in the $\ell_2$-norm, matching the information-theoretically optimal constant. We also argue through simulation that convergence from a random initialization is much more delicate in this setting, and does not appear to occur in general. Our results show that the EM algorithm can exhibit several unique behaviors when the covariate distribution is suitably structured.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-dhawan23a, title = {Sharp analysis of EM for learning mixtures of pairwise differences}, author = {Dhawan, Abhishek and Mao, Cheng and Pananjady, Ashwin}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {4384--4428}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/dhawan23a/dhawan23a.pdf}, url = {https://proceedings.mlr.press/v195/dhawan23a.html}, abstract = {We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design, which can be seen as a noisy version of a type of Euclidean distance geometry problem. We analyze the expectation-maximization (EM) algorithm locally around the ground truth and establish that the sequence converges linearly, providing an $\ell_\infty$-norm guarantee on the estimation error of the iterates. Furthermore, we show that the limit of the EM sequence achieves the sharp rate of estimation in the $\ell_2$-norm, matching the information-theoretically optimal constant. We also argue through simulation that convergence from a random initialization is much more delicate in this setting, and does not appear to occur in general. Our results show that the EM algorithm can exhibit several unique behaviors when the covariate distribution is suitably structured.} }
Endnote
%0 Conference Paper %T Sharp analysis of EM for learning mixtures of pairwise differences %A Abhishek Dhawan %A Cheng Mao %A Ashwin Pananjady %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-dhawan23a %I PMLR %P 4384--4428 %U https://proceedings.mlr.press/v195/dhawan23a.html %V 195 %X We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design, which can be seen as a noisy version of a type of Euclidean distance geometry problem. We analyze the expectation-maximization (EM) algorithm locally around the ground truth and establish that the sequence converges linearly, providing an $\ell_\infty$-norm guarantee on the estimation error of the iterates. Furthermore, we show that the limit of the EM sequence achieves the sharp rate of estimation in the $\ell_2$-norm, matching the information-theoretically optimal constant. We also argue through simulation that convergence from a random initialization is much more delicate in this setting, and does not appear to occur in general. Our results show that the EM algorithm can exhibit several unique behaviors when the covariate distribution is suitably structured.
APA
Dhawan, A., Mao, C. & Pananjady, A.. (2023). Sharp analysis of EM for learning mixtures of pairwise differences. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:4384-4428 Available from https://proceedings.mlr.press/v195/dhawan23a.html.

Related Material