Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models

Stefano Sarao Mannelli, Florent Krzakala, Pierfrancesco Urbani, Lenka Zdeborova
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:4333-4342, 2019.

Abstract

In this work we analyse quantitatively the interplay between the loss landscape and performance of descent algorithms in a prototypical inference problem, the spiked matrix-tensor model. We study a loss function that is the negative log-likelihood of the model. We analyse the number of local minima at a fixed distance from the signal/spike with the Kac-Rice formula, and locate trivialization of the landscape at large signal-to-noise ratios. We evaluate analytically the performance of a gradient flow algorithm using integro-differential PDEs as developed in physics of disordered systems for the Langevin dynamics. We analyze the performance of an approximate message passing algorithm estimating the maximum likelihood configuration via its state evolution. We conclude by comparing the above results: while we observe a drastic slow down of the gradient flow dynamics even in the region where the landscape is trivial, both the analyzed algorithms are shown to perform well even in the part of the region of parameters where spurious local minima are present.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-mannelli19a, title = {Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models}, author = {Mannelli, Stefano Sarao and Krzakala, Florent and Urbani, Pierfrancesco and Zdeborova, Lenka}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {4333--4342}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/mannelli19a/mannelli19a.pdf}, url = {https://proceedings.mlr.press/v97/mannelli19a.html}, abstract = {In this work we analyse quantitatively the interplay between the loss landscape and performance of descent algorithms in a prototypical inference problem, the spiked matrix-tensor model. We study a loss function that is the negative log-likelihood of the model. We analyse the number of local minima at a fixed distance from the signal/spike with the Kac-Rice formula, and locate trivialization of the landscape at large signal-to-noise ratios. We evaluate analytically the performance of a gradient flow algorithm using integro-differential PDEs as developed in physics of disordered systems for the Langevin dynamics. We analyze the performance of an approximate message passing algorithm estimating the maximum likelihood configuration via its state evolution. We conclude by comparing the above results: while we observe a drastic slow down of the gradient flow dynamics even in the region where the landscape is trivial, both the analyzed algorithms are shown to perform well even in the part of the region of parameters where spurious local minima are present.} }
Endnote
%0 Conference Paper %T Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models %A Stefano Sarao Mannelli %A Florent Krzakala %A Pierfrancesco Urbani %A Lenka Zdeborova %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-mannelli19a %I PMLR %P 4333--4342 %U https://proceedings.mlr.press/v97/mannelli19a.html %V 97 %X In this work we analyse quantitatively the interplay between the loss landscape and performance of descent algorithms in a prototypical inference problem, the spiked matrix-tensor model. We study a loss function that is the negative log-likelihood of the model. We analyse the number of local minima at a fixed distance from the signal/spike with the Kac-Rice formula, and locate trivialization of the landscape at large signal-to-noise ratios. We evaluate analytically the performance of a gradient flow algorithm using integro-differential PDEs as developed in physics of disordered systems for the Langevin dynamics. We analyze the performance of an approximate message passing algorithm estimating the maximum likelihood configuration via its state evolution. We conclude by comparing the above results: while we observe a drastic slow down of the gradient flow dynamics even in the region where the landscape is trivial, both the analyzed algorithms are shown to perform well even in the part of the region of parameters where spurious local minima are present.
APA
Mannelli, S.S., Krzakala, F., Urbani, P. & Zdeborova, L.. (2019). Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4333-4342 Available from https://proceedings.mlr.press/v97/mannelli19a.html.

Related Material