提出新型无约束梯度算法，高效求解最优传输中位数
Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysis
- 基于Sobolev几何设计梯度上升算法，无需复杂的c-凹投影
- 理论证明全局收敛速度与经典方法相当，达到最优率
- 适合需要精确中位数计算的高维分布建模任务
本文提出一种新的无约束凹对偶公式来求解Wasserstein中位数。针对Kantorovich对偶势函数的Sobolev几何，我们设计了可扩展的Sobolev梯度上升（SGA）算法，用于在规则网格上离散化分布的中位数计算。尽管算法结构简单，我们仍给出了全局收敛性分析，其收敛速率与欧氏空间中最小化非光滑凸函数的经典次梯度下降法相同。本算法的核心优势在于：无需强制执行计算昂贵的c-凹投影算子即可保证收敛，相较于现有所有原始与对偶方法，实现了显著的算法与理论简化。数值实验表明，SGA在性能上优于现有最优传输中位数求解器。
原文摘要 · Abstract (English)
This paper introduces a new constraint-free concave dual formulation for the Wasserstein barycenter. Tailoring the vanilla dual gradient ascent algorithm to the Sobolev geometry, we derive a scalable Sobolev gradient ascent (SGA) algorithm to compute the barycenter for input distributions discretized over a regular grid. Despite the algorithmic simplicity, we provide a global convergence analysis that achieves the same rate as the classical subgradient descent methods for minimizing nonsmooth convex functions in the Euclidean space. A central feature of our SGA algorithm is that the computationally expensive $c$-concavity projection operator enforced on the Kantorovich dual potentials is unnecessary to guarantee convergence, leading to significant algorithmic and theoretical simplifications over all existing primal and dual methods for computing the exact barycenter. Our numerical experiments demonstrate the superior empirical performance of SGA over the existing optimal transport barycenter solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。