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

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.

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, 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.

本文介绍了一种新的基于仿真的推理程序，以对访问I.I.D. \ samples的多维概率分布进行建模和样本，从而规避明确建模密度函数或设计Markov Chain Monte Carlo的通常方法。我们提出了一个称为可逆的Gromov-monge（RGM）距离的新概念的距离和同构的动机，并研究了RGM如何用于设计新的转换样本，以执行基于模拟的推断。我们的RGM采样器还可以估计两个异质度量度量空间之间的最佳对齐$（\ cx，\ mu，c _ {\ cx}）$和$（\ cy，\ cy，\ nu，c _ {\ cy}）$从经验数据集中，估计的地图大约将一个量度$ \ mu $推向另一个$ \ nu $，反之亦然。我们研究了RGM距离的分析特性，并在轻度条件下得出RGM等于经典的Gromov-Wasserstein距离。奇怪的是，与Brenier的两极分解结合了连接，我们表明RGM采样器以$ C _ {\ cx} $和$ C _ {\ cy} $的正确选择诱导了强度同构的偏见。研究了有关诱导采样器的收敛，表示和优化问题的统计率。还展示了展示RGM采样器有效性的合成和现实示例。

在数据集中定义样本之间有意义的距离是机器学习中的一个基本问题。最佳传输（OT）在样品之间提高特征（“地面度量”）到几何意义上的距离之间的距离。但是，通常没有直接的地面度量选择。有监督的地面度量学习方法存在，但需要标记的数据。在没有标签的情况下，仅保留临时地面指标。因此，无监督的地面学习是启用数据驱动的OT应用程序的基本问题。在本文中，我们首次通过同时计算样本之间和数据集功能之间的OT距离来提出规范答案。这些距离矩阵自然出现，作为函数映射接地指标的正奇异向量。我们提供标准以确保这些奇异向量的存在和独特性。然后，我们使用随机近似和熵正则化引入可扩展的计算方法以在高维设置中近似它们。最后，我们在单细胞RNA测序数据集上展示了Wasserstein奇异向量。

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

Monge Map是指两个概率分布之间的最佳运输映射，并提供了将一个分发转换为另一个的原则方法。尽管最佳运输问题的数值方法的快速发展，但计算Monge地图仍然具有挑战性，特别是对于高维问题。在本文中，我们提出了一种可扩展算法，用于计算两个概率分布之间的Monge地图。我们的算法基于最佳运输问题的弱形式，因此它仅需要来自边缘的样本而不是其分析表达式，并且可以容纳两个具有不同尺寸的分布之间的最佳运输。我们的算法适用于一般成本函数，与其他现有方法相比，用于使用样本估计Monge Maps的方法，这些方法通常用于二次成本。通过具有合成和现实数据的一系列实验来证明我们的算法的性能。

在概率密度范围内相对于Wassersein度量的空间的梯度流程通常具有很好的特性，并且已在几种机器学习应用中使用。计算Wasserstein梯度流量的标准方法是有限差异，使网格上的基础空间离散，并且不可扩展。在这项工作中，我们提出了一种可扩展的近端梯度型算法，用于Wassersein梯度流。我们的方法的关键是目标函数的变分形式，这使得可以通过引流 - 双重优化实现JKO近端地图。可以通过替代地更新内部和外环中的参数来有效地解决该原始问题。我们的框架涵盖了包括热方程和多孔介质方程的所有经典Wasserstein梯度流。我们展示了若干数值示例的算法的性能和可扩展性。

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

引入了Wasserstein距离的许多变体，以减轻其原始计算负担。尤其是切成薄片的距离（SW），该距离（SW）利用了一维投影，可以使用封闭式的瓦斯汀距离解决方案。然而，它仅限于生活在欧几里得空间中的数据，而Wasserstein距离已被研究和最近在歧管上使用。我们更具体地专门地关注球体，为此定义了新颖的SW差异，我们称之为球形切片 - 拖鞋，这是朝着定义SW差异的第一步。我们的构造明显基于圆圈上瓦斯汀距离的封闭式解决方案，以及新的球形ra径。除了有效的算法和相应的实现外，我们在几个机器学习用例中说明了它的属性，这些用例中，数据的球形表示受到威胁：在球体上的密度估计，变异推理或超球体自动编码器。

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

比较概率分布是许多机器学习算法的关键。最大平均差异（MMD）和最佳运输距离（OT）是在过去几年吸引丰富的关注的概率措施之间的两类距离。本文建立了一些条件，可以通过MMD规范控制Wassersein距离。我们的作品受到压缩统计学习（CSL）理论的推动，资源有效的大规模学习的一般框架，其中训练数据总结在单个向量（称为草图）中，该训练数据捕获与所考虑的学习任务相关的信息。在CSL中的现有结果启发，我们介绍了H \“较旧的较低限制的等距属性（H \”较旧的LRIP）并表明这家属性具有有趣的保证对压缩统计学习。基于MMD与Wassersein距离之间的关系，我们通过引入和研究学习任务的Wassersein可读性的概念来提供压缩统计学习的保证，即概率分布之间的某些特定于特定的特定度量，可以由Wassersein界定距离。

