Approximate message passing with spectral initialization for generalized linear models

Mondelli M, Venkataramanan R. 2021. Approximate message passing with spectral initialization for generalized linear models. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. AISTATS: Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 130, 397–405.

Conference Paper | Published | English
Author
Mondelli, MarcoISTA ; Venkataramanan, Ramji
Editor
Banerjee, Arindam; Fukumizu, Kenji
Department
Series Title
Proceedings of Machine Learning Research
Abstract
We consider the problem of estimating a signal from measurements obtained via a generalized linear model. We focus on estimators based on approximate message passing (AMP), a family of iterative algorithms with many appealing features: the performance of AMP in the high-dimensional limit can be succinctly characterized under suitable model assumptions; AMP can also be tailored to the empirical distribution of the signal entries, and for a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms. However, a major issue of AMP is that in many models (such as phase retrieval), it requires an initialization correlated with the ground-truth signal and independent from the measurement matrix. Assuming that such an initialization is available is typically not realistic. In this paper, we solve this problem by proposing an AMP algorithm initialized with a spectral estimator. With such an initialization, the standard AMP analysis fails since the spectral estimator depends in a complicated way on the design matrix. Our main contribution is a rigorous characterization of the performance of AMP with spectral initialization in the high-dimensional limit. The key technical idea is to define and analyze a two-phase artificial AMP algorithm that first produces the spectral estimator, and then closely approximates the iterates of the true AMP. We also provide numerical results that demonstrate the validity of the proposed approach.
Publishing Year
Date Published
2021-04-01
Proceedings Title
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics
Acknowledgement
The authors would like to thank Andrea Montanari for helpful discussions. M. Mondelli was partially supported by the 2019 Lopez-Loreta Prize. R. Venkataramanan was partially supported by the Alan Turing Institute under the EPSRC grant EP/N510129/1.
Volume
130
Page
397-405
Conference
AISTATS: Artificial Intelligence and Statistics
Conference Location
Virtual, San Diego, CA, United States
Conference Date
2021-04-13 – 2021-04-15
ISSN
IST-REx-ID

Cite this

Mondelli M, Venkataramanan R. Approximate message passing with spectral initialization for generalized linear models. In: Banerjee A, Fukumizu K, eds. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. Vol 130. ML Research Press; 2021:397-405.
Mondelli, M., & Venkataramanan, R. (2021). Approximate message passing with spectral initialization for generalized linear models. In A. Banerjee & K. Fukumizu (Eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (Vol. 130, pp. 397–405). Virtual, San Diego, CA, United States: ML Research Press.
Mondelli, Marco, and Ramji Venkataramanan. “ Approximate Message Passing with Spectral Initialization for Generalized Linear Models.” In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, edited by Arindam Banerjee and Kenji Fukumizu, 130:397–405. ML Research Press, 2021.
M. Mondelli and R. Venkataramanan, “ Approximate message passing with spectral initialization for generalized linear models,” in Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, Virtual, San Diego, CA, United States, 2021, vol. 130, pp. 397–405.
Mondelli M, Venkataramanan R. 2021. Approximate message passing with spectral initialization for generalized linear models. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. AISTATS: Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 130, 397–405.
Mondelli, Marco, and Ramji Venkataramanan. “ Approximate Message Passing with Spectral Initialization for Generalized Linear Models.” Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, edited by Arindam Banerjee and Kenji Fukumizu, vol. 130, ML Research Press, 2021, pp. 397–405.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2010.03460

Search this title in

Google Scholar