Efficient Algorithms for Sparse Moment Problems without Separation

Zhiyuan Fan, Jian Li
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3510-3565, 2023.

Abstract

We consider the sparse moment problem of learning a $k$-spike mixture in high-dimensional space from its noisy moment information in any dimension. We measure the accuracy of the learned mixtures using transportation distance. Previous algorithms either assume certain separation assumptions, use more recovery moments, or run in (super) exponential time. Our algorithm for the 1-dimensional problem (also called the sparse Hausdorff moment problem) is a robust version of the classic Prony’s method, and our contribution mainly lies in the analysis. We adopt a global and much tighter analysis than previous work (which analyzes the perturbation of the intermediate results of Prony’s method). A useful technical ingredient is a connection between the linear system defined by the Vandermonde matrix and the Schur polynomial, which allows us to provide tight perturbation bound independent of the separation and may be useful in other contexts. To tackle the high-dimensional problem, we first solve the 2-dimensional problem by extending the 1-dimensional algorithm and analysis to complex numbers. Our algorithm for the high-dimensional case determines the coordinates of each spike by aligning a 1d projection of the mixture to a random vector and a set of 2d projections of the mixture. Our results have applications to learning topic models and Gaussian mixtures, implying improved sample complexity results or running time over prior work.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-fan23b, title = {Efficient Algorithms for Sparse Moment Problems without Separation}, author = {Fan, Zhiyuan and Li, Jian}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {3510--3565}, 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/fan23b/fan23b.pdf}, url = {https://proceedings.mlr.press/v195/fan23b.html}, abstract = {We consider the sparse moment problem of learning a $k$-spike mixture in high-dimensional space from its noisy moment information in any dimension. We measure the accuracy of the learned mixtures using transportation distance. Previous algorithms either assume certain separation assumptions, use more recovery moments, or run in (super) exponential time. Our algorithm for the 1-dimensional problem (also called the sparse Hausdorff moment problem) is a robust version of the classic Prony’s method, and our contribution mainly lies in the analysis. We adopt a global and much tighter analysis than previous work (which analyzes the perturbation of the intermediate results of Prony’s method). A useful technical ingredient is a connection between the linear system defined by the Vandermonde matrix and the Schur polynomial, which allows us to provide tight perturbation bound independent of the separation and may be useful in other contexts. To tackle the high-dimensional problem, we first solve the 2-dimensional problem by extending the 1-dimensional algorithm and analysis to complex numbers. Our algorithm for the high-dimensional case determines the coordinates of each spike by aligning a 1d projection of the mixture to a random vector and a set of 2d projections of the mixture. Our results have applications to learning topic models and Gaussian mixtures, implying improved sample complexity results or running time over prior work.} }
Endnote
%0 Conference Paper %T Efficient Algorithms for Sparse Moment Problems without Separation %A Zhiyuan Fan %A Jian Li %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-fan23b %I PMLR %P 3510--3565 %U https://proceedings.mlr.press/v195/fan23b.html %V 195 %X We consider the sparse moment problem of learning a $k$-spike mixture in high-dimensional space from its noisy moment information in any dimension. We measure the accuracy of the learned mixtures using transportation distance. Previous algorithms either assume certain separation assumptions, use more recovery moments, or run in (super) exponential time. Our algorithm for the 1-dimensional problem (also called the sparse Hausdorff moment problem) is a robust version of the classic Prony’s method, and our contribution mainly lies in the analysis. We adopt a global and much tighter analysis than previous work (which analyzes the perturbation of the intermediate results of Prony’s method). A useful technical ingredient is a connection between the linear system defined by the Vandermonde matrix and the Schur polynomial, which allows us to provide tight perturbation bound independent of the separation and may be useful in other contexts. To tackle the high-dimensional problem, we first solve the 2-dimensional problem by extending the 1-dimensional algorithm and analysis to complex numbers. Our algorithm for the high-dimensional case determines the coordinates of each spike by aligning a 1d projection of the mixture to a random vector and a set of 2d projections of the mixture. Our results have applications to learning topic models and Gaussian mixtures, implying improved sample complexity results or running time over prior work.
APA
Fan, Z. & Li, J.. (2023). Efficient Algorithms for Sparse Moment Problems without Separation. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:3510-3565 Available from https://proceedings.mlr.press/v195/fan23b.html.

Related Material