%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Jacobs Landscape Poster
% LaTeX Template
% Version 1.1 (14/06/14)
%
% Created by:
% Computational Physics and Biophysics Group, Jacobs University
% https://teamwork.jacobs-university.de:8443/confluence/display/CoPandBiG/LaTeX+Poster
% 
% Further modified by:
% Nathaniel Johnston (nathaniel@njohnston.ca)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[final]{beamer}

\usepackage[scale=1,size=a0,orientation=portrait]{beamerposter} % Use the beamerposter package for laying out the poster
\usepackage{multicol}
\usepackage{scrextend}
\changefontsizes{24pt}

\RequirePackage{tikz}		% for drawing the nice rounded boxes
\usetikzlibrary{arrows,backgrounds}
\RequirePackage[T1]{fontenc}
\RequirePackage{lmodern}
\usepackage{exscale}
\RequirePackage{textcomp}
\RequirePackage{amsmath,amssymb}
\usefonttheme{professionalfonts}
\usepackage{color}
\newcommand{\makeruleinbox}{{\usebeamercolor[bg]{block alerted title}\centering\hspace*{-0.7cm}\rule{\inboxrule}{0.5cm}}}
\usepackage{ragged2e}
\usepackage{changepage}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\algtext*{EndWhile}% Remove "end while" text
\algtext*{EndIf}% Remove "end if" text
\usepackage{caption}
\DeclareCaptionFormat{myformat}{#3}
\captionsetup[algorithm]{format=myformat}


\usepackage{pgffor}
\usepackage{pgfplots}
\usepackage{tikz,tkz-euclide}
\usepackage{tikz-3dplot}
\usetikzlibrary{shapes.multipart,calc}
\usetikzlibrary{decorations.markings}
\usetikzlibrary{arrows.meta}
\usepackage[export]{adjustbox}
\usepackage{rotating} % for vertical legends in figs

\usetheme{metropolis} % Use the confposter theme supplied with this template

\setsansfont[BoldFont={Fira Sans SemiBold}]{Fira Sans Book}




\renewcommand{\t}[1]{#1^{\mathsf{T}}}
\usepackage{mathtools}

\usepackage{xstring}	%\StrSubstitutees
\usepackage{ifthen}
\newcommand{\zp}[2][p]{%
  \!\IfStrEqCase{#1}{%
    {p}{\left(}%
    {c}{\:\left[}%
    {a}{\left\{}%
    {abs}{\left|}%
    {n}{\left\|}%
    {s}{\langle}%
    {i}{\left[\!\left[}%
  }[\left(]%
    #2%
  \IfStrEqCase{#1}{%
    {p}{\right)}%
    {c}{\right]}%
    {a}{\right\}}%
    {abs}{\right|}%
    {n}{\right\|}%
    {s}{\rangle}%
    {i}{\right]\!\right]}%
  }[\right)]%
} 

\usepackage{notations}
\usepackage{multicol}
\usepackage{array, multirow}    % for the first table
\usepackage{paracol}



\usepackage{import}
\setlength{\paperwidth}{900mm} % A0 width: 46.8in
\setlength{\paperheight}{1200mm} % A0 height: 33.1in

\newlength{\threecolwidth} \setlength{\threecolwidth}{230mm}
\newlength{\threecolinwidth} \setlength{\threecolinwidth}{190mm}
\newlength{\contribcolwidth} \setlength{\contribcolwidth}{290mm}
\newlength{\contribcolinwidth} \setlength{\contribcolinwidth}{250mm}
\newlength{\threecolheight} \setlength{\threecolheight}{145mm}


\newlength{\whitemargin} \setlength{\whitemargin}{35mm}

\newlength{\onecolwidth}   \setlength{\onecolwidth}{820mm}
\newlength{\onecolinwidth} \setlength{\onecolinwidth}{780mm}
\newlength{\onecolheight}  \setlength{\onecolheight}{185mm}


\newlength{\twocolwidth}  \setlength{\twocolwidth}{392mm}
\newlength{\twocolinwidth} \setlength{\twocolinwidth}{352mm}
\newlength{\twocolheight} \setlength{\twocolheight}{120mm}
\newlength{\twocolheighttwo} \setlength{\twocolheighttwo}{126mm}


\newlength{\footerheight} \setlength{\footerheight}{80mm}
\newlength{\refcolwidth}  \setlength{\refcolwidth}{500mm}
\newlength{\refcolinwidth} \setlength{\refcolinwidth}{460mm}
\newlength{\contactcolwidth}  \setlength{\contactcolwidth}{330mm}
\newlength{\contactcolinwidth} \setlength{\contactcolinwidth}{190mm}

\definecolor{lgreen} {RGB}{180,210,100}
\definecolor{dblue}  {RGB}{20,66,129}
\definecolor{ddblue} {RGB}{11,36,69}
\definecolor{lred}   {RGB}{220,0,0}
\definecolor{nred}   {RGB}{224,0,0}
\definecolor{norange}{RGB}{230,120,20}
\definecolor{nyellow}{RGB}{255,221,0}
\definecolor{ngreen} {RGB}{98,158,31}
\definecolor{dgreen} {RGB}{78,138,21}
\definecolor{nblue}  {RGB}{28,130,185}
\definecolor{jblue}  {RGB}{20,50,100}
\definecolor{links}  {RGB}{10,160,200}

\definecolor{mDarkBrown}{HTML}{604c38}
\definecolor{mDarkTeal}{HTML}{23373b}
\definecolor{mLightBrown}{HTML}{EB811B}
\definecolor{mLightGreen}{HTML}{14B03D}

\definecolor{mSeparation}{HTML}{EB811B}


\definecolor{mProgressGray}{RGB}{77,77,77}
\definecolor{mBackground}{HTML}{FAFAFA}




\definecolor{mSeparation}{HTML}{EB811B}
\definecolor{mBackground}{HTML}{FAFAFA}
\definecolor{blocktitle}{RGB}{20,50,100}
\setbeamercolor{block title}{fg=blocktitle,bg=mBackground!93!black}
\setbeamercolor{block body}{fg=black,bg=mBackground!96!black}
\setbeamercolor{block alerted title}{fg=mLightBrown,bg=mBackground!96!black}


\definecolor{om}{RGB}{0,0,200}
\newcommand{\om}[1]{\textcolor{om}{#1}}





\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=6pt] (char) {#1};}}


\setbeamertemplate{headline}{
 \leavevmode
  \begin{columns}
   \begin{column}{900mm}
    \vskip2cm
    \centering
    \usebeamercolor{title in headline}{\color{jblue}\Huge{\textbf{\inserttitle}}\\[0.5ex]}
    \usebeamercolor{title in headline}{\color{jblue}\Large{\textbf{De-biasing} the Sinkhorn loop to prevent the measures' supports from \textbf{shrinking}.}\\[1.2ex]}
    \usebeamercolor{author in headline}{\color{fg}\Large{\insertauthor}\\[.6ex]}
    \usebeamercolor{institute in headline}{\color{fg}\large{\insertinstitute}\\[1ex]}
    \vskip1cm
    
   \begin{flushleft}
      \begin{tikzpicture}[remember picture,overlay]
            \fill [color=mSeparation]
            (0,0) rectangle (\textwidth,0.2cm);
       \end{tikzpicture}
   \end{flushleft} 
   \end{column}
   \vspace{1cm}
   
  \end{columns}
 \vspace{0.5in}
 \hspace{0.5in}\begin{beamercolorbox}[wd=800mm,colsep=0.15cm]{cboxb}\end{beamercolorbox}
 \vspace{0.1in}
}
\newlength{\inboxwd}
\newlength{\iinboxwd}
\newlength{\inboxrule}
\makeatletter
\makeatother

% Block definition
\setbeamertemplate{block begin}
{
  \par\vskip\medskipamount
  \begin{beamercolorbox}[colsep*=0ex,dp={2ex},center]{block title}
    \vskip0.25cm
    \usebeamerfont{block title}\Large\insertblocktitle
    \begin{flushleft}
    \vskip-1cm
      \begin{tikzpicture}[remember picture,overlay]
            \fill [color=mSeparation]
            (0,0) rectangle (\textwidth,0.1cm);
       \end{tikzpicture}
    \end{flushleft}
  \end{beamercolorbox}
  {\parskip0pt\par}
  \ifbeamercolorempty[bg]{block title}
  {}
  {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}}
  \usebeamerfont{block body}
  \vskip-1.5cm
  \begin{beamercolorbox}[colsep*=0ex,dp={2ex},center]{block body}
  \justifying
}

\setbeamertemplate{block end}
{
  \end{beamercolorbox}
  \vskip\smallskipamount
}

\addtobeamertemplate{block begin}
  {}
  {\vspace{.5cm plus 0.5ex minus 0.5ex} % Pads top of block
     % separates paragraphs in a block
   \setlength{\parskip}{24pt plus 1pt minus 1pt}%
   \begin{adjustwidth}{2cm}{2cm}
}
\addtobeamertemplate{block end}
  {\end{adjustwidth}%
   \vspace{2ex plus 0.5ex minus 0.5ex}}% Pads bottom of block
  {\vspace{4ex plus 1ex minus 1ex}} % Seperates blocks from each other


\setbeamertemplate{block alerted begin}
{
  \par\vskip\medskipamount
  \begin{beamercolorbox}[colsep*=0ex,dp={2ex},left]{block alerted title}
    \vskip0.25cm
    \usebeamerfont{block alerted title}\large~~~~~\insertblocktitle
  \end{beamercolorbox}
  {\parskip0pt\par}
  \ifbeamercolorempty[bg]{block title}
  {}
  {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}}
  \usebeamerfont{block body}
  \vskip-.5cm
  \begin{beamercolorbox}[colsep*=0ex,center]{block body}
  \justifying
}

\addtobeamertemplate{block alerted begin}
  {}
  {\vspace{0cm plus 0.5ex minus 0.5ex} % Pads top of block
     % separates paragraphs in a block
   \setlength{\parskip}{24pt plus 1pt minus 1pt}%
   \begin{adjustwidth}{2cm}{2cm}
}
\addtobeamertemplate{block alerted end}
  {\end{adjustwidth}%
   \vspace{.5cm plus 0.5ex minus 0.5ex}}% Pads bottom of block
  {\vspace{4ex plus 1ex minus 1ex}} % Seperates blocks from each other










\usepackage{natbib}
\bibliographystyle{myalpha}
% make bibliography entries smaller
\renewcommand\bibfont{\fontsize{8}{9.6}\selectfont}
% If you have more than one page of references, you want to tell beamer
% to put the continuation section label from the second slide onwards
\setbeamertemplate{frametitle continuation}[from second]
% Now get rid of all the colours
\setbeamercolor*{bibliography entry title}{fg=black}
\setbeamercolor*{bibliography entry author}{fg=black}
\setbeamercolor*{bibliography entry location}{fg=black}
\setbeamercolor*{bibliography entry note}{fg=black}
% and kill the abominable icon
\setbeamertemplate{bibliography item}{}

\setlength{\bibsep}{0pt}








%\setbeamercolor{block title}{fg=ngreen,bg=white} % Colors of the block titles
%\setbeamercolor{block body}{fg=black,bg=white} % Colors of the body of blocks
%\setbeamercolor{block alerted title}{fg=white,bg=dblue!70} % Colors of the highlighted block titles
%\setbeamercolor{block alerted body}{fg=black,bg=dblue!10} % Colors of the body of highlighted blocks
% Many more colors are available for use in beamerthemeconfposter.sty

\usepackage{graphicx}  % Required for including images

\usepackage{booktabs} % Top and bottom rules for tables
\newcommand{\samelineand}{\qquad}
\makeatletter
\def\beamer@andinst{\\[0.2em]}
\makeatother

%----------------------------------------------------------------------------------------
%	TITLE SECTION 
%----------------------------------------------------------------------------------------

\title{Interpolating between Optimal Transport and MMD with Sinkhorn divergences} % Poster title

\author{Jean Feydy\inst{1,2} \and Thibault Séjourné\inst{1} 
\and  François-Xavier Vialard\inst{3} \and Shun-ichi Amari\inst{4} \and 
Alain Trouvé \inst{2} \and Gabriel Peyré\inst{1} }

\institute{
\inst{1} DMA, École Normale Supérieure
\samelineand
\inst{2} CMLA, ENS Paris-Saclay
\samelineand
\inst{3} LIGM, UPEM
\samelineand
\inst{4} Brain Science Institute, RIKEN
}

%----------------------------------------------------------------------------------------

\begin{document}

%\addtobeamertemplate{block end}{}{\vspace*{2ex}} % White space under blocks
%\addtobeamertemplate{block alerted end}{}{\vspace*{2ex}} % White space under highlighted (alert) blocks

%\setlength{\belowcaptionskip}{2ex} % White space under figures
%\setlength\belowdisplayshortskip{-1.5cm} % White space under equations

\begin{frame}[t,fragile] % The whole poster is enclosed in one beamer frame

\begin{columns}[t]


% The first two columns are in blue %%%%%%%%%%%%
\definecolor{mSeparation}{HTML}{54A9FF}%
\definecolor{mBackground}{HTML}{E5F5FF}%
\definecolor{blocktitle}{HTML}{004484}%
\setbeamercolor{block title}{fg=blocktitle,bg=mBackground!93!black}%
\setbeamercolor{block body}{fg=black,bg=mBackground!96!black}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\begin{column}{\whitemargin}
\end{column}

\begin{column}{\threecolwidth} % The first column
\begin{block}{ \circled{1} ~~Optimal Transport + Entropy~~~}
\minipage[t][\threecolheight][t]{\threecolinwidth}

If $\al$, $\be$ are Radon probability measures
on a compact feature space $\Xx$ endowed with a Lipschitz cost function 
$\dgreen{ \C : (x,y)\mapsto \C(x,y)}$
~(e.g. $\tfrac{1}{p}\|x-y\|^p$),
\textbf{Entropy-regularized OT} \cite{schrodinger1932theorie} is defined through: 

\vspace{-.5cm}
\centerline{
  \begin{minipage}{\linewidth}
\begin{align*}
&\OT_\varepsilon(\al,\be) ~=~
\text{Transport Cost} ~+~ \varepsilon\cdot \text{Entropy}\\
~&=~
\min_{0\leqslant \pi \ll \al\otimes\be}
\zp[s]{\pi, \C}
+ \varepsilon\, \KL(\pi, \al\otimes\be) ~~~
\text{s.t.} ~~\pi\mathbf{1} = \al,~\pi^\intercal \mathbf{1} = \be
\\
~&=~
\max_{\f,\g:\Xx\rightarrow \R}~~
\zp[s]{\al,\f}
+
\zp[s]{\be,\g}
\qquad\text{s.t.}~~
\maxe{\al\otimes\be} [\,\f\oplus \g - \C\,] \,\leqslant\, 0
\end{align*}
\end{minipage}
}
\vspace{.6cm}

This approximation of the linear OT program
can be solved efficiently using the iterative
\textbf{IPFP-SoftAssign-Sinkhorn algorithm}
\cite{wilson1969use,yuille,peyre2017computational},\\
i.e. coordinate ascent on the dual pair $(\f,\g)$.

\endminipage
\end{block}
\end{column}



\begin{column}{\whitemargin}
\end{column}



\begin{column}{\contribcolwidth} % The first column
\begin{block}{\circled{2} ~~Removing the entropic bias~~~}
\minipage[t][\threecolheight][t]{\contribcolinwidth}

When $\varepsilon > 0$, \textbf{fuzzy transport plans}
induce shrinking artifacts \cite{chuiraganajan}:
\vspace{.1cm}

\begin{tabular}{@{\hspace{15mm}}m{.3\linewidth}@{\hspace{9mm}}m{.1\linewidth}@{\hspace{5mm}}m{.4\linewidth}}
  \parbox[b]{\linewidth}{
    Minimize $\text{OT}_\varepsilon(\al,\be)$ \\
    \phantom{~}with respect to $\al$
  }
  & $\longrightarrow$ &
\includegraphics[width=\linewidth]{images/entropic_bias.png}
\end{tabular}
\vspace{.5cm}

$\Longrightarrow$ Use the \textbf{unbiased}
Sinkhorn divergence \cite{ramdas,genevay2018learning,OTGAN}:
\begin{align*}
\S_\varepsilon(\al,\be)
~=~
\OT_\varepsilon(&\al,\be)
- \tfrac{1}{2} \OT_\varepsilon(\al,\al)
- \tfrac{1}{2} \OT_\varepsilon(\be,\be),\\[.3cm]
  \underbrace{\text{OT}(\al,\be)}_{\text{Wasserstein}}~~
\xleftarrow{~~\varepsilon\rightarrow\, 0 ~~}~~&
\underbrace{
\S_\varepsilon(\al,\be)
}_{\text{Easy to compute}}
~~
\xrightarrow{~~\varepsilon\rightarrow +\infty~~}
~~
\underbrace{\text{MMD}_{-\C}(\al,\be) }_{\text{Kernel MMD}}
\end{align*}

\endminipage
\end{block}
\end{column}


\begin{column}{\whitemargin}
\end{column}


% The third column is in red %%%%%%%%%%%%
\definecolor{mSeparation}{HTML}{FF5454}% 
\definecolor{mBackground}{HTML}{FFE5E5}%
\definecolor{blocktitle}{HTML}{840000}%
\setbeamercolor{block title}{fg=blocktitle,bg=mBackground!93!black}%
\setbeamercolor{block body}{fg=black,bg=mBackground!96!black}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{column}{\threecolwidth}
\begin{block}{\circled{3} ~~Our contributions~~~}
\minipage[t][\threecolheight][t]{\threecolinwidth}
\textbf{Theorem:} If $e^{-\C(x,y)/\varepsilon}$ is a positive definite kernel,
\begin{align*}
  \S_\varepsilon(\be,\be)~=~0 ~&~\leqslant~~ \S_\varepsilon(\al,\be) \\
  \S_\varepsilon(\al,\be)~=~0 ~&\Longleftrightarrow~ \al = \be \\
  \S_\varepsilon(\dred{\al_n},\be)~\rightarrow~ 0 ~&\Longleftrightarrow~ \dred{\al_n} \rightharpoonup \be \\
  \text{Loss}_{\be} : \al\mapsto \S_\varepsilon(\al&,\be) ~~\text{is \textbf{convex}.}
\end{align*}

\textbf{In practice:} Our \texttt{PyTorch+KeOps} implementation has a
\textbf{linear memory footprint} and outperforms the standard
Sinkhorn loop by \textbf{two orders of magnitude}.
It is freely available on \texttt{pip} and at

\vspace{.4cm}
\begin{center}
\texttt{www.kernel-operations.io/geomloss}
\end{center}
\endminipage
\end{block}
\end{column}

\begin{column}{\whitemargin}
\end{column}


\end{columns} 







\vspace{.8cm}







\begin{columns}[t]
\begin{column}{\whitemargin}
\end{column}

\begin{column}{\onecolwidth} % The first column

\begin{block}{\circled{4}~ Geometric Loss functions for measure-fitting applications:
~~~~  GMM-loglikelihood vs. Kernel MMDs vs. Sinkhorn divergences~~}
\minipage[c][\onecolheight][s]{\onecolinwidth}

Wasserstein gradient flow:~~
$\dred{ \al \,=\, \tfrac{1}{\N} \sum_{i=1}^\N \delta_{x_i} }$,~~
$\dblue{ \be \,=\, \tfrac{1}{\M} \sum_{j=1}^\M \delta_{y_j} }$,~~
minimize
$\text{Loss}(\al,\be)$ through gradient descent on the $\dred{x_i}$'s.
\textbf{Toy model for generative networks} and shape registration, without regularizing prior.
\vspace{\baselineskip}



\setbeamercolor{smallblock title}{fg=blocktitle,bg=mBackground!90!black}%
\setbeamercolor{smallblock body}{fg=black,bg=mBackground!93!black}%

\newcommand{\sidecapY}[1]{ \begin{sideways}\parbox{.09\linewidth}{\centering\footnotesize #1}\end{sideways} }
\newcommand{\FigGF}[1]{\includegraphics[width=.09\linewidth]{images/flow_2D/#1}}
\newcommand{\FigRowGF}[1]{\FigGF{#1_000.png} & \FigGF{#1_025.png} & \FigGF{#1_050.png} & \FigGF{#1_100.png} & \FigGF{#1_500.png}}

\begin{tabular}{@{}c@{}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{25mm}} l@{}}
  & $\texttt{t}=\texttt{0.}$ & $\texttt{t}=\texttt{.25}$ & $\texttt{t}=\texttt{.50}$ & $\texttt{t}=\texttt{1.00}$ & $\texttt{t}=\texttt{5.00}$ &  \\
  \sidecapY{  GMM-loglikelhood,\\ $\sigma = \texttt{.1}$ } & \FigRowGF{hausdorff} 
  & \parbox[b]{38cm}{
    \begin{beamercolorbox}[colsep*=0ex,dp={2ex},left,wd=38cm]{smallblock title}
      \vskip0.05cm
      \qquad\textbf{GMM-loglikelihoods $\approx$ Chamfer distance $\approx$ Soft-Hausdorff:}
  \end{beamercolorbox}
  
  \vspace{-.2cm}
  \begin{beamercolorbox}[colsep*=0ex,dp={2ex},left,wd=38cm]{smallblock body}
      \vskip0.05cm
      \qquad If $k$ is a Gaussian kernel of deviation $\sigma$,~~
    $\text{ML-Loss}(\al,\be)~=~ 2\sigma^2\,\zp[s]{\,\al-\be\,,\, \text{log} (k\star \al) - \text{log}(k\star \be)\,}$\\
    \phantom{\qquad}and generalizes the \textbf{Chamfer distance}~~~\qquad $\zp[s]{~\al-\be\,,\, \text{dist}(\,\cdot\,,\,\text{supp}(\be)) \,-\, \text{dist}(\,\cdot\,,\,\text{supp}(\al))~}$
    \\\phantom{\qquad}with a SoftMin estimation of the \textbf{distances to the measures' supports}:\\
    \phantom{x}\qquad\qquad\qquad\qquad
    $\text{dist}^2(\,\dred{x},\, \text{supp}(\be)\,)~~\simeq~ - 2\sigma^2\, \log \dblue{\int_y} \exp( -\|\dred{x}-\dblue{y}\|^2 \,/\, 2 \sigma^2 )~  \dblue{\text{d}\be(y)}$  
  \end{beamercolorbox}
  \vskip\smallskipamount
  } 
  
  \\[.5cm]
  \sidecapY{  Gaussian MMD,\\ $\sigma = \texttt{.1}$ }     & \FigRowGF{gaussian} 
  &
  \multirow{2}{*}[6.2cm]{
    \hspace*{-.45cm}
  \parbox[b]{38cm}{
    \begin{beamercolorbox}[colsep*=0ex,dp={2ex},left,wd=38cm]{smallblock title}
        \vskip0.05cm
        \qquad\textbf{Kernel MMDs $\approx$ generalized Sobolev norms $\approx$ Electrostatic energies:}
    \end{beamercolorbox}
    \begin{beamercolorbox}[colsep*=0ex,dp={2ex},left,wd=38cm]{smallblock body}
        \vskip0.05cm
        \qquad If $k$ is a positive, translation-invariant kernel:\vspace{-.6cm}
        \begin{align*}
          2\,\text{MMD}_k&(\al,\be)~=~ \sup_f ~ \zp[s]{\,\al-\be\,,\, f\,}\qquad\text{s.t.}\qquad
          \|f\|_k^2~=~
          \int_{\omega \in \R^d} \tfrac{1}{\widehat{k}(\omega)} |\widehat{f}(\omega)|^2\,\text{d}\omega 
          ~\leqslant~1 \\
          &=~ \dred{ \sum_{i=1}^\N \sum_{j=1}^\N \al_i \al_j \, k(x_i,x_j) }
          ~-~ 2 \, \dred{ \sum_{i=1}^\N } \dblue{\sum_{j=1}^\M} \dred{\al_i} \dblue{\be_j} \, k(\dred{x_i},\dblue{y_j})
          ~+~ \dblue{ \sum_{i=1}^\M \sum_{j=1}^\M \be_i \be_j \, k(y_i,y_j) } \\
          &=~ \text{Generalization of the \textbf{Electrostatic Energy}$(\dred{+\al}, \dblue{-\be})$ to potentials~}k(x,y) \neq \frac{1}{\|x-y\|}.\vspace{-1cm}
        \end{align*}
        \qquad$\Longrightarrow$~~
        \textbf{Screening artifacts}, as in Coulombian physics:
        \textbf{dampening} of the attractive force\\
        \phantom{\qquad$\Longrightarrow$~~} generated by the $\dblue{y_j}$'s
        through the set $\al$ of positive charges.
  \end{beamercolorbox}
  \vskip\smallskipamount
  }
  }
  
  \\
  \sidecapY{  Energy Distance MMD,\\ $k(x,y)=-\|x-y\|$ }  & \FigRowGF{energy} & \\[.5cm]
  \sidecapY{ Sinkhorn divergence,\\ $p=2$,~~ $\sqrt{\varepsilon} = \texttt{.01}$  }  & \FigRowGF{sinkhorn}
  & 
  \parbox[b]{38cm}{
    \begin{beamercolorbox}[colsep*=0ex,dp={2ex},left,wd=38cm]{smallblock title}
        \vskip0.05cm
        \qquad\textbf{Optimal Transport $\approx$ Linear Assignment $\approx$ SoftAssign:}
    \end{beamercolorbox}
    \begin{beamercolorbox}[colsep*=0ex,dp={2ex},left,wd=38cm]{smallblock body}
        \vskip0.05cm
        \qquad \textbf{Sinkhorn divergences} are positive and definite generalizations of the Earth-Mover's distance:\vspace{-1cm}
    \begin{align*}
      \text{Wasserstein}_1(\al,\be)
      ~=~
      {\sup}_f ~ \zp[s]{\,\al-\be\,,\, f\,}\qquad\text{s.t. \qquad $f$~~ is 1-Lipschitz.}
    \end{align*}

    \vspace{-1cm}
    \qquad They perfectly retrieve \textbf{ global translations \textit{and} small deformations}
    in the feature space.
  \end{beamercolorbox}
  \vskip\smallskipamount
  }
 \end{tabular}

\endminipage
\end{block}
\end{column}

\begin{column}{\whitemargin}
\end{column}

\end{columns} 








\vspace{.7cm}


\begin{columns}[t]


% The third line is in green %%%%%%%%%%%%
\definecolor{mSeparation}{HTML}{96ED1C}% 
\definecolor{mBackground}{HTML}{EDFFE5}%
\definecolor{blocktitle}{HTML}{286B04}%
\setbeamercolor{block title}{fg=blocktitle,bg=mBackground!93!black}%
\setbeamercolor{block body}{fg=black,bg=mBackground!96!black}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{column}{\whitemargin}
\end{column}

\begin{column}{\twocolwidth} % The first column
\begin{block}{ \circled{5} ~~The multiscale Sinkhorn algorithm~~~}
\minipage[t][\twocolheight][t]{\twocolinwidth}

\vspace{-1.6cm}
\begin{align*}
\parbox{5cm}{{\small Baseline IPFP-\\Sinkhorn loop}}
~~~~\xrightarrow[~~\text{speedup}~~]{~~\text{x10}~~}~~~~
\parbox{7cm}{{\small $\varepsilon$-scaling heuristic\\ \phantom{.}\qquad~ \cite{yuille} }}
~~~~\xrightarrow[~~\text{speedup}~~]{~~\text{x10}~~}~~~~
\parbox{11cm}{{\small Coarse-to-fine decomposition\\ \phantom{~}~+~Kernel truncation \cite{bernhard}}}
\end{align*}

\vspace{2mm}

\newcommand{\FigGF}[1]{\includegraphics[width=.245\linewidth]{images/scaling/#1.png}}
  
\begin{tabular}{@{}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c@{}}
  \FigGF{it_01_blur_100} & \FigGF{it_04_blur_012} & \FigGF{it_06_blur_003} & \FigGF{it_08_blur_001}  \\
  {\footnotesize $\texttt{it}=\texttt{1}, ~~\sqrt{\varepsilon}=\texttt{1.00}$ }
  & {\footnotesize $\texttt{it}=\texttt{4},~~ \sqrt{\varepsilon}=\texttt{.125}$ }
  & {\footnotesize $\texttt{it}=\texttt{6},~~ \sqrt{\varepsilon}=\texttt{.031}$ }
  & {\footnotesize $\texttt{it}=\texttt{8},~~ \sqrt{\varepsilon}=\texttt{.01}$ }
\end{tabular}



\endminipage
\end{block}
\end{column}

\begin{column}{\whitemargin}
\end{column}

\begin{column}{\twocolwidth} % The first column
\begin{block}{\circled{6} ~~Scaling up to millions of samples on the GPU~~~}
\minipage[t][\twocolheighttwo][t]{\twocolinwidth}

\textbf{KeOps library:} Kernel Operations on the GPU, with autodiff, \textbf{without memory overflows}.\\
Provides efficient, \textbf{online} map-reduce CUDA routines 
through a simple \texttt{PyTorch} interface:
\vspace{.5cm}

\begin{tabular}{@{}c@{\hspace{10mm}}c@{}}
		\begin{tikzpicture}[scale=1.2]
		\begin{axis}[scale=.8,grid=both,ymin=1.1e-4, ymax=100, xmin=100, xmax=1000000,
			title={\scriptsize \textbf{Gaussian dot product} in 3D, on Google Colab},
					xlabel={\scriptsize Number of samples per measure}, 
					ylabel={\scriptsize Time (sec)}, 
					xmode=log, ymode=log,
					legend pos = north west,
					x post scale=1.7,
					grid=major,
          legend cell align={left},
          axis background/.style={fill=white},
          label style={font=\tiny},
          tick label style={font=\tiny},]
			\addplot[blue!50, thick,mark=*] table[x=Npoints,y=PyTorch]  {images/benchmark_convolutions_3D.csv} node[above]{\tiny \om{\textbf{out of mem!}}};
			\addplot[red!80, thick,mark=*] table[x=Npoints,y=KeOps]  {images/benchmark_convolutions_3D.csv};
			\addlegendentry{{\tiny \texttt{PyTorch}}}
			\addlegendentry{{\tiny \texttt{PyTorch+KeOps}}}
		\end{axis}
		\end{tikzpicture} & 
		\begin{tikzpicture}[scale=1.2]
		\begin{axis}[scale=.8,grid=both,ymin=1.1e-4, ymax=100, xmin=100, xmax=1000000,
			title={\scriptsize \textbf{Loss + gradient} in 3D, on Google Colab},
					xlabel={\scriptsize Number of samples per measure}, 
					%ylabel={\scriptsize Time (sec)}, 
					xmode=log, ymode=log,
					legend pos = north west,
					x post scale=1.7,
					grid=major,
          legend cell align={left},
          axis background/.style={fill=white},
          label style={font=\tiny},
          tick label style={font=\tiny},]
      \addplot[red!80, thick,mark=*] table[x=Npoints,y=sinkhorn]  {images/benchmark_loss.csv};
			\addplot[blue!50, thick,mark=*] table[x=Npoints,y=energy]  {images/benchmark_loss.csv};
			\addlegendentry{{\tiny Sinkhorn, $\sqrt{\varepsilon}=\texttt{.01}$}}
			\addlegendentry{{\tiny Energy Distance MMD}}
		\end{axis}
		\end{tikzpicture}\\
  \qquad~~\texttt{pip install pykeops}
  & ~~~~~\texttt{pip install geomloss}
\end{tabular}


\endminipage
\end{block}
\end{column}

\begin{column}{\whitemargin}
\end{column}


\end{columns} 

\vspace{.8cm}  
















\begin{columns}[t]


\begin{column}{35mm}
\end{column}

\begin{column}{\refcolwidth} % The first column
\begin{alertblock}{References}
\minipage[c][120mm][s]{\refcolinwidth}
%\nocite{theano2016,Avants2008,CharonT13,2016-chizat-focm,2016-chizat-sinkhorn,cuturi-2013,CuturiDoucet}
%\nocite{Gee1993,Gori14,LieroMielkeSavareLong,montavon2016wasserstein,santambrogio2015optimal}
%\nocite{sejdinovic2013,Sotiras2013,Vaillant2005}

%\setbeamerfont{bibliography item}{size=\Large}
%\setbeamerfont{bibliography entry author}{size=\Large}
%\setbeamerfont{bibliography entry title}{size=\Large}
%\setbeamerfont{bibliography entry location}{size=\Large}
%\setbeamerfont{bibliography entry note}{size=\Large}
%\renewcommand*{\bibfont}{\small}
%\bibliographystyle{splncs03}    
%\bibliography{biblio}    

   \setbeamerfont{mybiblio}{series=\mdseries,size={\fontsize{12}{14}}}
   \vspace{-.5cm}

   \begin{multicols}{3}
    \nocite{*}
    \begingroup
    \renewcommand{\section}[2]{}%
    \bibliography{biblio}
    \endgroup
    
   \end{multicols}

%\begin{columns}[t]

%\begin{column}[t]{0.3\textwidth}
%  \nocite{*}
%  \bibliography{biblio}
%
%   \usebeamerfont{mybiblio}{
%     blabla
%   }
%\end{column}
%\begin{column}[t]{0.3\textwidth}  %%<--- here
%   \usebeamerfont{mybiblio}{   
%     blabla
%   }
%\end{column}
%\begin{column}[t]{0.3\textwidth}  %%<--- here
%   \usebeamerfont{mybiblio}{    blabla
%   }
%\end{column}

%\end{columns}


\endminipage
\end{alertblock}
\end{column}

\begin{column}{35mm}
\end{column}

\begin{column}{\contactcolwidth} % The first column
\begin{alertblock}{Contact Information}
\minipage[t][50mm][t]{\contactcolinwidth}

\vspace{-2cm}

\begin{columns}
\begin{column}{177mm}
\vspace{-.3cm}

{\small
Jean Feydy, \\
PhD student with Prof. Alain Trouvé,\\
DMA, ENS Paris ~+~ CMLA, ENS Cachan.

%\vspace{.3cm}

~\\
\alert{Mail~:}~ jean.feydy@ens.fr\\
\alert{Web~:}~ \url{www.math.ens.fr/\~feydy}
}
\end{column}

\begin{column}{95mm}
\vspace{-2cm}
\includegraphics[width=\linewidth]{images/Feydy_Jean.jpg}
\end{column}
\end{columns}

\endminipage
\end{alertblock}
\end{column}


\end{columns} 







\end{frame}
\end{document}
