最优传输 III · Sinkhorn：先对平，再谈算准

前置：耦合与对偶证书、Wasserstein 几何、互信息与率失真。本页讨论有限概率分布与有限成本；先完成一个可以验算的矩阵问题，再连接生成模型。实验最多三行三列，不代表大模型训练或一般连续 OT 求解器。

1. 三个容易混用的“成本”

设 \(a\in\mathbb R_+^m\)、\(b\in\mathbb R_+^n\) 都是概率向量，\(C_{ij}\) 有限。运输多面体与原始目标为

对 \(\varepsilon>0\)，本页统一使用相对于独立耦合的 KL 正则化：

求得正则化最优计划 \(P_\varepsilon\) 后，运输部分 \(\langle C,P_\varepsilon\rangle\) 与完整目标 \(\mathrm{OT}_\varepsilon\) 仍是不同的数，二者也一般不等于 \(\mathrm{OT}_0\)。只有当成本来自同一度量空间的距离 \(p\) 次方时，原始目标的 \(p\) 次方根才对应 \(W_p\)。

有的书采用 \(F_\varepsilon(P)=\langle C,P\rangle+\varepsilon\sum P_{ij}(\log P_{ij}-1)\)。在可行集上，若 \(H(a)=-\sum_i a_i\log a_i\)，则

固定边缘时最优计划相同，最优值不同。 若边缘也在训练过程中改变，这个差额不再是与训练参数无关的常数，不能直接把两种损失及其梯度互换。

对还没有对平的非负矩阵，我们采用广义 KL 延拓

其中 \(0\log0=0\)。当 \(P\) 质量为 1 时，它与前面的 \(J_\varepsilon\) 相同。实验同时保留原始对数和、广义 KL、总质量，避免给一个质量不足的中间矩阵套上概率 KL 的解释。零边缘之外出现正质量会使 KL 无穷；实验始终禁止这种情况。

2. 为什么熵最优计划存在、唯一，而且有指数形式？

去掉零质量行列后，\(a_i,b_j>0\)。可行集非空，因为含有 \(a b^T\)；它又是有限维紧集，目标连续，所以存在最小值。函数 \(p\log p\) 严格凸，因而目标在可行集上严格凸，最优计划唯一。

它在活跃矩形内还必须处处为正。否则取 \(P_t=(1-t)P+t a b^T\)：原先为零的格子在熵项中的增量含有正系数乘 \(t\log t\)，其右导数为负无穷；成本增量及原先正格子的导数有限。足够小的正 \(t\) 会降低目标，矛盾。

将约束乘子记为 \(f_i,g_j\)，对广义 KL 形式逐格最小化拉格朗日函数，得到

这是“每条路的成本”与“两端的价格”共同决定货量。记 \(u_i=e^{f_i/\varepsilon}\)、\(v_j=e^{g_j/\varepsilon}\)、\(K_{ij}=e^{-C_{ij}/\varepsilon}\)，就有

与常见的 \(\operatorname{diag}(\widehat u)K\operatorname{diag}(\widehat v)\) 写法相比，这里把边缘权重显式提出了。二者只差 \(\widehat u=a\odot u\)、\(\widehat v=b\odot v\)。

势不唯一：\(f\mapsto f+c\mathbf1\)、\(g\mapsto g-c\mathbf1\) 不改变计划。实验每个半步用 \(a^Tf=0\) 固定这个自由度。势的平移不会改变货量，不应被误读为一次优化进展。

3. 一轮由两个半步组成：刚对齐的账会怎样？

在本页的约定下，固定 \(v\) 后对齐行边缘，固定新 \(u\) 后对齐列边缘：

第一式代回计划，行和恰为 \(a_i\)。第二式代回，列和恰为 \(b_j\)，但新的 \(v\) 一般会再次改变行和。因此每次保存行缩放和列缩放后的两种边缘，并计算

实验从 \(u=v=1\) 开始，初始矩阵是 \(a_i b_jK_{ij}\)。当成本非负时总质量不超过 1，但一般不是 1，它还不是一份合法运输计划。

