提出通信高效的最优传输采样框架,实现带验证的分布式采样。
Field Codes for Distributed Coupling Samplers and Certified Empirical Transport

- 用场编码编译器将近似传输场转为精确边际采样器
- 证书误差仅由目标划分直径控制,可达上界与真实值差不超过2Δ
- 适用于需验证输出的分布式机器学习场景
本文定义了最优传输中的三项通信任务:分布式耦合采样、可评估代价的耦合输出和标量认证采样。核心成果是提出一种场编码编译器:任何逼近最优经验Monge映射至误差η的传输场,可通过稀疏目标单元残差补全为精确边际的标量认证采样器,其证书满足 $W_1(μ,ν)\ leq U\ leq W_1(μ,ν)+2Δ$,其中 Δ 为公开目标划分直径。证书精度仅由 Δ 决定。场误差 η 在满足单元边际条件下控制残差通信量;若无边际条件,则 η 无法约束残差。我们通过自适应局部仿射与张量积样条编码实例化编译器,样条情形下需 $d(m+1)^db$ 字段比特,残差列表单独计费。下界分析表明,任何可评估代价、可认证代价或值认证协议都至少需要 $Ω(\varepsilon^{-2d/(d+4)})$ 通信量,且相同构造支持零通信采样,形式化分离采样与认证输出模型。结果表明,只要存在场编码,场就是最适通信对象,主要作为残差稀疏工具。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。