Algorithms Seminar

Statistical-Computational Tradeoffs in Tensor Learning

April 11, -
Speaker(s): Anru Zhang


The analysis of tensor data, i.e., arrays with multiple directions, has been an active research topic in data science. Datasets in the form of tensors arise from a wide range of scientific applications. Tensor methods also provide unique perspectives to many high-dimensional problems, where the observations are not necessarily tensors. On the other hand, many tensor problems exhibit intrinsic computational barriers and statistical-computational gaps. In this talk, we discuss several recent advances in the statistical-computational trade-offs in various tensor learning problems, such as tensor PCA, tensor clustering, and tensor regression. Our theory demonstrates a "blessing of statistical-computational gap" phenomenon: one usually requires stronger conditions than the statistical (or information-theoretic) limit to ensure the computationally feasible estimation is achievable in these tensor problems. Such conditions “incidentally” render a feasible low-rank tensor inference without debiasing and overparametrized estimation without the cost of extra samples.

Speaker Bio

Anru Zhang is the Eugene Anson Stead, Jr. M.D. Associate Professor at Duke. He is a primary faculty member in the Departments of Biostatistics & Bioinformatics and Computer Science and also a secondary faculty member in the Departments of Electrical & Computer Engineering, Mathematics, and Statistical Science.  He serves as the Associate Editor for Journal of the American Statistical Association (T&M); Statistica Sinica; and Statistics and Its Interface; His research interests include tensor learning, generative models, high-dimensional statistics, electronic health records, healthcare and microbiome studies.

Zoom Link


Yiheng Shen