Research map / Learning theory and algorithms / Sample complexity

On the Hardness of Approximating Distributions with Tractable Probabilistic Models

NeurIPS 2025 · Learning theory and algorithms › Sample complexity · approach: Hardness of learning neural networks · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that approximating distributions within a bounded f-divergence with any tractable-marginal model is NP-hard, and proves an unconditional exponential size gap between decomposable and deterministic-decomposable probabilistic circuits under TV approximation.

Problem

Whether allowing small approximation error (in f-divergence / total variation) avoids the exponential size blow-ups that exact representation of distributions by tractable probabilistic circuits incurs, and what approximate modeling implies for marginal and MAP inference.

Approach

Reduces SAT to approximate modeling of a uniform distribution over a constructed Boolean formula, showing bounded f-divergence approximation is NP-hard for any tractable-marginal model; separates decomposable from deterministic decomposable PCs by pruning a deterministic PC into a weak approximation of the Sauerhoff function and applying known d-DNNF rectangle lower bounds.

Key results

• Approximating a distribution with bounded f-divergence (k eps^2 for k-convex f, eps<1/4) is NP-hard for any model supporting tractable marginals, including decomposable PCs.
• A decomposable PC of size O(n^2) approximating within TV 1/16 - Omega(1/poly(n^2)) requires any deterministic decomposable PC of size 2^{Omega(n)}, an unconditional exponential gap.
• Bounded f-divergence implies absolute approximation of marginals and MAP, but not relative approximation or conditional queries (counterexamples given).

Surprising findings

• Bounded total variation distance does not imply relative approximation of marginals, and small TV can coexist with arbitrarily large conditional MAP error.

Limitations

• Results are for f-divergences (k-convex) and the hardness applies to worst-case distributions rather than typical learning settings.
• Separation is shown only for deterministic decomposable vs decomposable PCs, not other tractable classes.
• Paper contains no experiments.

Experimental setup

Builds on: probabilistic circuits k-convex f-divergences Sauerhoff function rectangle partitions for d-DNNF lower bounds

Closest papers by meaning

• The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models (NeurIPS 2026 · similarity 0.90)
• On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.89)
• Sum of Squares Circuits (AAAI 2025 · similarity 0.88)
• Scaling Probabilistic Circuits via Monarch Matrices (ICML 2025 · similarity 0.88)
• Probabilistic Neural Circuits (AAAI 2024 · similarity 0.87)
• Neural Network Approximators for Marginal MAP in Probabilistic Circuits (AAAI 2024 · similarity 0.87)