Rank-one matrix estimation: analytic time evolution of gradient descent dynamics

Antoine Bodin, Nicolas Macris
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:635-678, 2021.

Abstract

We consider a rank-one symmetric matrix corrupted by additive noise. The rank-one matrix is formed by an n-component unknown vector on the sphere of radius $\sqrt{n}$, and we consider the problem of estimating this vector from the corrupted matrix in the high dimensional limit of $n$ large, by gradient descent for a quadratic cost function on the sphere. Explicit formulas for the whole time evolution of the overlap between the estimator and unknown vector, as well as the cost, are rigorously derived. In the long time limit we recover the well known spectral phase transition, as a function of the signal-to-noise ratio. The explicit formulas also allow to point out interesting transient features of the time evolution. Our analysis technique is based on recent progress in random matrix theory and uses local versions of the semi-circle law.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-bodin21a, title = {Rank-one matrix estimation: analytic time evolution of gradient descent dynamics}, author = {Bodin, Antoine and Macris, Nicolas}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {635--678}, 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/bodin21a/bodin21a.pdf}, url = {https://proceedings.mlr.press/v134/bodin21a.html}, abstract = {We consider a rank-one symmetric matrix corrupted by additive noise. The rank-one matrix is formed by an n-component unknown vector on the sphere of radius $\sqrt{n}$, and we consider the problem of estimating this vector from the corrupted matrix in the high dimensional limit of $n$ large, by gradient descent for a quadratic cost function on the sphere. Explicit formulas for the whole time evolution of the overlap between the estimator and unknown vector, as well as the cost, are rigorously derived. In the long time limit we recover the well known spectral phase transition, as a function of the signal-to-noise ratio. The explicit formulas also allow to point out interesting transient features of the time evolution. Our analysis technique is based on recent progress in random matrix theory and uses local versions of the semi-circle law.} }
Endnote
%0 Conference Paper %T Rank-one matrix estimation: analytic time evolution of gradient descent dynamics %A Antoine Bodin %A Nicolas Macris %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-bodin21a %I PMLR %P 635--678 %U https://proceedings.mlr.press/v134/bodin21a.html %V 134 %X We consider a rank-one symmetric matrix corrupted by additive noise. The rank-one matrix is formed by an n-component unknown vector on the sphere of radius $\sqrt{n}$, and we consider the problem of estimating this vector from the corrupted matrix in the high dimensional limit of $n$ large, by gradient descent for a quadratic cost function on the sphere. Explicit formulas for the whole time evolution of the overlap between the estimator and unknown vector, as well as the cost, are rigorously derived. In the long time limit we recover the well known spectral phase transition, as a function of the signal-to-noise ratio. The explicit formulas also allow to point out interesting transient features of the time evolution. Our analysis technique is based on recent progress in random matrix theory and uses local versions of the semi-circle law.
APA
Bodin, A. & Macris, N.. (2021). Rank-one matrix estimation: analytic time evolution of gradient descent dynamics. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:635-678 Available from https://proceedings.mlr.press/v134/bodin21a.html.

Related Material