Search

We propose and investigate several statistical models and corresponding sampling schemes for data analysis based on unbalanced optimal transport (UOT) between finitely supported measures. Specifically, we analyse Kantorovich-Rubinstein (KR) distances with penalty parameter $C>0$. The main result provides non-asymptotic bounds on the expected error for the empirical KR distance as well as for its barycenters. The impact of the penalty parameter $C$ is studied in detail. Our approach justifies randomised computational schemes for UOT which can be used for fast approximate computations in combination with any exact solver. Using synthetic and real datasets, we empirically analyse the behaviour of the expected errors in simulation studies and illustrate the validity of our theoretical bounds.

We provide a unifying approach to central limit type theorems for empirical optimal transport (OT). In general, the limit distributions are characterized as suprema of Gaussian processes. We explicitly characterize when the limit distribution is centered normal or degenerates to a Dirac measure. Moreover, in contrast to recent contributions on distributional limit laws for empirical OT on Euclidean spaces which require centering around its expectation, the distributional limits obtained here are centered around the population quantity, which is well-suited for statistical applications. At the heart of our theory is Kantorovich duality representing OT as a supremum over a function class $\mathcal{F}_{c}$ for an underlying sufficiently regular cost function $c$. In this regard, OT is considered as a functional defined on $\ell^{\infty}(\mathcal{F}_{c})$ the Banach space of bounded functionals from $\mathcal{F}_{c}$ to $\mathbb{R}$ and equipped with uniform norm. We prove the OT functional to be Hadamard directional differentiable and conclude distributional convergence via a functional delta method that necessitates weak convergence of an underlying empirical process in $\ell^{\infty}(\mathcal{F}_{c})$. The latter can be dealt with empirical process theory and requires $\mathcal{F}_{c}$ to be a Donsker class. We give sufficient conditions depending on the dimension of the ground space, the underlying cost function and the probability measures under consideration to guarantee the Donsker property. Overall, our approach reveals a noteworthy trade-off inherent in central limit theorems for empirical OT: Kantorovich duality requires $\mathcal{F}_{c}$ to be sufficiently rich, while the empirical processes only converges weakly if $\mathcal{F}_{c}$ is not too complex., Comment: 29 pages, 1 figure

Empirical optimal transport (OT) plans and distances provide effective tools to compare and statistically match probability measures defined on a given ground space. Fundamental to this are distributional limit laws and we derive a central limit theorem for the empirical OT distance of circular data. Our limit results require only mild assumptions in general and include prominent examples such as the von Mises or wrapped Cauchy family. Most notably, no assumptions are required when data are sampled from the probability measure to be compared with, which is in strict contrast to the real line. A bootstrap principle follows immediately as our proof relies on Hadamard differentiability of the OT functional. This paves the way for a variety of statistical inference tasks and is exemplified for asymptotic OT based goodness of fit testing for circular distributions. We discuss numerical implementation, consistency and investigate its statistical power. For testing uniformity, it turns out that this approach performs particularly well for unimodal alternatives and is almost as powerful as Rayleigh's test, the most powerful invariant test for von Mises alternatives. For regimes with many modes the circular OT test is less powerful which is explained by the shape of the corresponding transport plan., 24 pages, 9 figures

For probability measures on countable spaces we derive distributional limits for empirical entropic optimal transport quantities. More precisely, we show that the empirical optimal transport plan weakly converges to a centered Gaussian process and that the empirical entropic optimal transport value is asymptotically normal. The results are valid for a large class of cost functions and generalize distributional limits for empirical entropic optimal transport quantities on finite spaces. Our proofs are based on a sensitivity analysis with respect to norms induced by suitable function classes, which arise from novel quantitative bounds for primal and dual optimizers, that are related to the exponential penalty term in the dual formulation. The distributional limits then follow from the functional delta method together with weak convergence of the empirical process in that respective norm, for which we provide sharp conditions on the underlying measures. As a byproduct of our proof technique, consistency of the bootstrap for statistical applications is shown., Comment: 68 pages

We consider a general linear program in standard form whose right-hand side constraint vector is subject to random perturbations. This defines a stochastic linear program for which, under general conditions, we characterize the fluctuations of the corresponding empirical optimal solution by a central limit-type theorem. Our approach relies on the combinatorial nature and the concept of degeneracy inherent in linear programming, in strong contrast to well-known results for smooth stochastic optimization programs. In particular, if the corresponding dual linear program is degenerate the asymptotic limit law might not be unique and is determined from the way the empirical optimal solution is chosen. Furthermore, we establish consistency and convergence rates of the Hausdorff distance between the empirical and the true optimality sets. As a consequence, we deduce a limit law for the empirical optimal value characterized by the set of all dual optimal solutions which turns out to be a simple consequence of our general proof techniques. Our analysis is motivated from recent findings in statistical optimal transport that will be of special focus here. In addition to the asymptotic limit laws for optimal transport solutions, we obtain results linking degeneracy of the dual transport problem to geometric properties of the underlying ground space, and prove almost sure uniqueness statements that may be of independent interest.