Publications | Shayan Hundrieser

2023

Lower Complexity Adaptation for Empirical Entropic Optimal Transport

Michel Groppe, and Shayan Hundrieser

Preprint arXiv:2306.13580 - 2023

Abstract Bibtex Link

Entropic optimal transport (EOT) presents an effective and computationally viable alternative to unregularized optimal transport (OT), offering diverse applications for large-scale data analysis. In this work, we derive novel statistical bounds for empirical plug-in estimators of the EOT cost and show that their statistical performance in the entropy regularization parameter ϵ and the sample size n only depends on the simpler of the two probability measures. For instance, under sufficiently smooth costs this yields the parametric rate n^−1/2 with factor ε^−d/2, where d is the minimum dimension of the two population measures. This confirms that empirical EOT also adheres to the lower complexity adaptation principle, a hallmark feature only recently identified for unregularized OT. As a consequence of our theory, we show that the empirical entropic Gromov-Wasserstein distance and its unregularized version for measures on Euclidean spaces also obey this principle. Additionally, we comment on computational aspects and complement our findings with Monte Carlo simulations. Our techniques employ empirical process theory and rely on a dual formulation of EOT over a single function class. Crucial to our analysis is the observation that the entropic cost-transformation of a function class does not increase its uniform metric entropy by much.
@article{Groppe2023LCA_EOT, title = {Lower Complexity Adaptation for Empirical Entropic Optimal Transport}, author = {Groppe, Michel and Hundrieser, Shayan}, journal = {Preprint arXiv:2306.13580}, year = {2023}, }
Convergence of Empirical Optimal Transport in Unbounded Settings

Thomas Staudt, and Shayan Hundrieser

Preprint arXiv:2306.11499 - 2023

Abstract Bibtex Link

In compact settings, the convergence rate of the empirical optimal transport cost to its population value is well understood for a wide class of spaces and cost functions. In unbounded settings, however, hitherto available results require strong assumptions on the ground costs and the concentration of the involved measures. In this work, we pursue a decomposition-based approach to generalize the convergence rates found in compact spaces to unbounded settings under generic moment assumptions that are sharp up to an arbitrarily small ε>0. Hallmark properties of empirical optimal transport on compact spaces, like the recently established adaptation to lower complexity, are shown to carry over to the unbounded case.
@article{staudt2023convergence, title = {Convergence of Empirical Optimal Transport in Unbounded Settings}, author = {Staudt, Thomas and Hundrieser, Shayan}, journal = {Preprint arXiv:2306.11499}, year = {2023}, }
Weak Limits for Empirical Entropic Optimal Transport: Beyond Smooth Costs

Alberto González-Sanz, and Shayan Hundrieser

Preprint arXiv:2305.09745 - 2023

Abstract Bibtex Link

