精读笔记

Problem Setting

这篇论文处理的是“熵正则 OT + 一般 coupling 约束 + 选择性 relaxed marginals”的统一求解问题。目标不是重新定义 OT，而是让 Sinkhorn-Knopp 这类乘法缩放算法离开传统行列边际框架后仍然可用。

真正困难在于约束类型同时跨三层：支撑层的硬零约束、边际层的硬/软混合约束、以及 coupling 上的任意线性统计约束。经典 Sinkhorn 的可扩展性来自行列约束的特殊 separability；一旦加入 martingale-style 或 fairness-style coupling constraint，这个结构通常消失。以前方法要么保持 Sinkhorn 但只能处理窄类约束，要么表达力增强但退化成通用凸优化/启发式迭代，收敛保证和规模优势都不清楚。

关键矛盾是：应用侧需要 heterogeneous compliance——有些供给/需求必须满足，有些可以付代价偏离；同时 transportation plan 本身还要满足业务约束。但算法侧希望所有约束仍能被写成低成本投影/缩放更新。这篇论文就是在这个矛盾上做统一化。

Motivation

已有路线不够的地方在于它们通常把 balanced OT、unbalanced OT、martingale OT、hard support constraint、fairness constraint 分开处理。这样的问题不是不能建模，而是缺少一个同一算法模板下可组合、可证明收敛的机制。

作者的核心观察是：很多应用约束本质上都是 transport plan 的线性统计量要求，例如某些行和、列和、条件期望、group utility parity、基础设施可达性等。若这些统计量都能在 KL-Bregman 几何下被单独投影，那么算法仍可保持 Sinkhorn 的乘法缩放风格。

关键缺口是 selective relaxation。标准 UOT 软化边际，但通常不是“某些行硬、某些行软、某些列硬、某些列软，并且还叠加 coupling 约束”的形式。论文最有用的动机是把 compliance 作为约束级别的属性，而不是任务级别的属性。

Core Idea

核心思想是把软约束也变成投影约束的一部分。对一个软线性统计量 \sum a^l_{ij}t_{ij} 希望接近 \tilde b^l，论文不只是把 KL penalty 放在 objective 里然后交给优化器，而是引入辅助变量 b^l，使约束写成 \sum a^l_{ij}t_{ij}-b^l=0，同时惩罚 b^l 与 \tilde b^l 的 KL 距离。这样，软约束被“硬化”为扩展空间中的线性等式，而 flexibility 被转移到 b^l 的偏离成本里。

这个重写使得每次对单个约束做 Bregman projection 时仍然是乘法形式：transport entry 按 c^{a^l_{ij}} 缩放，软约束的 b^l 按 c^{-1/\gamma_l} 缩放。硬约束是把统计量直接拉到目标值；软约束是让 transport 调整和 compliance slack 共同吸收不一致。直觉上，这就是 generalized iterative proportional fitting：不是只平衡行列，而是平衡任意线性统计量。

和 prior 的本质区别不在“用了 entropy”或“用了 Sinkhorn”，而在约束组织方式更一般：每个约束都有自己的硬/软状态和惩罚强度，新增业务约束不需要重写整个 solver。这个 inductive bias 很强：它假设合理的 plan 应该可以通过对 reference kernel K 做一组乘法 reweighting 得到，即最优解位于 exponential family / multiplicative scaling family 中。

Method

第一，论文将成本和 reference plan 合并成 Gibbs kernel K：k_{ij}=\tilde t_{ij}\exp(-c_{ij}/\gamma_0)，并在允许支撑 \mathcal Z 上最小化 KL(T|K)。这一步解决的是把 transport cost、entropy regularization 和 hard zero support 统一到一个非负 reference measure 上；核心变化是后续算法不再直接处理线性成本，而是对 K 做几何投影。

