Dynamic Scaled Sampling for Deterministic Constraints

Lei Li, Bharath Ramsundar, Stuart Russell

Introduction

Sampling from probabilistic models subject to deterministic constraints—such as requiring a set of variables to sum to a specific value—is a pervasive problem in fields ranging from systems biology to econometrics. Traditional Monte Carlo methods, including Markov Chain Monte Carlo (MCMC) and Importance Sampling (IS), often fail in these scenarios. In continuous spaces, the probability of a random sample satisfying a precise equality constraint is zero, while in discrete spaces, such constraints can create isolated regions that hinder efficient exploration.

This paper introduces Dynamic Scaled Sampling (DYSC), an algorithm designed to bypass these limitations. DYSC leverages sequential importance sampling with dynamic proposal scaling to achieve linear time complexity $O(k)$ and finite variance, effectively addressing a problem that is generally NP-hard.

The Challenge of Deterministic Constraints

Deterministic relationships, such as $X_1 + X_2 + \dots + X_k = s$, impose significant computational hurdles. The authors provide a formal proof that sampling from a posterior distribution given a sum constraint is NP-hard for both discrete and continuous variables, reducing the problem from the classic SUBSET-SUM problem.

Standard Importance Sampling (IS) typically uses the prior distribution as a proposal. However, as the number of variables $k$ increases, the likelihood of the final sum matching the constraint $s$ vanishes, leading to "explosive" variance and computational failure.

Methodology: Dynamic Scaled Sampling (DYSC)

DYSC approaches the problem through Sequential Importance Sampling (SIS), but with a critical innovation: Dynamic Scaling.

  1. Sequential Budgeting: Variables are sampled one by one. At each step $i$, the algorithm calculates a "target mean" $\eta_i$ based on the remaining "budget" required to satisfy the final constraint $s$.
  2. Proposal Rescaling: Rather than relying on the static prior, DYSC dynamically rescales the proposal distribution so its mean aligns with $\eta_i$. This keeps the sampling trajectory "on track" toward the target sum.
  3. Local Rejection: To ensure feasibility, a local rejection step prevents any single variable $X_i$ from exceeding the remaining allowable sum, guaranteeing that the final variable $X_k$ can always satisfy the constraint.
  4. Generality: While often demonstrated with summation, the framework applies to any deterministic function $f$ representable as a binary operation tree with computable inverses (e.g., multiplication or logical operators).

Key Results and Evaluation

The performance of DYSC was evaluated against standard IS using Poisson (discrete) and LogNormal (continuous) priors.

Linear Scalability

A standout result is DYSC's scalability. While standard IS becomes computationally intractable once the number of variables exceeds 10, DYSC maintains linear $O(k)$ time complexity. In experiments involving heavy-tailed LogNormal distributions, DYSC successfully sampled from a system with 1,000,000 variables in approximately 20 minutes.

Scalability of DYSC vs. Importance Sampling (IS). DYSC achieves linear O(k) time complexity, handling up to 1,000,000 variables.

Sample Quality

Beyond speed, DYSC provides high-quality samples that accurately reflect the true posterior. Using the Kolmogorov-Smirnov (KS) score—a measure of the distance between empirical and theoretical distributions—the authors demonstrated that DYSC converges rapidly. In contrast, non-dynamic methods fail to converge, producing empirical distributions that are wildly inaccurate.

Sample quality comparison using Kolmogorov-Smirnov (KS) score. DYSC converges rapidly to the true posterior (KS score near 0), while standard IS fails completely (KS score near 1).

Conclusion

DYSC represents a significant advancement in constrained sampling. By replacing static proposals with dynamic, budget-aware scaling, it transforms an NP-hard sampling task into a linear-time operation. While future work may explore extensions to dependent priors or more complex deterministic structures, DYSC currently offers a robust solution for high-dimensional models with sum-like constraints.

Summary updated

Abstract

Deterministic and near-deterministic relationships among subsets of random variables in multivariate systems are known to cause serious problems for Monte Carlo algorithms. We examine the case in w...
BibTeX
@inproceedings{li2013dynamic,
  author = {Lei Li and Bharath Ramsundar and Stuart Russell},
  title = {{Dynamic Scaled Sampling for Deterministic Constraints}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2013},
}
Figure