Interpolating between Optimal Transport and KL Regularized Optimal Transport using Rényi Divergences

Abstract Regularized optimal transport (OT) has received much attention in recent years starting from Cuturi’s introduction of Kullback-Leibler (KL) divergence regularized OT. In this paper, we propose regularizing the OT problem using the family of $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> -Rényi divergences for $$\alpha \in (0, 1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Rényi divergences are neither f -divergences nor Bregman distances, but they recover the KL divergence in the limit $$\alpha \nearrow 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>↗</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . The advantage of introducing the additional parameter $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> is that for $$\alpha \searrow 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>↘</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> we obtain convergence to the unregularized OT problem. For the KL regularized OT problem, this was achieved by letting the regularization parameter $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> tend to zero, which causes numerical instabilities. We present two different ways to obtain premetrics on probability measures, namely by Rényi divergence constraints and by penalization. The latter premetric interpolates between the unregularized and the KL regularized OT problem with weak convergence of the unique minimizer, generalizing the interpolation property of KL regularized OT. We use a nested mirror descent algorithm to solve the primal formulation. Both on real and synthetic data sets Rényi regularized OT plans outperform their KL and Tsallis counterparts in terms of being closer to the unregularized transport plans and recovering the ground truth in inference tasks better.