Speaker: Daniel Hsu, Columbia University
Talk title: Computational Lower Bounds for Tensor PCA
Time: Wednesday, April 6, 12:10pm-1:10pm (ET)
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.
Return to workshop schedule