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

CardsList
  1. Finite-Probe Total-Variation Certificates for Finite-Basis Drifting Models

    Aug 3, 2026Sam Andersson, Ricky MolénUncertainty QuantificationDrifting Models

  2. Testing Distributions Against Bounded Distinguishers

    Jul 17, 2026Mark Bun, Rathin Desai, Renato Ferreira PintoIntegral Probability Metrics

  3. Entropy Equivalence Testing

    May 22, 2026Clément L. Canonne, Yash Pote, Jonathan Scarlett +1Distribution Matching