CS Paper Radar

Compositional Information Geometry of Probabilistic Programs

Jacek Karwowski, Frank Nielsen, Sam Staton

cs.PL cs.CG ·submitted 2026-10-13 07:41 UTC · v1
highly cited

Abstract

We study the compositional, intensional information geometry of probabilistic programs. For a first-order probabilistic programming language with finite random variables, we construct a contravariant lax monoidal functor that, for a program of type $X \to Y$, pulls back a (degenerate) Riemannian metric on $Y$ to $X$. It specialises to the Fisher metric in the case of standard statistical models and to ordinary pullback in the case of deterministic programs. We further justify this construction in two ways. First, we show that this functor arises as a pullback of geometry from a universal space of programs over a type $Y$ with a fixed trace space. Second, we show that it is a special case of a more general pullback construction over weighted measures. Our compositional geometry depends on the presentation of the program, and we study how it relates to the (non-compositional) geometry of the realised measures by establishing a three-level inequality relating our score-velocity metric for the program, the program's corresponding output-conditioned metric, and the standard Wasserstein-Fisher-Rao metric of the realised family. Finally, we show how the theory can be extended to accommodate continuous random variables using diffeological quasi-Borel spaces. We also discuss several concrete directions for future work.

Closest papers

Nearest neighbours by meaning across the whole index.

Bayes Rule for Conditioning Probabilistic Programs

cs.PL cs.LO ·2026-10-07 ·Feras A. Saad
similarity 0.62
Abstract

Probabilistic programs provide a rigorous programming-language foundation for expressing rich probabilistic models and offer language-level support for solving challenging statistical inference problems. A key theoretical challenge that probabilistic programs inherit from probability theory is conditioning a probability distribution on an observation that has probability zero. Many languages address this challenge by using computational rules for conditioning that may work well for some problems but are statistically unsound for others. This article introduces a principled mathematical approach for conditioning probabilistic programs. We first show that existing techniques based on "soft conditioning" and "neighborhood limits" exhibit semantic issues from the perspective of measure theory and produce inference results that disagree with sound statistical reasoning. By leveraging tools from geometric measure theory, we construct a novel disintegration-based semantics for probabilistic program traces that enables sound conditioning. The theory delivers an explicit Bayes rule representation of the conditional distribution, which is directly compatible with widely used probabilistic inference algorithms that require access to unnormalized posterior densities. Our Bayes rule handles probabilistic models with loops, branches, discrete, continuous, and mixed-type distributions, observations on manifolds, differentiable structure, and additional modeling motifs that arise in practice.

0.15

Combinatorial Characterizations of the Learnability of Conditional Distributions

cs.LG stat.ML ·2026-10-22 ·Mihir Dhanakshirur, Ambuj Tewari
similarity 0.58
Abstract

We study the PAC-learnability of function classes that map inputs to probability distributions over a finite space. The learner observes i.i.d. input-label pairs, with each label sampled from the conditional distribution of an unknown target hypothesis in the class. We measure learning through excess risk under a bounded proper loss that satisfies two mild assumptions. We introduce the \textbf{fat$_γ$Natarajan dimension}, which generalizes both fat$_γ$ and Natarajan dimension, and prove that its finiteness at every positive scale is necessary and sufficient for learnability. We also introduce a \textbf{fat$_γ$Graph} dimension extending the classical \gra dimension and establish inequalities comparing the two dimensions at different scales, leading to an equivalent characterization of learnability. Finally, we show that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.

0.15

Monad Structures on Topological Spaces Comprising Mislove's Random Variables

cs.LO ·2026-08-19 ·Chengyu Zhou, Qingguo Li
similarity 0.58
Abstract

Mislove, Goubault and Varacca investigated how to define random variables in Domain theory to form monads over the category of bounded complete domains. They intended to model probabilistic programming languages with their random variables monads. In this paper, we focus on the random variables defined by Mislove from a topological perspective. We provide a topology for $\surd$-max continuous random variables on a $T_0$ space, we construct a new $T_0$ space, where $\surd$-max property is essential for the monad structures. We show that the spaces of normalized $\surd$-max simple random variables form a monad over the category of $T_0$ spaces and that the spaces of normalized $\surd$-max continuous random variables give a monad over the category of d-spaces. In addition, on a sober space, the space of normalized $\surd$-max continuous random variables is the sobrification of the space of normalized $\surd$-max simple random variables.

