Finite-sample Bounds for Marginal MAP

Qi Lou, Rina Dechter, Alexander Ihler
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:724-733, 2018.

Abstract

Marginal MAP is a key task in Bayesian in- ference and decision-making, and known to be very challenging in general. In this paper, we present an algorithm that blends heuristic search and importance sampling to provide any- time finite-sample bounds for marginal MAP along with predicted MAP solutions. We con- vert bounding marginal MAP to a surrogate task of bounding a series of summation prob- lems of an augmented graphical model, and then adapt dynamic importance sampling [Lou et al., 2017b], a recent advance in bounding the partition function, to provide finite-sample bounds for the surrogate task. Those bounds are guaranteed to be tight given enough time, and the values of the predicted MAP solutions will converge to the optimum. Our algorithm runs in an anytime/anyspace manner, which gives flexible trade-offs between memory, time, and solution quality. We demonstrate the effective- ness of our approach empirically on multiple challenging benchmarks in comparison with some state-of-the-art search algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-lou18a, title = {Finite-sample Bounds for Marginal {MAP}}, author = {Lou, Qi and Dechter, Rina and Ihler, Alexander}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {724--733}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/lou18a/lou18a.pdf}, url = {https://proceedings.mlr.press/r16/lou18a.html}, abstract = {Marginal MAP is a key task in Bayesian in- ference and decision-making, and known to be very challenging in general. In this paper, we present an algorithm that blends heuristic search and importance sampling to provide any- time finite-sample bounds for marginal MAP along with predicted MAP solutions. We con- vert bounding marginal MAP to a surrogate task of bounding a series of summation prob- lems of an augmented graphical model, and then adapt dynamic importance sampling [Lou et al., 2017b], a recent advance in bounding the partition function, to provide finite-sample bounds for the surrogate task. Those bounds are guaranteed to be tight given enough time, and the values of the predicted MAP solutions will converge to the optimum. Our algorithm runs in an anytime/anyspace manner, which gives flexible trade-offs between memory, time, and solution quality. We demonstrate the effective- ness of our approach empirically on multiple challenging benchmarks in comparison with some state-of-the-art search algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Finite-sample Bounds for Marginal MAP %A Qi Lou %A Rina Dechter %A Alexander Ihler %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-lou18a %I PMLR %P 724--733 %U https://proceedings.mlr.press/r16/lou18a.html %V R16 %X Marginal MAP is a key task in Bayesian in- ference and decision-making, and known to be very challenging in general. In this paper, we present an algorithm that blends heuristic search and importance sampling to provide any- time finite-sample bounds for marginal MAP along with predicted MAP solutions. We con- vert bounding marginal MAP to a surrogate task of bounding a series of summation prob- lems of an augmented graphical model, and then adapt dynamic importance sampling [Lou et al., 2017b], a recent advance in bounding the partition function, to provide finite-sample bounds for the surrogate task. Those bounds are guaranteed to be tight given enough time, and the values of the predicted MAP solutions will converge to the optimum. Our algorithm runs in an anytime/anyspace manner, which gives flexible trade-offs between memory, time, and solution quality. We demonstrate the effective- ness of our approach empirically on multiple challenging benchmarks in comparison with some state-of-the-art search algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
Lou, Q., Dechter, R. & Ihler, A.. (2018). Finite-sample Bounds for Marginal MAP. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:724-733 Available from https://proceedings.mlr.press/r16/lou18a.html. Reissued by PMLR on 04 October 2026.

Related Material