Daniel HSU (Columbia University) – “Computational Lower Bounds for Tensor PCA”
Statistical Seminar: Every Monday at 2:00 pm.
Time: 3:00 pm – 4:15 pm exceptionally
Date: 15th of November 2021
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.
Cristina BUTUCEA (CREST), Alexandre TSYBAKOV (CREST), Karim LOUNICI (CMAP) , Jaouad MOURTADA (CREST)