Date:
Location:
The Probabilitas Seminar series focuses on high-dimensional problems that combine statistics, probability, information theory, computer science, and other related fields. The upcoming seminar takes place on Friday, March 8, from 10:30-11:30am EST. This week's guest will be Cedric Gerbelot of NYU.
Title : Dynamics of optimization on the multi-rank spiked tensor and matrix model
Abstract : We consider the multi-rank spiked matrix and tensor model and study gradient flow (GF), Langevin dynamics and online stochastic gradient descent (SGD). This model arises from the well-known matrix and tensor PCA problem, in which we wish to recover \(r\) unknown orthogonal signal vectors lying in the \(N\)-dimensional unit sphere from a noisy observation of a planted order-\(p\) tensor in the presence of Gaussian noise. We determine conditions on the signal-to-noise ratios and number of samples under which the unknown spikes may be recovered one after the other or by groups, leading to different types of fixed points: perfect recovery of each spike, recovery of a permutation, recovery of the correct subspace or recovery of a rank-deficient subspace. We show that under gradient flow a single direction may be recovered with the same algorithmic threshold as in the rank one tensor PCA problem, i.e., the number of samples needs to be of order \(N^{p-1}\). To recover the subsequent directions, the number of samples needs to be of order \(N^{p}\) when p>3, while the exponent spans the interval (1,2) for p=2. Finally, we show that online SGD allows to recover subsequent directions with a number of samples of order \(N^{p-1}\). Our proof strategy relies on the construction of bounding flows for the noisy dynamics, leading to a low-dimensional effective dynamical system. We then provide a sharp analysis of this system to control the fluctuations due to the interaction of the variables at the microscopic level to isolate those that eventually become macroscopic, leading to stable recovery. Based on joint work with Gerard Ben Arous and Vanessa Piccolo.