Statistical and Computational Tradeoffs in Stochastic Composite Likelihood

Joshua V. Dillon, Guy Lebanon

Abstract

Maximum Likelihood Estimation (MLE) is often computationally intractable for complex models like Markov Random Fields due to the exponential complexity of the partition function. This paper introduces Stochastic Composite Likelihood (SCL), a framework that enables a principled tradeoff between statistical precision and computational cost. By randomly sampling components of the likelihood function, SCL produces consistent and asymptotically normal estimators that are significantly faster than the MLE.

Introduction

In statistical modeling, the Maximum Likelihood Estimator (MLE) is favored for its asymptotic efficiency. However, for many high-dimensional models, calculating the full likelihood is infeasible. While alternatives like Pseudo-Likelihood (PL) offer computational efficiency, they often suffer from significant loss in statistical accuracy. SCL bridges this gap by providing a tunable family of estimators that allow researchers to navigate the frontier between the "fast but loose" PL and the "optimal but impossible" MLE.

The Stochastic Composite Likelihood Framework

SCL decomposes the full likelihood into smaller, manageable "likelihood objects"—typically conditional probabilities of variable subsets. The framework introduces two key mechanisms for control:

  1. Stochastic Selection: Each likelihood component is assigned a selection probability $\lambda$. For each data point, components are sampled according to these probabilities, directly controlling the CPU budget.
  2. Weighting: Components are assigned weights $\beta$, allowing the estimator to prioritize more informative pieces of the likelihood.

The authors prove that despite the stochastic nature of the computation, the resulting SCL estimator remains statistically consistent and asymptotically normal.

Experimental Evaluation

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

  • Boltzmann Machines: Used to theoretically analyze variance behavior as higher-order components are integrated.
  • Movie Review Sentiment: A dataset of 249 reviews labeled with sentiment levels, used to test SCL within Conditional Random Fields (CRFs).

Analysis of Tradeoffs

A primary result of the study is the quantifiable reduction in estimator variance as higher-order components are added. As shown in Figure 1, moving from first-order (PL1) to fourth-order (PL4) components significantly reduces the variance, rapidly approaching the theoretical MLE limit.

Variance reduction in Boltzmann machines as a function of the mixing parameter $\alpha$ and likelihood order.

Empirical results on the movie review dataset revealed a surprising "win-win" scenario. While SCL was designed for speed, the use of lower-order likelihoods often acted as a form of regularization. This prevented overfitting, leading to better generalization on test data compared to more complex likelihood approximations. Figure 2 illustrates the loglikelihood surface, showing how performance varies with selection probability and component weighting.

Test-set loglikelihood surface showing the impact of selection probability and component weighting.

Conclusion

SCL provides a robust mathematical bridge between computation and statistics. It allows for the optimization of likelihood components within a fixed time budget, demonstrating that computational constraints do not necessarily preclude high statistical performance. Future work includes refining the selection of optimal weights $\beta$, which currently depends on unknown true parameters, and exploring the framework's performance across diverse graph structures in Markov Random Fields.

Summary updated

Abstract

Maximum likelihood estimators are often of limited practical use due to the intensive computation they require. We propose a family of alternative estimators that maximize a stochastic variation of the composite likelihood function. Each of the estimators resolve the computation-accuracy tradeoff differently, and taken together they span a continuous spectrum of computation-accuracy tradeoff resolutions. We prove the consistency of the estimators, provide formulas for their asymptotic variance, statistical robustness, and computational complexity. We discuss experimental results in the context of Boltzmann machines and conditional random fields. The theoretical and experimental studies demonstrate the effectiveness of the estimators when the computational resources are insufficient. They also demonstrate that in some cases reduced computational complexity is associated with robustness thereby increasing statistical accuracy.
BibTeX
@article{dillon2009statistical,
  author = {Joshua V. Dillon and Guy Lebanon},
  title = {{Statistical and Computational Tradeoffs in Stochastic Composite Likelihood}},
  journal = {AISTATS},
  year = {2009},
}
Figure