Fast Stochastic Quadrature for Approximate Maximum-Likelihood Estimation

Nico Piatkowski, Katharina Morik
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:714-723, 2018.

Abstract

Recent stochastic quadrature techniques for undirected graphical models rely on near- minimax degree-k polynomial approximations to the model’s potential function for inferring the partition function. While providing de- sirable statistical guarantees, typical construc- tions of such approximations are themselves not amenable to efficient inference. Here, we develop a class of Monte Carlo sampling algo- rithms for efficiently approximating the value of the partition function, as well as the asso- ciated pseudo-marginals. More precisely, for pairwise models with n vertices and m edges, the complexity can be reduced from O(dk) to O(k4 + kn + m), where d $\geq$4m is the parameter dimension. We also consider the uses of stochastic quadrature for the problem of maximum-likelihood (ML) parameter esti- mation. For completely observed data, our analysis gives rise to a probabilistic bound on the log-likelihood of the model. Maxi- mizing this bound yields an approximate ML estimate which, in analogy to the moment- matching of exact ML estimation, can be inter- preted in terms of pseudo-moment-matching. We present experimental results illustrating the behavior of this approximate ML estimator.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-piatkowski18a, title = {Fast Stochastic Quadrature for Approximate Maximum-Likelihood Estimation}, author = {Piatkowski, Nico and Morik, Katharina}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {714--723}, 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/piatkowski18a/piatkowski18a.pdf}, url = {https://proceedings.mlr.press/r16/piatkowski18a.html}, abstract = {Recent stochastic quadrature techniques for undirected graphical models rely on near- minimax degree-k polynomial approximations to the model’s potential function for inferring the partition function. While providing de- sirable statistical guarantees, typical construc- tions of such approximations are themselves not amenable to efficient inference. Here, we develop a class of Monte Carlo sampling algo- rithms for efficiently approximating the value of the partition function, as well as the asso- ciated pseudo-marginals. More precisely, for pairwise models with n vertices and m edges, the complexity can be reduced from O(dk) to O(k4 + kn + m), where d $\geq$4m is the parameter dimension. We also consider the uses of stochastic quadrature for the problem of maximum-likelihood (ML) parameter esti- mation. For completely observed data, our analysis gives rise to a probabilistic bound on the log-likelihood of the model. Maxi- mizing this bound yields an approximate ML estimate which, in analogy to the moment- matching of exact ML estimation, can be inter- preted in terms of pseudo-moment-matching. We present experimental results illustrating the behavior of this approximate ML estimator.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Fast Stochastic Quadrature for Approximate Maximum-Likelihood Estimation %A Nico Piatkowski %A Katharina Morik %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-piatkowski18a %I PMLR %P 714--723 %U https://proceedings.mlr.press/r16/piatkowski18a.html %V R16 %X Recent stochastic quadrature techniques for undirected graphical models rely on near- minimax degree-k polynomial approximations to the model’s potential function for inferring the partition function. While providing de- sirable statistical guarantees, typical construc- tions of such approximations are themselves not amenable to efficient inference. Here, we develop a class of Monte Carlo sampling algo- rithms for efficiently approximating the value of the partition function, as well as the asso- ciated pseudo-marginals. More precisely, for pairwise models with n vertices and m edges, the complexity can be reduced from O(dk) to O(k4 + kn + m), where d $\geq$4m is the parameter dimension. We also consider the uses of stochastic quadrature for the problem of maximum-likelihood (ML) parameter esti- mation. For completely observed data, our analysis gives rise to a probabilistic bound on the log-likelihood of the model. Maxi- mizing this bound yields an approximate ML estimate which, in analogy to the moment- matching of exact ML estimation, can be inter- preted in terms of pseudo-moment-matching. We present experimental results illustrating the behavior of this approximate ML estimator. %Z Reissued by PMLR on 04 October 2026.
APA
Piatkowski, N. & Morik, K.. (2018). Fast Stochastic Quadrature for Approximate Maximum-Likelihood Estimation. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:714-723 Available from https://proceedings.mlr.press/r16/piatkowski18a.html. Reissued by PMLR on 04 October 2026.

Related Material