Statistical Guarantees for Probabilistic Circuit Parameter Learning

Abstract

The expressive efficiency of PC classes has been studied extensively in the exact case and, although to a lesser degree, the approximate case. However, these results are mainly concerned with the theoretical ability of circuits to compactly represent functions. Statistical guarantees, such as sample complexity, for learning PCs remain largely unexplored. In this paper, we first prove a lower bound, linear in the size of the PC, on the number of samples needed forany learning algorithmto guarantee bounded statistical distance (Hellinger, reverse Kullback-Leibler, or total variation) with high probability. Next, for learning the parameters of decomposable PCs under known structure, we also show a matching upper bound on the number of samples in the case of the Hellinger distance and reverse KL divergence. Lastly, in the agnostic setting without the known-structure assumption, we provide an instance-specific statistical upper bound on the total variation distance using the Good-Turing denoising estimator, which approaches the irreducible distance due to PC structure as the number of samples increases.

Citation

@inproceedings{LelandTPM26,
  author    = {Leland, John and Choi, YooJung},
  title     = {Statistical Guarantees for Probabilistic Circuit Parameter Learning},
  booktitle = {The 9th Workshop on Tractable Probabilistic Modeling (TPM)},
  month     = {Aug},
  year      = {2026},
}