Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929639083999232 |
|---|---|
| author | Arous, Gérard Ben Gerbelot, Cédric Piccolo, Vanessa |
| author_facet | Arous, Gérard Ben Gerbelot, Cédric Piccolo, Vanessa |
| contents | We study nonconvex optimization in high dimensions through Langevin dynamics, focusing on the multi-spiked tensor PCA problem. This tensor estimation problem involves recovering $r$ hidden signal vectors (spikes) from noisy Gaussian tensor observations using maximum likelihood estimation. We study the number of samples required for Langevin dynamics to efficiently recover the spikes and determine the necessary separation condition on the signal-to-noise ratios (SNRs) for exact recovery, distinguishing the cases $p \ge 3$ and $p=2$, where $p$ denotes the order of the tensor. In particular, we show that the sample complexity required for recovering the spike associated with the largest SNR matches the well-known algorithmic threshold for the single-spike case, while this threshold degrades when recovering all $r$ spikes. As a key step, we provide a detailed characterization of the trajectory and interactions of low-dimensional projections that capture the high-dimensional dynamics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06401 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA Arous, Gérard Ben Gerbelot, Cédric Piccolo, Vanessa Machine Learning Probability Statistics Theory 68Q87, 62F30, 60G44, 60H30 We study nonconvex optimization in high dimensions through Langevin dynamics, focusing on the multi-spiked tensor PCA problem. This tensor estimation problem involves recovering $r$ hidden signal vectors (spikes) from noisy Gaussian tensor observations using maximum likelihood estimation. We study the number of samples required for Langevin dynamics to efficiently recover the spikes and determine the necessary separation condition on the signal-to-noise ratios (SNRs) for exact recovery, distinguishing the cases $p \ge 3$ and $p=2$, where $p$ denotes the order of the tensor. In particular, we show that the sample complexity required for recovering the spike associated with the largest SNR matches the well-known algorithmic threshold for the single-spike case, while this threshold degrades when recovering all $r$ spikes. As a key step, we provide a detailed characterization of the trajectory and interactions of low-dimensional projections that capture the high-dimensional dynamics. |
| title | Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA |
| topic | Machine Learning Probability Statistics Theory 68Q87, 62F30, 60G44, 60H30 |
| url | https://arxiv.org/abs/2408.06401 |