Timezone: »

 
Poster
On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
Tianyi Lin · Nhat Ho · Michael Jordan

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #181
in Posters Tue »
We provide theoretical analyses for two algorithms that solve the regularized optimal transport (OT) problem between two discrete probability measures with at most $n$ atoms. We show that a greedy variant of the classical Sinkhorn algorithm, known as the \emph{Greenkhorn algorithm}, can be improved to $\bigOtil\left(n^2/\varepsilon^2\right)$, improving on the best known complexity bound of $\bigOtil\left(n^2/\varepsilon^3\right)$. This matches the best known complexity bound for the Sinkhorn algorithm and helps explain why the Greenkhorn algorithm outperforms the Sinkhorn algorithm in practice. Our proof technique is based on a primal-dual formulation and provide a \textit{tight} upper bound for the dual solution, leading to a class of \emph{adaptive primal-dual accelerated mirror descent} (APDAMD) algorithms. We prove that the complexity of these algorithms is $\bigOtil\left(n^2\sqrt{\gamma}/\varepsilon\right)$ in which $\gamma \in (0, n]$ refers to some constants in the Bregman divergence. Experimental results on synthetic and real datasets demonstrate the favorable performance of the Greenkhorn and APDAMD algorithms in practice.
Keywords: Computational Learning Theory · Convex Optimization · Metric Learning · Optimization - Others

Author Information

Tianyi Lin (UC Berkeley)
Nhat Ho (University of California, Berkeley)
Michael Jordan (UC Berkeley)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors