我们研究了摊销优化的使用来预测输入度量的最佳运输（OT）图，我们称之为元。通过利用过去问题的知识和信息来快速预测和解决新问题，这有助于反复解决不同措施之间的类似OT问题。否则，标准方法忽略了过去解决方案的知识，并从头开始重新解决每个问题。元模型在离散设置中超过了log-sinkhorn求解器的标准收敛速率，并在连续设置中凸电势。我们通过在图像，球形数据和调色板之间的离散和连续传输设置中多个数量级来改善标准ot求解器的计算时间。我们的源代码可在http://github.com/facebookresearch/meta-ot上找到。

计算分布之间的最佳传输（OT）耦合在机器学习中起着越来越重要的作用。虽然可以将OT问题求解为线性程序，但添加熵平滑项会导致求解器对离群值更快，更强大，可区分且易于并行化。 Sinkhorn固定点算法是这些方法的基石，结果，已经进行了多次尝试以缩短其运行时，例如退火，动量或加速度。本文的前提是，\ textit {initialization}的sindhorn算法受到了相对较少的关注，可能是由于两个先入为主的：由于正规化的ot问题是凸的，因此可能不值得制定量身定制的初始化，因为\ textit {\ textit { }保证工作；其次，由于sindhorn算法在端到端管道中通常是区分的，因此数据依赖性初始化可能会通过展开迭代而获得的偏差梯度估计。我们挑战了这种传统的观点，并表明精心选择的初始化可能会导致巨大的加速，并且不会偏向梯度，这些梯度是通过隐式分化计算的。我们详细介绍如何使用1D或高斯设置中的已知结果从封闭形式或近似OT解决方案中恢复初始化。我们从经验上表明，这些初始化可以在现成的情况下使用，几乎没有调整，并且导致各种OT问题的速度持续加速。

The Sinkhorn algorithm (arXiv:1306.0895) is the state-of-the-art to compute approximations of optimal transport distances between discrete probability distributions, making use of an entropically regularized formulation of the problem. The algorithm is guaranteed to converge, no matter its initialization. This lead to little attention being paid to initializing it, and simple starting vectors like the n-dimensional one-vector are common choices. We train a neural network to compute initializations for the algorithm, which significantly outperform standard initializations. The network predicts a potential of the optimal transport dual problem, where training is conducted in an adversarial fashion using a second, generating network. The network is universal in the sense that it is able to generalize to any pair of distributions of fixed dimension. Furthermore, we show that for certain applications the network can be used independently.

Wasserstein BaryCenter是一种原理的方法来表示给定的一组概率分布的加权平均值，利用由最佳运输所引起的几何形状。在这项工作中，我们提出了一种新颖的可扩展算法，以近似于旨在在机器学习中的高维应用的Wassersein重构。我们所提出的算法基于Wassersein-2距离的Kantorovich双重制定以及最近的神经网络架构，输入凸神经网络，其已知参数化凸函数。我们方法的显着特征是：i）仅需要来自边缘分布的样本; ii）与现有方法不同，它代表了具有生成模型的重心，因此可以在不查询边际分布的情况下从重心产生无限样品; III）它与一个边际案例中的生成对抗性模型类似。我们通过在多个实验中将其与最先进的方法进行比较来证明我们的算法的功效。

在各种机器学习问题中，包括转移，多任务，连续和元学习在内，衡量不同任务之间的相似性至关重要。最新的测量任务相似性的方法依赖于体系结构：1）依靠预训练的模型，或2）在任务上进行培训网络，并将正向转移用作任务相似性的代理。在本文中，我们利用了最佳运输理论，并定义了一个新颖的任务嵌入监督分类，该分类是模型的，无训练的，并且能够处理（部分）脱节标签集。简而言之，给定带有地面标签的数据集，我们通过多维缩放和串联数据集样品进行嵌入标签，并具有相应的标签嵌入。然后，我们将两个数据集之间的距离定义为其更新样品之间的2-Wasserstein距离。最后，我们利用2-wasserstein嵌入框架将任务嵌入到矢量空间中，在该空间中，嵌入点之间的欧几里得距离近似于任务之间提出的2-wasserstein距离。我们表明，与最佳传输数据集距离（OTDD）等相关方法相比，所提出的嵌入导致任务的比较显着更快。此外，我们通过各种数值实验证明了我们提出的嵌入的有效性，并显示了我们所提出的距离与任务之间的前进和向后转移之间的统计学意义相关性。

Optimal Transport（OT）提供了一个多功能框架，以几何有意义的方式比较复杂的数据分布。计算Wasserstein距离和概率措施之间的大地测量方法的传统方法需要网络依赖性域离散化，并且受差异性的诅咒。我们提出了Geonet，这是一个网状不变的深神经操作员网络，该网络从输入对的初始和终端分布对到Wasserstein Geodesic连接两个端点分布的非线性映射。在离线训练阶段，Geonet了解了以耦合PDE系统为特征的原始和双空间中OT问题动态提出的鞍点最佳条件。随后的推理阶段是瞬时的，可以在在线学习环境中进行实时预测。我们证明，Geonet在模拟示例和CIFAR-10数据集上达到了与标准OT求解器的可比测试精度，其推断阶段计算成本大大降低了。

最佳运输（OT）理论描述了定义和选择在许多可能的选择中，将概率度量映射到另一个概率的最有效方法。该理论主要用于估计，给定一对源和目标概率测量$（\ MU，\ nu）$，这是一个可以有效地将$ \ mu $映射到$ \ nu $的参数化映射$ t_ \ theta $。在许多应用程序中，例如预测细胞对治疗的响应，数据测量$ \ mu，\ nu $（未处理/处理过的单元的功能）定义了最佳运输问题并非孤立地出现，但与上下文$ c $相关联（治疗）。为了说明并将该上下文纳入OT估计，我们介绍了Condot，一种使用上下文标签$ C_I $标记的几对测量$（\ mu_i，\ nu_i）$使用几对测量$（\ mu_i，\ nu_i）$。我们的目标是从标记对的数据集$ \ {（c_i，（（\ mu_i，\ nu_i））中提取％\}）\} $学习全局映射$ \ mathcal {t} _ {\ theta} $，不仅是预期的适合数据集中的所有对$ \ {（（c_i，（\ mu_i，\ nu_i）））\} $，即$，但应概括以产生有意义的地图$ \ Mathcal {t} _ {\ theta}（c _ {\ text {new}}）$在未看到的上下文上调节的$ c _ {\ text {new}} $。我们的方法利用并为部分输入凸神经网络提供了新颖的用法，为此我们引入了受高斯近似启发的强大而有效的初始化策略。我们仅使用对所述扰动的作用观察到遗传或治疗性扰动对单个细胞的任意组合对单个细胞的任意组合的影响的能力。