We establish weak limits for the empirical entropy regularized optimal transport cost, the expectation of the empirical plan and the conditional expectation. Our results require only uniform boundedness of the cost function and no smoothness properties, thus emphasizing the far-reaching regularizing nature of entropy penalization. To derive these results, we employ a novel technique that sidesteps the intricacies linked to empirical process theory and the control of suprema of function classes determined by the cost. Instead, we perform a careful linearization analysis for entropic optimal transport with respect to an empirical L2-norm, which enables a streamlined analysis. As a consequence, our work gives rise to new implications for a multitude of transport-based applications under general costs, including pointwise distributional limits for the empirical entropic optimal transport map estimator, kernel methods as well as regularized colocalization curves. Overall, our research lays the foundation for an expanded framework of statistical inference with empirical entropic optimal transport.
@article{gonzalez2023weak, title = {Weak Limits for Empirical Entropic Optimal Transport: Beyond Smooth Costs}, author = {Gonz{\'a}lez-Sanz, Alberto and Hundrieser, Shayan}, journal = {Preprint arXiv:2305.09745}, year = {2023}, }
Empirical optimal transport under estimated costs: Distributional limits and statistical applications

Shayan Hundrieser, Gilles Mordant, Christoph Alexander Weitkamp, and Axel Munk

Preprint arXiv:2301.01287 - 2023

Abstract Bibtex Link

Optimal transport (OT) based data analysis is often faced with the issue that the underlying cost function is (partially) unknown. This paper is concerned with the derivation of distributional limits for the empirical OT value when the cost function and the measures are estimated from data. For statistical inference purposes, but also from the viewpoint of a stability analysis, understanding the fluctuation of such quantities is paramount. Our results find direct application in the problem of goodness-of-fit testing for group families, in machine learning applications where invariant transport costs arise, in the problem of estimating the distance between mixtures of distributions, and for the analysis of empirical sliced OT quantities. The established distributional limits assume either weak convergence of the cost process in uniform norm or that the cost is determined by an optimization problem of the OT value over a fixed parameter space. For the first setting we rely on careful lower and upper bounds for the OT value in terms of the measures and the cost in conjunction with a Skorokhod representation. The second setting is based on a functional delta method for the OT value process over the parameter space. The proof techniques might be of independent interest.
@article{Hundrieser2023OTestcost, author = {Hundrieser, Shayan and Mordant, Gilles and Weitkamp, Christoph Alexander and Munk, Axel}, title = {Empirical optimal transport under estimated costs: Distributional limits and statistical applications}, year = {2023}, journal = {Preprint arXiv:2301.01287}, }
A Unifying Approach to Distributional Limits for Empirical Optimal Transport

Shayan Hundrieser, Marcel Klatt, Thomas Staudt, and Axel Munk

Bernoulli [To appear, preprint arXiv:2202.12790] - 2023

Abstract Bibtex Link

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 F_c for an underlying sufficiently regular cost function c. In this regard, OT is considered as a functional defined on ℓ∞(F_c) the Banach space of bounded functionals from F_c to 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 ℓ∞(F_c). The latter can be dealt with empirical process theory and requires 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 F_c to be sufficiently rich, while the empirical processes only converges weakly if F_c is not too complex.
@article{hundrieser2022unifying, title = {A Unifying Approach to Distributional Limits for Empirical Optimal Transport}, author = {Hundrieser, Shayan and Klatt, Marcel and Staudt, Thomas and Munk, Axel}, journal = {Bernoulli [To appear, preprint arXiv:2202.12790]}, year = {2023}, }
Empirical Optimal Transport between Different Measures Adapts to Lower Complexity

Shayan Hundrieser, Thomas Staudt, and Axel Munk

Annales de l’Institut Henri Poincaré, Probabilités et Statistiques [to appear, preprint arXiv:2202.10434] - 2023

Abstract Bibtex Link

The empirical optimal transport (OT) cost between two probability measures from random data is a fundamental quantity in transport based data analysis. In this work, we derive novel guarantees for its convergence rate when the involved measures are different, possibly supported on different spaces. Our central observation is that the statistical performance of the empirical OT cost is determined by the less complex measure, a phenomenon we refer to as lower complexity adaptation of empirical OT. For instance, under Lipschitz ground costs, we find that the empirical OT cost based on n observations converges at least with rate n^(−1/d) to the population quantity if one of the two measures is concentrated on a d-dimensional manifold, while the other can be arbitrary. For semi-concave ground costs, we show that the upper bound for the rate improves to n^(−2/d). Similarly, our theory establishes the general convergence rate n^(−1/2) for semi-discrete OT. All of these results are valid in the two-sample case as well, meaning that the convergence rate is still governed by the simpler of the two measures. On a conceptual level, our findings therefore suggest that the curse of dimensionality only affects the estimation of the OT cost when both measures exhibit a high intrinsic dimension. Our proofs are based on the dual formulation of OT as a maximization over a suitable function class F_c and the observation that the c-transform of F_c under bounded costs has the same uniform metric entropy as F_c itself
@article{hundrieser2022empirical, title = {Empirical Optimal Transport between Different Measures Adapts to Lower Complexity}, author = {Hundrieser, Shayan and Staudt, Thomas and Munk, Axel}, journal = {Annales de l'Institut Henri Poincar\'{e}, Probabilit\'{e}s et Statistiques [to appear, preprint arXiv:2202.10434]}, year = {2023}, }
Limit Distributions and Sensitivity Analysis for Empirical Entropic Optimal Transport on Countable Spaces

Shayan Hundrieser, Marcel Klatt, and Axel Munk

The Annals of Applied Probabilites [to appear, preprint arXiv:2105.00049] - 2023

Abstract Bibtex Link

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.
@article{hundrieser2023limit, title = {Limit Distributions and Sensitivity Analysis for Empirical Entropic Optimal Transport on Countable Spaces}, author = {Hundrieser, Shayan and Klatt, Marcel and Munk, Axel}, journal = {The Annals of Applied Probabilites [to appear, preprint arXiv:2105.00049]}, year = {2023}, }

2022

On the Uniqueness of Kantorovich Potentials

Thomas Staudt, Shayan Hundrieser, and Axel Munk

Preprint arXiv:2201.08316 - 2022

Abstract Bibtex Link

Kantorovich potentials denote the dual solutions of the renowned optimal transportation problem. Uniqueness of these solutions is relevant from both a theoretical and an algorithmic point of view, and has recently emerged as a necessary condition for asymptotic results in the context of statistical and entropic optimal transport. In this work, we challenge the common perception that uniqueness in continuous settings is reliant on the connectedness of the support of at least one of the involved measures, and we provide mild sufficient conditions for uniqueness even when both measures have disconnected support. Since our main finding builds upon the uniqueness of Kantorovich potentials on connected components, we revisit the corresponding arguments and provide generalizations of well-known results. Several auxiliary findings regarding the continuity of Kantorovich potentials, for example in geodesic spaces, are established along the way.
@article{staudt2022uniqueness, title = {On the Uniqueness of Kantorovich Potentials}, author = {Staudt, Thomas and Hundrieser, Shayan and Munk, Axel}, journal = {Preprint arXiv:2201.08316}, year = {2022} }
The Statistics of Circular Optimal Transport

Shayan Hundrieser, Marcel Klatt, and Axel Munk

In Directional Statistics for Innovative Applications - 2022

Abstract Bibtex Link

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.
@inproceedings{hundrieser2022statistics, title = {The Statistics of Circular Optimal Transport}, author = {Hundrieser, Shayan and Klatt, Marcel and Munk, Axel}, booktitle = {Directional Statistics for Innovative Applications}, pages = {57--82}, year = {2022}, editor = {"SenGupta, Ashis and Arnold, Barry C."}, url = {https://link.springer.com/chapter/10.1007/978-981-19-1044-9_4}, publisher = {Springer} }

2021

Finite Sample Smeariness on Spheres

Benjamin Eltzner, Shayan Hundrieser, and Stephan Huckemann

In International Conference on Geometric Science of Information, - 2021

Abstract Bibtex Link

Finite Sample Smeariness (FSS) has been recently discovered. It means that the distribution of sample Fréchet means of underlying rather unsuspicious random variables can behave as if it were smeary for quite large regimes of finite sample sizes. In effect classical quantile-based statistical testing procedures do not preserve nominal size, they reject too often under the null hypothesis. Suitably designed bootstrap tests, however, amend for FSS. On the circle it has been known that arbitrarily sized FSS is possible, and that all distributions with a non-vanishing density feature FSS. These results are extended to spheres of arbitrary dimension. In particular all rotationally symmetric distributions, not necessarily supported on the entire sphere feature FSS of Type I. While on the circle there is also FSS of Type II it is conjectured that this is not possible on higher-dimensional spheres.
@inproceedings{eltzner2021finite, title = {Finite Sample Smeariness on Spheres}, author = {Eltzner, Benjamin and Hundrieser, Shayan and Huckemann, Stephan}, booktitle = {International Conference on Geometric Science of Information, }, pages = {12--19}, year = {2021}, organization = {Springer} }

2020

Finite Sample Smeariness of Fréchet Means and Application to Climate

Shayan Hundrieser, Benjamin Eltzner, and Stephan Huckemann

Preprint arXiv:2005.02321 - 2020

Abstract Bibtex Link

Fréchet means on non-Euclidean spaces may exhibit nonstandard asymptotic rates rendering quantile-based asymptotic inference inapplicable. We show here that this affects, among others, all circular distributions whose support exceeds a half circle. We exhaustively describe this phenomenon and introduce a new concept which we call finite samples smeariness (FSS). In the presence of FSS, it turns out that quantile-based tests for equality of Fréchet means systematically feature effective levels higher than their nominal level which perseveres asymptotically in case of Type I FSS. In contrast, suitable bootstrap-based tests correct for FSS and asymptotically attain the correct level. For illustration of the relevance of FSS in real data, we apply our method to directional wind data from two European cities. It turns out that quantile based tests, not correcting for FSS, find a multitude of significant wind changes. This multitude condenses to a few years featuring significant wind changes, when our bootstrap tests are applied, correcting for FSS.
@article{hundrieser2020finite, title = {Finite Sample Smeariness of Fréchet Means and Application to Climate}, author = {Hundrieser, Shayan and Eltzner, Benjamin and Huckemann, Stephan}, journal = {Preprint arXiv:2005.02321}, year = {2020} }