Iterative Bregman Projections for Regularized Transportation Problems

By Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, G. Peyr'e. 2014

901 citations recorded by the source corpus.

This article details a general numerical framework to approximate so-lutions to linear programs related to optimal transport. The general idea is to introduce an entropic regularization of the initial linear program. This regularized problem corresponds to a Kullback-Leibler Bregman di-vergence projection of a vector (representing some initial joint distribu-tion) on the polytope of constraints. We show that for many problems related to optimal transport, the set of linear constraints can be split in an intersection of a few simple constraints, for which the projections can be computed in closed form. This allows us to make use of iterative Bregman projections (when there are only equality constraints) or more generally Bregman-Dykstra iterations (when inequality constraints are in-volved). We illustrate the usefulness of this approach to several variational problems related to optimal transport: barycenters for the optimal trans-port metric, tomographic reconstruction, multi-marginal optimal trans-port and in particular its application to Brenier's relaxed solutions of in-compressible Euler equations, partial un-balanced optimal transport and optimal transport with capacity constraints.

Subfields: Applied Mathematics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Optimization & Training

Citations in the corpus

GAIT: A Geometric Approach to Information Theory (2019, methodology): “Moreover, the proposals of Cuturi and Doucet (2014); Benamou et al. (2014) require at least Ω((|κ|+L)mn) operations, where L denotes the number of Sinkhorn iterations, which is an increasing function of the desired optimization tolerance.”
Model Fusion via Optimal Transport (2019, methodology): “However, it is not possible to directly employ the commonly used Iterative Bregman Projections (IBP) scheme (Benamou et al., 2015) to compute the averaged model.”
Wasserstein Fair Classification (2019, methodology): “We ﬁx the support of potential barycenters to bins of equal-width spanning the [0 , 1] interval, and use the iterative KL-projection method proposed by Benamou et al. (2015).”
Computational Optimal Transport (2018, methodology): “2) using the special structure of the cost, as detailed in [Benamou et al., 2015].”
A Fast Proximal Point Method for Computing Wasserstein Distance (2018, methodology): “While the time complexity of our method is in the same order of magnitude with Sinkhorn algo-rithm [5], the space complexity is K times of it, because K different transport maps need to be stored.”
Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation (2020, background): “Two popular ones include entropy regularization [8, 3] and marginal relaxation [13, 6, 7, 9, 12].”
Context Mover's Distance & Barycenters: Optimal transport of contexts for building representations (2018, methodology): “Employing the iterative Bregman projections (Benamou et al., 2015), we obtain an approximation of the solution at a reasonable computational cost.”
Automatic Text Evaluation through the Lens of Wasserstein Barycenters (2021, background): “…tractable, the measure µ is often constrained to be a discrete measure with free (Cuturi and Doucet, 2014; Álvarez Esteban et al., 2016; Cuturi and Peyré, 2016; Luise et al., 2019) or fixed support (Benamou et al., 2015; Dvurechenskii et al., 2018; Lin et al., 2020; Janati et al., 2020).”
Gromov-Wasserstein Averaging of Kernel and Distance Matrices (2016, methodology): “Our algorithm solves a entropically-regularized version of this quadratic program by extending recent advances in the computation of OT (Cuturi, 2013; Benamou et al., 2015).”
Sampling of probability measures in the convex order and approximation of Martingale Optimal Transport problems (2017, neutral): “The two first projections are explicit (see for instance Proposition 1 [5]).”
Rectify Heterogeneous Models with Semantic Mapping (2018, methodology): “With types of solution strategy (Cuturi, 2013; Wang & Banerjee, 2014; Benamou et al., 2015), OT has been successfully applied in various machine learning fields with both its objective measure or the learned transportation plan.”
Applications of weak transport theory (2020, positive): “Starting with the articles [24, 16, 27], the Schrödinger problem has received significant attention as a regularized, numerically tractable version of the classical transport problem.”
Differentiable Top-k with Optimal Transport (2020, methodology): “Specifically, we run iterative Bregman projections (Benamou et al., 2015), where at the `-th iteration, we update”
Sliced Wasserstein Kernels for Probability Distributions (2015, background): “Recent advances utilizing variational minimization [16, 9], particle approximation [44], multi-scale schemes [27, 29], and entropy regularization [11, 39, 4], have enabled transport metrics to be efficiently applied to machine learning and computer vision problems.”
Graph Optimal Transport for Cross-Domain Alignment (2020, methodology): “…the proposed GOT distance is deﬁned as: We apply the Sinkhorn algorithm (Cuturi, 2013; Cuturi & Peyr´e, 2017) to solve WD (4) with an entropic regular-izer (Benamou et al., 2015): where H ( T ) = i,j T ij log T ij , and β is the hyper-parameter controlling the importance of the entropy term.”
Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm (2019, methodology): “This contrasts with previous methods for barycenter estimation [6, 14, 20, 50], which require the support set, or at least its cardinality, to be fixed beforehand.”
Fréchet means and Procrustes analysis in Wasserstein space (2017, background): “[11] exploit the structure of the constraints as an intersection of convex sets by means of iterating Bregman projections that can be evaluated efficiently.”