最佳运输距离（OT）已广泛应用于最近的机器学习工作作为比较概率分布的方法。当数据在高尺寸处生存时，这些都是昂贵的。Paty等人的最新工作是，2019年，专门针对使用数据的低级别投影（视为离散措施）来降低这一成本。我们扩展了这种方法，并表明，通过使用更多地图的地图族可以近距离近距离近距离。通过在给定的家庭上最大化OT来获得最佳估计。随着在将数据映射到较低维度空间之后进行OT计算，我们的方法使用原始数据维度缩放。我们用神经网络展示了这个想法。

Optimal transport (OT) has become exceedingly popular in machine learning, data science, and computer vision. The core assumption in the OT problem is the equal total amount of mass in source and target measures, which limits its application. Optimal Partial Transport (OPT) is a recently proposed solution to this limitation. Similar to the OT problem, the computation of OPT relies on solving a linear programming problem (often in high dimensions), which can become computationally prohibitive. In this paper, we propose an efficient algorithm for calculating the OPT problem between two non-negative measures in one dimension. Next, following the idea of sliced OT distances, we utilize slicing to define the sliced OPT distance. Finally, we demonstrate the computational and accuracy benefits of the sliced OPT-based method in various numerical experiments. In particular, we show an application of our proposed Sliced-OPT in noisy point cloud registration.

Optimal transport has recently been reintroduced to the machine learning community thanks in part to novel efficient optimization procedures allowing for medium to large scale applications. We propose a Python toolbox that implements several key optimal transport ideas for the machine learning community. The toolbox contains implementations of a number of founding works of OT for machine learning such as Sinkhorn algorithm and Wasserstein barycenters, but also provides generic solvers that can be used for conducting novel fundamental research. This toolbox, named POT for Python Optimal Transport, is open source with an MIT license.

