CS Paper Radar

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

Patrick Forré

cs.LG math.CTcs.LOcs.PLmath.PR ·submitted 2026-08-14 04:13 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Compositional Information Geometry of Probabilistic Programs

cs.PL cs.CG ·2026-10-13 ·Jacek Karwowski, Frank Nielsen, Sam Staton
highly cited similarity 0.57
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.

0.43

Monad Structures on Topological Spaces Comprising Mislove's Random Variables

cs.LO ·2026-08-19 ·Chengyu Zhou, Qingguo Li
similarity 0.55
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

Metrization of Quasi-Uniformities, Powerset Monads, and Qualitative Robustness Analysis

cs.LO math.GN ·2026-09-02 ·Francesco Dagnino, Amin Farjudian, Eugenio Moggi
theory similarity 0.53
Abstract · 24 pages

We study the relationship between quasi-uniform spaces, topological spaces, and quantale-valued metric spaces. Our main result is a metrization theorem establishing an equivalence between the category of quasi-uniform spaces and a category of quantale-valued metric spaces. We also obtain a quantale-based metrization theorem for arbitrary topological spaces that refines existing constructions. These results identify quasi-uniformities as the appropriate qualitative counterpart of quantale-valued metrics. Building on this correspondence, we show that the Hausdorff-Smyth monad on quantale-valued metric spaces, which is used in quantitative robustness analysis, arises as a lifting of a corresponding monad on quasi-uniform spaces along the equivalence. This provides a unified categorical framework connecting topology, quasi-uniformity, and quantitative robustness analysis.

0.23

A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

cs.LG math.LOmath.PR ·2026-08-31 ·Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira Rodrigues
theory similarity 0.52
Abstract

The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on $[0,1]$ of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.

0.24

Fibered Separation Logic: Weakest Preconditions, Universal Constructions, and Local Independence

cs.PL cs.LO ·2026-11-05 ·John M. Li, Ryan Doenges, Pedro H. Azevedo de Amorim
similarity 0.49
Abstract · 41 pages, 5 figures

This paper introduces a categorical framework for models of higher-order separation logic including the weakest precondition modality. Weakest preconditions are interpreted by strong monads on a category fibered over a model of Moggi's computational lambda calculus. The fibered categories in question are termed bunched fibrations and shown to be equivalent to BI hyperdoctrines. Well-known heuristic techniques for obtaining weakest preconditions are shown to be expressible in categorical terms and are proved sound. The ``baking in the frame rule'' trick is shown to satisfy a universal property. Constructions are given for extending a program logic with cost credits. Our largest case study is parametrized by a category having local independent product (LIP) structure, a notion due to Simpson that axiomatizes name generation, randomness, and local state. From an LIP category, we construct an allocation monad, a bunched fibration, and a monad lifting. We instantiate our construction to obtain a novel probabilistic separation logic for measure-theoretic probability that both simplifies and clarifies prior work.

0.31

Products of Distinguisher Hulls

cs.CC cs.CR ·2026-11-19 ·John Paul Steinberger, Zhe Zhang
theory similarity 0.49
Abstract

The distinguisher hull of two distributions is the convex hull of the pairs of acceptance probabilities of tests in a specified class. We study its behavior under independent products for size-bounded Boolean circuits. We derive a geometric consequence of Dwork and Tankala's supersimulator theorem (FOCS 2026), giving a substantially different proof of approximate product containment for distinguisher hulls. In particular, our construction uses nonadaptive sampling in place of adaptive score corrections.

0.38

How far is Kolmogorov-Loveland randomness from Martin-Löf randomness?

cs.CC cs.IT ·2026-10-09 ·Tomislav Petrović
unusual similarity 0.48
Abstract

We'll call a map from basic to clopen sets of binary sequences an \textit{encoding} if it preserves uniform Lebesgue measure and the disjointedness relation. For some notion of randomness $R$ we can ask if there is a computable encoding $E$ such that for every non-Martin-Löf-random (non-MLR) sequence $α$, the sequences in $E(α)$ are non-$R$. Thus we can use $E$ and randomness test for $R$ to construct a randomness test for MLR. We show that there is no such $E$ for partial computable randomness (PCR), but there is one for Kolmogorov-Loveland randomness. Indeed, there is a total computable $E$ and a pair of total computable non-monotonic betting strategies such that on every sequence in $E(α)$ at least one of the strategies wins whenever $α$ is non-MLR.

0.27

Universal Approximation of Measure-to-Measure Operators by Pushforwards

cs.LG math.NAstat.ML ·2026-09-28 ·Takashi Furuya, Nicholas H. Nelsen, Frank Cole
theory similarity 0.48
Abstract · 31 pages (9 main text, 19 appendix, and 3 references pages)

Many learning tasks map an input distribution to an output distribution. A natural way to model such an operator is to transform each input sample using a continuous function that may depend on the entire input distribution, and then take the distribution of the transformed samples. This defines a measure-dependent pushforward model and includes measure-theoretic formulations of transformers. We ask when such models can approximate arbitrary continuous operators between spaces of probability measures. We first show that universal approximation fails when atomic inputs are allowed: some continuous measure-to-measure operators that split or redistribute atomic mass cannot be approximated arbitrarily well by deterministic pushforward models. We then introduce the uniform level set condition, which requires a continuous measure-dependent scalarization whose shrinking level set neighborhoods carry uniformly vanishing mass over the input family. This condition is satisfied, in particular, by compact families of absolutely continuous measures. On every compact family satisfying this condition, we prove that any continuous measure-to-measure operator with outputs of finite $p$-th moment can be uniformly approximated, in the $p$-Wasserstein distance, by continuous measure-dependent pushforwards. Combining our theorem with existing approximation results for measure-dependent in-context maps yields universal approximation by measure-theoretic transformers. We also extend the framework to continuously-varying source measures, yielding a corresponding universality result for a class of pushforward models that are closely aligned with cross-attention architectures.

0.36