On the Hardness of Approximating Distributions with Tractable Probabilistic Models

Thank you for the constructive feedback. We will incorporate your suggestions to improve presentation in the revision. The additional page available for camera-ready versions upon acceptance would allow us to provide more background on different queries, add a graphical summary, and discuss more related work on approximate weighted model counting. In particular, we agree that our results outside of Section 4 are more broadly applicable beyond PCs, and we will revise to make this clearer. This would strengthen the significance of our contributions to a broader community.

Q1. Thank you for the interesting suggestion. We had not considered probabilistic approximations for this paper, but this relaxation is a promising future direction. It could also be worthwhile to consider in conjunction with the average case complexity that Reviewer Leaf has brought to our attention.

Q2. We agree that ''easy form of approximation'' is not exactly correct. More precisely, there exists a randomized algorithm for the absolute approximation of marginals. We still would not have absolute approximation from this in our sense, but this is one of the few types of approximation we discuss throughout our paper which even has a randomized algorithm. We will adjust the paragraph accordingly.

Q3. While this paper mostly contains negative results, we hope that this will inspire future works on approximations to provide approximate inference guarantees, through relaxations such as probabilistic approximations or average-case guarantees or by considering a special case of target distributions.

Thank you for the constructive feedback.

While Pote and Meel are concerned with a different problem setup, we agree that the proof technique of thresholding using total variation distance and the area are related to our work. Thank you for the pointer, and we will cite the work in the revision. Furthermore, we will adjust the citations to ensure they have the correct capitalization, thank you for catching that mistake.

To answer your question: The total variation distance is indeed hard to compute for many probabilistic models. While some f-divergences such as the KL-divergence can be computed exactly between two PCs, this requires structural constraints that are more restrictive than those we consider in this paper. Nevertheless, note that upper-bounding the divergences suffices to apply our results. Thus, we hope that this work can motivate approximation/learning schemes that provide bounds on divergences which can derive some approximate inference bounds. Moreover, while we showed that approximate modeling with bounded f-divergences is NP-hard, the hope is that with further assumptions we can provide more guarantees that hold in practical settings.

Thank you for the constructive feedback. We answer each question below.

Q1. First, while NP-hardness is only concerned with worst-case complexity, we believe it is important to understand the limitations of the approximation scheme before we can move onto average cases. That being said, while outside the scope of this work, we think that this suggestion is very interesting. In fact, existing literature on expressive efficiency of different PC classes for exact representations is still limited to only worst-case complexity results. Average case complexity would be a good extension to this work, and would answer more questions about PC/tractable model representations in practice. The challenge would be in defining a good notion of ''average case'', for instance by limiting the set of distributions to be of a certain form and defining distributions over its parameter space.

Q2. This is an interesting idea, we have not considered that in this work. We appreciate the suggestion and will consider this in the future.

Thank you for the constructive feedback. We answer individual questions below.

Q1. When we consider relative approximation, we consider arbitrary distributions without assuming a particular representation form. For example, in Section 3.3 we consider a uniform distribution $P$ over the models of $f$, but we do not explicitly encode $P$ as a PC nor any other representation. In fact, representing this uniform distribution $P$ exactly is a non-trivial task because it would need to solve model counting which is #P-hard.

Q2. The main difference between our proofs in Section 4 and those by Bova et al. [1] and De Colnet and Mengel [2] is two-fold. First, we use the Sauerhoff function, which Bova et al. used to show the exponential separation between DNNFs and d-DNNFs, to prove that the exponential gap exists even for weak approximation, defined by De Colnet and Mengel. The latter work in fact only showed that there exists a function that requires an exponential size for a d-DNNF to approximate, but not that such function can be represented by a polysized DNNF. Secondly, we extend this exponential separation to deterministic and decomposable PCs that can represent arbitrary distributions, where as previous results only applied to the case of PCs that are only allowed to represent uniform distributions over a logical formula.

Q3. Understanding the expressive efficiency between different classes of PCs is of high interest to the community and well documented in the literature for the case of exact representations, but is significantly underexplored for approximations. The two PC classes that we consider are two of the most expressive efficient ones in the literature: for instance, all PC structure learning algorithms will output smooth and decomposable circuits. While the condition may seem restrictive, decomposable PCs have been shown to outperform even intractable models on density estimation tasks [3,4,5], while being tractable for marginals. Thus, finding that it is NP-Hard to approximate with decomposable PCs with a non-zero but bounded error is significant. Moreover, our NP-hardness result applies to any model that allows tractable marginal inference, and thus extends beyond decomposable PCs to a wide variety of models, such as determinantal point processes, probabilistic generating circuits, etc.

