Afonso Bandeira
ETH Zürich
WebsiteComputation, Statistics, and Optimization of Random Functions
When faced with a data analysis, learning, or statistical inference problem, the amount and quality of data available fundamentally determines 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.