Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models

Graphical models are a general-purpose tool for modeling complex distributions in a way which facilitates probabilistic reasoning, with numerous applications across machine learning and the sciences. This thesis deals with algorithmic and statistical problems of learning a high-dimensional graphical model from samples, and related problems of performing inference on a known model, both areas of research which have been the subject of continued interest over the years. Our main contributions are the first computationally efficient algorithms for provably (1) learning a (possibly ill-conditioned) walk-summable Gaussian Graphical Model from samples, (2) learning a Restricted Boltzmann Machine (or other latent variable Ising model) from data, and (3) performing naive mean-field variational inference on an Ising model in the optimal density regime. These different problems illustrate a set of key principles, such as the diverse algorithmic applications of “pinning” variables in graphical models. We also show in some cases that these results are nearly optimal due to matching computational/cryptographic hardness results.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Koehler, Frederic

Advisor dc:contributor.advisor

• Mossel, Elchanan

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139373

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139373