论文标题
关于不平衡的最佳运输：梯度方法，稀疏性和近似误差
On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error
论文作者
论文摘要
我们研究了两种可能不同质量的度量之间的不平衡最佳运输（UOT），最多$ n $组件，其中标准最佳传输的边际约束（OT）是通过kullback-lebler差异和正则化因子$τ$放松的。尽管仅在文献中分析了$ {o} \ big（\ tfrac {τ\ log（n）} {\ varepsilon} \ log \ log \ big big big（\ big big）（\ tfrac { $ o（n^2）$用于达到所需的错误$ \ varepsilon $，其积极的致密输出运输计划极大地阻碍了实用性。另一方面，虽然被用作计算现代深度学习应用中UOT的启发式方法，并且在稀疏的OT问题中表现出成功，但尚未正式研究应用于UOT的梯度方法。在本文中，我们提出了一种基于梯度外推法（Gem-uot）的新颖算法，以找到$ \ o \ big（κ\ log \ big（\ frac {\ frac {° $ \ widetilde {o}（n^2）$每题费，其中$κ$是条件编号，具体取决于两个输入度量。我们的证明技术是基于平方$ \ ell_2 $ -norm UOT目标的新颖双重配方，该配方填充了缺乏稀疏的UOT文献，并且还导致了UOT和OT之间近似误差的新特征。为此，我们进一步提出了从UOT中检索OT的新方法，UOT是基于Gem-uot，带有微调的$τ$和后进程的投影步骤。关于合成和真实数据集的广泛实验验证了我们的理论，并证明了我们方法在实践中的有利性能。
We study the Unbalanced Optimal Transport (UOT) between two measures of possibly different masses with at most $n$ components, where the marginal constraints of standard Optimal Transport (OT) are relaxed via Kullback-Leibler divergence with regularization factor $τ$. Although only Sinkhorn-based UOT solvers have been analyzed in the literature with the iteration complexity of ${O}\big(\tfrac{τ\log(n)}{\varepsilon} \log\big(\tfrac{\log(n)}{\varepsilon}\big)\big)$ and per-iteration cost of $O(n^2)$ for achieving the desired error $\varepsilon$, their positively dense output transportation plans strongly hinder the practicality. On the other hand, while being vastly used as heuristics for computing UOT in modern deep learning applications and having shown success in sparse OT problem, gradient methods applied to UOT have not been formally studied. In this paper, we propose a novel algorithm based on Gradient Extrapolation Method (GEM-UOT) to find an $\varepsilon$-approximate solution to the UOT problem in $O\big( κ\log\big(\frac{τn}{\varepsilon}\big) \big)$ iterations with $\widetilde{O}(n^2)$ per-iteration cost, where $κ$ is the condition number depending on only the two input measures. Our proof technique is based on a novel dual formulation of the squared $\ell_2$-norm UOT objective, which fills the lack of sparse UOT literature and also leads to a new characterization of approximation error between UOT and OT. To this end, we further present a novel approach of OT retrieval from UOT, which is based on GEM-UOT with fine tuned $τ$ and a post-process projection step. Extensive experiments on synthetic and real datasets validate our theories and demonstrate the favorable performance of our methods in practice.
