ORIE Colloquium: Afonso Bandeira (ETH Zurich) - Computation, Statistics, and Optimization of Random Functions

Description

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.

Bio:
Afonso Bandeira holds a bachelor’s and master’s degree from the University of Coimbra, Portugal. He received his Ph.D. in applied and computational mathematics from Princeton University, under the supervision of Amit Singer. After spending a year 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. Bandeira's research interests are in the broadly defined area of Mathematics of Data Science. Recent recognitions include a Sloan Fellowship in 2008, the 2019 ISAAC prize for Young Scientists, the 2020 Stephen Smale Prize from the FoCM society, and the 2020 Information Theory Society Paper Award.