stat.MLFeb 5, 2026

Distribution-free certificate of similarity between distributions with blurred total variation distance

Authors: Rohan Hore, Rina Foygel Barber

Organizations: Department of Statistics and Data Science, Carnegie Mellon University · Department of Statistics, University of Chicago

Abstract

Classical two-sample tests aim to determine whether two distributions are equal or not based on samples from each one. Even in an distribution-free setting, well-known methods such as the permutation test can provide statistical evidence that the two distributions differ. However, failure to reject equality does not necessarily establish that they are similar. In this work, we study the complementary problem of certifying distributional similarity with finite-sample confidence, without imposing assumptions on the underlying distributions. We show, however, that for continuous distributions, any distribution-free upper confidence bound on the total variation (TV) distance must be trivial with high probability, even if the distributions are identical. Thus, certifying similarity in TV with a distribution-free guarantee is practically impossible. We therefore examine the blurred TV distance, a relaxation of TV distance that enables us to quantify similarity after applying a common blurring operation while retaining the interpretation of TV. We construct distribution-free upper and lower confidence bounds on blurred TV, establish their finite-sample validity, and examine its properties in high dimensions.

Figures & tables

Explore similar work

Aug 3, 2026

Finite-Probe Total-Variation Certificates for Finite-Basis Drifting Models

Drifting objectives compare a target and model distribution through a vector field observed noisily at finitely many locations. We ask what distributional conclusion such a frozen measurement system warrants. For integrable antisymmetric interactions and absolutely continuous laws in a declared finite density basis, the unnormalized sampled numerator satisfies vec⁡(VX)=Mc\operatorname{vec}(V_X)=Mc, where cc is an antisymmetric mismatch and MM is probe-dependent. This identity yields an a posteriori total-variation (TV) upper confidence bound accounting for held-out field noise, estimated-operator error, and externally validated L1L^1 residual radii around normalized density approximants in the span; a nonpositive observability margin returns the trivial TV bound and abstains. The audit recomputes this numerator from held-out samples; a normalized drift statistic requires a separate joint numerator--denominator analysis. For Gaussian-RBF interactions, a global envelope supports distribution-free and empirical-Bernstein radii without truncation, with companion bounds for the Laplace similarity in the original drifting objective. We characterize random-probe observability by a population Gram matrix, identify rank and symmetry degeneracies, and prove large-bandwidth collapse toward mean matching. Synthetic studies exercise Gaussian and Laplace numerators, separately prespecified bounded-vector and variance-adaptive radii, Monte Carlo-calibrated operators, nonzero residual radii around normalized finite-basis approximants, outward-rounded observability bounds, and designed abstention. A joint basis-size/dimension stress path extends evaluation through m=8m=8. The result is a conditional diagnostic for a finite density class, or for normalized finite-basis density approximants with external residual radii, not a universal guarantee from small training drift.
Jul 17, 2026

Testing Distributions Against Bounded Distinguishers

Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution PP over a very large domain to decide between two cases: P=PrefP = P_{\mathsf{ref}} for a fixed reference distribution PrefP_{\mathsf{ref}}, or there exists a distinguisher ff in a bounded class F\mathcal{F} which witnesses the separation ∣EP[f]−EPref[f]∣>ε|\mathbf{E}_P[f] - \mathbf{E}_{P_{\mathsf{ref}}}[f]| > ε. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.) We show that testing with respect to fooling distance is not only a natural computational problem that admits sample-efficient algorithms even in high-dimensional settings, but also one that reveals and underlies connections between three seemingly unrelated areas of study: testable learning, verification of learning algorithms, and testing of structured distributions (whose "Ak\mathcal{A}_k-testing" model our framework extends). These connections yield new results for all of these models, including: 1. Testable proper learners using membership queries for halfspaces and decision trees. 2. A lower bound for testable PAC verification in terms of Rademacher complexity, and a distribution-free verification protocol for disjoint unions of kk multidimensional rectangles. 3. Identity testers (with respect to total variation distance) for decision tree distributions and distributions with low-degree polynomial densities, over Boolean and continuous hypercube domains.
May 22, 2026

Entropy Equivalence Testing

We introduce the problem of entropy equivalence testing for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions p,qp,q and a parameter ε∈(0,1/2]\varepsilon \in(0,1/2], between p=qp=q and ∣H(p)−H(q)∣≥ε|H(p)-H(q)| \geq \varepsilon (where HH denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree Bayesian networks, which significantly improves on either the sample or time complexity of a baseline based on full learning.