Inference in High-Dimensional Statistical Models: Algorithmic Tractability and Computational Barriers

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Extracting knowledge from data using statistical and machine learning methods often involves computations, which don't scale well with dataset sizes. This is dictated by the necessity of analyzing large scale statistical models, where the scale of the data ever increases due to our unprecedented ability to accumulative massive amounts of it. Often this leads to models where the number of parameters far exceeds the amount of collected data, rendering many classical inference models ill-posed and classical computational methods prohibitively time consuming. Thus the value brought about by the abundance of data comes at the expense of the necessity to develop completely novel computational tools that are capable of dealing with the curse of dimensionality. While there is an abundance of literature devoted to designing efficient computational methods of inference in high-dimensional statistical models, it was discovered that many algorithms hit a certain computational barrier, beyond which seemingly only brute-force and thus computationally prohibitive algorithms can succeed. Not much is known regarding the fundamental computational limitations arising above this barrier, which is popularly dubbed the nformation Theoretic vs Computation gap. What is the origin of this barrier? Does it indeed correspond to the onset of algorithmically intractable problems, or is it just a matter of being more clever about designing faster algorithms? The project also provides research training opportunities for graduate students. In the present project the PI develops a completely novel approach for understanding fundamental computational barriers arising in high dimensional statistical models. The approach is based on powerful and illuminating insights derived from the field of statistical physics, specifically the theory of spin glasses. In particular, the PI intends to establish that the onset of the algorithmic barriers is caused by phase transition in the landscape of the solution space, marking a drastic change in the solution space geometry of underlying inference problems. This change in geometry of the solution space landscape taking the form of the so-called Overlap Gap Property (OGP), can further be used to rule out broad classes of algorithms as potential contenders to bridge the information theoretic and algorithmic gap. These classes of algorithms include algorithms based on local improvements, such as Gradient Descent and Stochastic Gradient Descend algorithms, algorithms based on Markov Chain Monte Carlo Method, algorithms broadly defined as Approximate Message Passing iterations, and algorithms based on constructing low-degree polynomials. The PI in particular intends to investigate the validity of a bold conjecture stating that for most, if not all of the known models exhibiting apparent algorithmic barriers, the onset of this barrier coincides with the onset of the OGP. The PI intends to investigate this conjecture in the context of several widely studied modern models of high dimensional statistics and machine learning fields, including the Stochastic Block Model, the Spiked Tensor Model, and Wide Neural Networks model. All of these models are known to exhibit an apparent algorithmic hardness in some parameter regimes and thus these models offer a valuable framework for investigating the validity of the aforementioned conjecture, as well as algorithmic intractability implications. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.