On the Hardness of Approximating Distributions with Probabilistic Circuits

• URL: http://arxiv.org/abs/2506.01281v1
• Date: Mon, 02 Jun 2025 03:35:07 GMT
• Title: On the Hardness of Approximating Distributions with Probabilistic Circuits
• Authors: John Leland, YooJung Choi,
• Abstract summary: We show that approximating an arbitrary distribution with bounded $f$-divergence is $mathsfNP$-hard for any model that can tractably compute marginals.<n>We then prove an exponential size gap for approximation between the class of decomposable PCs and additionally deterministic PCs.
• Score: 8.582070926175966
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental challenge in probabilistic modeling is balancing expressivity and tractable inference. Probabilistic circuits (PCs) aim to directly address this tradeoff by imposing structural constraints that guarantee efficient inference of certain queries while maintaining expressivity. Since inference complexity on PCs depends on circuit size, understanding the size bounds across circuit families is key to characterizing the tradeoff between tractability and expressive efficiency. However, expressive efficiency is often studied through exact representations, where exactly encoding distributions while enforcing various structural properties often incurs exponential size blow-ups. Thus, we pose the following question: can we avoid such size blow-ups by allowing some small approximation error? We first show that approximating an arbitrary distribution with bounded $f$-divergence is $\mathsf{NP}$-hard for any model that can tractably compute marginals. We then prove an exponential size gap for approximation between the class of decomposable PCs and additionally deterministic PCs.

Related papers

• The Limits of Tractable Marginalization [23.716205079188608]
  Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem.<n>We show that when there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation.<n>We conclude with a result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation.
  arXiv  Detail & Related papers  (2025-04-17T07:54:56Z)
• Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress [2.2164989053903805]
  Efficient probabilistic inference by variable elimination in graphical models requires an optimal elimination order.<n>We adapt a reinforcement learning approach to find efficient contraction orders in tensor networks.<n>We show that leveraging specific structures during inference allows for introducing compact encodings of intermediate results.
  arXiv  Detail & Related papers  (2025-03-11T18:00:23Z)
• Robust Counterfactual Inference in Markov Decision Processes [1.5197843979051473]
  Current approaches assume a specific causal model to make counterfactuals identifiable.<n>We propose a novel non-parametric approach that computes tight bounds on counterfactual transition probabilities.
  arXiv  Detail & Related papers  (2025-02-19T13:56:20Z)
• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Scalable Computation of Causal Bounds [11.193504036335503]
  We consider the problem of computing bounds for causal queries on causal graphs with unobserved confounders and discrete valued observed variables. Existing non-studied approaches for computing such bounds use linear programming (LP) formulations that quickly become intractable for existing solvers. We show that this LP can be significantly pruned, allowing us to compute bounds for significantly larger causal inference problems compared to existing techniques.
  arXiv  Detail & Related papers  (2023-08-04T21:00:46Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach [7.059472280274009]
  We present an exact Bayesian inference method for discrete statistical models. We use a probabilistic programming language that supports discrete and continuous sampling, discrete observations, affine functions, (stochastic) branching, and conditioning on discrete events. Our inference method is provably correct and fully automated.
  arXiv  Detail & Related papers  (2023-05-26T16:09:59Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  Inference in discrete graphical models with variational methods is difficult. Many sampling-based methods have been proposed for estimating Evidence Lower Bound (ELBO) We propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN) We show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is aweighted the corresponding ELBO can be computed analytically.
  arXiv  Detail & Related papers  (2020-10-22T05:04:38Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.