Learning sparse mixtures of permutations from noisy information

Anindya De, Ryan O’Donnell, Rocco Servedio
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1429-1466, 2021.

Abstract

We study the problem of learning an unknown mixture of k permutations over n elements, given access to noisy samples drawn from the unknown mixture. We consider a range of different noise models, including natural variants of the “heat kernel” noise framework and the Mallows model. We give an algorithm which, for each of these noise models, learns the unknown mixture to high accuracy under mild assumptions and runs in $n^{O(log k)}$ time. Our approach is based on a new procedure that recovers an unknown mixture of permutations from noisy higher-order marginals.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-de21b, title = {Learning sparse mixtures of permutations from noisy information}, author = {De, Anindya and O'Donnell, Ryan and Servedio, Rocco}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {1429--1466}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/de21b/de21b.pdf}, url = {https://proceedings.mlr.press/v134/de21b.html}, abstract = {We study the problem of learning an unknown mixture of k permutations over n elements, given access to noisy samples drawn from the unknown mixture. We consider a range of different noise models, including natural variants of the “heat kernel” noise framework and the Mallows model. We give an algorithm which, for each of these noise models, learns the unknown mixture to high accuracy under mild assumptions and runs in $n^{O(log k)}$ time. Our approach is based on a new procedure that recovers an unknown mixture of permutations from noisy higher-order marginals.} }
Endnote
%0 Conference Paper %T Learning sparse mixtures of permutations from noisy information %A Anindya De %A Ryan O’Donnell %A Rocco Servedio %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-de21b %I PMLR %P 1429--1466 %U https://proceedings.mlr.press/v134/de21b.html %V 134 %X We study the problem of learning an unknown mixture of k permutations over n elements, given access to noisy samples drawn from the unknown mixture. We consider a range of different noise models, including natural variants of the “heat kernel” noise framework and the Mallows model. We give an algorithm which, for each of these noise models, learns the unknown mixture to high accuracy under mild assumptions and runs in $n^{O(log k)}$ time. Our approach is based on a new procedure that recovers an unknown mixture of permutations from noisy higher-order marginals.
APA
De, A., O’Donnell, R. & Servedio, R.. (2021). Learning sparse mixtures of permutations from noisy information. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:1429-1466 Available from https://proceedings.mlr.press/v134/de21b.html.

Related Material