Inference in High Dimensions: Information Theoretic Limits and Efficient Algorithms

Today, we are at the center of a revolution in information technology, with data being the most valuable commodity. Exploiting this exploding number of data sets requires to address complex inference problems, spanning different fields and arising in a variety of applications from engineering and the natural sciences. In particular, in machine learning, given a model for the observations, the focus is on (i) how many samples convey sufficient information to perform a certain task, (ii) how to design low-complexity algorithms that optimally utilize these samples, and (iii) what are the properties of the solution found by such algorithms. While the high dimensionality of the problem is often regarded as a ‘curse’ which makes it challenging to answer these questions, in the talk I will discuss how the high dimensionality is in fact the key ingredient that allows analytical tractability. Specifically, in the first part, I will focus on gradient descent algorithms optimizing over-parameterized deep neural networks. In the second part, I will move towards fundamental models, such as generalized linear models and principal component analysis, discussing how to achieve the Bayes-optimal limits of inference.