Shayan Hundrieser

Selected Publications

1. Lower Complexity Adaptation for Empirical Entropic Optimal Transport

   Michel Groppe, and Shayan Hundrieser

   Journal of Machine Learning Research - 2024

   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{Groppe2024LCA_EOT,
     title = {Lower Complexity Adaptation for Empirical Entropic Optimal Transport},
     author = {Groppe, Michel and Hundrieser, Shayan},
     journal = {Journal of Machine Learning Research},
     volume = {25},
     number = {344},
     pages = {1--55},
     year = {2024},
   }

2. Statistical Optimal Transport and its Entropic Regularization: Compared and Contrasted

   Shayan Hundrieser

   Ph.D. thesis - University of Göttingen - 2024

   Abstract Bibtex Link

   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},
   }

3. A unifying approach to distributional limits for empirical optimal transport

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

   Bernoulli - 2024

   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{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},
     url = {https://projecteuclid.org/journals/bernoulli/volume-30/issue-4/A-unifying-approach-to-distributional-limits-for-empirical-optimal-transport/10.3150/23-BEJ1697.short},
   }

4. 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 - 2024

   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{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},
   }