【博士论文】最优传输的进展：低秩结构及其在机器学习中的应用，364页pdf

最优传输（OT）在机器学习（ML）中比较概率分布时扮演着越来越重要的角色。OT问题已被用于许多应用，并有多种表述。其中，蒙日答案和康托罗维奇线性程序最为突出。前者涉及寻找一个有效的前推映射，可以将一个测度变形到另一个；而后者则放宽了测度的匹配，允许质量的分裂。康托罗维奇OT在计算上更为宜人，并已成为数据科学的主要焦点。然而，当用于应用问题时，其原始形式提出了几个挑战：（i）在离散分布之间计算OT相当于解决一个大型且昂贵的网络流问题，这需要在点数上具有超立方的复杂性；（ii）使用采样测度估计OT受到维数诅咒的困扰。可以使用熵正则化来缓解这些问题，使用Sinkhorn算法解决，这在统计和计算方面都有所改进。尽管速度更快，但熵OT仍然需要与点数的二次复杂性，因此对于大规模问题仍然是禁止的。抓住这个机会，我在我的论文中花了很大的篇幅研究OT的可扩展方法，这导致了我关于低秩最优传输（LOT）的工作线。我还意识到，康托罗维奇提出的放宽OT的基本思想可以应用于其他设置，我提出了使用这个非常相同的想法来处理公平分割问题和通过OT的视角进行对抗攻击问题的新方法。因此，这篇论文分为两个主要部分。

在第一部分，我提出了新的OT问题的正则化方法，以及其二次扩展，即Gromov-Wasserstein（GW）问题，通过对耦合施加低秩结构。这在时间和内存上都产生了线性复杂性，与点数有关。在我朝着这个目标的第一次尝试中，我建议近似解决熵OT的Sinkhorn算法的迭代，通过强制对所涉及的核进行特定的低秩分解，从而导致最优耦合的低非负秩分解。然后我建议将这个想法推广，并直接解决OT问题以及在可接受的耦合上的低非负秩约束下的GW问题。我们证明这些新的正则化方案与熵方法相比具有更好的计算和统计性能，并且在对基础成本矩阵进行低秩假设时甚至可以达到线性复杂性。这些新的计算方案为OT在大规模环境中的使用铺平了道路。

在第二部分，我提出了两种设置，康托罗维奇提出的放宽OT问题的基本思想也可以应用，为长期存在的ML问题提供了新的视角。更确切地说，我们提议放宽并提升多个代理之间的公平分割问题到分布空间，允许在分区中分裂资源质量。这样做，我们证明总是可能获得资源的公平分割，并且当涉及多个成本时，我们得到OT问题的泛化。我们还使用OT解决对抗性示例的问题。在这个问题中，攻击者可以被表示为一个确定性映射，将数据分布向前推到一个旨在最大化分类器风险的对抗性分布。通过放宽攻击者的定义为一个耦合，我们得到了对抗风险的变分形式，这使我们能够将对抗风险最小化问题解释为一个两玩家零和游戏，我们研究了在这个游戏中纳什均衡的存在性问题。