When faced with a data analysis, learning, or statistical inference problem, the amount and quality of data available fundamentally determine whether such tasks can be performed with certain levels of accuracy. Indeed, many theoretical disciplines study limits of such tasks by investigating whether a dataset effectively contains the information of interest. With the growing size of datasets however, it is crucial not only that the underlying statistical task is possible, but also that is doable by means of efficient algorithms. In this talk, we will discuss methods aiming to establish limits of when statistical tasks are possible with computationally efficient methods or when there is a fundamental «Statistical-to-Computational gap›› in which an inference task is statistically possible but inherently computationally hard. This is intimately related to understanding the geometry of random functions, with connections to statistical physics, study of spin glasses, random geometry; and in an important example, algebraic invariant theory.
Speaker: Afonso S. Bandeira (Professor of Mathematics, ETH Zürich)
Afonso holds a Bachelors and Masters degree from the University of Coimbra, Portugal. He was awarded a PhD in Applied and Computational Mathematics from Princeton University, under the supervision of Amit Singer. After spending a year at the Department of Mathematics at MIT, he joined the faculty at the Mathematics Department of the Courant Institute of Mathematical Sciences and the Center for Data Science, both at the New York University. Since September 2019 he is a Professor of Mathematics at the ETH Zurich. Afonso’s research interests are in the broadly defined area of Mathematics of Data Science. Recent recognitions include a Sloan Fellowship in 2018, the 2019 ISAAC prize for Young Scientists, the 2020 Stephen Smale Prize from the FoCM society, and the 2020 Information Theory Society Paper Award.