每个半步也是对偶中的一次精确块最大化，实数精确计算下对偶值不下降。边缘误差的每一个单独分量则不必逐步单调。实现只按指定轮数运行，不用一个未经说明的“误差足够小”按钮代替误差标准。

4. 一个完整的收敛论证：正性为什么重要？

下面给出易于检查、但不追求最优常数的有限矩阵证明。设 \(0\lt L\le K_{ij}\le U\)，对正向量定义 Hilbert 射影距离

它忽略整体倍数。逐项取倒数和乘一个固定正对角矩阵，都保持这个距离。关键是证明正矩阵作用会压缩：

令 \(A_i(z)=\log\sum_jK_{ij}e^{z_j}\)。其梯度是一份概率权重

每一行梯度都包含同一份总质量 \(L/U\) 的公共权重。把这部分剥掉，剩下的总质量是 \(q\)。对任意方向 \(h\)，不同两行的方向导数之差，绝对值不超过 \(q\operatorname{osc}(h)\)。沿从 \(\log w\) 到 \(\log v\) 的线段积分，就得到上面的压缩式。

常见缩放变量的一整轮为

两次正矩阵作用使压缩系数不超过 \(q^2\)。对数向量模去常数后是一个有限维完备空间，故 Banach 不动点定理给出唯一射影不动点和几何收敛。若 \(T(v)=\lambda v\)，令 \(u=a\oslash(Kv)\)，则当前计划的行质量为 1、列质量总和为 \(1/\lambda\)；两者必须一致，故 \(\lambda=1\)，不动点确实同时满足两侧边缘。

这个证明只用于有限、严格正的活跃核。实际二进制浮点若把正数下溢成零，便不再满足证明的假设。ε 变小时 \(L/U\) 可能极小，压缩因子接近 1；“有几何收敛定理”与“100 轮就够”是两件事。更精细的迭代复杂度与可行化分析可读 Altschuler–Weed–Rigollet 原文。

5. log 域计算：保住正路，不等于自动收敛

直接生成 \(K_{ij}\) 可能遇到 \(e^{-10^6}\)。数学上它为正，常用浮点中却会变成 0。随后用 \(10^{-300}\) 替换零分母，会把失败隐藏成另一套未经证明的迭代。本实验让直接核法明确记录失败位置。

在 log 域中写

最大指数成为 1，所以求和不会因为所有项同时下溢而变成 0。最终的

可以仍是一个有限负数，即使把它指数化后的显示值为 0。实验完整保存两者；热图的暗格不能证明严格零质量。

全成本相同的例子最清楚。若 \(C_{ij}=100\)，每个可行计划的运输成本都是 100，KL 最小的计划是 \(a b^T\)。取 ε 为 0.0001，直接核完全下溢，log 计算仍能恢复独立耦合。另一方面，小 ε 的不均匀边缘例即便没有数值失败，100 轮后仍可能有很大行残差。稳定表示解决了“怎样计算这一步”，没有替你完成尚未收敛的那些步。

6. 第三张账：可行化与原始成本的精确上下界

中间矩阵 \(F\) 未必可行，其成本既不一定是上界，也不是最优值。可以先只缩小过大的行，再只缩小过大的列：

零分母时取缩放系数 1。此时两种边缘都不超过目标，令

若 \(\delta>0\)，补上 \(d e^T/\delta\)；若为零，直接保留 \(F''\)：

为什么正确？新增矩阵的第 \(i\) 行总和是 \(d_i\)，第 \(j\) 列总和是 \(e_j\)，且没有负质量。它正好补齐缺口。

这个修复的改动也有可控量级。设第一次削去质量 \(A=\sum_i((F\mathbf1)_i-a_i)_+\)，第二次削去质量 \(B\)。由于只做削减，\(B\le\sum_j((F^T\mathbf1)_j-b_j)_+\)。记初始总质量为 \(M\)，则

最后一步使用 \(2A+1-M=\|F\mathbf1-a\|_1\) 及 \(B\) 的上界。这是矩阵可行化，不是再运行一次熵优化。算法对应 原论文 Algorithm 2 与 Lemma 7。

还需要下界。取任意有限源势 \(\phi\)，令 \(\psi_j=\min_i(C_{ij}-\phi_i)\)，便有 \(\phi_i+\psi_j\le C_{ij}\)。因此