在共享潜在空间中对齐两个或更多个分布的无监督任务具有许多应用，包括公平表示，批量效果缓解和无监督域适应。现有的基于流动的方法独立估计多个流动，这相当于学习多个完整的生成模型。其他方法需要对抗性学习，这可以是可以计算地昂贵和挑战的优化。因此，我们的目标是在避免对抗性学习的同时联合对齐多个分布。通过从最佳运输（OT）理论的高效对准算法的启发，我们开发了一种简单的迭代方法来构建深层和富有效力的流动。我们的方法将每次迭代分成两个子问题：1）形成分配分配的变化近似，并且2）通过基于已知的OT结果的闭合形式可逆对准映射最小化该变分近似。我们的经验结果证明了这种迭代算法以低计算成本实现了竞争分布对准，同时能够自然地处理两个以上的分布。

Wasserstein生成的对抗网络（WGANS）是基于最佳运输理论（OT）和Kantorovich二元性的流行生成模型。尽管WGAN取得了成功，但仍不清楚基础双求解器的基础差如何近似OT成本（Wasserstein-1距离，$ \ Mathbb {W} _ {1} $）和更新发电机所需的OT梯度。在本文中，我们解决了这些问题。我们构建1-卢比奇的功能，并使用它们来构建射线单调传输计划。该策略在高维空间（例如图像空间）中产生了与分析已知的OT计划，OT成本和OT梯度的连续基准分布对。我们使用这些基准对彻底评估了流行的wgan双表求解器（梯度惩罚，光谱归一化，熵正则化等）。即使这些求解器在WGAN中表现良好，也没有一个忠实地计算出高维度的$ \ Mathbb {w} _ {1} $。然而，许多人提供了OT梯度的有意义的近似。这些观察结果表明，这些求解器不应被视为$ \ mathbb {w} _ {1} $的良好估计量，但在某种程度上，它们确实可以用于各种问题，需要最小化$ \ mathbb {w} _ { 1} $。

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.

A normalizing flow (NF) is a mapping that transforms a chosen probability distribution to a normal distribution. Such flows are a common technique used for data generation and density estimation in machine learning and data science. The density estimate obtained with a NF requires a change of variables formula that involves the computation of the Jacobian determinant of the NF transformation. In order to tractably compute this determinant, continuous normalizing flows (CNF) estimate the mapping and its Jacobian determinant using a neural ODE. Optimal transport (OT) theory has been successfully used to assist in finding CNFs by formulating them as OT problems with a soft penalty for enforcing the standard normal distribution as a target measure. A drawback of OT-based CNFs is the addition of a hyperparameter, $\alpha$, that controls the strength of the soft penalty and requires significant tuning. We present JKO-Flow, an algorithm to solve OT-based CNF without the need of tuning $\alpha$. This is achieved by integrating the OT CNF framework into a Wasserstein gradient flow framework, also known as the JKO scheme. Instead of tuning $\alpha$, we repeatedly solve the optimization problem for a fixed $\alpha$ effectively performing a JKO update with a time-step $\alpha$. Hence we obtain a "divide and conquer" algorithm by repeatedly solving simpler problems instead of solving a potentially harder problem with large $\alpha$.

最佳运输（OT）背后的匹配原理在机器学习中起着越来越重要的作用，这一趋势可以观察到ot被用来消除应用程序中的数据集（例如，单细胞基因组学）或用于改善更复杂的方法（例如，平衡平衡）注意变形金刚或自我监督的学习）。为了扩展到更具挑战性的问题，越来越多的共识要求求解器可以在数百万而不是数千点上运作。在\ cite {scetbon2021lowrank}中提倡的低级最佳运输方法（LOT）方法在这方面有几个诺言，并被证明可以补充更确定的熵正则化方法，能够将自己插入更复杂的管道中，例如Quadratic OT。批次将低成本耦合的搜索限制在具有低位级等级的耦合方面，在感兴趣的情况下产生线性时间算法。但是，只有在比较感兴趣的属性时，只有将批次方法视为熵正则化的合法竞争者，这些诺言才能实现，记分卡通常包含理论属性（统计复杂性和与其他方法）或实际方面（偏见，偏见，偏见，依据，，依据，统计复杂性和关系）高参数调整，初始化）。我们针对本文中的每个领域，以巩固计算OT中低级别方法的影响。

分发比较在许多机器学习任务中起着核心作用，例如数据分类和生成建模。在这项研究中，我们提出了一种称为希尔伯特曲线投影（HCP）距离的新型度量，以测量具有高鲁棒性和低复杂性的两个概率分布之间的距离。特别是，我们首先使用希尔伯特曲线投射两个高维概率密度，以获得它们之间的耦合，然后根据耦合在原始空间中这两个密度之间的传输距离进行计算。我们表明，HCP距离是一个适当的度量标准，对于绝对连续的概率度量，定义明确。此外，我们证明，经验HCP距离在规律性条件下以不超过$ O（n^{ - 1/2d}）$的速度收敛到其人口。为了抑制差异性的诅咒，我们还使用（可学习的）子空间投影开发了HCP距离的两个变体。合成数据和现实世界数据的实验表明，我们的HCP距离是瓦斯汀距离的有效替代，其复杂性低并克服了切成薄片的瓦斯坦距离的缺点。

最近表明，在光滑状态下，可以通过吸引统计误差上限可以有效地计算两个分布之间的平方Wasserstein距离。然而，而不是距离本身，生成建模等应用的感兴趣对象是底层的最佳运输地图。因此，需要为估计的地图本身获得计算和统计保证。在本文中，我们提出了第一种统计$ L ^ 2 $错误的第一批量算法几乎匹配了现有的最低限度用于平滑地图估计。我们的方法是基于解决具有无限尺寸的平方和重构的最佳运输的半双向配方，并导致样品数量的无尺寸多项式速率的算法，具有潜在指数的维度依赖性常数。