Permutation recovery of spikes in noisy high-dimensional tensor estimation

• URL: http://arxiv.org/abs/2412.14650v2
• Date: Fri, 20 Dec 2024 07:17:38 GMT
• Title: Permutation recovery of spikes in noisy high-dimensional tensor estimation
• Authors: Gérard Ben Arous, Cédric Gerbelot, Vanessa Piccolo,
• Abstract summary: We study the dynamics of flow in high dimensions for the multi-spiked tensor problem. Our work builds on our companion paper [Ben A, Gerbelot, Langevin], which determines the sample separation conditions for the SNRs necessary for ensuring exact recovery.
• Score: 8.435118770300999
• License:
• Abstract: We study the dynamics of gradient flow in high dimensions for the multi-spiked tensor problem, where the goal is to estimate $r$ unknown signal vectors (spikes) from noisy Gaussian tensor observations. Specifically, we analyze the maximum likelihood estimation procedure, which involves optimizing a highly nonconvex random function. We determine the sample complexity required for gradient flow to efficiently recover all spikes, without imposing any assumptions on the separation of the signal-to-noise ratios (SNRs). More precisely, our results provide the sample complexity required to guarantee recovery of the spikes up to a permutation. Our work builds on our companion paper [Ben Arous, Gerbelot, Piccolo 2024], which studies Langevin dynamics and determines the sample complexity and separation conditions for the SNRs necessary for ensuring exact recovery of the spikes (where the recovered permutation matches the identity). During the recovery process, the correlations between the estimators and the hidden vectors increase in a sequential manner. The order in which these correlations become significant depends on their initial values and the corresponding SNRs, which ultimately determines the permutation of the recovered spikes.

Related papers

• Stochastic gradient descent in high dimensions for multi-spiked tensor PCA [8.435118770300999]
  We study the dynamics in high dimensions of online gradient descent for the multi-spiked tensor model. We find that the spikes are recovered sequentially in a process we term "sequential elimination"
  arXiv  Detail & Related papers  (2024-10-23T17:20:41Z)
• Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA [8.435118770300999]
  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. As a key step, we provide a detailed characterization of the spikes and interactions that capture the high-dimensional trajectory dynamics.
  arXiv  Detail & Related papers  (2024-08-12T12:09:25Z)
• High-dimensional robust regression under heavy-tailed data: Asymptotics and Universality [7.416689632227865]
  We investigate the high-dimensional properties of robust regression estimators in the presence of heavy-tailed noise. We show that, despite being consistent, the Huber loss with optimally tuned location parameter $delta$ is suboptimal in the high-dimensional regime. We derive the decay rates for the excess risk of ridge regression.
  arXiv  Detail & Related papers  (2023-09-28T14:39:50Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• SNIPS: Solving Noisy Inverse Problems Stochastically [25.567566997688044]
  We introduce a novel algorithm dubbed SNIPS, which draws samples from the posterior distribution of any linear inverse problem. Our solution incorporates ideas from Langevin dynamics and Newton's method, and exploits a pre-trained minimum mean squared error (MMSE) We show that the samples produced are sharp, detailed and consistent with the given measurements, and their diversity exposes the inherent uncertainty in the inverse problem being solved.
  arXiv  Detail & Related papers  (2021-05-31T13:33:21Z)
• On Signal-to-Noise Ratio Issues in Variational Inference for Deep Gaussian Processes [55.62520135103578]
  We show that the gradient estimates used in training Deep Gaussian Processes (DGPs) with importance-weighted variational inference are susceptible to signal-to-noise ratio (SNR) issues. We show that our fix can lead to consistent improvements in the predictive performance of DGP models.
  arXiv  Detail & Related papers  (2020-11-01T14:38:02Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  We show that depending on the structure of the Hessian of the loss at the minimum, the SGD iterates will converge to a emphheavy-tailed stationary distribution. We translate our results into insights about the behavior of SGD in deep learning.
  arXiv  Detail & Related papers  (2020-06-08T16:43:56Z)
• Information Directed Sampling for Linear Partial Monitoring [112.05623123909895]
  We introduce information directed sampling (IDS) for partial monitoring with a linear reward and observation structure. IDS achieves adaptive worst-case regret rates that depend on precise observability conditions of the game. We extend our results to the contextual and the kernelized setting, which significantly increases the range of possible applications.
  arXiv  Detail & Related papers  (2020-02-25T21:30:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.