A First Step Towards Even More Sparse Encodings of Probability Distributions

Florian Andreas Marwitz; Tanya Braun; Ralf Möller

cs.AIMar 31, 2026

A First Step Towards Even More Sparse Encodings of Probability Distributions

Authors: Florian Andreas Marwitz, Tanya Braun, Ralf Möller

Organizations: Institute of Information Systems, University of Lübeck, Lübeck, Germany

Abstract

Real world scenarios can be captured with lifted probability distributions. However, distributions are usually encoded in a table or list, requiring an exponential number of values. Hence, we propose a method for extracting first-order formulas from probability distributions that require significantly less values by reducing the number of values in a distribution and then extracting, for each value, a logical formula to be further minimized. This reduction and minimization allows for increasing the sparsity in the encoding while also generalizing a given distribution. Our evaluation shows that sparsity can increase immensely by extracting a small set of short formulas while preserving core information.

Figures & tables

$a\in\{0,1\}$	$b\in\{0,1\}$	$c\in\{0,1\}$	$\phi(a,b,c)$	quartile	cluster
0	0	0	1	1	1
0	0	1	4.7	1	2
0	1	0	4.8	2	2
0	1	1	4.9	2	2
1	0	0	5	3	2
1	0	1	5.1	3	2

Table 1: Reduction result for a parfactor

\phi:\{0,1\}^{3}\to\mathbb{R}^{+}

. The last two columns show which numbers are mapped to the same one when applying the respective strategy. DBSCAN parameters are

\theta_{d}=1,\theta_{n}=1

. Without reduction, we need eight formulas. With quartiles, we need four formulas and two with clustering.

Table 2: Evaluating CoFE: Number of formulas extracted per parfactor (

\#

), number of atoms per formula (

L

), and the mean absolute error (

E

Panel of Figure 1 — Figure 1: Hellinger distances from the original to the noised and mapped models

Probabilistic Logic

Probabilistic logic combines formal rules with probability to represent uncertainty and support inference, learning, and decision-making.

See all 24 papers

Sparse Priors for Efficient Distribution Learning
Sep 16, 2026Saumya Goyal, Barnabás PóczosStatistical Learning Theory Bayesian Inference
Machine Learning Department, Carnegie Mellon University
On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
Aug 31, 2026Guy EmersonProbabilistic Circuits
Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse
Mar 29, 2026Gregory MagarshakLossless Data Compression LLM Inference Acceleration

Sep 16, 2026J/K move · Enter open · S save

Sparse Priors for Efficient Distribution Learning

Saumya Goyal, Barnabás Póczos

Machine Learning Department, Carnegie Mellon University

Statistical Learning Theory Bayesian Inference

Open paper AskPDF arXiv

Despite the widespread use and success of generative AI techniques today, theoretical guarantees on learning a distribution supported in

d

dimensions from

n

samples degrade as

O(n^{-1/Θ(d)})

, though shown to be minimax optimal. We hypothesize that present bounds are too pessimistic because smoothness assumptions are not enough to capture the structure of distributions that often appear in real applications. Consequently, we introduce the class of sparse priors and define the "Sparse Dimension" as a measure of sparsity of a prior over the space of all distributions. We show that distribution learning under a

k

-sparse prior achieves a Bayesian risk lower bound of

Ω(\sqrt{k/n})

under common distance metrics, and show a matching (up to logarithmic terms asymptotically in

n,k

) upper bound for the TV distance under mild additional assumptions. We show the statistical equivalence of distribution learning and learning to sample in the Bayesian setting so that our results apply to learning to sample as well. While

k

can still depend on the dimension

d

, or a notion of intrinsic dimension, our results show that learning under an appropriate prior overcomes the curse of dimensionality with respect to the dependence on

n

Abstract

Probabilistic Logic

Explore similar work

Sparse Priors for Efficient Distribution Learning

On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions

Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse