Statistical Guarantees for Probabilistic Circuit Parameter Learning

Abstract

The expressive capabilities of probabilistic circuits (PCs) in the exact case has been studied extensively, as well as, to a lesser degree the approximate case. However, statistical guarantees such as the sample complexity for learning PCs remain largely unexplored. In this paper, we show a number of results to address this gap. First, we prove a lower bound, linear in the size of the PC, on the number of samples needed for any learning algorithm to guarantee bounded distance (Hellinger, reverse Kullback-Leibler, or total variation). Next, for deterministic and decomposable PCs with known structure, we show that this is a tight bound on the number of samples for closed-form maximum-likelihood parameter estimation to ensure small Hellinger distance and reverse KL divergence. Lastly, considering the agnostic setting without the known-structure assumption, we provide a statistical upper bound on the total variation distance via the Good-Turing denoising estimator, and show that as the number of samples increases this bound approaches the distance depending only on the PC structure.