\begin{document}

\begin{center}

{\bf{\LARGE{Projection Robust Wasserstein Distance and Riemannian Optimization}}}

\vspace*{.2in}
{\large{
\begin{tabular}{ccccc}
Tianyi Lin$^{*, \diamond}$ & Chenyou Fan$^{*, \circ, \square}$ & Nhat Ho$^\ddagger$ & Marco Cuturi$^{\triangleleft, \triangleright}$ & Michael I. Jordan$^{\diamond, \dagger}$ \\
 \end{tabular}
}}

\vspace*{.2in}

\begin{tabular}{c}
Department of Electrical Engineering and Computer Sciences$^\diamond$ \\
Department of Statistics$^\dagger$ \\ 
University of California, Berkeley \\
The Chinese University of Hong Kong, Shenzhen$^\square$ \\
Department of Statistics and Data Sciences, University of Texas, Austin$^\ddagger$ \\ 
CREST - ENSAE$^\triangleleft$, Google Brain$^\triangleright$
\end{tabular}

\vspace*{.2in}


\today

\vspace*{.2in}

\begin{abstract}
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 conducting 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. 
\end{abstract}
\let\thefootnote\relax\footnotetext{$^*$ Tianyi Lin and Chenyou Fan contributed equally to this work.}
\let\thefootnote\relax\footnotetext{$^\circ$ Chenyou Fan contributed during working at Google.}
\end{center}

\input{sec/intro}
\input{sec/background}
\input{sec/algorithm}
\input{sec/experiment}
\input{sec/conclusion}


\section{Acknowledgements}
We would like to thank Minhui Huang for very helpful discussion with the proof of Lemma 3.4 and Theorem 3.7. This work is supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number N00014-18-1-2764.


\bibliographystyle{plainnat}
\bibliography{ref}


\input{sec/appendix}

\end{document}
{"config": "arxiv", "file": "2006.07458/Arxiv_submission.tex"}