Field Codes for Distributed Coupling Samplers and Certified Empirical Transport
Hung PQ. Mai1,2 Duc Hai Nguyen1,3 Luong Doan1 Ngoc Vu1 Khanh Nguyen1,3 Nhung Duong1 Tuan Do1,4 1
B0Labs, N2TP Technology 2 National Economics University, Vietnam 3 Nanyang Technological University 4 Phenikaa University, Vietnam Correspondence: [email protected]
arXiv:2607.27078v1 [cs.CC] 29 Jul 2026
Abstract In this paper, we formulate three communication tasks for empirical optimal transport: distributed coupling sampling, cost-evaluable coupling output, and scalar value-certified sampling. Our main result is a field-code compiler: any communicated transport field approximating an optimal empirical Monge map to error η can be completed by sparse target-cell residuals into an exact-marginal valuecertified sampler with scalar certificate W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆, where ∆ is the public target-partition diameter. The certificate accuracy is controlled by ∆ alone. The field error η controls residual communication under a cell-margin condition; without a margin, η alone does not bound residuals. We instantiate the compiler via adaptive local-affine and tensor-product spline codes with d(m + 1)d b field bits in the spline case, plus residual lists charged separately. For lower bounds, exact Gap-Hamming embeddings prove certified output is hard, including a smooth cell-packing diffeomorphism family requiring Ω(ε−2d/(d+4) ) communication for any cost-evaluable, cost-certified, or value-certified protocol. The same gadgets admit zero-communication samplers, formally separating the sampler and certificate-bearing output models. These results identify the transport field as the right communicated object whenever a field code is available, primarily as a residual-sparsity tool.
1
Introduction
1.1
Motivation
Normalizing flows, flow matching, rectified flows, and OT-CFM methods learn objects that are fundamentally transport-based: maps, velocity fields, or couplings that move mass from a source distribution to a target distribution (Lipman et al., 2023; Liu et al., 2023; Tong et al., 2024a,b; Guo and Schwing, 2025). In standard centralized training, the learner can access both source and target samples and can construct pairs, costs, or velocity targets directly. This assumption breaks in distributed settings. If the source samples and target samples are held by different parties, then the transport object is no longer merely a computational output; it becomes an information-theoretic object that must be communicated. The basic question is therefore: what must be transmitted in order to construct a coupling, not just estimate its cost? This distinction is important for flow-based learning. A scalar estimate of a Wasserstein distance may certify that two empirical distributions are close, but it does not tell the source party which target atom should be paired with a source atom, nor does it provide the velocity target y − x used by flow-matching-style objectives. Coupling output is therefore a stronger and more operational task Preprint.
than distance estimation. The paper studies this task directly: under a bit budget, which representation should be communicated—target counts, support prototypes, an explicit plan, or a transport field? Let ∥ · ∥2 denote the Euclidean norm, write δz for the Dirac mass at a point z, and let Π(µ, ν) denote the set of couplings of two probability measures µ and ν. One party observes the source sample set X = {x1 , . . . , xn } ⊂ [0, 1]d , while the other observes set Y = {y1 , . . . , yn } ⊂ Pn the target sampleP n [0, 1]d . These define the empirical measures µ = n1 i=1 δxi and ν = n1 i=1 δyi . The distributed task is to communicate enough information to output a coupling between µ and ν. The quality measure is the Wasserstein-1 transport cost Z W1 (µ, ν) = inf ∥x − y∥2 dπ(x, y), π∈Π(µ,ν)
and the communication measure is the number of transmitted bits. The output model matters because different ways of exposing a coupling reveal different amounts of information. A protocol that samples matched pairs, a protocol that reveals an explicit public transport plan, a protocol whose coupling cost is evaluable by one party, and a sampler equipped with a scalar value certificate are distinct communication tasks. This paper separates these notions and asks which transport representation is sufficient for each task. The contribution of this paper is to answer this question through a direct coupling-output formulation for empirical OT. We show that a communicated transport field, combined with sparse residual target-cell counts, can be compiled into an exact-marginal distributed sampler with a scalar value certificate. We also show that stronger certificate-bearing outputs, namely cost-evaluable, costcertified, and value-certified protocols, remain communication-hard even on smooth map-induced instances. Thus, field communication is not only a modeling choice inherited from flow methods; it is also a natural information-theoretic object for making distributed coupling output possible. We instantiate this principle through compiler-style upper bounds, smooth diffeomorphic lower-bound families, and empirical comparisons between field-based summaries, target-count summaries, and support-prototype summaries under explicit bit budgets. 1.2
Research Questions
The paper formalizes four research questions. RQ1 asks for the right two-party formulation for outputting an approximate coupling, as opposed to estimating an OT cost. RQ2 asks which communicated object gives a constructive upper bound in smooth map-induced regimes, among target counts, support prototypes, and transport fields. RQ3 asks whether smooth map-induced OT instances are communication-hard. RQ4 asks whether field-based summaries are empirically useful under explicit bit budgets on synthetic and natural benchmarks. 1.3
Contributions and Evidence
Definitions 1–2 settle the formulation question RQ1 by distinguishing three output strengths: distributed samplers, cost-evaluable couplings, and scalar value-certified samplers. Theorem 1 is the field-code compiler: any communicated field code with error η is completed into an exact-marginal sampler equipped with a scalar value certificate of additive error 2∆, where ∆ is the diameter of a public target partition. The field error η does not enter the certificate bound; it is the quantity relevant to residual communication, but does not by itself bound the residual lists without a margin or sparsity assumption. Smooth constructive instantiations of the compiler are Theorem 2, an adaptive local-affine code controlled by local curvature with explicit ε-rate in Corollary 1, and Theorem 3, a dimension-explicit tensor-product spline code with explicit value-certified field-bit rate in Corollary 2; together these answer RQ2. Certificate-bearing communication lower bounds for RQ3 come from Theorem 4, a bounded-support separated Gap-Hamming embedding, and Theorem 5, a smooth cell-packing diffeomorphism embedding with exponent 2d/(d + 4) that binds against cost-evaluable, cost-certified, and value-certified output alike. Proposition 3 supplies model separation by exhibiting zero-communication distributed samplers for the same Gap-Hamming gadgets, scoping the lower bounds to the certificate-bearing models. The empirical study in Section 5 addresses RQ4 by evaluating support summaries, grids, affine fields, local-affine fields, and spline fields under matched bit accounting on smooth synthetic tasks, 5D scale-ups, MNIST to USPS in shared PCA-5, and DOTmark ClassicImages. 2
The central message is theorem-first: in smooth empirical OT, a low-complexity transport field is the communication object that makes coupling output possible. Residual target-mass mismatch is handled afterward by sparse cell corrections, and the experiments study that design principle under explicit bit budgets.
2
Related Work
This work connects communication complexity, optimal transport, and flow-based generative modeling. We use Yao’s two-party communication framework (Yao, 1979), with lower bounds based on hard predicates such as Gap-Hamming (Sherstov, 2012) and Set-Disjointness (Håstad and Wigderson, 2007); distributed approximate matching lower bounds (Huang et al., 2020) are conceptually related because empirical OT on separated supports behaves like weighted bipartite matching. Prior EMD sketching and streaming work studies compression of transportation distances (Andoni et al., 2008, 2009; Chen et al., 2022; Andoni et al., 2016), while Sinkhorn, sliced/projection-robust OT, decentralized barycenters, and federated transport focus on scalable computation or networked optimization (Cuturi, 2013; Altschuler et al., 2017; Peyré and Cuturi, 2019; Lin et al., 2021; Nadjahi et al., 2021; Nguyen et al., 2024; Staib et al., 2017; Dvurechenskii et al., 2018; Uribe et al., 2018; CisnerosVelarde and Bullo, 2023; Krishnan and Martínez, 2025; Kulcsar et al., 2025). In parallel, Flow Matching, Rectified Flow, OT-CFM, simulation-free bridge methods, and structured transport-map models learn maps or velocity fields related to couplings (Lipman et al., 2023; Liu et al., 2023; Tong et al., 2024a,b; Guo and Schwing, 2025; Cuturi et al., 2023; Sidheekh et al., 2022). Unlike these lines of work, we study the communication needed to output a coupling with exact empirical marginals and certificates, and we identify transport fields plus residual counts as the central communication object.
3
Problem Formulation and Assumptions
3.1
Coupling-Output Communication
Definition 1 (Distributed coupling sampler). Let C(x, y) = ∥x − y∥2 . Let Alice denote the source party holding X = {x1 , . . . , xn }, and let Bob denote the target party holding Y = {y1 , . . . , yn }. A distributed coupling sampler is a public-coin two-party protocol in which Alice and Bob communicate a transcript T and then use public randomness together with their local inputs to sample a pair (xi , yj ). The protocol is valid if the induced law ΠT on P X × Y has marginals exactly µ and ν almost surely. Its expected cost is Eprot ⟨ΠT , C⟩ = Eprot i,j ΠT (i, j)∥xi − yj ∥2 . An additive-ε expected-cost protocol satisfies Eprot ⟨ΠT , C⟩ ≤ W1 (µ, ν) + ε on every instance in the class. The transcript length is the communication cost. This sampler model is stronger than distance sketching because it must instantiate matched mass. It is weaker than a public explicit plan, because Bob may use his private target samples during the final sampling step. Definition 2 (Cost-evaluable, cost-certified, and value-certified coupling output). Three output strengths beyond Definition 1 are distinguished. In all three, success probability is denoted p ∈ (0, 1]. A cost-evaluable coupling protocol outputs a representation of the induced coupling distribution ΠT , not merely one sampled pair, such that Alice can compute the expected transportation cost ⟨ΠT , C⟩ from her final view: her input, public randomness, transcript, and the output representation. Any representation needed for this computation is either computable from that final view or must be communicated and counted in the protocol cost. An additive-ε cost-evaluable protocol satisfies Pr[ΠT is a valid coupling and ⟨ΠT , C⟩ ≤ W1 (µ, ν) + ε] ≥ p. Since validity implies ⟨ΠT , C⟩ ≥ W1 (µ, ν), the evaluable cost is itself an additive-ε estimator on the success event. c that, on the A protocol is cost-certified if it is cost-evaluable and additionally outputs a scalar W c ≤ W1 (µ, ν) + ε. success event, satisfies W1 (µ, ν) ≤ W A protocol is a scalar value-certified sampler if it is a valid distributed sampler in the sense of Definition 1 and additionally produces a scalar U available to Alice from her final view, namely input, public randomness, transcript, and any additional output representation, such that, with probability at least p, W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + ε. Any communication required so that U becomes computable from Alice’s final view is part of the protocol cost. A value-certified sampler 3
need not be cost-evaluable: Alice may not be able to compute the realized expected sampler cost ⟨ΠT , C⟩ from her final view, but she does have a scalar W1 upper bound. The three notions are distinct. Cost-evaluable, cost-certified, and value-certified protocols all imply additive-ε estimation of W1 (µ, ν). A bare distributed sampler does not: a public sampler may generate the correct pair structure without revealing the numerical transport cost. 3.2
Standing Assumptions
The theory uses at most five assumptions. Assumptions 1–3 define the common coupling-output model. Assumptions 4–5 are invoked only by the smooth constructive instantiations. Assumption 1 (Bounded Euclidean empirical OT). The samples lieP in [0, 1]d , the transport Pncost is n 1 C(x, y) = ∥x−y∥2 , and the empirical measures are uniform: µ = n i=1 δxi and ν = n1 i=1 δyi . Assumption 2 (Public communication model). The parties use public randomness and shared public quantizers. A sampler is valid only if the returned randomized coupling has marginals exactly µ and ν almost surely. Lower bounds specify when the stronger cost-evaluable, cost-certified, or scalar value-certified output model is required. Assumption 3 (Public target partition). For the constructive protocols, both parties know a target partition {Cj }M j=1 with representatives zj ∈ Cj and Euclidean cell diameter at most ∆. Assumption 4 (Smooth empirical Monge realization). There is an optimal empirical permutation σ and a map T : [0, 1]d → [0, 1]d such that T (xi ) = yσ(i) for all i ∈ [n]. Assumption 5 (One field-complexity condition). In each constructive theorem, a preliminary fieldcode stage produces a field satisfying exactly one of the following representation conditions: 1. Field approximation: a communicated field Fθ satisfies maxi ∥Fθ (xi ) − T (xi )∥2 ≤ η. 2. Adaptive local-affine smoothness: T is C 1,1 and each active dyadic leaf Q satisfies the Lipschitz-gradient condition Lip(DT ; Q) diam(Q)2 ≤ 8τ , where Lip(DT ; Q) is the operator-norm Lipschitz constant of DT on Q. 3. Tensor-product spline smoothness: every component Tk is C 2 and ∥∂jj Tk ∥∞ ≤ H for all j, k ∈ [d]. These assumptions are appropriate for the paper’s object of study for three reasons. First, normalizing flows and continuous transport models represent maps or velocity fields, so Assumptions 4–5 are the natural communication analogues of a flow parameterization. Second, public quantization in Assumptions 2–3 is the standard shared-coordinate structure needed for bit-counted protocols with exact empirical marginals. Third, Theorem 5 proves certified-output hardness inside a uniformly smooth diffeomorphic subclass, establishing that smoothness is also where the lower bounds bind.
4
Theoretical Results
This section gives the main theoretical results of the paper. We first present a shared-grid baseline that communicates target cell counts, then introduce the field-code compiler that turns a communicated transport field and sparse residual counts into an exact-marginal value-certified sampler. We instantiate the compiler with adaptive local-affine and tensor-product spline field codes, and then prove certified communication lower bounds together with a sampler/certificate separation. Full proofs of all theoretical results are provided in Appendix A; the main text states the results and highlights their communication consequences. 4.1
A Grid Coupling Baseline
Proposition 1 (Shared-grid coupling). Let {Cj }M j=1 have diameter at most ∆. Bob sends the counts PM m mj = #{i : yi ∈ Cj } using M ⌈log2 (n + 1)⌉ bits. Alice forms ν̃ = j=1 nj δzj . An optimal coupling from µ to ν̃, followed by Bob’s within-cell lift from zj to the actual points in Cj , gives a valid randomized coupling between µ and ν with expected cost at most W1 (µ, ν) + 2∆. The main upper bound improves this by using a communicated transport field before residual counts are sent. 4
4.2
Field-Preconditioned Residual Coupling
Theorem 1 (Field-code-to-sampler-and-certificate compiler). Let µ, ν be empirical measures in [0, 1]d . Fix a public target partition of diameter at most ∆. Suppose a preliminary communication stage of Bfield bits leaves Alice able to evaluate a public-family field Fθ satisfying, for some optimal empirical permutation σ, ∥Fθ (xi )−yσ(i) ∥2 ≤ η for all i ∈ [n]. Then there is a public-coin two-round compiler that outputs a scalar value-certified sampler in the sense of Definition 2: a distributed sampler with exact marginals µ, ν almost surely and Eprot ⟨Π, C⟩ ≤ W1 (µ, ν) + 2∆, together with a deterministic scalar certificate U = W1 (µ, ν̃) + ∆ satisfying W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆, where ν̃ =
PM
j=1 (mj /n)δzj is the collapsed measure built from the exact reconstructed cell counts.
The certificate accuracy and the realized sampler-cost bound depend only on the target-partition diameter ∆, not on the field-approximation error η. The role of η is communication: it is the quantity relevant to residual-list size, but it does not deterministically bound ŝ and s on its own. Bounding the residual lists from η requires a cell-margin condition, Proposition 2, distributional regularity, or an explicit residual-sparsity assumption. With a trivial field, the protocol degrades to the grid baseline of Proposition 1. The compiler does not produce a cost-evaluable representation: Alice’s final view determines the collapsed plan and the cell counts but not the within-cell target coordinates Bob will sample, so the realized expected sampler cost ⟨Π, C⟩ is generally not computable from her view. The scalar U is what is certified, not the realized cost. If ŝ is the number of occupied predicted cells and s is the number of nonzero residual cells, the compiler adds ŝ ⌈log2 M ⌉ + ⌈log2 (n + 1)⌉ + s ⌈log2 M ⌉ + ⌈log2 (2n + 1)⌉ bits beyond the preliminary field-code stage, plus O(log M + log n) self-delimiting header bits if one insists on a prefix-free encoding of the two sparse lists. The certificate adds no communication beyond ordinary numerical precision for the collapsed OT solve. The proof is in Appendix A.1. The preliminary field-code stage may depend on both parties’ inputs, and all of its bits are charged to Bfield . Any protocol, model, or oracle that produces a field code is completed into an exact-marginal distributed sampler with a scalar value certificate by the residual stage above; the compiler does not yield a cost-evaluable representation in the strict sense of Definition 2. Proposition 2 (Cell-margin implies vanishing Bob residuals). Suppose every matched true target lies in the interior of its public cell at distance more than η from the cell boundary: dist(yσ(i) , ∂Cc(i) ) > η for all i ∈ [n], where c(i) is the index of the cell containing yσ(i) . Then the predicted cell of ŷi = Π[0,1]d (Fθ (xi )) equals c(i) for every i, hence m̂j = mj for all j and Bob’s residual vector is zero. In particular, the residual sparsity parameter s in Theorem 1 satisfies s = 0. The proposition forces s = 0 but does not bound Alice’s predicted-count support ŝ, which equals the number of occupied predicted cells and can still be as large as min(n, M ). Therefore the displayed compiler communication is small only if ŝ is also small, or if the margin condition is itself a promised subclass: on a promised margin subclass satisfying the bound above, one may run a specialized margin-certified protocol that omits Bob’s residual correction and uses m̂ = m directly. Without a verifiable margin promise, the residual exchange in Theorem 1 should be retained, and the predicted-count list still costs ŝ ⌈log2 M ⌉ + ⌈log2 (n + 1)⌉ bits. Without the margin condition, η alone does not bound either residual list: a target yk within distance ≤ η of a cell boundary can fall on the opposite side of the boundary from ŷk , producing a residual entry. Field accuracy controls residual communication only through margin, distributional regularity, or explicit sparsity assumptions. 4.3
Adaptive Local-Affine Transport Codes
Theorem 2 (Adaptive local-affine protocol). Assume Assumptions 1–4 and the adaptive local-affine branch of Assumption 5. Let P be a public dyadic partition with leaves L(P), and let AQ (x) = 5
T (cQ ) + DT (cQ )(x − cQ ), x ∈ Q, be the Taylor chart at the center cQ of leaf Q. Suppose every leaf satisfies the Lipschitz-gradient condition Lip(DT ; Q) diam(Q)2 ≤ 8τ , and a preliminary field-code stage communicates a quantized piecewise-affine field FeP with supx ∥FeP (x) − FP (x)∥2 ≤ λ, where FP (x) = AQ (x) for x ∈ Q. Then the field-preconditioned residual protocol of Theorem 1 outputs a value-certified sampler with exact marginals and Eprot ⟨ΠP , C⟩ ≤ W1 (µ, ν) + 2∆,
W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆.
The field accuracy parameters τ and λ are the empirical-field-error scale η = τ + λ relevant to the residual stage of Theorem 1, but they do not by themselves bound ŝ and s; a margin or sparsity condition is needed for that. They do not enter the value-certificate bound. If each scalar affine coefficient is sent using b bits, one valid field budget is X Bfield (P, b) ≤ d ℓ(Q) + |L(P)|d(d + 1)b, Q∈L(P)
where ℓ(Q) is the dyadic depth of Q. See full proof in Appendix A.2. Corollary 1 (Local-affine field-bit rate). Let Kτ (T ) be the minimum number of dyadic leaves needed so that every leaf satisfies the Lipschitz-gradient condition in Theorem 2, and let Lτ be the maximum depth of such a tree. Assume public coefficient ranges for the affine charts; if these ranges are not constant-size, the range, sign, and exponent bits are included in b. Choose ∆ ≤ ε/2 so that the value certificate satisfies W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + ε by Theorem 2, and choose τ = Θ(ε), λ = Θ(ε) with b = O(log(1/ε)) bits per scalar coefficient to keep the empirical field error η = τ + λ at scale ε. The local-affine field code then has field-description budget O(Kτ (T )dLτ + Kτ (T )d(d + 1) log(1/ε)) e τ (T )d(d + 1) + Kτ (T )dLτ ), plus the sparse residual lists from Theorem 1. If T is bits, or O(K 1,1 C with Lip(DT ) ≤ H globally and a uniform dyadic mesh is used, then Kτ (T ) ≤ O (H/ε)d/2 , recovering the same worst-case exponent as tensor-product splines while allowing smaller budgets when curvature is spatially localized. The value-certificate accuracy is controlled by ∆; the choice of τ, λ at the same scale serves the residual-sparsity objective rather than the certificate bound. Full proof is in Appendix A.2.1 4.4
Tensor-Product Spline Transport Codes
Theorem 3 (Tensor-product spline protocol). Assume Assumptions 1–4 and the tensor-product spline branch of Assumption 5. Let Gh be a public tensor grid with spacing h = 1/m, and let Seh be the multilinear spline reconstructed from quantized nodal values satisfying ∥Te(z) − T (z)∥∞ ≤ ρ for all z ∈ Gh . If needed, clip these nodal values coordinatewise to [0, 1]d before interpolation; this cannot increase the nodal error because T (z) ∈ [0, 1]d . Then the empirical field-error parameter is η = sup ∥Seh (x) − T (x)∥2 ≤ x
√ d3/2 Hh2 + d ρ, 8
and the field-preconditioned residual protocol of Theorem 1 outputs a value-certified sampler with exact marginals and Eprot ⟨Πh , C⟩ ≤ W1 (µ, ν) + 2∆,
W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆.
The spline interpolation bound and the nodal quantization error set the empirical-field-error scale η relevant to the residual stage of Theorem 1; bounding ŝ and s from this η requires a margin or sparsity assumption. They do not enter the value-certificate bound. If every scalar control value uses b bits, then the spline field uses Bfield (h, b) = d(m + 1)d b bits. The theorem gives the explicit low-dimensional field-bit law e −d/2 ) Bfield,spline (ε) = O(ε when the interpolation term dominates and quantization is chosen at the same scale. The full sampler and scalar value certificate add the residual lists from Theorem 1, so the total communication is Btotal (ε) ≤ d(m+1)d b+ŝ ⌈log2 M ⌉+⌈log2 (n+1)⌉ +s ⌈log2 M ⌉+⌈log2 (2n+1)⌉ +O(log M +log n). 6
e −d/2 ) only under an explicit residual-sparsity condition s + ŝ = O(ε e −d/2 ). The total rate is O(ε −d Without such sparsity, a uniform target partition with ∆ = O(ε) requires M = Ω(ε ), and the e worst-case residual term contributes O(min(n, ε−d )). See full proof in Appendix A.3 Corollary 2 (Value-certified smooth field-code upper rates). The local-affine and spline instantiations are scalar value-certified samplers in the sense of Definition 2, where Alice outputs the scalar certificate U from Theorem 1 in addition to the sampler. Choose ∆ ≤ ε/2 so that W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + ε by Theorem 1, regardless of the spline interpolation parameters h and ρ. Choosing h = Θ((ε/H)1/2 ) √ 3/2 and ρ = Θ(ε) keeps the empirical field error η = d 8 Hh2 + dρ at scale ε, which is the residuale −d/2 ). The total rate sparsity-relevant scale; this gives a field-bit budget Bfield,spline (ε) = O(ε −d/2 e e −d/2 ); without such is O(ε ) only under the explicit residual-sparsity condition s + ŝ = O(ε −d sparsity, a uniform target partition forces M = Ω(ε ) and the worst-case residual term contributes e O(min(n, ε−d )). Full proof is in Appendix A.3.1. 4.5
Certified Lower Bounds and Sampler Separation
The lower bounds use the standard randomized public-coin communication model. They apply to all three certificate-bearing output models in Definition 2: cost-evaluable, cost-certified, and scalar √ value-certified. The hard√predicate is Gap-Hamming: under the promise dH (u, v) ≤ m/2 − β m or dH (u, v) ≥ m/2 + β m, distinguishing the two cases requires Ω(m) communication Sherstov (2012). Lemma 1 (Certificate output implies cost estimation on the success event). If an additive-ε costevaluable, cost-certified, or scalar value-certified protocol succeeds with probability at least 2/3 in the sense of Definition 2, then with probability at least 2/3 Alice’s final view determines a c satisfying W1 (µ, ν) ≤ W c gives a randomized c ≤ W1 (µ, ν) + ε. Hence thresholding W value W communication protocol for any embedded predicate that depends on W1 (µ, ν). Full proof is in Appendix A.4. √ Theorem 4 (Bounded separated-support certified lower bound). Fix h ∈ (0, 3) and let L = 3m + 1. m 2 For u, v ∈ {0, 1} , define empirical measures in [0, 1] by m
µu =
m
1 X δ(3i/L,hui /L) , m i=1
νv =
1 X δ((3i+1)/L,hvi /L) . m i=1
Then
p 1 dH (u, v) 2 W1 (µu , νv ) = 1 + ( 1 + h − 1) . L m Consequently, additive-ε cost-evaluable, cost-certified, or scalar value-certified coupling output √ 2 √ −1 . See on this bounded-support family requires Ω(m) communication whenever ε < β 1+h L m Appendix A.5 for full proof. Because L = Θ(m), Theorem 4 gives the elementary certified rate Ω(ε−2/3 ). The next theorem recovers the same exponent at d = 2 while adding a smooth diffeomorphic realization, and extends the exponent to all fixed dimensions. Theorem 5 (Smooth cell-packing lower bound). Fix d ≥ 1 and an integer q ≥ 2. Let ϕ(t) = Qd t3 (1 − t)3 1[0,1] (t), Ψ(ξ) = r=1 ϕ(ξr ), and set κd = Ψ(1/2, . . . , 1/2) = 64−d . Let B1,d = supξ ∥∇Ψ(ξ)∥2 and B2,d = supξ ∥D2 Ψ(ξ)∥op , and choose 0 < α ≤ min{1, (4B1,d )−1 }. For d m = q d , encode u ∈ {0, 1}[q] by X Fu (x) = x + αq −2 uc Ψ(qx − c + 1)e1 . c∈[q]d
At cell centers zc =
c− 21 1 q
, define
µu =
1 X δFu (zc ) , m d
νv =
c∈[q]
1 X δFv (zc ) . m d c∈[q]
7
Then every Fu is a global C 2 diffeomorphism, the optimal coupling is induced by Tu,v = Fv ◦ Fu−1 , the map satisfies ∥D2 Tu,v ∥∞ := sup ∥D2 Tu,v (x)∥op ≤ Hd,α := x
128 αB2,d , 27
and
ακd dH (u, v). m1+2/d Therefore additive-ε cost-evaluable, cost-certified, or scalar value-certified coupling output on this βακd smooth d-dimensional family requires Ω(m) communication whenever ε < m1/2+2/d , equivalently −2d/(d+4) d Ω(ε ) communication along the infinite sequence m = q . See proof in Appendix A.6. W1 (µu , νv ) =
Proposition 3 (Sampler separation for the lower-bound gadgets). The lower-bound families in Theorems 4 and 5 do not lower-bound uncoded distributed samplers. Each admits a zero-communication exact distributed sampler. Proof is in Appendix A.7. Proposition 3 is the reason the paper separates sampler upper bounds from certified lower bounds. Cost-estimation hardness alone is not a sampler lower bound. 4.6
Tightness
The upper and lower exponents should not be read as a matched rate theorem. The spline upper bound counts field-description bits, while the lower bound is a total communication lower bound for certificate-bearing outputs. The gap reflects basis choice and residual sparsity. Appendix B discusses this distinction and states an open sampler-hardness problem.
5
Empirical Study
The experiments evaluate the communication objects predicted by the theory under matched bit accounting. Each protocol summarizes the target distribution under a bit budget, and we compare the resulting certified Wasserstein-1 cost with an exact empirical-OT reference over repeated seeds. The reported metric is mean absolute relative error in the certified cost; the bit budget includes both the communicated summary and the residual cell counts from Theorem 1. We compare five protocol families. gridM sends public grid cell counts, matching Proposition 1; (b) kmeansK sends weighted target prototypes; and affine_flow, local_affineK , and splinem communicate transport fields, corresponding respectively to a global affine map, the adaptive localaffine code of Theorem 2, and the tensor-product spline code of Theorem 3. Fields are fit to paired targets on synthetic and semi-synthetic tasks, and to exact empirical-OT targets on MNIST–USPS and DOTmark. Additional details and full results are in Appendix C.
Figure 1: Mean absolute relative error of the certified transport cost as a function of communicated bits on sinusoidal_warp and swirl_warp (d = 2, n = 128) and on digits_pca5_warp (d = 5, n = 256). Error bars are sample standard deviations over 5 seeds. The lowest plotted bit budget per family is its minimum valid encoding cost in the corresponding dimension. 8
The benchmarks cover smooth 2D maps, nonlinear 2D maps, 5D scale-ups, and natural unpaired transport. Figure 1 shows the main pattern: on nonlinear 2D tasks, spline fields dominate the frontier by more than an order of magnitude over grid and k-means summaries. The local-affine sweep improves as coefficient precision b increases until the fixed dyadic curvature error dominates, matching the η = τ + λ structure of Theorem 2. Refining the spline grid gives a direct multiplicative improvement, consistent with the h2 scaling of Theorem 3. Table 1 gives the high-dimensional comparison. Spline fields give the smallest error in every 5D setting tested; for n = 256, spline_4 reaches 0.001672 ± 0.000341 on gaussian_nonlinear_d5 and 0.000287 ± 0.000085 on digits_pca5_warp, while grid and prototype summaries are one to three orders of magnitude worse. At n = 1024, field methods remain clearly separated from support summaries. Table 1: Mean absolute relative error on the 5D scale-up benchmarks. Dataset
n
spline_4
spline_3
local affine_2
kmeans_64
grid_3
gaussian_nonlinear_d5
256
1.7e−3 ±3.4e−4
1.47e−2 ±1.64e−3
8.15e−2 ±1.24e−2
3.56e−1 ±1.89e−2
1.19 ±1.36e−2
digits_pca5_warp
256
2.9e−4 ±8.5e−5
1.51e−2 ±3.97e−3
3.99e−2 ±8.50e−3
1.18 ±5.23e−2
3.25 ±1.09e−1
gaussian_nonlinear_d5
1024
4.9e−3 ±3.2e−4
3.06e−2 ±1.35e−3
5.76e−2 ±1.72e−3
5.23e−1 ±3.85e−3
1.17 ±1.69e−2
digits_pca5_warp
1024
1.7e−3 ±4.6e−5
3.59e−2 ±1.47e−3
2.12e−2 ±2.83e−3
1.63 ±1.62e−2
3.25 ±2.11e−2
On natural unpaired benchmarks, spline fields also attain the best absolute accuracy on MNIST– USPS and remain competitive on DOTmark; the smaller DOTmark gap reflects that raster-image transport is not generated by a smooth diffeomorphism. Full natural-benchmark numbers and the cross-dataset plot are in Appendix C.2. Overall, the results support the field-first view: when transport has smooth or approximately smooth geometry, communicating a transport field is more bit-efficient than communicating only target counts or support prototypes.
6
Discussion & Conclusion
This paper studies empirical OT as a coupling-output communication problem rather than a distanceestimation problem. The main positive result is a field-code compiler: once a low-complexity transport field has been communicated, sparse residual target-cell counts restore exact marginals and yield a scalar value certificate W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆. Adaptive local-affine and tensor-product spline codes instantiate this principle on smooth map-induced instances. The lower bounds show that certificate-bearing outputs remain communication-hard even in smooth diffeomorphic families. At the same time, the sampler separation shows that cost-estimation hardness is not automatically sampler hardness: the optimal pair structure may be publicly sampleable while the cost remains hidden. This separates distributed sampler output from cost-evaluable, cost-certified, and value-certified output. The empirical study supports the same field-first view. Under matched bit budgets, field summaries outperform target-count and support-prototype summaries on smooth synthetic tasks and remain competitive on natural benchmarks. The main limitation is that the upper bounds are conditional on the availability of a low-complexity field code and on residual sparsity or cell-margin structure when one wants the total communication to remain small. The compiler guarantees exact marginals and a scalar value certificate, but it does not by itself make the realized sampler cost evaluable from one party’s view. The experiments also use paired or empirical-OT supervision to fit field summaries, so jointly learning such fields under communication constraints remains an important systems-level extension. 9
References Altschuler, J., Weed, J., and Rigollet, P. (2017). Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 1961–1971, Red Hook, NY, USA. Curran Associates Inc. Andoni, A., Ba, K. D., Indyk, P., and Woodruff, D. (2009). Efficient sketches for earth-mover distance, with applications. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’09, page 324–330, USA. IEEE Computer Society. Andoni, A., Indyk, P., and Krauthgamer, R. (2008). Earth mover distance over high-dimensional spaces. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08, page 343–352, USA. Society for Industrial and Applied Mathematics. Andoni, A., Naor, A., and Neiman, O. (2016). Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. In Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., and Sangiorgi, D., editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 83:1–83:14, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. Chen, X., Jayaram, R., Levi, A., and Waingarten, E. (2022). New streaming algorithms for high dimensional emd and mst. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 222–233, New York, NY, USA. Association for Computing Machinery. Cisneros-Velarde, P. and Bullo, F. (2023). Distributed wasserstein barycenters via displacement interpolation. IEEE Transactions on Control of Network Systems, 10(2):785–795. Cuturi, M. (2013). Sinkhorn distances: lightspeed computation of optimal transport. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS’13, page 2292–2300, Red Hook, NY, USA. Curran Associates Inc. Cuturi, M., Klein, M., and Ablin, P. (2023). Monge, Bregman and occam: Interpretable optimal transport in high-dimensions with feature-sparse maps. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J., editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 6671–6682. PMLR. Dvurechenskii, P., Dvinskikh, D., Gasnikov, A., Uribe, C., and Nedich, A. (2018). Decentralize and randomize: Faster algorithm for wasserstein barycenters. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc. Guo, P. and Schwing, A. G. (2025). Variational rectified flow matching. In Proceedings of the 42nd International Conference on Machine Learning, ICML’25. JMLR.org. Håstad, J. and Wigderson, A. (2007). The randomized communication complexity of set disjointness. Theory of Computing, 3(11):211–219. Huang, Z., Radunovic, B., Vojnovic, M., and Zhang, Q. (2020). Communication complexity of approximate maximum matching in the message-passing model. Distrib. Comput., 33(6):515–531. Hull, J. (1994). A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5):550–554. Krishnan, V. and Martínez, S. (2025). Distributed online optimization for multi-agent optimal transport. Automatica, 171(C). Kulcsar, J., Kungurtsev, V., Korpas, G., Giaconi, G., and Shoosmith, W. (2025). Federated sinkhorn. arXiv preprint arXiv:2502.07021. Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324. 10
Lin, T., Zheng, Z., Chen, E., Cuturi, M., and Jordan, M. (2021). On projection robust optimal transport: Sample complexity and model misspecification. In Banerjee, A. and Fukumizu, K., editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 262–270. PMLR. Lipman, Y., Chen, R. T. Q., Ben-Hamu, H., Nickel, M., and Le, M. (2023). Flow matching for generative modeling. In The Eleventh International Conference on Learning Representations. Liu, X., Gong, C., and qiang liu (2023). Flow straight and fast: Learning to generate and transfer data with rectified flow. In The Eleventh International Conference on Learning Representations. Nadjahi, K., Durmus, A., Jacob, P. E., Badeau, R., and Simsekli, U. (2021). Fast approximation of the sliced-wasserstein distance using concentration of random projections. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 12411–12424. Curran Associates, Inc. Nguyen, K., Zhang, S., Le, T., and Ho, N. (2024). Sliced wasserstein with random-path projecting directions. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org. Peyré, G. and Cuturi, M. (2019). Computational optimal transport. Found. Trends Mach. Learn., 11(5–6):355–607. Schrieber, J., Schuhmacher, D., and Gottschlich, C. (2017). Dotmark – a benchmark for discrete optimal transport. IEEE Access, 5:271–282. Sherstov, A. A. (2012). The communication complexity of gap hamming distance. Theory of Computing, 8(8):197–208. Sidheekh, S., Dock, C. B., Jain, T., Balan, R., and Singh, M. K. (2022). VQ-flows: Vector quantized local normalizing flows. In The 38th Conference on Uncertainty in Artificial Intelligence. Staib, M., Claici, S., Solomon, J., and Jegelka, S. (2017). Parallel streaming wasserstein barycenters. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 2644–2655, Red Hook, NY, USA. Curran Associates Inc. Tong, A., FATRAS, K., Malkin, N., Huguet, G., Zhang, Y., Rector-Brooks, J., Wolf, G., and Bengio, Y. (2024a). Improving and generalizing flow-based generative models with minibatch optimal transport. Transactions on Machine Learning Research. Expert Certification. Tong, A. Y., Malkin, N., Fatras, K., Atanackovic, L., Zhang, Y., Huguet, G., Wolf, G., and Bengio, Y. (2024b). Simulation-free Schrödinger bridges via score and flow matching. In Dasgupta, S., Mandt, S., and Li, Y., editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 1279–1287. PMLR. Uribe, C. A., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., and Nedić, A. (2018). Distributed computation of wasserstein barycenters over networks. In 2018 IEEE Conference on Decision and Control (CDC), pages 6544–6549. Yao, A. C.-C. (1979). Some complexity questions related to distributive computing(preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC ’79, page 209–213, New York, NY, USA. Association for Computing Machinery.
11
A
Full Proofs
A.1
Proof of Theorem 1
Pn Let ŷi = Π[0,1]d (Fθ (xi )) and ν̂ = n1 i=1 δŷi . Because yσ(i) ∈ [0, 1]d and Euclidean projection onto the cube is nonexpansive, ∥ŷi − yσ(i) ∥2 ≤ ∥Fθ (xi ) − yσ(i) ∥2 ≤ η for all i. Let m̂j be the number of predicted points in cell Cj , and let mj be the number of true target points in Cj . The preliminary field-code stage leaves Alice able to evaluate Fθ , so she can compute m̂j . Bob can compute mj and therefore the residual rj = mj − m̂j . The communication protocol is: 1. A preliminary field-code stage communicates θ using Bfield bits. 2. Alice sends the sparse list of occupied predicted cell counts (j, m̂j ) as an index-sorted sequence together with a self-delimiting header for its length. 3. Bob sends the sparse list of nonzero residuals (j, rj ) as an index-sorted sequence together with a self-delimiting header for its length. PM m 4. Alice reconstructs all true target cell counts mj and forms ν̃ = j=1 nj δzj . between µ and ν̃. 5. Alice computes an optimal collapsed plan γ ∈ Rn×M + P 6. Alice outputs the certificate U = i,j γij ∥xi − zj ∥2 + ∆ = W1 (µ, ν̃) + ∆. 7. The distributed sampler uses public randomness to draw a cell J with probability mJ /n. Conditional on J = j, Alice samples I with probability P[I = i | J = j] = γij /(mj /n) when mj > 0, and Bob samples uniformly from his target atoms in Cj using a public ordering. The residual bit count follows from the encoding: each occupied predicted count costs one cell index and one count; each residual costs one cell index and one signed integer in {−n, . . . , n}. The length headers contribute only O(log M + log n) extra bits, so the total communication is the displayed sparse-pair cost plus this low-order self-delimiting overhead and Bfield . The sampler has exact marginals. For the source marginal, X mj γij X 1 P[I = i] = = γij = . n m /n n j j:m >0 j j
m
For a target atom yk in cell Cj , P[Y = yk ] = nj · m1j = n1 . Bob never needs to know γ; only Alice uses it to sample the source conditional on the public cell. It remains to prove the cost. Map each true target yk to the representative zc(k) of its cell. Since cell diameters are at most ∆, ∥yk − zc(k) ∥2 ≤ ∆, so this gives a coupling between ν and ν̃ of cost at most ∆. Hence W1 (ν, ν̃) ≤ ∆, and by thePtriangle inequality for W1 , W1 (µ, ν̃) ≤ W1 (µ, ν) + ∆. Since γ is optimal for µ to ν̃, W1 (µ, ν̃) = i,j γij ∥xi − zj ∥2 . Now bound the realized sampler cost. By the construction in step 7, the sampled pair (I, Y ) satisfies Y ∈ CJ chosen uniformly among Bob’s targets in CJ , so X X 1 X E⟨Π, C⟩ = γij ∥xi − yk ∥2 . mj j:m >0 i k:yk ∈Cj
j
Triangle inequality and ∥yk − zj ∥2 ≤ ∆ for yk ∈ Cj give 1 X ∥xi − yk ∥2 ≤ ∥xi − zj ∥2 + ∆, mj k:yk ∈Cj
hence E⟨Π, C⟩ ≤
X
γij (∥xi − zj ∥2 + ∆) = W1 (µ, ν̃) + ∆.
i,j
Combining with the previous display, E⟨Π, C⟩ ≤ W1 (µ, ν̃) + ∆ ≤ W1 (µ, ν) + 2∆. 12
The certificate is U = W1 (µ, ν̃) + ∆. The lower bound U ≥ W1 (µ, ν) follows from W1 (µ, ν) ≤ W1 (µ, ν̃) + W1 (ν̃, ν) ≤ U . The upper bound U ≤ W1 (µ, ν) + 2∆ follows from W1 (µ, ν̃) ≤ W1 (µ, ν) + ∆. The field-approximation error η does not appear in the cost or certificate bounds. It enters only through the sparsity parameters ŝ and s: a field that predicts targets close to their true cells reduces the number of occupied predicted cells and the number of nonzero residual cells, hence the residual-list cost. A.2
Proof of Theorem 2
Fix a leaf Q and x ∈ Q. For C 1,1 maps, the integral form of Taylor’s theorem gives Z 1 T (x) − T (cQ ) − DT (cQ )(x − cQ ) = DT (cQ + t(x − cQ )) − DT (cQ ) (x − cQ ) dt. 0
Using the operator-norm Lipschitz constant Lip(DT ; Q) and ∥x − cQ ∥2 ≤ diam(Q)/2, Z 1 1 1 ∥FP (x)−T (x)∥2 ≤ Lip(DT ; Q)t∥x−cQ ∥22 dt = Lip(DT ; Q)∥x−cQ ∥22 ≤ Lip(DT ; Q) diam(Q)2 ≤ τ. 2 8 0 Quantization gives ∥FeP (x) − T (x)∥2 ≤ ∥FeP (x) − FP (x)∥2 + ∥FP (x) − T (x)∥2 ≤ λ + τ. Evaluating at xi and using T (xi ) = yσ(i) shows that the field-approximation parameter in Theorem 1 is η = τ + λ. Theorem 1 then yields the value-certified sampler Eprot ⟨ΠP , C⟩ ≤ W1 (µ, ν) + 2∆,
W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆,
with η = τ + λ entering only through the residual sparsity parameters ŝ and s of Theorem 1. The field budget consists of one dyadic address per leaf plus d(d + 1) scalar affine coefficients per leaf, giving X Bfield (P, b) ≤ d ℓ(Q) + |L(P)|d(d + 1)b. Q∈L(P)
A.2.1
Proof of Corollary 1
Take ∆ ≤ ε/2. By Theorem 2, the value certificate satisfies W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + ε regardless of τ and λ. By definition, a tree with Kτ (T ) leaves and maximum depth Lτ satisfies the Lipschitz-gradient condition on every leaf. Encoding the dyadic leaf addresses costs at most X d ℓ(Q) ≤ Kτ (T )dLτ Q∈L(P)
bits up to delimiter overhead. The affine charts require Kτ (T )d(d + 1) scalar coefficients. Quantizing coefficients with b = O(log(1/ε)) bits per scalar is enough to make the induced uniform field error at most λ = O(ε) when the coefficient ranges are bounded by the smoothness and support assumptions. If ranges are not known to be constant-size, the sign, exponent, and range-description bits are included in b. Thus Bfield ≤ O(Kτ (T )dLτ + Kτ (T )d(d + 1) log(1/ε)) , e bound. The chosen scale τ, λ = Θ(ε) keeps the empirical field error η = which is the stated O τ + λ = Θ(ε), which is the residual-sparsity-relevant scale rather than the certificate-relevant scale. If T is C√1,1 with Lip(DT ) ≤ H globally, a uniform grid with side length r has Euclidean diameter at most d r and satisfies the Lipschitz-gradient condition whenever Hdr2 ≤ 8τ . Taking τ = Θ(ε) gives r = Θ((ε/(Hd))1/2 ) and therefore Kτ (T ) ≤ O((Hd/ε)d/2 ). For fixed d, this is O((H/ε)d/2 ), as claimed. 13
A.3
Proof of Theorem 3
Let f be a scalar C 2 function on [0, 1]d , and let Lj be linear interpolation in coordinate j on mesh spacing h, keeping all other coordinates fixed. The multilinear interpolant is Ih f = L1 L2 · · · Ld f . The telescoping identity f − Ih f = (I − L1 )f + L1 (I − L2 )f + · · · + L1 · · · Ld−1 (I − Ld )f and the fact that each Lj is a sup-norm contraction imply ∥f − Ih f ∥∞ ≤
d X
∥(I − Lj )f ∥∞ .
j=1
For each fixed choice of the other coordinates, the one-dimensional linear interpolation remainder 2 2 gives ∥(I − Lj )f ∥∞ ≤ h8 ∥∂jj f ∥∞ . Applying this to component Tk yields ∥Tk − Sh,k ∥∞ ≤ dHh 8 . Taking the Euclidean norm over k = 1, . . . , d gives ∥T (x) − Sh (x)∥2 ≤
d3/2 Hh2 . 8
Coordinatewise clipping of the quantized nodal values to [0, 1]d cannot increase the nodal error because every exact nodal value T (z) already lies in the cube. The multilinear basis functions are nonnegative and sum to one on each cell, so the interpolated clipped nodal values remain in [0, 1]d . Therefore nodal quantization error at most ρ in ℓ∞ norm gives ∥Seh (x) − Sh (x)∥∞ ≤ ρ and hence √ ∥Seh (x) − Sh (x)∥2 ≤ d ρ. Combining the two bounds, d sup ∥Seh (x) − T (x)∥2 ≤ x
3/2
8
Hh2 +
√ d ρ.
At empirical points, this equals the field error relative to yσ(i) . The empirical field-error parameter √ 3/2 η = d 8 Hh2 + d ρ is the scale relevant to residual communication in Theorem 1, not a deterministic bound on ŝ or s. Theorem 1 nevertheless yields the value-certified sampler Eprot ⟨Πh , C⟩ ≤ W1 (µ, ν) + 2∆,
W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆,
independent of η. The interpolation and quantization terms enter only through the residual lists, and bounds on those lists require a margin or sparsity assumption beyond η. There are (m + 1)d grid nodes and each carries a d-vector with b bits per scalar, so Bfield (h, b) = d(m + 1)d b. A.3.1
Proof of Corollary 2
Theorem 1 proves more than an expected-cost sampler bound: after the residual stage, Alice can compute U = W1 (µ, ν̃) + ∆ from her source sample, the reconstructed collapsed target counts, and the public representatives. The sharpened proof of Theorem 1 shows W1 (µ, ν) ≤ U ≤ W1 (µ, ν) + 2∆, independent of the field-error parameter η. Choosing ∆ ≤ ε/2 gives the value-certified guarantee. The field-bit count d(m + 1)d b for the spline instantiation is inherited from Theorem 3, and the scale h = Θ((ε/H)1/2 ), ρ = Θ(ε) keeps the empirical field error η = Θ(ε) for the residual-sparsity analysis rather than the certificate bound. The communication is unchanged because U is computed from quantities already available to Alice after the residual compiler. A.4
Proof of Lemma 1
Condition on the success event E from Definition 2; this event has probability at least 2/3. On E the output coupling Π is valid, so ⟨Π, C⟩ ≥ W1 (µ, ν). c = ⟨Π, C⟩. By definition of cost-evaluability, Alice can compute W c In the cost-evaluable case, let W from her final view, namely input, public randomness, transcript, and output representation. On E, c ≤ W1 (µ, ν) + ε. the cost-evaluable guarantee yields W 14
c to be the protocol’s scalar W c ; the cost-certified guarantee on E is In the cost-certified case, take W c ≤ W1 (µ, ν) + ε. exactly W1 (µ, ν) ≤ W c = U , where U is the protocol’s scalar certificate; on E the In the scalar value-certified case, take W same two-sided bound holds by definition of value certification. c in In all three cases, with probability at least 2/3, Alice’s final view determines a value W [W1 (µ, ν), W1 (µ, ν) + ε]. In a communication reduction, the parties run the OT protocol on the embedded instance and Alice thresholds this final-view value to solve the hard predicate. Outside E the output may be arbitrary, but the predicate is decided correctly with probability at least 2/3. A.5
Proof of Theorem 4 √ Let αh = 1 + h2 − 1. For the ith source-target pair, 3i hui 1 3i + 1 hvi = (1 + αh 1{ui ̸= vi }) . , − , L L L L L 2 For i ̸= j, the horizontal coordinate gap between (3i/L, hui /L) and√((3j + 1)/L, hvj /L) is at least√ 2/L, so every cross-index match costs at least 2/L. Since h < 3, the largest same-index cost 1 + h2 /L is strictly less than 2/L. For any non-identity permutation, every moved row uses a√cross-index edge of cost at least 2/L, while the identity edge in that same row costs at most 1 + h2 /L < 2/L; summing over moved rows shows that any non-identity permutation is strictly more expensive than the identity. Therefore every optimal transport plan matches index i to index i. The exact cost is m 1 X1 1 1 + αh 1{ui ̸= vi } = W1 (µu , νv ) = m i=1 L L
dH (u, v) 1 + αh . m
Under the Gap-Hamming promise, the two cases are separated by 2β Lα√hm . An additive-ε costevaluable, cost-certified, or scalar value-certified coupling-output protocol with ε < β Lα√hm would, by Lemma 1, estimate the OT cost accurately enough on the success event to decide Gap-Hamming by thresholding. This contradicts the Ω(m) randomized communication lower bound for Gap-Hamming. A.6
Proof of Theorem 5
The scalar bump ϕ(t) = t3 (1 − t)3 1[0,1] (t) is C 2 on R: at t = 0 and t = 1, the polynomial and its first two derivatives vanish, so the zero extension matches through second order. Hence Ψ and the maps Fu are C 2 . Qd The supports of the translated bumps x 7→ Ψ(qx − c + 1) are the public cells Qc = r=1 [(cr − 1)/q, cr /q], and these supports are disjoint. Write gu = Fu − id. On an active cell, Dgu (x) = αq −1 uc e1 ∇Ψ(qx − c + 1)⊤ . Therefore ∥Dgu (x)∥op ≤ αq −1 B1,d ≤ αB1,d ≤ 1/4. Thus gu is globally 1/4-Lipschitz on Rd and compactly supported in [0, 1]d . For any y ∈ Rd , the map x 7→ y − gu (x) is a contraction and has a unique fixed point xy . This fixed point satisfies Fu (xy ) = y, so Fu is bijective on Rd . Since DFu is everywhere invertible and Fu is C 2 , Fu is a global C 2 diffeomorphism of Rd . Outside [0, 1]d , all bumps vanish and Fu is the identity. The boundary check below shows that the restriction of this global diffeomorphism maps [0, 1]d onto itself, so it is also a C 2 self-map of the cube. Moreover, Fu maps the cube into itself. Only the first coordinate moves, and the displacement is nonnegative. On the right boundary cell, write the local coordinate as ξ = qx − c + 1 and its first coordinate as t = ξ1 ∈ [0, 1]. The distance to the boundary x1 = 1 is (1 − t)/q, while αq −2 Ψ(ξ) ≤ αq −2 t3 (1 − t)3 ≤ 1−t q because α ≤ 1 and q ≥ 1. Thus no point crosses the right boundary; all other boundaries are unchanged or moved inward. At the cell center zc , the local coordinate is (1/2, . . . , 1/2), so Fu (zc ) − Fv (zc ) = αq −2 (uc − vc )κd e1 . 15
The displaced centers remain in [0, 1]d : the only moved coordinate shifts by at most ακd q −2 , which is smaller than the distance 1/(2q) from a cell center to the nearest boundary when q ≥ 2. Thus same-cell costs are ∥Fu (zc ) − Fv (zc )∥2 = ακd q −2 1{uc ̸= vc }. For c ̸= c′ , the center distance is at least 1/q. The displacement of any center is at most ακd q −2 , hence 1 ∥Fu (zc ) − Fv (zc′ )∥2 ≥ − 2ακd q −2 . q Since α ≤ 1, κd ≤ 1/64, and q ≥ 2, this cross-cell lower bound is strictly larger than the maximum same-cell cost. Indeed, 1 − 2ακd q −2 > ακd q −2 q
⇐⇒
q > 3ακd ,
which holds because q ≥ 2 and 3ακd ≤ 3/64. The unique optimal coupling is therefore the cellwise matching Fu (zc ) ↔ Fv (zc ). It is induced by Tu,v = Fv ◦ Fu−1 . The exact cost follows by summing the same-cell costs: ακd ακd 1 X ακd q −2 1{uc ̸= vc } = dH (u, v) = 1+2/d dH (u, v). W1 (µu , νv ) = m c mq 2 m It remains to bound the Hessian of Tu,v . On an active cell, ∥D2 Fu (x)∥op ≤ αB2,d . From ∥DFu − I∥op ≤ 1/4, ∥DFu−1 ∥op ≤ 4/3. Let Gu = Fu−1 . Differentiating Fu (Gu (y)) = y twice gives D2 Gu (y)[h, k] = −DFu (Gu (y))−1 D2 Fu (Gu (y))[DGu (y)h, DGu (y)k]. Consequently, ∥D2 Gu (y)∥op ≤
4 · αB2,d · 3
2 4 64 = αB2,d . 3 27
Now Tu,v = Fv ◦ Gu . The chain rule yields D2 Tu,v (y)[h, k] = D2 Fv (Gu (y))[DGu (y)h, DGu (y)k] + DFv (Gu (y))D2 Gu (y)[h, k]. Using ∥D2 Fv ∥op ≤ αB2,d , ∥DGu ∥op ≤ 4/3, and ∥DFv ∥op ≤ 5/4, we get 2 5 64 128 4 2 + · αB2,d = αB2,d . ∥D Tu,v ∥∞ ≤ αB2,d 3 4 27 27 βακd ακd Under the Gap-Hamming promise, the exact cost identity creates a gap 2β m1/2+2/d . If ε < m1/2+2/d , Lemma 1 would turn an additive-ε cost-evaluable, cost-certified, or scalar value-certified couplingoutput protocol into a Gap-Hamming protocol, requiring Ω(m) bits. Since ε ≍ m−1/2−2/d is equivalent to m ≍ ε−2d/(d+4) , the ε-dependent lower bound is Ω(ε−2d/(d+4) ).
A.7
Proof of Proposition 3
For Theorem 4, the public randomness samples i ∈ [m] uniformly. Alice outputs her ith source atom 3i hui 3i+1 hvi L , L , and Bob outputs his ith target atom L , L . The proof of Theorem 4 shows that this indexwise matching is optimal for every u, v. The protocol communicates zero bits and produces the exact optimal distributed sampler. The cost still depends on dH (u, v), so a cost certificate is not produced. For Theorem 5, the public randomness samples a cell c ∈ [q]d uniformly. Because ακd q −2 < 1/(2q), every displaced center remains inside its original public cell, so Alice and Bob can recover the common label c from their local samples without communication. Alice outputs Fu (zc ) and Bob outputs Fv (zc ). The proof of Theorem 5 shows that the cellwise matching is optimal for every u, v. Again the protocol communicates zero bits and produces the exact optimal distributed sampler, while the cost remains hidden in the mismatch pattern. 16
B
Tightness
e −d/2 ), and Theorem 5 gives Corollary 2 gives a field-description upper rate Bfield,spline (ε) = O(ε −2d/(d+4) a total certified-output lower rate Bcert (ε) = Ω(ε ). At d = 2, the exponents are 1 and 2/3. At d = 5, they are 5/2 and 10/9. The two quantities are not the same complexity measure: the upper rate counts only the spline-field bits, while the lower rate is a total communication lower bound for any cost-evaluable, cost-certified, or value-certified protocol. The corresponding total value-certified upper rate is the field cost plus the residual-count lists in Theorem 1, and it matches e −d/2 ). Hence the displayed exponent e −d/2 ) only on subclasses with s + ŝ = O(ε the field rate O(ε gap is a basis-and-residual-sparsity gap rather than a matched upper-versus-lower theorem in the same total communication measure. The spline upper theorem pays for a uniform tensor basis on the field, while the lower bound creates a certified cost gap from small independent perturbations of size q −2 in public cells. Proposition 3 shows that the lower-bound perturbations leave the optimal pair structure publicly determined, so they impose no sampler communication. Closing the exponent gap will require either residual-sparse upper-bound classes or a lower bound stated in the same field-complexity model. The open tightness problem is basis-aware. The algorithmic direction asks for an adaptive field code that spends bits only on cells where the transport field has nonzero perturbation, improving over the uniform tensor rate on localized families. The converse direction asks for a sampler lower bound that makes the near-optimal pair structure itself depend on both inputs, rather than only on the certified cost value. We conjecture that adaptive certified field codes match the cell-packing exponent ε−2d/(d+4) on localized smooth families, and that the right complexity parameter for smooth sampler output is the metric entropy of the transport field in the communicated basis plus the residual exact-marginal correction cost. Open Problem 1 (Sampler-hard smooth transport). Replace the public one-atom-per-cell gadgets by two-by-two switch cells. In each cell, Alice’s private bit and Bob’s private bit would jointly decide whether the lower-cost local matching is diagonal or off-diagonal, so public randomness could no longer choose the correct pair label without communication. A smooth version would pack these switch cells into separated boxes and realize their perturbations by local diffeomorphisms. The missing proof obligation is stability: cross-cell transport must remain dominated while each local switch keeps a robust cost gap. This is the next sampler lower-bound target.
C
Additional Empirical Details
C.1
Benchmark Suite Table 2: Benchmark groups used in the empirical study.
Group Smooth 2D Nonlinear 2D 5D scale-up
Datasets gaussian_shift gaussian_affine sinusoidal_warp swirl_warp gaussian_nonlinear_d5 digits_pca5_warp
Sample size
Role
n = 128, 5 seeds
Affine-field sanity
n = 128, 5 seeds n = 256, 5 seeds; n = 1024, 3 seeds
Spline/local-field test
mnist_usps_pca5 Natural unpaired dotmark_classicimages_2d n = 512, 5 seeds
Dimension and sample-size check Real-data transport geometry
mnist_usps_pca5 uses MNIST (Lecun et al., 1998) resized from 28 × 28 to 16 × 16, USPS (Hull, 1994) normalized to [0, 1], and PCA-5 fit on the union so that both parties share coordinates. dotmark_classicimages_2d uses DOTmark ClassicImages (Schrieber et al., 2017) at resolution 64, treating each image as a discrete mass distribution and sampling point clouds with within-pixel jitter. In all ten real-benchmark trials, the exact empirical OT plan has 512 nonzero entries for n = 512, so the oracle target is permutation-valued. 17
Table 3: Mean absolute relative error on natural unpaired benchmarks. Benchmark mnist_usps_pca5 dotmark_classicimages_2d
spline_4
spline_3
local_affine_2
kmeans_64
grid_3
0.020219 ± 0.001204 0.151760 ± 0.096331
0.028262 ± 0.001418 0.201435 ± 0.151991
0.037872 ± 0.001950 0.162634 ± 0.123231
0.031616 ± 0.002307 0.166822 ± 0.100585
0.096345 ± 0.013789 0.982010 ± 0.512256
Figure 2: Best per-family mean absolute relative error on each benchmark, with 5 seeds per benchmark and error bars sampling standard deviation; sample sizes are n = 128 for the 2D tasks, n = 256 for the 5D scale-up tasks, and n = 512 for the natural benchmarks. C.2
Additional Results
On the smooth 2D tasks gaussian_shift and gaussian_affine, the global affine field already saturates the achievable accuracy. The frontier AUCs, seedwise mean ± sample standard deviation, are 0.000243 ± 0.000131 and 0.002156 ± 0.000956 for the field family, against 0.001847 ± 0.000453 and 0.004388 ± 0.001516 for k-means and 0.004337 ± 0.003855 and 0.006057 ± 0.007196 for grid summaries. Representative individual points include affine_flow at 1.51 · 10−4 ± 1.08 · 10−4 on gaussian_shift and 4.46 · 10−4 ± 5.05 · 10−4 on gaussian_affine, both at 160 bits. On the nonlinear 2D tasks sinusoidal_warp and swirl_warp, spline fields dominate the frontier, with AUCs 0.002716 ± 0.001307 and 0.001673 ± 0.000605, by more than an order of magnitude over local-affine (0.037643, 0.037393), affine (0.044503, 0.015347), grid (0.091259, 0.106692), and k-means (0.162777, 0.185490). The strongest spline points reach 3.11 · 10−4 ± 1.74 · 10−4 on sinusoidal_warp and 3.06 · 10−4 ± 1.76 · 10−4 on swirl_warp. On swirl_warp, the local-affine error decreases from 0.309 ± 0.437 at b = 4, 91.2 bits, to a plateau of 0.0134 ± 0.007 at b ≥ 12. On natural unpaired benchmarks, spline fields again attain the best absolute accuracy. On mnist_usps_pca5, spline_4 reaches 0.020219 ± 0.001204 against 0.031616 ± 0.002307 for kmeans_64 and 0.096345 ± 0.013789 for grid_3. On dotmark_classicimages_2d, the spline error is 0.151760 ± 0.096331 versus 0.166822 ± 0.100585 for kmeans_64 and 0.982010 ± 0.512256 for grid_3; the closer race reflects that the underlying transport between raster images is not generated by a smooth diffeomorphism.
18
NeurIPS Paper Checklist The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit. Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist: • You should answer [Yes] , [No] , or [NA] . • [NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available. • Please provide a short (1–2 sentence) justification right after your answer (even for NA). The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper. The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] " provided a proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] " or "[NA] " is not grounds for rejection. While the questions are phrased in a binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found. IMPORTANT, please: • Delete this instruction block, but keep the section heading “NeurIPS Paper Checklist", • Keep the checklist subsection headings, questions/answers and guidelines below. • Do not modify the questions and only use the provided macros for your answers. 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] . Justification: The abstract and introduction state the paper’s scope as empirical OT couplingoutput communication, distinguish the output models, and summarize the field-code compiler, smooth certified lower bounds, sampler/certificate separation, and empirical bit-budget comparisons. The claims are matched by the formal results in Sections 3–4, the experiments in Section 5, and the limitations in Section 6. Guidelines: • The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations 19
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] . Justification: Section ?? discusses the main limitations: the upper bounds require a lowcomplexity field code, total communication depends on residual sparsity or cell-margin structure, the compiler gives a scalar value certificate but not a cost-evaluable representation, and the experiments fit fields using paired or empirical-OT supervision. Guidelines: • The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] . Justification: The standing assumptions are stated in Section 3.2, and the theorem, proposition, corollary, and lemma statements reference the relevant assumptions and output models. Full proofs are provided in Appendix A, with the main results cross-referenced from Section 4. Guidelines: • The answer NA means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility 20
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] . Justification: Section 5 and Appendix C describe the protocol families, benchmark groups, sample sizes, seeds, metrics, bit accounting, and how field summaries are fit. The experiments use synthetic or publicly available datasets, and the reported tables and figures specify the main comparisons needed to verify the empirical claims. Guidelines: • The answer NA means that the paper does not include experiments. • If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] . Justification: The paper describes the synthetic generation procedure, public datasets, protocols, and evaluation setup, but the source code is not openly released at submission time. The source code will be released after acceptance with scripts and instructions to reproduce the main experimental results. Guidelines: • The answer NA means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. 21
• While we encourage the release of code and data, we understand that this might not be possible, so “No” is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] . Justification: Section 5 and Appendix C specify the protocol families, benchmark datasets, sample sizes, number of seeds, bit accounting, field-fitting supervision, and evaluation metric. The experiments do not train neural networks; the main algorithmic choices are the communicated summaries and their resolutions or coefficient precisions. Guidelines: • The answer NA means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] . Justification: The main figure and result tables report seedwise mean ± sample standard deviation over repeated seeds. Section 5 and Appendix C.2 state the number of seeds used for each benchmark and identify the error bars as sample standard deviations. Guidelines: • The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. 22
• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [No] . Justification: The current version reports the experimental setup and repeated-seed evaluation but does not yet provide detailed compute-worker type, memory, runtime per run, or total compute. These details will be added to the supplemental material together with the code release after acceptance. Guidelines: • The answer NA means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] . Justification: The paper is theoretical and empirical work on optimal transport communication, uses synthetic and publicly available benchmark datasets, and does not involve human-subject experiments, private data collection, or deployment of a high-risk model. The work is intended to conform to the NeurIPS Code of Ethics. Guidelines: • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] . Justification: The paper discusses the foundational nature of the work and its potential positive impact on communication-efficient distributed OT and flow training. It also notes limitations and risks relevant to distributed settings, including that communicating summaries or fields does not by itself provide privacy guarantees. Guidelines: • The answer NA means that there is no societal impact of the work performed. • If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. 23
• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] . Justification: The paper does not release pretrained language models, image generators, scraped datasets, or other high-risk assets. The experiments use synthetic data and standard public benchmark datasets. Guidelines: • The answer NA means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] . Justification: The paper cites the original sources for the public datasets used in the empirical study, including MNIST, USPS, and DOTmark. The datasets are used only as standard research benchmarks; no new redistribution of these datasets is introduced by the paper. Guidelines: • The answer NA means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 24
• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] . Justification: The paper does not introduce a new dataset, pretrained model, or benchmark asset. The planned code release after acceptance will document the synthetic data generation and experimental scripts. Guidelines: • The answer NA means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [NA] . Justification: The paper does not involve crowdsourcing, user studies, or research with human subjects. All experiments use synthetic data or standard public benchmark datasets. Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] . Justification: The paper does not involve crowdsourcing, user studies, or research with human subjects, so IRB approval or equivalent human-subject review is not applicable. Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. 25
• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required. Answer: [NA] . Justification: LLMs are not used as part of the core methodology, theory, experiments, or scientific contribution. Any language editing or formatting assistance does not affect the originality, rigor, or results of the research. Guidelines: • The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy (https://neurips.cc/Conferences/2025/LLM) for what should or should not be described.
26