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 nearminimax degree-k polynomial approximations to the model’s potential function for inferring the partition function. While providing desirable statistical guarantees, typical constructions of such approximations are themselves not amenable to efficient inference. Here, we develop a class of Monte Carlo sampling algorithms for efficiently approximating the value of the partition function, as well as the associated 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 estimation. For completely observed data, our analysis gives rise to a probabilistic bound on the log-likelihood of the model. Maximizing this bound yields an approximate ML estimate which, in analogy to the momentmatching of exact ML estimation, can be interpreted 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 nearminimax degree-k polynomial approximations to the model’s potential function for inferring the partition function. While providing desirable statistical guarantees, typical constructions of such approximations are themselves not amenable to efficient inference. Here, we develop a class of Monte Carlo sampling algorithms for efficiently approximating the value of the partition function, as well as the associated 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 estimation. For completely observed data, our analysis gives rise to a probabilistic bound on the log-likelihood of the model. Maximizing this bound yields an approximate ML estimate which, in analogy to the momentmatching of exact ML estimation, can be interpreted 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 nearminimax degree-k polynomial approximations to the model’s potential function for inferring the partition function. While providing desirable statistical guarantees, typical constructions of such approximations are themselves not amenable to efficient inference. Here, we develop a class of Monte Carlo sampling algorithms for efficiently approximating the value of the partition function, as well as the associated 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 estimation. For completely observed data, our analysis gives rise to a probabilistic bound on the log-likelihood of the model. Maximizing this bound yields an approximate ML estimate which, in analogy to the momentmatching of exact ML estimation, can be interpreted 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