Probability Seminar

Monday, November 26, 2018 at 4:15pm to 5:15pm

2-147, 2-147

Aukosh Jagannath (Harvard University)

Algorithmic thresholds for tensor principal component analysis
 
Abstract: Consider the problem of recovering a rank 1 tensor of order k that has been subject to Gaussian noise. The log-likelihood for this problem is highly non-convex. It is information theoretically possible to recover the tensor with a finite number of samples via maximum likelihood estimation, however, it is expected that one needs a polynomially diverging number of samples to efficiently recover it. What is the cause of this large statistical–to–algorithmic gap? To study this question, we investigate the thresholds for efficient recovery for a simple family of algorithms, Langevin dynamics and gradient descent. We view this problem as a member of a broader class of problems which correspond to recovering a signal from a non-linear observation that has been perturbed by isotropic Gaussian noise. We propose a mechanism for success/failure of recovery of such algorithms in terms of the strength of the signal on the high entropy region of the initialization. Joint work with G. Ben Arous (NYU) and R. Gheissari (NYU).
Event Type

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

Public

Tags

harmonjo, prob_sem

Department
Department of Mathematics
Add to my calendar

You're not going yet!

This event requires registration.