Probabilistic graphical models are widely used throughout science and engineering to solve difficult problems, understand large data sets, or make predictions about complex phenomena. Making predictions or decisions out of graphical models involves challenging #P-hard computational problems, and efficient approximation methods are highly demanded. The most useful approximations should give not only accurate estimates, but also (1) come with tight and conservative error bounds and (2) can be improved continuously to trade time for increased accuracy in a memory efficient and predictable way (an "anytime" property). Such algorithms should allow us to solve easy problems with strong certificates of accuracy, and also identify harder problems together with clear guidance for further improvement. Unfortunately, most state-of-the-art methods, including deterministic variational methods and Monte Carlo-based methods, often do not fully satisfy these criteria.

This project aims to develop a new generation of inference tools with tight non-asymptotic confidence bounds and anytime property. Based on several key insights that connect variational inference with non-asymptotic bounds of Monte Carlo, the PI derives a spectrum of powerful methods that naturally integrate and combine the advantages of these two approaches, providing a new foundation for more reliable inference. The project also develops novel non-asymptotic error bounds for advanced Monte Carlo methods such as annealed importance sampling (AIS), based on which the researchers construct highly efficient estimates and bounds built on the state-of-the-art AIS. The approaches are tested extensively on various application domains, and provide practical guidance and open source packages for practitioners. The new powerful anytime, error-aware inference tools will lead much more reliable use of graphical models across different application domains, greatly expanding our ability of reasoning over large datasets and complex phenomena.

Agency
National Science Foundation (NSF)
Institute
Division of Information and Intelligent Systems (IIS)
Type
Standard Grant (Standard)
Application #
1565796
Program Officer
Weng-keen Wong
Project Start
Project End
Budget Start
2016-04-01
Budget End
2018-04-30
Support Year
Fiscal Year
2015
Total Cost
$157,670
Indirect Cost
Name
Dartmouth College
Department
Type
DUNS #
City
Hanover
State
NH
Country
United States
Zip Code
03755