实验把浮点迭代值的十进制表示转成精确分数，然后以分数完成削减、补账和取最小值；这些上下界证明的是所得有理数计划的原始离散成本。它们没有把指数、对数或正则化最优值变成精确数。额外的三行三列 LP 枚举给出精确基准；这是教学用的独立对照规模，不是 Sinkhorn 每轮需要做的工作。

7. 熵目标也有对偶，但不要把浮点差叫严格证书

广义 KL 的逐格共轭给出

对任意有限势与任意可行 \(Q\)，令 \(P^{f,g}_{ij}=a_i b_j e^{(f_i+g_j-C_{ij})/\varepsilon}\)，直接展开可得

因此实数精确计算下，\(D_\varepsilon\le\mathrm{OT}_\varepsilon\le J_\varepsilon(Q)\)。而对于不满足边缘的当前指数矩阵，有

它可能为负，不能当作标准原始—对偶间隙。实验采用修复后的 \(Q\) 计算上端，保留当前势计算下端，同时展示行列残差。

这里的对数与指数仍用浮点求值，没有区间算术。极小的“上端减下端”可能因舍入显示为负，完整账本保留符号，不把它裁成零。它是数值诊断；上一节基于有理数线性成本的不等式才是本实验的精确证书。两个层次不能混称。

8. ε 改变了什么：有限步误差与极限偏差分开

在固定有限边缘下，任意可行计划的互信息满足

右侧可由条件熵非负得到。将正则化最优计划与一个原始 OT 最优计划 \(P_0\) 比较：

这是已经求到熵最优解时的偏差界，不能直接拿来保证只迭代一轮的结果。对有限步，先检查第 6 节的可行原始成本上下界和第 7 节的数值优化差。

当 ε 趋零，紧性保证子列极限；上式使所有极限都为原始 OT 最优计划。进一步，对任何原始最优计划 \(P_0\)，由同一比较式和运输成本不低于最优值得到 \(\mathrm{KL}(P_\varepsilon\mid a b^T)\le\mathrm{KL}(P_0\mid a b^T)\)。所以极限选择原始最优面上 KL 最小、等价于熵最大的唯一计划，不是任意挑一个顶点。

当 ε 趋无穷，与独立耦合比较：

Pinsker 不等式给出 \(P_\varepsilon\to a b^T\)。这解释了大 ε 时路线更多地由边缘质量决定。它不意味着独立耦合是原始运输成本的最优解。

9. Sinkhorn 散度：要同时算好三份问题

对同一空间上的对称成本，用同一 ε 定义

这确保 \(S_\varepsilon(a,a)=0\)。若换用第 1 节的 \(F_\varepsilon\) 约定，三个额外的边缘熵常数恰好抵消，所以去偏后的值一致。

非负性并不是任意成本矩阵做三次相减的代数事实。 一个可用的定理条件是：紧度量空间、对称 Lipschitz 成本，且 \(e^{-C/\varepsilon}\) 是正的 universal 核；此时散度非负，零值识别同一分布，并刻画弱收敛。有限有界实线上的平方距离对应高斯核，属于这个框架。定理见 Feydy 等原文 Theorem 1。它没有承诺一般三角不等式，因此本页称“散度”。

数值上有三份误差。若实数算术的三个目标分别位于 \([D_{ab},U_{ab}]\)、\([D_{aa},U_{aa}]\)、\([D_{bb},U_{bb}]\)，则

实验在五个相邻 ε 上分别重算三份问题，保留每份修复前后的计划、势、误差和数值端点。显示的估计是三个区间中点按上式相减；它不是一个已经严格求出的散度值。自分布问题如果还没算好，跨分布问题看起来稳定也不够。这里同样没有区间算术，负的舍入宽度会原样记录。

10. 从计算 OT 走向生成模型：哪些结论可以带走？

WGAN 连接的是 第一页的 KR 对偶：

取 \(\mu=\delta_{-1}\)、\(\nu=\delta_1\)，函数 \(f(x)=-x\) 给出 \(1-(-1)=2\)，达到距离 2；\(f(x)=x\) 给出的是 \(-2\)。检验函数的符号与对偶中两个分布的顺序必须一起核对。