Lastly, we would like to also reiterate that, to the best of our knowledge, we are the first to concretely establish relationships between approximate inference guarantees and bounded f-divergences. Previously, many types of approximate inference were implicitly assumed to hold when learning to achieve small f-divergences. This result applies generally to probabilistic models, not just PCs.

To address your formatting concerns,

• The computational graph has a scope function $\phi$ which associates each unit $n$ to a subset of the set of random variables $\mathbf{X}$, defined recursively by $\phi(n) = \cup_{c \in \text{in}(c)} \phi(c)$. The scope of a leaf node is simply the variable mentioned at that node. Alternatively, the scope of a node is the union of scopes of all leaf node with paths to that node. We will clarify this in the revision.

• $P$ being non-negative is a typo, this should instead say $P$ is positive only over the models of $f$. Thank you for catching this!

• $Y$ in this case is only a single auxiliary variable, not a set of variables.

[1] Bova, Simone, et al. "Knowledge Compilation Meets Communication Complexity." IJCAI. Vol. 16. 2016.

[2] De Colnet, Alexis, and Stefan Mengel. "Lower bounds for approximate knowledge compilation." Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 2021.

[3] Gala, Gennaro, et al. "Probabilistic integral circuits." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

[4] Liu, Anji, and Guy Van den Broeck. "Tractable regularization of probabilistic circuits." Advances in Neural Information Processing Systems 34 (2021): 3558-3570.

[5] Liu, Anji, Honghua Zhang, and Guy Van den Broeck. "Scaling Up Probabilistic Circuits by Latent Variable Distillation." The Eleventh International Conference on Learning Representations.

We do not need to explicitly construct any model that represents a uniform distribution over the satisfying assignments. The problem that we are showing is NP-hard is to take as an input an unnormalized distribution $\hat{P}$, which can really be any non-negative function, and output a PC representing a distribution that is close (according to $D_f$) to the normalized distribution $P$ defined as: $P(\mathbf{x}) = \hat{P}(\mathbf{x})/Z$ where $Z=\sum_\mathbf{x} \hat{P}(\mathbf{x})$ is the normalizing constant. We know that $\hat{P} \propto P$, and an algorithm to solve this problem, hypothetically, could output the approximation without ever constructing $P$ explicitly.

In our proof, we reduce the SAT problem for formula $f$ by constructing $f'$ from it as described in the paper, and give it as input to our ``approximate modeling' problem. Here, $f'$ can be seen as a Boolean function where $f'(\mathbf{x})=1$ if $\mathbf{x}$ is a satisfying assignment and $f'(\mathbf{x})=0$ otherwise; because it is non-negative, we can treat it as an unnormalized distribution. The goal is to output a PC representing a distribution close to $P = f'(\mathbf{x})/MC(f')$ which we show is NP-hard because such PC can be used to answer SAT for the original formula $f$. We hope this answers your question.

Sorry, got busy for a few days. I agree, sampling solutions to a combinatorial problem is at least as hard as determining existence of a solution. My point is that the difficulty lies in starting with an instance of a combinatorial problem, and that the difficulty of sampling depends on the representation of the distribution. I don't think my example made that clear, though.

"Our proof shows that unless P=NP, such distribution cannot be contained in the set of distributions that can be exactly or approximately modeled by polysized smooth and decomposable PCs."

I still don't think this is true- what your proof shows is that you can't convert a boolean function $f$ into a poly-sized smooth decomposable PC that is uniform on solutions to $f$ in polynomial time, unless P=NP. That's different from saying that you can't have a poly-sized smooth decomposable PC that is uniform on solutions to $f$. In fact, for any poly-sized smooth decomposable PC that models a uniform distribution, there are boolean functions whose solution set is the support of $P$. You just can't compute the PC from the function (in polytime unless P=NP).

Going back to your original theorem statement, this is why I'm so hung up on how you represent the distribution $P$. If $P$ is represented as a boolean formula, then the problem is at least as hard as solving SAT. I agree that Theorem 3.3 proves this. I believe my Theorem 3.3+ is also correct: for some representations of $P$, the problem is uncomputable.

So I think what's going on is that

1. I had different expectations about what the theorem was proving. I initially assumed you were proving that it's hard to convert an arbitrary PC $P$ into a poly-sized marginal-tractable approximation of $P$.

I think my expectations were wrong because when you discuss models of distributions you primarily discuss PCs, so I never considered a boolean function to be a model of a distribution.

2. there are some default assumptions about what a valid model of a distribution is, which I'm not aware of. (Solution to boolean function: good, halting input for Turing machine: silly.)

I personally would like you to make explicit your assumptions about what a valid model of a distribution are. I believe this would fix both issues 1 and 2 for me simultaneously.

Additional notation comment: you use $f$ for both the function in $D_f$ and the boolean function. I think you should fix this one, it's not likely to confuse but it's easy to fix.

Thank you for your patience in reading all of these!