Optimal transport at finite temperature

Optimal transport (OT) has become a discipline by itself that offers solutions to a wide range of theoretical problems in probability and mathematics. Despite its appealing theoretical properties, solving the OT problem involves the resolution of a linear program whose computational cost can quickly become prohibitive whenever the size of the problem exceeds a few hundred points. The recent introduction of entropy regularization, however, has led to the development of fast algorithms for solving an approximate OT problem. The successes of those algorithms have resulted in a popularization of the applications of OT in several applied fields such as imaging sciences and machine learning, and in data sciences in general. Problems remain, however, as to the numerical convergence of those regularized approximations towards the actual OT solution. In addition, the physical meaning of this regularization is unclear. In this paper, we propose an approach to solving the discrete OT problem using techniques adapted from statistical physics. Our first contribution is to fully describe this formalism, including all the proofs of its main claims. In particular we derive a strongly concave effective free energy function that captures the constraints of the optimal transport problem at a finite temperature. Its maximum defines a pseudo distance between the two set of weighted points that are compared, which satisfies the triangular inequalities. The temperature dependent OT pseudo distance decreases monotonically to the standard OT distance, providing a robust framework for temperature annealing. Our second contribution is to show that the implementation of this formalism has the same properties as the regularized OT algorithms in time complexity, making it a competitive approach to solving the OT problem. We illustrate applications of the framework to the problem of protein fold recognition based on sequence information only.

Figure 1

Discriminative power of the temperature-based optimal transport distances for protein fold recognition. The probability of correct classification of a protein sequence into its fold defined by SCOPe based on the distance measure $D\left(\beta \right)=U_{\beta }^{MF}$ (see text for details) is plotted against $\beta =1/T$ for different sizes of the k-mers used to represent the sequences. All the curves are arithmetic means over 10 000 classification experiments (see text for details). Shaded areas represent standard deviations.

Figure 2

Optimal transport plans between concanavalin A (horizontal axis) and peanut lectin (vertical axis), for k-mer sizes of 3 (a) and 10 (b). The local alignments of the two domains of these sequences, as well as the domain swap, appear clearly from the transportation plans.

Figure 3

Time complexity for FreeOT and EntropyOT. The running times for the finite temperature procedure (FreeOT) and for the entropy-regularized procedure (EntropyOT, blue circles) used for comparing two sequences are plotted against the size of the sequences, including two options for the inner solver of the linear system of equations (see text for details), namely a direct solver (black circles) or an iterative conjugate gradient solver (red circles). The corresponding solid lines shows the best fit to a cubic polynomial for the direct solver data, and to a quadratic polynomial for the iterative solver. The timings are computed on a single Intel Core I7 processor running at 4.0 GHz with 64 GB of RAM.

Figure 4

Convergence of the nonlinear solver in FreeOT for successive values of $\beta$. The number of Newton-Ralphson iterations needed for solving the SPA conditions is plotted against the value of $\beta$, for the standard implementation of FreeOT with transfer of variables between two consecutive $\beta$ values (in black), and for the reset version of FreeOT in which the variables are reset to 0 at each value of $\beta$. The solid line corresponds to the arithmetic means over the 602 sequence comparison experiments (see text for details). Shaded area represents standard deviations.

Figure 5

The two functions $\varphi \left(x\right)$ and $f\left(x\right)$.