Sparse Regularized Optimal Transport without Curse of Dimensionality

Alberto González-Sanz, Stephan Eckstein, Marcel Nutz · 2025

Read Sparse Regularized Optimal Transport without Curse of Dimensionality by Alberto González-Sanz, Stephan Eckstein, Marcel Nutz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04721.txt.

Introduction

Alberto González-Sanz, Stephan Eckstein, and Marcel Nutz present a 2025 statistics paper overturning a piece of conventional wisdom about optimal transport. Transport problems match one distribution to another at least cost, and smoothing the matching makes it statistically well behaved. The catch: the standard smoothing spreads mass everywhere, while true matchings are sparse, often just a mapping.

Rougher smoothings allow sparse matchings but were believed to suffer the curse of dimensionality, with errors growing as dimension rises. The authors prove the opposite for a broad family: the cost, the coupling, and the dual prices all settle at the fast parametric rate regardless of dimension. Their proof uses a direct estimation argument they expect to serve elsewhere in statistics.

Catalog record

CREATORAlberto González-Sanz, Stephan Eckstein, Marcel Nutz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-04721

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sparse Regularized Optimal Transport without Curse of Dimensionality Alberto González-Sanz, Stephan Eckstein, Marcel Nutz Abstract Entropic optimal transport—the optimal transport problem regularized by KL divergence—is highly successful in statistical applications. Thanks to the smoothness of the entropic coupling, its sample complexity avoids the curse of dimensionality suffered by unregularized optimal transport. The flip side of smoothness is overspreading: the entropic coupling always has full support, whereas the unregularized coupling that it approximates is usually sparse, even given by a map. Regularizing optimal transport by less-smooth f f -divergences such as Tsallis divergence (i.e., L p L^{p} -regularization) is known to allow for sparse approximations, but is often thought to suffer from the curse of dimensionality as the couplings have limited differentiability and the dual is not strongly concave. We refute this conventional wisdom and show, for a broad family of divergences, that the key empirical quantities converge at the parametric rate, independently of the dimension. More precisely, we provide central limit theorems for the optimal cost, the optimal coupling, and the dual potentials induced by i.i.d. samples from the marginals. These results are obtained by a powerful yet elementary approach that is of broader interest for Z-estimation in function classes that are not Donsker. , and ?? Department of Statistics, Columbia University ?? ?? Department of Mathematics, University of Tübingen ?? ?? Departments of Statistics and Mathematics, Columbia University ?? 1 Introduction Optimal transport has become ubiquitous following computational advances enabling applications in statistics, machine learning, image processing, and other domains where distributions or data sets need to be compared (e.g., [ 37 , 43 ] ). Given probability measures P and Q on \mathbb{R}^{d} , and a cost function c:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R} , the Monge–Kantorovich optimal transport problem is \OT(P,Q)=\inf_{\pi\in\Pi(P,Q)}\int c(x,y)d\pi(x,y) (1) where \Pi(P,Q) denotes the set of couplings; i.e., joint distributions \pi on \mathbb{R}^{d}\times\mathbb{R}^{d} with marginals P and Q . A key bottleneck for statistical applications is that optimal transport suffers from the curse of dimensionality in terms of sample complexity (see [ 4 , 12 , 16 ] among many others). More specifically, let X_{1},\dots,X_{n} and Y_{1},\dots,Y_{n} be i.i.d. samples from P and Q , respectively, and consider their empirical measures P_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}} and Q_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{Y_{i}} . Then \OT(P_{n},Q_{n}) , the value of ( 1 ) computed with marginals (P_{n},Q_{n}) instead of (P,Q) , converges to the population value \OT(P,Q) at a rate that deteriorates exponentially with the dimension d . For instance, for the important cost c(x,y)=\|x-y\|^{2} defining the 2-Wasserstein distance, \mathbb{E}[|\OT(P_{n},Q_{n})-\OT(P,Q)|]\sim n^{-2/d} for dimension d\geq 5 , under regularity conditions on the population marginals P and Q (see [ 33 ] for this particular result). By contrast, the celebrated entropy-regularized optimal transport (EOT) avoids the curse of dimensionality. The EOT problem penalizes ( 1 ) with the Kullback–Leibler (KL) divergence \KL(\pi|P\otimes Q) between the coupling \pi and the product P\otimes Q of the marginals, {\rm EOT}_{\varepsilon}(P,Q):=\inf_{\pi\in\Pi(P,Q)}\int cd\pi+\varepsilon\KL(\pi|P\otimes Q) (2) where \varepsilon>0 is a fixed parameter determining the strength of regularization. Indeed, a series of works starting with [ 18 ] has shown that {\rm EOT}_{\varepsilon}(P_{n},Q_{n}) converges to {\rm EOT}_{\varepsilon}(P,Q) at the parametric rate n^{-1/2} , thus the dimension d (and the parameter \varepsilon ) only affect the constants. Literature is reviewed in Section 1.1 below. The prevailing thinking is that EOT overcomes the curse of dimensionality thanks to its smoothness. Indeed, the entropic penalty leads to optimal couplings whose density is smooth (or at least as smooth as the cost c ), and this regularity holds independently of the marginals. In particular, it holds uniformly over the empirical measures (P_{n},Q_{n}) , and this fact drives the aforementioned result of [ 18 ] . The flip side of smoothness is that the optimal coupling of EOT always has full support (i.e., the same support as P\otimes Q ), for any value of the regularization parameter \varepsilon>0 . By contrast, the unregularized optimal transport coupling that it approximates, typically has sparse support (the graph of a function, namely the Monge map). This disconnect can be undesirable depending on the application; for instance, the large support (or “overspreading”) can amount to blurrier images in an image processing task as shown in [ 2 ] , bias in a manifold learning task as in [ 45 ] , or unfaithful approximation of barycenters [ 29 ] . In such cases, sparse approximations are desirable. It is known that less-smooth f -divergence penalties give rise to sparse approximations. Indeed, consider the divergence-regularized optimal transport problem with the divergence D_{\varphi}(\pi|P\otimes Q) defined by a function \varphi , \displaystyle{\rm ROT}_{\varepsilon}(P,Q) \displaystyle:=\inf_{\pi\in\Pi(P,Q)}\int cd\pi+{\varepsilon}D_{\varphi}(\pi|P\otimes Q), (3) \displaystyle D_{\varphi}(\pi|P\otimes Q) \displaystyle:=\int\varphi\left(\frac{d\pi}{d(P\otimes Q)}\right)d(P\otimes Q), (4) where \varphi:\mathbb{R}_{+}\to\mathbb{R} is convex and satisfies certain conditions (see Assumption 2.1 ). While the KL divergence of EOT is recovered for \varphi(t)=t\log t , replacing this by a power \varphi(t)=(p-1)^{-1}(t^{p}-1) for p>1 (Tsallis divergence, including the quadratic or \chi^{2} divergence for p=2 ) was studied starting with [ 35 , 2 , 15 ] and empirically seen to have sparse solutions. Recent investigations underline this finding with theoretical results; see the literature review below. The main objection against such regularizations is that they lack the smoothness of EOT. Indeed, the density of the optimal coupling is only as smooth as the derivative of the convex conjugate \psi(s)=\sup_{t\geq 0}\{st-\varphi(t)\} of \varphi , which for \varphi(t)=(p-1)^{-1}(t^{p}-1) is k -times differentiable only for k<p/(p-1) . In particular, it does not enjoy the \mathcal{C}^{\infty} -smoothness crucially used in EOT, where the proof of sample complexity uses derivatives of higher and higher order as the dimension d grows. Following the aforementioned prevailing thinking, it is often assumed that ( 3 ) thus suffers from the curse of dimensionality when it is not smooth. This idea is in line with the recent work [ 1 ] which gives an upper bound for the sample complexity that deteriorates exponentially with the dimension d (see Section 1.1 ). In the present paper, our goal is to refute this prevailing thinking. For a broad class of regularizations \varphi , we show that ( 3 ) overcomes the curse of dimensionality and converges at the parametric rate, despite a lack of smoothness (and also of a PL inequality, cf. Section 1.1 ). In fact, our results are much more detailed: we establish central limit theorems for all key objects. As a consequence, ( 3 ) provides approximate solutions to optimal transport with precise statistical guarantees. Synopsis of main results We consider marginals P,Q with bounded supports, at least one of them connected. The transport cost c is a general \mathcal{C}^{1} function. The main assumption on the divergence is that the convex conjugate \psi of \varphi is \mathcal{C}^{2} . This includes the KL divergence where \psi is \mathcal{C}^{\infty} , but also Tsallis divergences that yield sparse approximations of unregularized optimal transport. There are three main objects under consideration. The first is the optimal cost \displaystyle{\operatorname{ROT}}_{\varepsilon}(P_{n},Q_{n}) ; here the result is simple to state as the object is scalar. In Theorem 3.5 , we show that the optimal cost is asymptotically normal at rate \sqrt{n} . More precisely, \sqrt{n}\big(\displaystyle{\operatorname{ROT}}(P_{n},Q_{n})-\displaystyle{\operatorname{ROT}}(P,Q)\big)\to N(0,\sigma^{2}) where N(0,\sigma^{2}) is the centered normal distribution with a variance \sigma^{2} detailed in Theorem 3.5 . The second key object is the optimal coupling \pi_{n}\in\Pi(P_{n},Q_{n}) . Here

Read the complete text