Publications
Publications in reversed chronological order.
2024
- Statistical Optimal Transport and its Entropic Regularization: Compared and ContrastedShayan HundrieserPh.D. thesis - University of Göttingen - 2024
In recent years, statistical methodology based on optimal transport witnessed a considerable increase in practical and theoretical interest. A central reason for this trend is the ability of optimal transport to compare data in a manner that is consistent with the geometry of the domain. This development was further amplified by computational advances spurred by the introduction of entropy regularized optimal transport. The presented doctoral thesis delves into statistical aspects of empirical optimal transport and its entropy regularized surrogate. It focuses on the statistical performance and uncertainty of empirical plug-in estimators based on sampling from unknown distributions, and collects four research articles which contribute to these topics. The first article analyzes the performance of empirical optimal transport under different population measures and uncovers that for increasing sample size the convergence rate is governed by the less complex measure, a phenomenon termed lower complexity adaptation. The second article provides a unifying approach to distributional limits for the empirical optimal transport cost. The third article extends upon this and establishes distributional limits for empirical optimal transport when additionally the cost function is estimated. Notably, the second and third article both align with the principle of lower complexity adaptation and also showcase that similar limits do not hold in high-dimensional settings. Finally, the fourth article derives distributional limits for empirical entropy regularized surrogates and confirms their validity in arbitrary high-dimensional settings. Altogether, this doctoral thesis highlights key similarities and differences between empirical optimal transport and its entropic regularization, offering comprehensive insights into strengths and limitations of transport-based methodologies in statistical contexts.
@article{hundrieser2024thesis, title = {Statistical Optimal Transport and its Entropic Regularization: Compared and Contrasted}, author = {Hundrieser, Shayan}, journal = {Ph.D. thesis - University of Göttingen}, year = {2024}, } - A unifying approach to distributional limits for empirical optimal transportShayan Hundrieser, Marcel Klatt, Axel Munk, and Thomas StaudtBernoulli - 2024
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{hundrieser2024unifying, title = {A unifying approach to distributional limits for empirical optimal transport}, author = {Hundrieser, Shayan and Klatt, Marcel and Munk, Axel and Staudt, Thomas}, journal = {Bernoulli}, volume = {30}, number = {4}, pages = {2846--2877}, year = {2024}, } - Empirical optimal transport between different measures adapts to lower complexityShayan Hundrieser, Thomas Staudt, and Axel MunkAnnales de l’Institut Henri Poincaré, Probabilités et Statistiques - 2024
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{hundrieser2024empirical, 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}, volume = {60}, number = {2}, pages = {824--846}, year = {2024}, } - Limit distributions and sensitivity analysis for empirical entropic optimal transport on countable spacesShayan Hundrieser, Marcel Klatt, and Axel MunkThe Annals of Applied Probabilites - 2024
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{hundrieser2024entropic, 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}, volume = {34}, number = {1B}, pages = {1403--1468}, year = {2024}, } - Finite sample smeariness of Fréchet means with application to climateShayan Hundrieser, Benjamin Eltzner, and Stephan HuckemannElectronic Journal of Statistics - 2024
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{hundrieser2024fss, title = {Finite sample smeariness of Fréchet means with application to climate}, author = {Hundrieser, Shayan and Eltzner, Benjamin and Huckemann, Stephan}, journal = {Electronic Journal of Statistics}, volume = {18}, number = {2}, pages = {3274--3309}, url = {https://projecteuclid.org/journalArticle/Download?urlId=10.1214%2F24-EJS2276}, year = {2024} } - A Lower Bound for Estimating Fréchet MeansShayan Hundrieser, Benjamin Eltzner, and Stephan HuckemannPreprint arXiv:2402.12290 - 2024
Fréchet means, conceptually appealing, generalize the Euclidean expectation to general metric spaces. We explore how well Fréchet means can be estimated from independent and identically distributed samples and uncover a fundamental limitation: In the vicinity of a probability distribution P with nonunique means, independent of sample size, it is not possible to uniformly estimate Fréchet means below a precision determined by the diameter of the set of Fréchet means of P. Implications were previously identified for empirical plug-in estimators as part of the phenomenon \emphfinite sample smeariness. Our findings thus confirm inevitable statistical challenges in the estimation of Fréchet means on metric spaces for which there exist distributions with nonunique means. Illustrating the relevance of our lower bound, examples of extrinsic, intrinsic, Procrustes, diffusion and Wasserstein means showcase either deteriorating constants or slow convergence rates of empirical Fréchet means for samples near the regime of nonunique means.
@article{hundrieser2024lower, title = {A Lower Bound for Estimating Fréchet Means}, author = {Hundrieser, Shayan and Eltzner, Benjamin and Huckemann, Stephan}, journal = {Preprint arXiv:2402.12290}, year = {2024}, }
2023
- Lower Complexity Adaptation for Empirical Entropic Optimal TransportMichel Groppe, and Shayan HundrieserPreprint arXiv:2306.13580 - 2023
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 SettingsThomas Staudt, and Shayan HundrieserBernoulli [To appear, preprint arXiv:2306.11499] - 2023
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 = {Bernoulli [To appear, preprint arXiv:2306.11499]}, year = {2023}, } - Weak Limits for Empirical Entropic Optimal Transport: Beyond Smooth CostsAlberto González-Sanz, and Shayan HundrieserPreprint arXiv:2305.09745 - 2023
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 applicationsShayan Hundrieser, Gilles Mordant, Christoph Alexander Weitkamp, and Axel MunkPreprint arXiv:2301.01287 - 2023
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{hundrieser2023costs, 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}, }
2022
- On the Uniqueness of Kantorovich PotentialsThomas Staudt, Shayan Hundrieser, and Axel MunkPreprint arXiv:2201.08316 - 2022
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 TransportShayan Hundrieser, Marcel Klatt, and Axel MunkIn Directional Statistics for Innovative Applications - 2022
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} } - Unbalanced Kantorovich-Rubinstein distance, plan, and barycenter on finite spaces: A statistical perspectiveShayan Hundrieser, Florian Heinemann, Marcel Klatt, Marina Struleva, and 1 more authorPreprint arXiv:2211.08858 - 2022
We analyze statistical properties of plug-in estimators for unbalanced optimal transport quantities between finitely supported measures in different prototypical sampling models. Specifically, our main results provide non-asymptotic bounds on the expected error of empirical Kantorovich-Rubinstein (KR) distance, plans, and barycenters for mass penalty parameter C>0. The impact of the mass penalty parameter C is studied in detail. Based on this analysis, we mathematically justify randomized computational schemes for KR quantities which can be used for fast approximate computations in combination with any exact solver. Using synthetic and real datasets, we empirically analyze the behavior of the expected errors in simulation studies and illustrate the validity of our theoretical bounds.
@article{hundrieser2022unbalanced, title = {Unbalanced Kantorovich-Rubinstein distance, plan, and barycenter on finite spaces: A statistical perspective}, author = {Hundrieser, Shayan and Heinemann, Florian and Klatt, Marcel and Struleva, Marina and Munk, Axel}, journal = {Preprint arXiv:2211.08858}, year = {2022}, }
2021
- Finite Sample Smeariness on SpheresBenjamin Eltzner, Shayan Hundrieser, and Stephan HuckemannIn International Conference on Geometric Science of Information, - 2021
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} }