Loading Events

« All Events

  • This event has passed.

Algorithmic thresholds for tensor principle component analysis

October 19 @ 11:00 am - 12:00 pm

Aukosh Jagannath (Harvard University)

E18-304

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).

Biography: Aukosh Jagannath is a Benjamin Pierce Fellow and NSF Postdoctoral fellow at Harvard University with undergraduate and graduate degree from NYU. He works in probability at the interface of  statistical physics,  data science, combinatorics, and statistics.

Details

Date:
October 19
Time:
11:00 am - 12:00 pm
Event Category:

Venue

E18-304
50 Ames Street
Cambridge, MA 02139

Other

Speaker Name(s)
Aukosh Jagannath (Harvard University)
Bldg-Room #
E18-304
speaker URL
http://math.harvard.edu/~aukosh/