0.22

Bregman geometry in regular exponential families: dual representations and relative smoothness

cs.LG stat.MLmath.OC ·2026-11-13 ·Mame Diarra Fall, Éric Barat, Nicolas Dobigeon
similarity 0.57
Abstract

Regular exponential-family distributions are ubiquitous in statistics due to their appealing and convenient properties. Notably, they can be expressed in terms of Bregman divergences, revealing fundamental connections between statistics, convex analysis, and information geometry. However, this geometric structure has not been systematically exploited to characterize these distributions with respect to their expectation parametrization. Building on a projective characterization, we establish a general construction of equivalent dual Bregman representations, together with normalization and uniqueness results. These representations express log-densities as ordinary Bregman divergences in dual coordinate systems, providing geometric characterizations of the parameter space. So-called $β$- and $α$-scaled dual representations emerge as particular instances of this framework. We further derive dual Bregman representations of conjugate priors and establish that they preserve conjugacy. Applications to classical distributions illustrate the geometric structures underlying seemingly different statistical models. Moreover, we show that these representations provide natural reference geometries for establishing relative smoothness of the primal Bregman representation of the distribution, with explicit bounds that are sharp in the scalar and separable settings. An illustrative application to the Poisson distribution sheds new light on several works in the literature, providing complementary geometric justifications for reference geometries while deriving existing algorithms.

0.34

Sample-Smooth Spaces: A Convenient Category for Differentiable Probabilistic Programming

cs.LG math.CTcs.LOcs.PL+1 ·2026-08-14 ·Patrick Forré
theory similarity 0.57
Abstract

We introduce the category $\mathbf{SSS}$ of sample-smooth spaces over a mixed site. The test objects are the products $Ω_n := \mathbb{R}^n \times Ω$ of a Cartesian space with the universal Hilbert cube $Ω$ carrying all universally measurable sets, and a space is a set with a family of admissible plots $Ω_n \to \mathcal{X}$ closed under precomposition. Smoothness and measurability are then not two structures glued along an axiom, but one structure over one site. The site has finite non-empty products, because $Ω$ absorbs its own square; its Karoubi envelope contains every $\mathbb{R}^n$; and it has mixed morphisms $ω\mapsto (W(ω),Φ(ω))$, which turn measurability of a smooth family from an axiom into a consequence. $\mathbf{SSS}$ is a concrete quasitopos: complete, cocomplete, cartesian closed and locally cartesian closed, with a classifier for embeddings. Morphisms of Cartesian spaces are exactly the $C^\infty$ maps and manifolds embed full and faithfully, both without Boman's theorem. Every object has tangent and cotangent spaces, every morphism a differential. The modalities sit in an adjoint string $Π\dashv \flat \dashv \natural \dashv \sharp \dashv Λ$, making $\mathbf{SSS}$ cohesive over quasi-universal spaces. The point is the probability monad. Defining the plots of $\mathsf{P}(\mathcal{X})$ as push-forwards of $\mathcal{X}$-plots at every test object, $\mathsf{P}$ is an unconditional strong commutative affine monad on all of $\mathbf{SSS}$ -- functor, unit, product of kernels, multiplication and the monad laws are each one line of seed splitting -- and its Kleisli category, of differentiable simulators, is a Markov category. The reparametrisation trick holds by construction: every Kleisli morphism is plot-wise a sampler, stably under composition. A reflection theorem locates the whole gain in a single plot family.

0.04

Countable Nondeterminism in Weighted Programming with an Application to Mechanized Foundations for Probabilistic Program Verification

cs.PL cs.LO ·2026-10-29 ·Sebastian Körner, Oliver Emil Bøving, Christoph Matheja
theory similarity 0.55
Abstract

Weighted programming is a framework by Batz et al. for describing mathematical models or optimization problems as imperative programs parametrized over semirings and then analyzing them with program verification techniques like weakest precondition calculi. Applications include reasoning about expected outcomes of probabilistic programs and competitive analysis of online algorithms. We extend weighted programming with (1) countable nondeterminism and (2) user-defined additive rewards, where programs are parametrized over modules instead of semirings. The resulting framework enables reasoning about expected resource consumption of probabilistic programs and about optimal scores of combinatorial games. A technical challenge is that wp-calculi for weighted programs with (1) and (2) over arbitrary modules can be unsound, because it is well-known that continuity properties commonly used in program semantics break in the presence of countable nondeterminism. We study conditions under which a wp-style transformer for reasoning about weighted programs is sound with respect to an operational ground truth defined in terms of weighted decision processes (WDPs) - transition systems that generalize Markov decision processes by drawing transition weights and state rewards from a module. Based on those conditions, we show that a range of concrete instances of the weighted programming framework enjoy sound weakest precondition reasoning. We demonstrate the usefulness of our wp-semantics through case studies for different modules. We mechanized our extended weighted programming framework and our main soundness results in the interactive theorem prover Lean. Instantiating these results for probabilistic programming yields, to the best of our knowledge, the first mechanized proof of a fixed point characterization of minimal expected rewards in Markov decision processes with countable nondeterminism.

0.25

Second-order Sinkhorn Geometry and $\sqrt{n}$-Inference

cs.LG stat.MLmath.ST ·2026-10-27 ·Tristan Luca Saidi, Florian Gunsilius, Gonzalo Mena
theory similarity 0.54
Abstract

The Sinkhorn divergence, a debiased form of entropic optimal transport, has been widely used in various scientific disciplines due to its computational and statistical tractability. Unlike the Wasserstein distance, however, the Sinkhorn divergence is not a metric and it does not naturally admit a formal Riemannian structure. These properties are central to many applications of optimal transport methods that utilize interpolation, barycentric averaging, parallel transport or other geometric operations. Recent work addresses these shortcomings by constructing a formal Riemannian tangent space and a metric tensor on the space of probability measures that quadratically approximates the Sinkhorn divergence. In this work, we extend this framework with two major threads of contributions. For a suitable class of finite-smoothness cost functions, we prove Hadamard differentiability of the Sinkhorn metric tensor and we derive the Levi-Civita covariant derivative in this geometry; we then use the covariant derivative to obtain the geodesic and parallel transport equations, each of which amount to an ODE on a fixed Reproducing Kernel Hilbert Space (RKHS) with smooth coefficients. Our second contribution is to linearize the solutions to the geodesic and parallel transport equations using standard tools from Banach space ODE theory. We show that under standard regularity conditions these linearizations imply $\sqrt{n}$-limiting Gaussian processes centered at population values for the plugin estimators of the exponential map, the logarithmic map, parallel transport and the induced Sinkhorn distance. Moreover, we show that the nonparametric bootstrap is consistent for all objects mentioned. To the best of our knowledge, these are the first $\sqrt{n}$--limit theorems and bootstrap consistency results for canonical geometric operations in a transport-based geometry on the space of probability measures.

0.11

Beyond Blackwell: Constrained Data Processing Inequalities

cs.LG ·2026-10-31 ·Brendan van Rooyen
theory similarity 0.54
Abstract

We study the comparison of statistical experiments from a decision-theoretic standpoint, working with Markov transitions as basis-free linear maps on dual spaces. Our starting observation is that the data-processing inequality, that adding noise to an experiment cannot lower its Bayes risk, is the functoriality of fibrewise minimisation over a presheaf of decision rules: the rules available after an experiment form a presheaf, garbling acts on it by precomposition, and a risk functional is a natural transformation from it to the ordered reals. The argument refers to neither probabilities nor expected values, and it survives replacing the decision presheaf by a sub-presheaf of admissible rules. Any constraint imposed on the strategy that a rule induces fairness, unbiasedness, is automatically of this form, and so yields a data-processing inequality with no counterpart in the unconstrained Blackwell theory. Our main result is their quantitative companion. For constraints closed under post-processing we define a constrained deficiency and prove a constrained randomization theorem: one experiment dominates another on every admissible decision problem exactly when the constrained deficiency is small. The classical theorem is the case of no constraint, where the identity is itself an admissible rule; in general it is not, and the constrained deficiency is an optimisation over the coarsenings of an experiment that render it compliant. Specialising to equalized odds, we exhibit a pair of experiments that unconstrained Bayes risk identifies at a given loss and prior but that the constrained risk separates, giving a one-line certificate of Blackwell-incomparability. We work throughout with finite sets.

0.19