第二，一般线性约束分为硬约束和软约束。硬约束保持为 \sum a^l_{ij}t_{ij}=\tilde b^l；软约束则通过 KL penalty 和辅助变量 b^l 表达。需要它是因为单纯 penalty 会破坏简单投影解释，而辅助变量让问题重新落入 Bregman projection theorem 可处理的形式。

第三，算法以循环方式逐个约束投影。对于每个约束，只需求一个正标量 c，然后所有相关 t_{ij} 乘以 c^{a^l_{ij}}。这解决的是高维 constrained convex problem 的可扩展性问题：每次更新不需要求解大规模线性系统，而是一次稀疏扫描加一维根求解。

第四，选择性 relaxed marginals 是一般框架的特例。硬行/列约束恢复标准 Sinkhorn 的比例缩放；软行/列约束的缩放指数为 \gamma/(1+\gamma)，形成从完全放松到近似硬约束的连续谱。这个机制是论文最可迁移的部分，因为它把 heterogeneous flexibility 直接变成可解释的缩放指数。

Key Insight / Why It Works

真正有效的原因是 KL-Bregman 几何与线性约束的匹配。KL 的一阶条件给出指数/乘法形式；线性约束的单约束投影只需确定一个拉格朗日乘子；因此每轮更新天然是 multiplicative scaling。这不是工程 trick，而是信息几何结构决定的。

最核心贡献是“软约束的扩展变量化”。如果没有 b^l，选择性 relaxation 只是 objective 中的额外非线性项，很难维持 Sinkhorn-like projection 形式；引入 b^l 后，软约束和硬约束都变成扩展空间里的线性等式，只是变量权重不同。这是方法成立的关键。

第二个重要 insight 是边界解性质：若最优解在某个允许 entry 上为零，则所有可行 plan 在该 entry 上都必须为零。这个结果说明 KL objective 不会因为优化偏好主动把一个本可为正的允许边压到零；边界零来自约束结构本身。这对理解带 hard zero/support constraint 的收敛很重要，也解释了为什么乘法缩放从正 K 出发不会“错过”内部可行解。

哪些可能只是辅助：Algorithm 2/4 的 d 参数化主要是把递推写得更像 Sinkhorn，便于实现和比较，但不是理论本体；应用案例中的 ridesharing/energy 也主要展示表达力，不是算法核心。这里没有 data scaling、retrieval、hidden supervision 这类问题；增益主要来自 better inductive bias，即把复杂业务约束投射到 KL projection family 中。

需要警惕的是“generalised martingale-type constraints”的说法可能比理论条件更宽。文中一般算法的单调正根和收敛讨论大量依赖正系数/正目标；标准 martingale constraint 含正负系数和零右端。论文给出形式表达，但对这类约束是否完全落在同一证明条件下，文中未充分说明。

Relation To Prior Work

这篇属于 entropic OT / Sinkhorn / iterative proportional fitting / Bregman projection 谱系，而不是新的 OT relaxation 理论。它最接近 Cuturi-style Sinkhorn、Bregman projection 方法、unbalanced OT、martingale OT 计算方法，以及 constrained OT 中对 support/zero entries 的处理。

和经典 Sinkhorn 的本质差异是：经典方法只在行列边际两个约束族之间交替缩放；本文把“行列”替换为任意线性统计量，并允许每个统计量硬满足或 KL 软满足。因此它是 Sinkhorn 的约束维度泛化，而不是 cost 或 regularizer 的根本创新。

和 unbalanced OT 的差异是 selective compliance。UOT 通常把边际失配作为整体 relaxation；本文允许某些行/列完全硬、某些软、软化强度还可异质。这对资源分配应用更自然。

和 martingale OT / constrained OT 的差异是算法模板和收敛保证。许多 MOT 或 bespoke constrained OT 方法能写出约束，但不一定保留乘法缩放、也不一定给出在这种混合硬软约束下的收敛证明。本文实质创新是把这些约束放回 Bregman 交替投影框架，而不是发明新的 martingale formulation。

看似新的部分中，Bregman projection 和乘法缩放是已有思想；真正新增的信息是：如何通过扩展变量统一软线性约束，并把选择性 relaxed marginals 作为一般线性约束系统的特例推出。

Dataset / Evaluation

评估是两个合成/模拟应用案例，而不是标准 benchmark。ridesharing 案例覆盖 fairness-style coupling constraint：通过性别组成和 fare 权重构造 group utility equality，展示在运输成本小幅上升下可消除模拟 pay gap。energy 案例覆盖 unbalanced supply-demand 和 heterogeneous flexibility：部分消费者必须满足，部分消费者按 flexibility cost 软化，结果呈现低成本 flexible agent 承担更多偏离。

这些实验支持的 claim 是“框架能表达多种资源分配约束，并且数值上可收敛”。它们没有充分支持更强 claim，例如相比 ADMM、commercial LP/QP solver、general KL projection solver 或已有 UOT algorithms 的速度优势；也没有系统测试约束数量、稀疏度、病态可行集、负系数约束、边界解下的稳定性。

没有真实世界部署或真机系统；ridesharing 和 energy 都是 stylized simulation。对于一篇偏算法/优化理论的论文这可以接受，但 evaluation 的角色更像 sanity check，不是 decisive empirical validation。

Limitation

第一，理论适用范围和标题中的 generalised martingale-type 存在潜在落差。主公式和唯一正根讨论多处要求 a^l_{ij}\ge 0、\tilde b^l>0；而 martingale equality 通常有正负系数且 RHS 为 0。文中虽然展示可写成线性约束，但完整收敛条件如何覆盖这类约束，文中未充分说明。

第二，可扩展性的上限取决于约束结构。若约束是行列和，更新是标准 Sinkhorn 级别；若是大量 dense arbitrary linear constraints，每轮都要扫描大范围 entries 并解标量方程，复杂度可能接近通用投影方法。所谓 generality 并非免费。

第三，方法把问题从“大规模凸优化”转移成“设计合适线性统计量和 compliance 参数”。\gamma 的经济含义、fairness constraint 的合理性、flexibility cost 与 KL penalty 的对应关系，都需要应用侧校准。若这些参数设错，算法仍收敛，但收敛到的 plan 未必有实际意义。

第四，边界和可行性问题仍然敏感。若 hard zero support 与硬约束组合导致可行集低维或接近空，乘法缩放可能数值很慢；如果某些允许边实际上被所有可行解强制为零，从正初始化出发只能渐近逼近，可能出现 underflow 或收敛判据误判。

第五，实验没有证明泛化能力。这里的“generalizable”是建模范式上的可组合，不是跨数据分布或真实系统上的经验泛化。增益来源主要是约束表达正确，而不是某种隐藏的优化性能突破。

Takeaway

• 1. 最值得记住的是软约束扩展变量化：把 KL penalty 的统计量变成辅助变量上的硬等式，可以把 heterogeneous relaxation 重新纳入 Bregman projection。
• 2. 这篇推动的是 constrained entropic OT 的工程可组合性和理论整洁性，而不是 OT cost、regularization 或 convergence acceleration 的根本突破。
• 3. 对其他问题可迁移的 insight 是：只要目标是 KL-like，且约束能写成低维线性统计，就可以尝试把复杂 compliance/soft constraint 变成扩展空间中的投影问题，从而保留 multiplicative updates。
• 4. 未来真正值得做的是负系数/零 RHS 约束的严格理论、加速与 block projection、以及大规模稀疏真实网络上的稳定实现；否则 general linear constraint 的优势会停留在建模表达层面。

一句话总结

这篇论文把 Sinkhorn 从“行列边际平衡算法”推进为“KL 几何下的一般线性统计量平衡框架”，真正贡献是用扩展变量统一硬/软约束并给出 Bregman 投影收敛保证，但其 generality 在含负系数 martingale 约束和大规模 dense constraint 下仍需谨慎看待。