论文精选

分布式耦合采样器的场编码与认证经验传输

Field Codes for Distributed Coupling Samplers and Certified Empirical Transport

精选理由

这篇论文从通信复杂度角度重新审视最优传输,提出了场编码编译器,把误差η的传输场变成带证书的采样器,下界还很紧。做分布式最优传输或通信复杂度的人可以看看。

AI 摘要

本文提出了经验最优传输的三种通信任务:分布式耦合采样、成本可评估耦合输出和标量值认证采样。主要结果是场编码编译器:任何逼近最优经验Monge映射至误差η的通信传输场,可通过稀疏目标单元残差补全为精确边际的值认证采样器,其标量证书满足W₁(μ,ν)≤U≤W₁(μ,ν)+2Δ,其中Δ是公开目标划分直径。证书精度仅由Δ控制。实例化编译器采用自适应局部仿射和张量积样条编码,样条情况需d(m+1)^db场比特,残差列表另计。下界方面,精确Gap-Hamming嵌入证明认证输出是困难的,包括一个平滑单元填充微分同胚族,要求任何成本可评估、成本认证或值认证协议至少Ω(ε^{-2d/(d+4)})通信。

原文 · arXiv cs.LG

Field Codes for Distributed Coupling Samplers and Certified Empirical Transport

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 value-certified sampler with scalar certificate $W_1(μ,ν)\leq U\leq W_1(μ,ν)+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)^db$ 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 $Ω(\varepsilon^{-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.