Provable Scalability for high-dimensional Bayesian Learning

Introduction

As the scale and complexity of available data increase, developing a rigorous understanding of the computational properties of statistical procedures has become a key scientific priority of our century. In line with such priority, this project develops a mathematical theory of computational scalability for Bayesian learning methods, with a focus on extremely popular high-dimensional and hierarchical models.

Methodological Integration

Unlike most recent literature, we will integrate computational and statistical aspects in the analysis of Bayesian learning algorithms. This approach will provide novel insight into the interaction between commonly used model structures and fitting algorithms.

Key Breakthroughs

Key methodological breakthroughs will include:

1. A novel connection between computational algorithms for hierarchical models and random walks on the associated graphical models.
2. The use of statistical asymptotics to derive computational scalability statements.
3. A novel understanding of the computational implications of model misspecification and data heterogeneity.

Results and Applications

We will derive a broad collection of results for popular Bayesian computation algorithms, especially Markov chain Monte Carlo ones, in a variety of modeling frameworks, such as:

• Random-effect models
• Shrinkage models
• Hierarchical models
• Nonparametric models

These algorithms are routinely used for various statistical tasks, such as multilevel regression, factor analysis, and variable selection in various disciplines ranging from political science to genomics.

Implications for Computational Schemes

Our theoretical results will have direct implications on the design of novel and more scalable computational schemes, as well as on the optimization of existing ones. Focus will be given to developing algorithms with provably linear overall cost both in the number of datapoints and unknown parameters.

Conclusion

The above contributions will dramatically reduce the gap between theory and practice in Bayesian computation and allow us to fully benefit from the huge potential of the Bayesian paradigm.