Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
69,807 characters · 17 sections · 96 citation commands
Generalized Optimal Transport
\doparttoc \faketableofcontents \parttoc
Many causal and structural parameters in economics can be identified and estimated by solving an optimization problem over all distributions consistent with the economic model and the empirical evidence. For example, one may wish to find the smallest value of a long-term average treatment effect that is consistent with both experimental and observational datasets (as in athey2020combining, aizer2024lifetime, and obradovic2024identification), or to assess matching efficiency in a marriage market (as in chiappori2017partner) by comparing the realized surplus to the maximum achievable surplus given the observed marginal distributions of partner characteristics. In entry games (e.g. tamer2003incomplete, gurussell), English auctions (auctions) and network formation models (e.g. miyauchi2016structural, de2018identifying), assessing whether a structural parameter is compatible with the observed distribution of equilibria amounts to checking whether the minimum violation of the model over all data-consistent distributions is zero. In each case, the parameter of interest is the value of an optimization problem over a set of distributions constrained by model structure and data.
This paper introduces a general identification and estimation framework for such problems, which we refer to as Generalized Optimal Transport (GOT). Let $T \in \mathbb{R}^d$ denote the vector of variables, both observed and unobserved, that is restricted by an an economic model to a known subset $\mathcal{T} \subseteq \mathbb{R}^d$. Suppose $T$ is distributed according to a true unknown probability measure $\mathbb{P}$, and the parameter of interest is of the form $\mathbb{E}_\mathbb{P}[b(T)]$ for some identified function $b$. Using the theory of characteristic kernels (see steinwart2021strictly), we show that two common types of identification conditions -- i) identification of certain joint distributions of subvectors of $T$, and ii) (conditional) independence restrictions on components of $T$ -- can both be represented as moment equalities satisfied by the true distribution $\mathbb{P}$. Sharp bounds on $\mathbb{E}_\mathbb{P}[b(T)]$ can then be obtained by solving optimization problems over all distributions supported on $\mathcal{T}$ that satisfy these conditions.
GOT accommodates empirical settings that go beyond those typically handled by existing tools, such as linear programming (e.g. honoreadriana2006, santos, laffers2019) or classical optimal transport (ober2023estimating, torous2024optimal). In particular, it allows for continuously distributed variables, overlapping identified marginals (e.g., $(T_1, T_2)$ and $(T_2, T_3)$, but not their joint), and structural assumptions such as (conditional) independence. These features are central to many modern empirical applications, including athey2020combining, aizer2024lifetime, obradovic2024identification, and luo2024selecting.
We develop a computationally simple procedure for finding the value of GOT. First, using duality theory for linear programs (LP) in Banach spaces (shapiro2001duality) and the exact penalization approach of voronin2025linear, we rewrite GOT as an unconstrained convex program over an $\mathcal{L}^2$ space. Projecting onto a subspace of polynomials of order up to $J$, we obtain a finite-dimensional semi-infinite LP that can be easily solved using cutting-plane methods (see reemtsen1998numerical). Crucially, we exploit self-adjointness of the projection operator to derive a Jackson-type bound on the approximation bias of the form $C J^{-r}$, where $C, r > 0$ depend only on known parameters and kernel smoothness.
When the identified components of the model are estimated from data, we construct a computationally simple and consistent estimator of the sharp upper bound\footnote{The same conclusions hold for the lower bound, since $\min_P \mathbb{E}_P[b(T)]=-\max_P-\mathbb{E}_P[b(T)]$.} on $\mathbb{E}_\mathbb{P}[b(T)]$. This estimator converges from below at the uniform rate $\sqrt{n}$, i.e., it is $\sqrt{n}$-uniformly valid for the upper bound, and pointwise consistent from above. The lack of $\sqrt{n}$-uniform consistency from above reflects a positive, vanishing bias term, closely related to the ill-posed inverse problem (see horowitz2011applied). Fortunately, the bias is conservative—our estimator does not underestimate the upper bound and overestimate the lower bound uniformly.
GOT nests several important special cases. When $T$ is discrete, it reduces to a linear program and recovers classical identification results (see balke1994counterfactual, balke1997bounds, santos, torgovitsky2019partial, laffers2019). When $T$ is supported on a product space and only its disjoint marginals are identified, GOT coincides with multimarginal optimal transport (OT), which has seen growing use in economics (e.g., galichon2011, galichon2016optimal, carlier2016vector, ober2023estimating, gunsilius2025primer). manole2024sharp show that empirical two-marginal OT with a Lipschitz cost suffers from the curse of dimensionality, achieving the minimax rate of $n^{2/d}$. Our estimator remains valid for the upper bound, given by the OT value, at rates up to $\sqrt{n}$. Moreover, for any $\eta \in (0,1]$ chosen by the researcher, we provide an estimator that converges to the OT value at $n^{(1- \eta d/(d+2))/2}$ from below and $n^{\eta/(d+2)}$ from above uniformly.
This work builds on the insight, developed in discrete settings by balke1994counterfactual, balke1997bounds, santos, torgovitsky2019partial, and laffers2019, that partial identification problems can often be formulated as optimization problems over distributions. While GOT is also related to the literature on moment (in)equalities (andrews2013inference, ANDREWS2017275, armstrong2014weighted, armstrong2016multiscale, chernozhukov2019inference, andrews2023, chernozhukovneweysantos2023), in our case a continuum of moment restrictions involve probability measures as their infinite-dimensional parameters, precluding the application of previously developed methods. There is extensive literature on estimation and inference in the special cases of GOT: the empirical LP (bhattacharya2009inferring, santos, semenova2023adaptive, chorussel2023, gafarov2024simple, voronin2025linear) and the empirical optimal transport (ober2023estimating, manole2024sharp, sadhu2024stability, hundrieser2024unifying). More broadly, GOT is related to the literature on partial identification (MP2000, MP2009, beresteanu2011sharp, santos) and estimation of partially identified models (beresteanu2008asymptotic, CHT, CLR).
The rest of the paper is organized as follows. Section (ref) introduces the setup, discusses key applications, and develops general identification theory. Section (ref) develops the estimation theory. Section (ref) analyzes the vanishing conservative bias term and examines the special case of optimal transport. Section (ref) presents simulation evidence.
Let $T \in \mathbb{R}^{d}$ be the vector of all economic variables in the model, distributed according to an unknown true probability measure $\mathbb{P}$. The object of interest is the value of a linear functional $\mathbb{E}_P[b(T)]$ evaluated at $P = \mathbb{P}$, where $b$ is an identified cost function. We suppose that two types of identification conditions are available. Firstly, the researcher restricts the support of $T$ to a known compact subset $\mathcal{T} \subseteq \mathbb{R}^d$. Rescaling $T$ if needed, we suppose that $\mathcal{T} \subseteq [-1,1]^d$ without loss of generality. Secondly, for a separable measure space $(S, \mathcal{S}, \nu)$ and identified maps $a$ and $c$, there is a collection of moment restrictions $\mathbb{E}_P[a(T)(s)] = c(s), ~ \nu-\text{a.s. in } s \in S$ that are assumed to be satisfied at $P = \mathbb{P}$.
The value $\mathbb{E}_{\mathbb{P}}[b(T)]$ of the functional of interest may not be point-identified under the imposed restrictions. Let $\mathcal{P}$ be the collection of all Borel probability measures supported on $\mathcal{T}$, and define $\theta = (a,b,c)$. Moreover, suppose that $\beta(\theta)$ is the sharp upper bound on the value of interest. It follows that
We call the problem (GOT) the generalized optimal transport problem. The rest of this section discusses the applications of (GOT). Any restrictions introduced for that purpose do not apply to the rest of the paper.
The simplest applications of (GOT) arise in discrete settings. In case the sets $\mathcal{T}$ and $S$ are finite, (GOT) reduces to a finite-dimensional linear program (LP), a tool long used for partial identification of treatment effects (see, e.g., balke1994counterfactual, balke1997bounds, santos, torgovitsky2019partial, laffers2019, voronin2025linear).
As we show below, (GOT) nests multimarginal optimal transport (OT), which has a variety of economic applications (e.g., galichon2011, galichon2016optimal, carlier2016vector, luo2024selecting). Unlike in Example (ref), OT settings often involve uncountable $\mathcal{T}$ and $S$. We defer (GOT) characterizations of the remaining examples to the sequel.
While linear programming and optimal transport are both nested within (GOT), our framework is most useful when their generality falls short—namely, when $T$ is continuously distributed and the identification pattern does not reduce to observing disjoint marginals. (GOT) accommodates settings with overlapping identified marginals—e.g., the joint distributions of $T_1, T_2$, and $T_2,T_3$ are identified—and additional structure on $\mathbb{P}$, such as (conditional) independence between components of $T$ (see galichon2011, athey2020combining, aizer2024lifetime, obradovic2024identification, luo2024selecting).
Support restrictions in the form of a known compact\footnote{Compactness of $\mathcal{T}$ is not easily relaxed: it underlies the identification of the dual of the space of continuous functions with the space of finite Borel measures, $C^*(\mathcal{T}) \simeq \mathcal{M}(\mathcal{T}),$ on which we rely heavily in Section 3.} support $\mathcal{T}$ may reflect discreteness or boundedness of some components of $T$, and incorporate structural relations. The choice of cost function $b(T)$ determines the target functional of interest $\mathbb{E}_\mathbb{P}[b(T)]$.
\addtocounter{example}{-1}
The estimation procedure for (GOT) will be developed under the assumption of a continuous $b$ -- however, discontinuous functions can often be accommodated by augmenting the vector $T$ and redefining the support accordingly. \addtocounter{example}{-1}
Some parts of the distribution of the random vector $T$ may be identified. This information is straightforwardly incorporated into (GOT) in the discrete setting, as shown in Example (ref). We now discuss the more general case. Suppose there is a collection of sets of indices $\mathcal{I} = \{I_i\}^q_{i=1} \subseteq 2^{d}$, such that for any $I \in \mathcal{I}$, the marginal distribution $\mathbb{P}_{I} \equiv \text{proj}_I \mathbb{P}$ is identified. In what follows, we also denote by $T_I$ the subvector of $T$ comprised of variables with indices in $I$. Unlike in the OT setting (e.g. manole2024sharp and sadhu2024stability), in (GOT) identified marginals need not be disjoint, nor collectively exhaustive, and $q$ may be greater than $2$.
Let us first consider the case of a single identified marginal distribution $\mathbb{P}_I$. To rewrite this identification restriction in the form of a moment condition in (GOT), we leverage the concept of a characteristic kernel\footnote{We refer the reader to Wendland_2004, Chapter 10 for the discussion of kernels and their Reproducing Kernel Hilbert Spaces. Also see steinwart2021strictly for a detailed discussion of characteristic kernels.}.
Intuitively, a characteristic kernel is a device that `separates' probability measures. Let $\lambda$ be the Lebesgue measure over $\mathbb{R}^d$. The following Lemma relies on the fact that continuous functions on a closed cube are equal $\lambda-$a.e. iff they are equal everywhere on it. It is convenient to denote the $d-$cube with side $2$, centered at $t_0$, by $H_d(t_0) \equiv [-1 + t_0 ,1+ t_0]^d$.
Fix a continuous characteristic kernel $K: (\text{proj}_I \mathcal{T})^2 \to \mathbb{R}$. Using Lemma 1, observe that
Thus, a restriction $P_I = \mathbb{P}_I$ can be introduced to the problem (GOT) by setting $S \equiv H_d(0)$, with $\mathcal{S}$ being its Borel $\sigma-$algebra, $\nu$ being the Lebesgue measure $\lambda$, and $a(T)(s) \equiv K(s_I, T_I)$ with $c(s) \equiv \mathbb{E}_{\mathbb{P}_I} [K(s_I, T_I)]$ for $s \in S$.
\addtocounter{example}{-1}
We denote by $\iota$ the vector of ones, with dimension inferred from the context. To incorporate many identified marginals simultaneously, one simply constructs $S \equiv \bigcup^{q}_{j = 1} H_{d}(3j)$, with $\mathcal{S}$ being a Borel $\sigma-$algebra over $S$, lets $\nu \equiv \mathcal{\lambda}$, and defines $a(T)(s) \equiv K_j(s_{I_j} - 3\iota j, T_{I_j})$, and $c(s) \equiv \mathbb{E}_{\mathbb{P}_{I_j}}[a(T)(s)]$ for $s \in H_{d}(3j)$ and $T \in \mathcal{T}$, where $K_j: \mathbb{R}^{2|I_j|}\to \mathbb{R}$ is a continuous characteristic kernel, and $j \in [q]$.
In some applications, such as in Examples (ref) and (ref), it may be reasonable to assume independence between subvectors of $T$. The result below allows to incorporate such restrictions into (GOT). Our construction requires identification of the marginal distribution of at least one subvector involved in the independence condition.
Suppose that vector $T$ contains disjoint subvectors $T_1$ and $T_2$ with $(T_1, T_2) \in \mathbb{R}^q$, and $s_1, s_2$ are the projections of $s \in \mathbb{R}^d$ onto their respective coordinates. Moreover, the marginal distribution $\mathbb{P}_2$ of $T_2$ is identified. Fixing a continuous characteristic kernel $K: H_{2q}(0)\to \mathbb{R}$, observe that the map $(s,t_1) \to \mathbb{E}_{\mathbb{P}}[K((s_1,s_2),(t_1,T_2))]$ is then also identified. By Lemma 2, to embed the restriction that $T_1 \rotatebox[origin=c]{90}{$\models$}_{\mathbb{P}} T_2$ into (GOT), one may set $S = H_d(0)$, and let $\mathcal{S}$ be the corresponding Borel $\sigma-$algebra, $\nu = \lambda$, and $a(T)(s) \equiv K((s_1,s_2), (T_1, T_2)) - \int K((s_1,s_2),(T_1,T_2))\text{d}\mathbb{P}_2(T_2)$, while $c(s) = 0$ for $s \in S$. Multiple independence restrictions, as well as their combinations with other identifying conditions are accommodated by analogy with the construction in Section (ref). \setcounter{example}{2}
The researcher may be willing to impose conditional independence between subvectors of $T$ - for instance, if a conditionally exogenous instrument is available. The following Lemma allows to embed conditional independence restrictions into (GOT). As in the unconditional case, the construction requires identification of certain marginal distributions.
Suppose that vector $T$ contains disjoint subvectors $T_1, T_2, T_3$, and denote by $s_i$ the projections of $s \in \mathbb{R}^d$ onto their respective coordinates. Moreover, suppose that the distribution $\mathbb{P}_{1,3}$ of $(T_1, T_3)$ is identified, so that the conditional MGF of $T_1$ given $T_3$ is also identified. Using Lemma 3, to embed the restriction $T_1 \rotatebox[origin=c]{90}{$\models$}_{\mathbb{P}} T_2 | T_3$ into (GOT), one may set $a(T)(s) = \exp(\sum^3_{j=1}s'_{j} T_{j}) - \mathbb{E}_{\mathbb{P}}[\exp(s'_{1}T_{1})|T_{3}] \exp(\sum^3_{j=2}s'_{j} T_{j})$ and $c(s) = 0$ for an appropriate range of $s$ with Lebesgue measure over it, as discussed in previous sections.
This section develops estimation theory for the problem (GOT). In what follows it will be convenient to reformulate (GOT) as a problem solved over the space of finite positive Borel measures over $\mathcal{T}$, which we denote by $\mathcal{M}^+(\mathcal{T})$. We refer to the following problem as the dual problem throughout the paper:
Denote the set of solutions of (D) by $\mathcal{A}^*(\theta)$. Further, consider the Hilbert space $X \equiv \mathcal{L}^2(S,\mathcal{S},\nu)$ with the dot product $\langle f, g\rangle \equiv \int f(s)g(s) \text{d}\nu(s)$ for $f, g \in X$.
Assumption 1.i requires the cost function to be continuous, and demands that the constraint map be continuous in $\mathcal{L}^2$ norm. Note that it does not require $a(t)(\cdot)$ to be continuous for all $t \in \mathcal{T}$. Assumption 1.ii ensures that the problem (D) is equivalent to (GOT), as every feasible measure in (D) should satisfy $\int a(t)(s^*)\text{d}\mu(t) = c(s^*) \iff \int 1\text{d}\mu(t) = 1$. Assumption 1.iii means that the imposed identifying conditions cannot be rejected.
Recall that the parameter $\theta$ is not known. In what follows, it will be estimated via some $\hat{\theta}$. The sampling uncertainty in $\hat{\theta}$ renders the direct analysis of (D) complicated, motivating us to approach it using duality for generalized linear programs. Consider the program
which we refer to as the primary program.
Under Assumption 1, the problem (D) is the dual to (P)\footnote{Observe that (P) is not necessarily the dual of (D), because the Banach space $\mathcal{C}(\mathcal{T})$ is not reflexive.}. Assumption 1.ii enforces the Slater condition\footnote{See shapiro2001duality for the definitions.} in problem (P), ensuring strong duality and solvability of (D) (see e.g. shapiro2001duality). One can then adapt the exact penalization idea in voronin2025linear to reformulate (P) as an unconstrained optimization problem. Namely, for some $w > 0$, define
The objective function in (ref) is called the penalty function, with $\beta_\infty(\theta) \leq \beta(\theta)$ in general. However, if $w$ is larger than the norm of at least one Lagrange multiplier of (P), defined as the solution of (D), then the penalty term $ w \left(\max_{t \in \mathcal{T}} b(t) - \langle a(t), x \rangle \right)^+$ is `large enough' for $x$ that violate the constraints of (P) to ensure that $\beta_\infty(\theta) = \beta(\theta)$. Recall that the solutions of (D) are probability measures under Assumption 1.ii, so their total variation is upper bounded by $1$. Combining these observations leads to the following result.
We assume that $w \equiv 1$ in what follows.
Unfortunately, even when strong duality holds, $\beta(\theta) = \beta^*(\theta)$ and (D) is solvable, both (P) and the unconstrained problem defined in (ref) may fail to have a solution. To circumvent that, we consider a version of the penalized problem solved over a weak-compact subset of $X$. For any $\gamma > 0$, we define $B_\gamma \equiv \{x \in X: ||x||\leq \gamma\}$, and consider
and let the solution set of the above problem be $\mathcal{A}(\theta; \gamma)$. Moreover, suppose the distance between the compactified and the unconstrained versions is $\Delta(\theta; \gamma) \equiv \beta_{\infty}(\theta; \gamma) - \beta(\theta)$. Banach-Alaoglu Theorem and properties of infimum lead to the following Lemma.
While the function $\beta_\infty(\theta;\gamma)$ already allows for perturbation analysis with estimated $\hat{\theta}$, it is computed via infinite-dimensional optimization, and so does not yet constitute a practical estimator. To build the latter, we first formalize the structure of the space $(S, \mathcal{S}, \nu)$.
Assumption 2 allows for continuous restrictions, such as discussed in Section (ref), and accommodates an additional finite collection of moment conditions\footnote{Observe that the measure described in Assumption 2 can be constructed as $\nu(A) = \sum^{m}_{i = 1} \lambda(A \cap H_i) + l^{-1} \sum_{s \in H_{m + 1}}\mathds{1}\{s \in A\}$ for $A \in \mathcal{S} \equiv \sigma (\bigcup^{m+1}_{i = 1} \mathcal{B}(H_i))$. The exact shape and size of sets $H_i$ is inconsequential, so long as their maximum radius is controlled. For approximation using Assumption 3, it is important that their interiors be Lipschitz domains.}. Whenever Assumptions 1 and 2 are assumed simultaneously, we suppose that $s^* \in H_{m + 1}$.
For a cube $H \subseteq \mathbb{R}^d$, denote by $\mathbf{P}_j(H)$ the space of all polynomials\footnote{While other sieve spaces may also be used, we work with polynomials, as the Jackson-type inequality for them is readily available.} over $H$ of degree up to $j \in \mathbb{N}$. Under Assumption 2, for a collection $J \equiv (k_i)^{m}_{i = 1}$ with $k_i \in \mathbb{N}$ for $i \in [m]$, consider a finite-dimensional closed linear subspace of $X$, given by $\mathbf{P}_{J} \equiv \{f \in X: f|_{H_i} \in \mathbf{P}_{k_i}(H_i), \text{for } i \in [m]\}$. Let $\mathbf{p}_J: X \to \mathbf{P}_J$ be an orthogonal projection onto $\mathbf{P}_J$. It is well-defined by Hilbert projection theorem. Define
The value $\beta_J(\theta;\gamma)$ is now computed over a finite-dimensional subspace of $X$. It corresponds to the value of a semi-infinite linear program with $1+l+ \sum^{m}_{i=1} k^d_i$ variables\footnote{Note that this problem is equivalent to $\min_{x^* \geq 0, x \in B_\gamma \cap \mathbf{P}_J} \langle c, x \rangle + x^*~ \text{s.t.:} ~x^* \geq b(t) -\langle a(t), x\rangle ~ \forall t \in \mathcal{T}$. }, which is feasible computationally even for relatively large $d$, see reemtsen1998numerical for details. $\beta_{J}(\theta; \gamma)$ is used to construct our final estimator.
Suppose Assumption 1 holds, and consider $x^* \in B_\gamma \cap \mathcal{A}(\theta, \gamma)$, which is guaranteed to exist by Lemma (ref). Because $\mathbf{p}_J$ is an orthogonal projection, $||\mathbf{p}_Jx|| \leq ||x||,$ so $\mathbf{p}_{J} x \in B_\gamma \cap \mathbf{P}_J$. Using that and the triangle inequality, one obtains
Controlling the RHS of the above expression directly is impractical, as $x^*$ may not be smooth, and therefore need not be well-approximated by polynomials\footnote{Of course, because polynomials are dense in $X$, $||(I-\mathbf{p}_J)x^*||_2 \to 0$ as $\min_i k_i \to \infty$ for any fixed $x^*$.}. However, we may use the fact that projection operators are self-adjoint, $\langle x_1, (I - \textbf{p}_J)x_2\rangle = \langle (I - \textbf{p}_J)x_1, x_2\rangle$ for any $x_1, x_2 \in X$. Applying Cauchy-Schwarz inequality then yields
where, if the functions $c$ and $a(t)$ for all $t \in \mathcal{T}$ have appropriate Sobolev smoothness, the right-hand-side is uniformly of polynomial order in $k_i$, see Theorem (ref).
For a cube $H$, let $\tilde{H}$ denote its interior, and let $W^{r,2}(\tilde{H})$ be the $r-$order Sobolev space of $\mathcal{L}^2-$functions over $\tilde{H}$, equipped with the Sobolev norm $||\cdot||_{W^{r,2}}$.
Consider a perturbed version $\hat{\theta} = (\hat{a}, \hat{b}, \hat{c})$ of $\theta$. Under restrctions in Sections (ref)-(ref), it can be obtained using empirical analogues of $a, c$ and some estimator of $b$. The following Theorem is our main deterministic result, treating $\hat{\theta}$ as fixed.
We now specify the deterministic Theorem (ref) to the case of (GOT) under restrictions in Sections (ref)-(ref). In this case, the parameters $a, c$ are linear functionals of the true unknown probability measure $\mathbb{P}$, and $\hat{\theta}$ is a random map.
Assumption 4 defines $\hat{\theta}$ under the single-sample assumption for notational convenience. It is straightforward to incorporate multiple samples in the spirit of Example (ref) by nesting them in a single collection, see athey2020combining. When studying uniformity in $\mathbb{P}$, its support $\mathcal{T}$ is taken to be fixed; the set $I$ and the kernels employed in the construction of $\theta$ in Assumption 4.i are also treated as fixed.
We now generalize our procedure to some asymptotic regimes, where the set $S = S_n$ and the parameter $\theta = \theta_n$ are allowed to change with $n$. The set $\mathcal{T}$ is treated as fixed. If Assumption 2 holds, we can decompose any $x = \tilde{x}+ \overline{x} \in X$ into a discrete, $\overline{x} \in \mathbb{R}^l$, and a functional part, $\tilde{x} \in \mathcal{L}^2(\bigcup_{j \in [m]}H_j)$. By analogy, for $a$ and $c$, write $\langle a(\cdot), x\rangle=\langle \tilde{a}(\cdot), \tilde{x} \rangle + \overline{a}(\cdot)'\overline{x}$ and $\langle c, x\rangle = \langle \tilde{c}, \tilde{x}\rangle + \overline{c}'\overline{x}$, where $\langle \cdot\rangle$ also denotes the $\mathcal{L}^2(\bigcup_{j \in [m]}H_j)$ dot-product. Denote $\mathcal{L}_\infty(x;\theta) = \langle c, x \rangle + \left(\max_{t \in \mathcal{T}} b(t) -\langle a(t),x\rangle \right)^+$. When fundamentals $X_n, \theta_n$ change with $n$, the map $\mathcal{L}_\infty$ also changes, which we ignore in notation for simplicity.
When the number of discrete moments grows with $n$, control over the $\mathcal{L}^2-$norms of the components $\overline{x}, \overline{c}$ may no longer be adequate. For example, one may wish to use Hölder inequality to get $|\overline{x}'(\hat{\overline{c}} - \overline{c})| \leq ||\overline{x}||_z ||\hat{\overline{c}} - \overline{c}||_{z^*},$ where $z^*$ is the conjugate exponent of $z$. If $z^* = + \infty,$ an application of the vector-valued Hoeffding inequality then yields control over the RHS when the dimension of $\overline{c}$ grows. Motivated by this, we consider $\gamma = (\tilde{\gamma}, \overline{\gamma}) \in \mathbb{R}_{++}^2$. Accordingly, for some $z \in \mathbb{N}$, we redefine $B_\gamma \equiv \{x \in X: ||\tilde{x}|| \leq \tilde{\gamma}, ||\overline{x}||_z\leq \overline{\gamma}\}$. If $X$ changes with $n,$ so does $B_\gamma$, which we ignore in our notation. Moreover, $\gamma_n \to \infty$ w.p.a.1 is taken to mean $\min\{\tilde{\gamma}_n, \overline{\gamma}_n\} \to \infty$. The rest of the definitions are used mutantis mutandis.
Assumption 5 restricts us to asymptotic regimes, in which the feasible sets of the compactified problem corresponding to $\theta_n$ grow monotonically with the sample size in the sense of condition iii), while the optimal value stays fixed.
Suppose that $\hat{\theta}_n = (\hat{a}_n, \hat{b}_n, \hat{c}_n)$ is a deterministic perturbed version of $\theta_n$. The following analogue of Theorem (ref) is obtained by combining Hölder inequality and Lemma (ref).
Combining Theorem (ref) with the maximal inequality, we derive the convergence rate in the high-dimensional regime, where the number of discrete moments in (GOT), $l_n$, is allowed to grow with $n \to \infty$. In the assumption below, a quantity is `fixed' if it is constant in $n$.
Assumption (ref) formalizes the construction of $\theta_n$ that combines a fixed collection of conditions in Assumption (ref) with a growing discrete collection of moments of some known bounded functions of $T$. Boundedness of $\textbf{B}_n$ may likely be relaxed to a restriction on tail behavior, which we leave for future research.
Define $\mathbf{A}: \mathcal{L}^2(\nu) \to \mathcal{C}(\mathcal{T})$ to be the bounded linear operator mapping $x \to \langle a(\cdot), x \rangle$, and let $R(\mathbf{A})$ be its range. Under Assumption 1, we can then rewrite the problem $(P)$ as
In the proposition below, we treat $\gamma$, and $B_\gamma$ as in Section (ref), and $\iota$ is the vector of ones.
Proposition (ref) suggests that to control $\Delta(\theta, \gamma)$ in terms of $\gamma$, one needs to study how well the solution $f^*$ (if it exists) can be approximated by functions in the range of $\textbf{A}$. We now provide further evidence on that issue in the special case of optimal transport.
Under Assumption 7, let $\mathbf{M}(\mathbb{P}_1, \mathbb{P}_2) \subseteq \mathcal{T}$ be the set of all probability distributions over $\mathcal{T}= \mathcal{T}_1 \times \mathcal{T}_2$ with marginals $\mathbb{P}_1, \mathbb{P}_2$. The classical optimal transport problem is
For a Lipschitz-continuous cost function $b(\cdot)$, because the measures $\mathbb{P}_i$ are compactly supported under Assumption 7, a standard duality result asserts that the value of (OT) is equal to the minimum of the following dual Kantorovich problem
where the minimum is attained by some Lipschitz-continuous dual potentials $f^*_{i}$ (see Theorem 5.10 and p.68 in villani2008optimal and Lemma E9 in ober2023estimating). Smoothness of these potentials can then be used to characterize the error $\Delta(\cdot)$ using arguments similar to those in Proposition (ref).
We use the procedure discussed in Section (ref), augmenting it with a collection of discrete moment conditions, as described in Section (ref). Write $s = (s_1, s_2) \in \mathbb{R}^d$, with $s_i \in \mathbb{R}^{d_i}$. Let $\mathbf{B}^{(k)}_i: H_{d_i}(0) \to \mathbb{R}^{k^{d_i}}$ be the basis of $k^{d_i}$ equally-spaced normalized linear splines over $H_{d_i}(0)$. Suppose $K_i: \mathbb{R}^{2d_i} \to \mathbb{R}$ is a fixed continuous characteristic kernel, and $a(T)(s) = K_i(s_i - 3i,T_j)$ for $s \in H_d(3i)$, $T \in \mathcal{T}$. Moreover, fix $H = \{s^*\} \cup \{h_j\}^{l}_{j = 1} \subseteq \mathbb{R}^d$, such that i) $|H| = l + 1$, and ii) $\{H, \{H_d(3i)\}_{i=1,2}\}$ are disjoint, and iii) $l = k_1^{d_1} + k_2^{d_2}$ for some $k_1, k_2\in \mathbb{N} \cup \{0\}$. Let $(a(T)(h_j))^l_{j =1} = (\mathbf{B}^{(k_i)}_i(T_i))_{i=1,2}$, while the point $s^*$ is as in Assumption 1. Finally, construct $S$ as in Assumption 2, and set $c(\cdot)$ to be the identified expectation of $a(T)(\cdot)$. Understanding that $k_i = k_{in}$ for $i = 1,2$, let $\theta^{(ot)}_n$ and $\mathbf{A}^{(ot)}_n$ be the resulting parameter and the linear operator.
Lemma (ref) thus yields a uniform decay rate for $\Delta(\cdot)$ term in the special case of optimal transport, provided we consider asymptotics $k_{i} \to \infty$.The following result is a straightforward combination of Lemma (ref) and the results in Section (ref). We develop it for $d_1 = d_2$ and $k_{1n} = k_{2n} \equiv k_n$. We also suppose that $\ell^1$ norm of $\overline{x}$ is controlled, i.e. $z = 1$.
Consider a simple example, in which $T = (T_1, T_2, T_3) \in \mathcal{T} = [0,1]^3$. Accordingly, $s = (s_1, s_2, s_3) \in \mathbb{R}^3$. Suppose that the marginal distributions $\mathbb{P}_{1,2}$ and $\mathbb{P}_{2,3}$ are identified. Namely, suppose that $T_i \sim U[0,1]$ for $i = 1,2,3$, and $T_1 \rotatebox[origin=c]{90}{$\models$} T_2$, and $T_2 \rotatebox[origin=c]{90}{$\models$} T_3$. Consider
It is clear that the value of (ref) is identified and equal to $\mathbb{E}_{\mathbb{P}_{3}} T_3 - \mathbb{E}_{\mathbb{P}_1} T_1 = 0$. For simplicity, we generate one i.i.d. sample $\{T_i\}^n_{i = 1}$ per simulation. Accordingly, we define the oracle estimator to be $\hat{\beta}^{oracle}\equiv \frac{1}{n}\sum^{n}_{i = 1} T_{3i} - T_{1i}$.
To apply our estimation procedure, we set $b(T) = T_3 - T_1$, $a(T)(s) = \exp(s_1 T_1 + s_2T_2)$ for $s \in [-1,1]^3$, $a(T)(s) = \exp((s_2 - 3)T_2 + (s_3-3)T_2)$ for $s \in [-1,1]^3 + 3$. $c(s) = M_{1}(s_1,s_2) - $ the MGF for $s \in [-1,1]^3$, and $c(s) = M_2(s_1-3,s_2-3)$ for $s \in [-1,1]^3 + 3$. $\nu = \lambda$, and $s^* = (5,5)$. Denote $\psi_{ijk}(s) \equiv s^i_1s^j_2s_3^k$, and $H \equiv [-1,1]^3$. Performing the polynomial expansion of degree $J \in \mathbb{N}$ for each dimension of $T$, we obtain the problem
where $B_\gamma$ is obtained by restricting $||(x, y, x^*)||_\infty < \gamma$ for simplicity\footnote{The resulting space is still a convex bounded subset of $X$, and so all results in Section 3 apply.}. The sample analogue of the problem (ref), with the value of $\beta_J(\hat{\theta}; \gamma)$, is then obtained by substituting the true MGF. $M_1(s_1,s_2)$ with its plug-in estimator, $\hat{M}_{1}(s_1,s_2) \equiv n^{-1}\sum^n_{i = 1} \exp(T_{1i}s_1 + T_{2i} s_2)$ for all $s_{1}, s_2 \in [-1,1]^3$, and similarly for $M_2(\cdot)$.
Using the exponential kernel allows to avoid numerical integration. We have
where $I_j(t) \equiv \int^1_{-1} \exp(ts)s^{j}\text{d}s$. For $j \in \mathbb{N}$ and $t \ne 0$, one obtains
with $I_0 (t) = \frac{1}{t}(e^t - e^{-t})$. For $t = 0$, $I_j(0) = \frac{2}{j+1} \mathds{1} \{ j \mod 2 = 0\}$ for all $j \in \mathbb{N} \cup \{0\}$.
\selectlanguage{english}
\nocite{*}
\addcontentsline{toc}{section}{6 References.}