Statistical Seminar: Every Monday at 2:00 pm.
Time: 3:00 pm – 4:15 pm exceptionally
Date: 15th of November 2021
Place: visio

Daniel HSU (Columbia University) – “Computational Lower Bounds for Tensor PCA ”

Abstract: Tensor PCA is a model statistical inference problem introduced by Montanari and Richard in 2014 for studying method-of-moments approaches to parameter estimation in latent variable models. Unlike the matrix counterpart of the problem, Tensor PCA exhibits a computational-statistical gap in the sample-size regime where the problem is information-theoretically solvable but no computationally-efficient algorithm is known. I will describe unconditional computational lower bounds on classes of algorithms for solving Tensor PCA that shed light on limitations of commonly-used solution approaches, including gradient descent and power iteration, as well as the role of overparameterization. This talk is based on joint work with Rishabh Dudeja.

Organizers:
Cristina BUTUCEA (CREST), Alexandre TSYBAKOV (CREST), Karim LOUNICI (CMAP) , Jaouad MOURTADA (CREST)
Sponsors:
CREST-CMAP