再取 \(\nu_\theta=\delta_\theta\)、\(\mu=\delta_0\)：\(W_1=|\theta|\)；当 \(\theta\ne0\) 时，标准等权 JS 为 \(\log2\)，两个方向 KL 都为无穷。这是“支撑分离”的具体例子，不是说所有 KL 的梯度都为零。\(|\theta|\) 在 0 还不可微；即使更换了分布距离，神经网络参数化和训练误差仍可能导致梯度问题。WGAN 原文 Theorem 1给的是带条件的连续性与几乎处处可微性。

有限神经网络检验函数类未必包含最优势；训练有限轮也未必到达上确界。权重裁剪约束的是参数范围，不能直接证明网络恰为 1-Lipschitz。WGAN-GP 的梯度罚只在采样点施加软惩罚，不是全空间的精确 Lipschitz 证书。本页不把一个训练损失曲线标成已求出的 \(W_1\)。

流匹配中，给定端点耦合，令 \(X_t=(1-t)X_0+tX_1\)，平方回归的总体最优速度为

若连续性方程及相应 ODE 有足够的存在唯一性、可积性条件，这个速度可保持指定的边缘路径。条件期望投影与 Jensen 不等式解释了为什么理想 rectification 可以降低凸位移成本。这没有自动选出一个指定成本的全局最优耦合。 见作者对 Rectified Flow 与成本特定 OT 的区别说明。实际训练还增加了回归误差和数值 ODE 误差；上一页的交叉配对反例已经说明直线粒子路径并不足以保证分布最短路。

11. 四道迁移题：每一道都给出可验算答案

题 1：同价矩阵。 两侧质量均为 \((1/2,1/2)\)，所有成本为 3。写出原始最优值、正则化最优计划与完整 KL 正则化目标。若 ε 极小、核全下溢，哪些数学结论仍成立？

题 2：把近似计划补成合法计划。 令 \(a=b=(1/2,1/2)\)，\(F=\operatorname{diag}(0.6,0.2)\)，成本对角为 0、非对角为 1。完成两次削减与补账，再用零势给出原始 OT 上下界。

题 3：相同分布的自成本为何非零？ 两侧都均匀分布在位置 0、1，平方距离成本为 \(\bigl(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\bigr)\)。写出正则化最优计划与目标，解释去偏。

题 4：没有训练误差也不能忽略前提。 对 \(\delta_{-1}\) 与 \(\delta_1\) 写出正确 KR 检验函数。再说明：一个全空间恒等为零的检验函数是否 1-Lipschitz？它是否一定最优？

12. 下一步研究：先选清楚目标，再选择加速方法

本页完成有限平衡问题的机制与可核查误差。向大规模前进时，可以研究 ε 延续、稀疏截断与低秩核近似，但每次加速都要说明它改变了哪个对象、删掉了多少质量、误差如何进入最终目标。每轮稠密乘法是 \(O(mn)\)；总复杂度还乘以精度、ε、成本范围和边缘条件决定的迭代数，不能把单轮复杂度当作完整求解复杂度。

向不平衡 OT 前进，需要给边缘违约另设代价，重新推导对偶与缩放，不能对质量总和不同的输入偷偷归一化。向 Schrödinger 桥前进，需要明确参考路径测度、端点约束与相对熵；“都是熵”不是把任意生成 ODE 等同于桥过程的证明。向可微优化前进，需要区分对已收敛最优值求导、对有限展开迭代求导，以及忽略内层误差的近似。

统计采样误差又是第四张账：总体分布换成经验分布后，即使有限矩阵求得精确，也没有消除采样误差。固定 ε 的统计结论可能带有随 ε 恶化的常数；本页不把某个正则化估计量的根号样本数速率推广成所有维数下原始 Wasserstein 距离的普遍速率。

完成本页的退出条件是：能写清目标约定，解释两个半步，区分三种误差，用补账和对偶给出原始成本范围，并指出生成模型连接中尚未验证的条件。三页的主线分别是耦合与证书、最短路径与重心、本页的数值求解；后续前沿需要沿这条链继续补证据。