分位数回归（QR）是一个强大的工具，用于估计目标变量$ \ mathrm {y} $的一个或多个条件分位数给定的解释功能$ \ boldsymbol {\ mathrm {x}}} $。 QR的一个限制是，由于其目标函数的提出，它仅针对标量目标变量定义，并且由于分位数的概念对多元分布没有标准定义。最近，由于通过最佳传输将分位数概念对多变量分布的有意义的概括，提出了矢量分位数回归（VQR）作为矢量值目标变量的QR扩展。尽管它优雅，但VQR可以说是由于几个限制而在实践中不适用：（i）假设目标$ \ boldsymbol {\ mathrm {y}} $给定功能$ \ boldsymbol {\ mathrm {\ mathrm {\ mathrm {\ mathrm { {x}} $; （ii）即使在目标维度，回归分位数或特征数量的数量方面，它的确切配方也是棘手的，即使对于适度的问题，并且其放松的双重配方可能违反了估计的分位数的单调性； （iii）当前不存在VQR的快速或可扩展求解器。在这项工作中，我们完全解决了这些局限性，即：（i）将VQR扩展到非线性情况，显示出对线性VQR的实质性改进； （ii）我们提出{矢量单调重排}，该方法可确保VQR估计的分位数函数是单调函数； （iii）我们为线性和非线性VQR提供快速的GPU加速求解器，这些求解器保持固定的内存足迹，并证明它们扩展到数百万个样品和数千个分位数； （iv）我们发布了求解器的优化Python软件包，以广泛使用VQR在现实世界应用中的使用。

Wasserstein barycenter, built on the theory of optimal transport, provides a powerful framework to aggregate probability distributions, and it has increasingly attracted great attention within the machine learning community. However, it suffers from severe computational burden, especially for high dimensional and continuous settings. To this end, we develop a novel continuous approximation method for the Wasserstein barycenters problem given sample access to the input distributions. The basic idea is to introduce a variational distribution as the approximation of the true continuous barycenter, so as to frame the barycenters computation problem as an optimization problem, where parameters of the variational distribution adjust the proxy distribution to be similar to the barycenter. Leveraging the variational distribution, we construct a tractable dual formulation for the regularized Wasserstein barycenter problem with c-cyclical monotonicity, which can be efficiently solved by stochastic optimization. We provide theoretical analysis on convergence and demonstrate the practical effectiveness of our method on real applications of subset posterior aggregation and synthetic data.

Projection robust Wasserstein (PRW) distance, or Wasserstein projection pursuit (WPP), is a robust variant of the Wasserstein distance. Recent work suggests that this quantity is more robust than the standard Wasserstein distance, in particular when comparing probability measures in high-dimensions. However, it is ruled out for practical application because the optimization model is essentially non-convex and non-smooth which makes the computation intractable. Our contribution in this paper is to revisit the original motivation behind WPP/PRW, but take the hard route of showing that, despite its non-convexity and lack of nonsmoothness, and even despite some hardness results proved by~\citet{Niles-2019-Estimation} in a minimax sense, the original formulation for PRW/WPP \textit{can} be efficiently computed in practice using Riemannian optimization, yielding in relevant cases better behavior than its convex relaxation. More specifically, we provide three simple algorithms with solid theoretical guarantee on their complexity bound (one in the appendix), and demonstrate their effectiveness and efficiency by conducing extensive experiments on synthetic and real data. This paper provides a first step into a computational theory of the PRW distance and provides the links between optimal transport and Riemannian optimization.

我们考虑人口Wasserstein Barycenter问题，用于随机概率措施支持有限一组点，由在线数据流生成。这导致了复杂的随机优化问题，其中目标是作为作为随机优化问题的解决方案给出的函数的期望。我们采用了问题的结构，并获得了这个问题的凸凹陷的随机鞍点重构。在设置随机概率措施的分布是离散的情况下，我们提出了一种随机优化算法并估计其复杂性。基于内核方法的第二个结果将前一个延伸到随机概率措施的任意分布。此外，这种新算法在许多情况下，与随机近似方法相结合的随机近似方法，具有优于随机近似方法的总复杂性。我们还通过一系列数值实验说明了我们的发展。

不平衡最佳传输（UOT）扩展了最佳传输（OT），以考虑质量变化以比较分布。这是使IT在ML应用程序中成功的至关重要，使其对数据标准化和异常值具有强大。基线算法陷入沉降，但其收敛速度可能比OT更慢。在这项工作中，我们确定了这种缺陷的原因，即缺乏迭代的全球正常化，其等效地对应于双口电的翻译。我们的第一款贡献利用了这种想法来开发一种可怕的加速陷阱算法（为UOT开发了一种可怕的陷阱算法（创建了“翻译不变的烟囱”），弥合了与OT的计算间隙。我们的第二次贡献侧重于1-D UOT，并提出了一个适用于这种翻译不变制剂的弗兰克 - 沃尔夫求解器。每个步骤的线性oracle都能求解1-D OT问题，从而导致每个迭代的线性时间复杂度。我们的最后贡献将这种方法扩展到计算1-D措施的UOT BaryCenter。数值模拟展示这三种方法带来的收敛速度改进。

比较图形等结构的对象是许多学习任务中涉及的基本操作。为此，基于最优传输（OT）的Gromov-Wasserstein（GW）距离已被证明可以成功处理相关对象的特定性质。更具体地说，通过节点连接关系，GW在图表上运行，视为特定空间上的概率测量。在OT的核心处是质量守恒的想法，这在两个被认为的图表中的所有节点之间施加了耦合。我们在本文中争辩说，这种财产可能对图形字典或分区学习等任务有害，我们通过提出新的半轻松的Gromov-Wasserstein发散来放松它。除了立即计算福利之外，我们讨论其属性，并表明它可以导致有效的图表字典学习算法。我们经验展示其对图形上的复杂任务的相关性，例如分区，聚类和完成。

最佳运输（OT）理论下潜许多新兴机器学习（ML）方法现在解决了各种任务，例如生成建模，转移学习和信息检索。然而，这些后者通常会在传统的OT设置上具有两个分布，同时留下更一般的多边缘OT配方，稍微探索。在本文中，我们研究了多边缘OT（MMOT）问题，并通过促进关于耦合的结构信息，统一其伞下的几种流行的OT方法。我们表明将这种结构信息结合到MMOT中，在允许我们在数值上解决它的不同凸（DC）编程问题的实例。尽管后一级的计算成本高，但DC优化提供的解决方案通常与使用当前采用的优化方案获得的解决方案一样定性。

在用于图形结构数据的几台机器学习任务中，所考虑的图形可以由不同数量的节点组成。因此，需要设计汇集方法，该方法将不同大小的图形表示聚合到固定大小的表示，其可以用于下游任务，例如图形分类。现有的图形池池方法没有关于图形表示的相似性和其汇总版的保证。在这项工作中，我们通过提出流池来解决这些限制，通过最小化其Wassersein距离，通过最佳地将图形表示的统计数据统计到其汇集的对应物。这是通过对汇集的图形表示来执行Wasserstein梯度流来实现的。我们提出了我们的方法，可以通过任何基础成本考虑表示空间的几何形状。该实施依赖于与最近提出的隐式差异化方案的Wasserstein距离的计算。我们的汇集方法可用于自动分化，可以集成在端到端的深度学习架构中。此外，流量池是不变的，因此可以与GNN中的置换设备提取层组合，以便获得与节点的排序无关的预测。实验结果表明，与现有在图形分类任务中的现有汇集方法相比，我们的方法导致性能增加。

Optimal Transport (OT) provides a useful geometric framework to estimate the permutation matrix under unsupervised cross-lingual word embedding (CLWE) models that pose the alignment task as a Wasserstein-Procrustes problem. However, linear programming algorithms and approximate OT solvers via Sinkhorn for computing the permutation matrix come with a significant computational burden since they scale cubically and quadratically, respectively, in the input size. This makes it slow and infeasible to compute OT distances exactly for a larger input size, resulting in a poor approximation quality of the permutation matrix and subsequently a less robust learned transfer function or mapper. This paper proposes an unsupervised projection-based CLWE model called quantized Wasserstein Procrustes (qWP). qWP relies on a quantization step of both the source and target monolingual embedding space to estimate the permutation matrix given a cheap sampling procedure. This approach substantially improves the approximation quality of empirical OT solvers given fixed computational cost. We demonstrate that qWP achieves state-of-the-art results on the Bilingual lexicon Induction (BLI) task.

我们研究了两种可能不同质量的度量之间的不平衡最佳运输（UOT），其中最多是$ n $组件，其中标准最佳运输（OT）的边际约束是通过kullback-leibler差异与正则化因子$ \ tau $放松的。尽管仅在文献中分析了具有复杂性$ o \ big（\ tfrac {\ tau n^2 \ log（n）} {\ varepsilon} \ log \ big（\ tfrac {\ log（ n）} {{{\ varepsilon}} \ big）\ big）$）$用于实现错误$ \ varepsilon $，它们与某些深度学习模型和密集的输出运输计划不兼容，强烈阻碍了实用性。虽然被广泛用作计算现代深度学习应用中UOT的启发式方法，并且在稀疏的OT中表现出成功，但尚未正式研究用于UOT的梯度方法。为了填补这一空白，我们提出了一种基于梯度外推法（Gem-uot）的新颖算法，以找到$ \ varepsilon $ -Approximate解决方案，以解决$ o \ big中的UOT问题（\ kappa n^2 \ log \ log \ big（big） \ frac {\ tau n} {\ varepsilon} \ big）\ big）$，其中$ \ kappa $是条件号，具体取决于两个输入度量。我们的算法是通过优化平方$ \ ell_2 $ -norm UOT目标的新的双重配方设计的，从而填补了缺乏稀疏的UOT文献。最后，我们在运输计划和运输距离方面建立了UOT和OT之间近似误差的新颖表征。该结果阐明了一个新的主要瓶颈，该瓶颈被强大的OT文献忽略了：尽管OT放松了OT，因为UOT承认对离群值的稳健性，但计算出的UOT距离远离原始OT距离。我们通过基于Gem-uot从UOT中检索的原则方法来解决此类限制，并使用微调的$ \ tau $和后进程投影步骤来解决。关于合成和真实数据集的实验验证了我们的理论，并证明了我们的方法的良好性能。