Tensor Networks and Phase Transitions in Machine Learning

Visiting speaker

###### Cristopher Moore

Professor, Santa Fe Institute

Past Talk

Hybrid

Thursday

Oct 10, 2024

Watch video

3:30 pm

EST

Virtual

177 Huntington Ave.

11th floor

11th floor

Devon House

58 St Katharine's Way

London E1W 1LP, UK

58 St Katharine's Way

London E1W 1LP, UK

Suppose we observe a matrix of data with a low-rank “signal” obscured by noise. The standard way to find the signal, at least approximately, is PCA (principal component analysis): just look at the eigenvectors of the matrix. For Gaussian noise, random matrix theory tells us exactly how well this works: that is, the accuracy we can achieve as a function of the signal-to-noise ratio. For tensors, such as three-index tables A_{ijk}, the situation is much more complex. Here there seems to be a “statistical-computational gap,” namely a regime where finding the signal is possible but exponentially hard. Physically, this corresponds to a “glass transition,” where the optimum becomes hidden behind an energy barrier. Mathematically, it means that we believe no polynomial-time algorithm exists, and that exhaustive search is necessary. I’ll give evidence for this exponential hardness by showing that no algorithm remotely similar to PCA can work. Along the way, I’ll give an introduction to tensor networks — a generalization of matrix products and traces thaat everyone, including network theorists, should know about.

About the speaker

About the speaker

Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. Since 2012, Moore has been a resident professor at the Santa Fe Institute; he has also held visiting positions at École Normale Superieure, École Polytechnique, Université Paris 7, École Normale Superieure de Lyon, Northeastern University, the University of Michigan, and Microsoft Research. He has written 160 papers at the boundary between mathematics, physics, and computer science, ranging from quantum computing, social networks, and phase transitions in NP-complete problems and Bayesian inference, to risk assessment in criminal justice. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.

Cristopher Moore received his B.A. in Physics, Mathematics, and Integrated Science from Northwestern University, and his Ph.D. in Physics from Cornell. From 2000 to 2012 he was a professor at the University of New Mexico, with joint appointments in Computer Science and Physics. Since 2012, Moore has been a resident professor at the Santa Fe Institute; he has also held visiting positions at École Normale Superieure, École Polytechnique, Université Paris 7, École Normale Superieure de Lyon, Northeastern University, the University of Michigan, and Microsoft Research. He has written 160 papers at the boundary between mathematics, physics, and computer science, ranging from quantum computing, social networks, and phase transitions in NP-complete problems and Bayesian inference, to risk assessment in criminal justice. He is an elected Fellow of the American Physical Society, the American Mathematical Society, and the American Association for the Advancement of Science. With Stephan Mertens, he is the author of The Nature of Computation from Oxford University Press.

## Want to be notified about upcoming NetSI events? Sign up for our email list below!

Thank you! You have been added to our email list.

Oops! Something went wrong while submitting the form