Faster Computation of Entropic Optimal Transport via Stable Low Frequency Modes
In this paper, we propose an accelerated version for the Sinkhorn algorithm, which is the reference method for computing the solution to Entropic Optimal Transport. Its main draw-back is the exponential slow-down of convergence as the regularization weakens $\varepsilon \rightarrow 0$. Thanks to spectral insights on the behavior of the Hessian, we propose to mitigate the problem via an original spectral warm-start strategy. This leads to faster convergence compared to the reference method, as also demonstrated in our numerical experiments.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An improved central limit theorem and fast convergence rates for entropic transportation costs
We prove a central limit theorem for the entropic transportation cost between subgaussian probability measures, centered at the population cost. This is the first result which allows for asymptotically valid inference fo…
validSinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
Optimal transportation distances are a fundamental family of parameterized distances for histograms. Despite their appealing theoretical properties, excellent performance in retrieval tasks and intuitive formulation, the…
RetrievalSinkhorn Distances: Lightspeed Computation of Optimal Transport
Optimal transportation distances are a fundamental family of parameterized distances for histograms in the probability simplex. Despite their appealing theoretical properties, excellent performance and intuitive formulat…
Progressive Entropic Optimal Transport Solvers
Optimal transport (OT) has profoundly impacted machine learning by providing theoretical and computational tools to realign datasets. In this context, given two large point clouds of sizes $n$ and $m$ in $\mathbb{R}^d$, …
Entropic estimation of optimal transport maps
We develop a computationally tractable method for estimating the optimal map between two distributions over $\mathbb{R}^d$ with rigorous finite-sample guarantees. Leveraging an entropic version of Brenier's theorem, we s…