On the Hardness of Approximating Distributions with Probabilistic Circuits

John Leland, YooJung Choi · 2025

Read On the Hardness of Approximating Distributions with Probabilistic Circuits by John Leland, YooJung Choi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01281.txt.

Introduction

John Leland and YooJung Choi ask whether allowing small errors can save probabilistic models from ballooning in size. Such models are built so that key questions can be answered fast, but exact copies of real-world patterns often need circuits of exponential size. The pair studies approximation instead: a model counts as good if it stays within a small distance of the target pattern, measured by a family of standard scores.

Under that looser goal, they prove that approximating an arbitrary pattern is still NP-hard for any model that can answer basic marginal questions quickly. They also prove an exponential size gap between two circuit families under approximation. The blow-up, in short, cannot be dodged by settling for almost right.

Catalog record

CREATORJohn Leland, YooJung Choi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01281

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Hardness of Approximating Distributions with Probabilistic Circuits John Leland, YooJung Choi 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 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. 1]School of Computing and Augmented Intelligence Arizona State University Tempe, Arizona, USA 1 Introduction Generative models have shown remarkable success in capturing complex distributions [ 21 , 24 , 28 , 22 , 38 ] ; yet, despite their expressivity, they often do not support efficient computation of fundamental probabilistic queries, which are critical for inference in domains such as healthcare [ 33 ] , neuro-symbolic AI [ 36 ] , algorithmic fairness [ 7 ] , and environmental science [ 3 ] . Probabilistic circuits address this by balancing expressivity and tractable inference. Naturally, there have been many works characterizing the expressive efficiency of different circuit classes [ 16 , 1 , 6 , 40 , 41 , 17 ] . However, how structural constraints affect the ability to approximate distributions remains underexplored. This paper studies the following fundamental question: does allowing small approximation error alleviate the exponential separation between circuit classes observed in exact modeling, or does hardness persist even in the approximate setting? Our motivation is two-fold. (1) Showing that certain distributions cannot be approximated within a bounded distance compactly by a family of PCs implies that any learning algorithm whose hypothesis space is that family of PCs would fail to learn the distribution with a bounded approximation error. (2) Moreover, PCs can also be used to perform inference on other probabilistic models (such as Bayesian networks or probabilistic programs) by compiling them into PCs then performing inference on the compiled circuits [ 2 , 23 , 14 , 5 , 20 ] . This suggests the following approximate inference scheme: approximately compile a probabilistic model into a PC then run efficient exact inference on the approximately compiled PC. Thus, if we can bound the distance between the target distribution and approximate model, we can hope to provide guarantees on the approximate inference results as well. Our main contributions are as follows: (1) we prove that it is \mathsf{NP} -hard to approximate distributions within a bounded f -divergence using any model that tractably computes marginals, via a reduction from SAT (Theorem 3.3 and 3.4 ); (2) we derive an unconditional, exponential separation between decomposable PCs and decomposable & deterministic PCs for approximate modeling (Theorem 4.1 ); (3) we study the relationship between bounds on divergence measures for approximate modeling and approximation errors for marginal and maximum-a-posteriori (MAP) inference, characterizing when one is or is not sufficient to guarantee the other (Section 3 and further discussion in Appendix B ). 2 Preliminaries Notations We use uppercase letters ( X ) to denote random variables and lowercase letters ( x ) to denote their assignments. Sets of random variables and assignments are denoted using bold letters ( \mathbf{X}\text{ and }\mathbf{x} ). The accepting models of a Boolean function f:\{0,1\}^{n}\!\rightarrow\!\{0,1\} over n variables is denoted by f^{-1}(1) , and the number of accepting models by \MC(f) . Moreover, a Boolean function f is the support of a distribution P , if P is positive only over the models of f . Probabilistic Circuits A probabilistic circuit (PC) recursively encodes a joint probability distribution over random variables through a parameterized directed acyclic graph (DAG), composed of 3 types of nodes: leaf, product \otimes , and sum nodes \oplus . PCs are closely related to logical circuits in the knowledge compilation literature [ 16 ] . Logical circuits encode Boolean functions as directed acyclic graphs (DAGs) consisting of AND ( \wedge ) and OR ( \vee ) gates—analogous to \otimes and \oplus nodes, respectively—with positive and negative literals as leaf nodes. We can characterize different families of both probabilistic and logical circuits based on their structural properties, such as decomposability and determinism . These circuit properties allow tractable (polytime) computation of various queries); for instance, decomposable PCs admit linear-time marginal inference while deterministic and decomposable PCs additionally allow linear-time maximum-a-posteriori (MAP) inference. There is a rich literature studying different families of circuit representations in terms of their tractability for inference and operations, as well as their relative succinctness (expressive efficiency) for both exact and approximate compilation, which we will leverage for our hardness results and size lower bounds on PCs. See Appendix A for further background on PCs. Measures of Difference between Probability Distributions To study the hardness of approximating probability distributions, we must first measure how “good” an approximation is. We focus on the class of f -divergences. Definition 2.1 ( f -divergence [ 29 ] ) . Let f:(0,\infty)\to\mathbb{R} be a convex function with f(1)=0 , and P,Q be two probability distributions over a set of Boolean variables \mathbf{X} . If Q>0 wherever P>0 , the f -divergence between P and Q is defined as D_{f}(P||Q)=\sum_{\mathbf{x}}Q(\mathbf{x})f(\frac{P(\mathbf{x})}{Q(\mathbf{x})}) . Commonly used f -divergences include the Kullback-Leibler divergence, \chi^{2} -divergence, and the total variation distance, which is especially relevant to our results. Definition 2.2 (Total Variation Distance) . The total variation distance (TVD) between two probability distributions P and Q over a set of n Boolean variables \mathbf{X} is defined as D_{\mathsf{TV}}(P\|Q)=\frac{1}{2}\sum_{\mathbf{x}\in\mathbf{X}}\left\lvert P(\mathbf{x})-Q(\mathbf{x})\right\rvert , or equivalently D_{\mathsf{TV}}(P\|Q)=\max_{S\subseteq\{0,1\}^{n}}\left\lvert P(S)-Q(S)\right\rvert . To more compactly describe PCs that approximate distributions under some bounded distance, we use the following. Definition 2.3 ( \epsilon - D -Approximation) . Let P,Q be some probability measures and D be some distance we want to minimize between P and Q . We say that Q is an \epsilon - D -Approximator of P if D(P||Q)<\epsilon for some \epsilon>0 . We refer to any circuit Q such that it approximates our target distribution P within D_{\mathsf{TV}}(P\|Q)<\epsilon a \epsilon - \mathcal{D}_{\mathsf{TV}} - Approximator . The majority of our results are derived using properties of the total variation distance, due to its properties as a distance metric. To extend our results to f -divergences, we utilize the class of k -convex f-divergences, which provides an upper bound on the total variation distance. We can define a k -convex f-divergence [ 27 ] as a \mathbb{R}\cup\{\infty\} -valued function f on a convex set K\subseteq\mathbb{R} is k -convex when x,y\in K and t\in[0,1] implies f((1-t)x+ty)\leq(1-t)f(x)+tf(y)-kt(1-t)\frac{(x-y)^{2}}{2}. When f is twice differentiable, this is equivalent to f^{\prime\prime}(x)\geq k for x\in K . In the case that k=0 this reduces to the normal notion of convexity. An f -divergence D_{f} is k -convex over an interval K for

Read the complete text