Fast Stochastic Quadrature for Approximate Maximum-Likelihood Estimation

Nico Piatkowski, Katharina MorikUAI 2018 · OpenReview

Abstract

Undirected graphical models, such as Markov Random Fields, are powerful tools for modeling complex dependencies but suffer from the computational intractability of their partition functions. This paper presents Fast Stochastic Quadrature (FSQ), an advancement of Stochastic Clenshaw-Curtis Quadrature (SCCQ) that achieves high-performance approximate maximum-likelihood estimation. By exploiting combinatorial symmetries and introducing a direct sampling scheme, the authors reduce the complexity of the approximation from exponential to polynomial. The resulting algorithm is structure-oblivious, embarrassingly parallel, and provides rigorous statistical guarantees, making it suitable for high-dimensional models where traditional methods like MCMC or Variational Inference struggle.

Introduction

In the realm of undirected graphical models, calculating the probability of an observation requires the normalization constant known as the partition function ($Z$). For most non-trivial models, computing $Z$ is a #P-hard problem, as it involves a summation over an exponentially large state space. While Markov Chain Monte Carlo (MCMC) and Variational Inference (VI) are common workarounds, they often lack convergence diagnostics or rigorous error bounds.

Stochastic Quadrature offers a promising alternative by using polynomial approximations to provide statistical guarantees. However, the original formulation of Stochastic Clenshaw-Curtis Quadrature (SCCQ) was computationally prohibitive, requiring a "naive" summation over $d^k$ terms, where $d$ is the parameter dimension and $k$ is the polynomial degree. This paper introduces Fast Stochastic Quadrature, transforming this theoretical method into a practical tool for large-scale machine learning.

Methodology

The core contribution of this work is the reduction of SCCQ's complexity from $O(d^k)$ to $O(k^4 + kn + m)$. This is achieved through three primary innovations:

1. Combinatorial Normalization

The authors demonstrate that for discrete models, the "tuple mass"—the weight assigned to different regions of the polynomial approximation—can be normalized in $O(1)$ time. By utilizing the properties of Stirling numbers and combinatorial identities, the total mass can be calculated analytically rather than through exhaustive summation.

2. Direct Sampling

To replace slow rejection sampling, the authors developed a multi-stage direct sampling scheme. This process involves:

  1. Selecting the number of distinct cliques.
  2. Identifying the specific cliques.
  3. Determining the joint states. This ensures that every generated sample is valid and that the sampling process remains within polynomial time complexity.

3. Marginal Inference and ML Estimation

The framework is extended to estimate marginal probabilities using importance sampling. This allows the same set of stochastic quadrature samples to be reused for estimating all marginals simultaneously. This efficiency is crucial for Maximum-Likelihood (ML) parameter estimation, which requires repeated marginal calculations during optimization.

Experimental Results

The proposed method was evaluated on both synthetic and real-world datasets:

  • Runtime Performance: On a $4 \times 4$ binary Ising grid, the new normalization and sampling methods achieved speedups of several orders of magnitude. For a polynomial degree $k=4$, runtime was reduced from approximately $10^{10}$ nanoseconds to just $10^2$ nanoseconds.
  • Accuracy on High-Dimensional Data: Using the UCI Mushroom dataset ($|X| \approx 2^{43}$), the authors demonstrated that even a low-degree polynomial ($k=3$) yielded negative log-likelihood and Mean Squared Error (MSE) results nearly identical to exact calculations.

Discussion

A key advantage of FSQ is its structure obliviousness. Unlike message-passing algorithms (e.g., Belief Propagation), FSQ's performance does not depend on the graph's treewidth or the presence of loops. It relies solely on the "integrability" of the statistics. Furthermore, because the Monte Carlo samples are independent, the algorithm is embarrassingly parallel, scaling linearly with hardware resources.

Conclusion

Fast Stochastic Quadrature bridges the gap between the theoretical rigor of polynomial approximation and the practical needs of high-dimensional machine learning. By bypassing the "curse of dimensionality" through combinatorial symmetry, it provides a robust, scalable alternative for inference and learning in complex undirected models. Future work will explore extensions to mixed domains and non-tree-structured models where exact inference remains impossible.

Summary updated

BibTeX
@inproceedings{piatkowski2018fast,
  author = {Nico Piatkowski and Katharina Morik},
  title = {{Fast Stochastic Quadrature for Approximate Maximum-Likelihood Estimation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=xAHBuGAsvJP9},
}
Figure