Source-linked AI summary
Smooth and Sparse Optimal Transport
Mathieu Blondel, Vivien Seguy, Antoine Rolet
TL;DR
Entropy-regularized optimal transport is smooth and computationally convenient but produces dense plans, limiting applications where plan sparsity matters. The paper uses strongly convex regularization and smooth constraint relaxations to obtain sparse plans, bounds approximation error, and applies the framework to color transfer. It reports that squared 2-norm regularization can have smaller approximation error than entropic regularization for the regularized primal.
Problem
Entropy keeps transportation plans strictly positive and dense, creating a sparsity problem when the transportation plan itself is of interest.
Method
The paper regularizes primal and dual OT with strongly convex terms and uses smooth approximations of dual and primal constraints, including squared 2-norm and group-lasso regularization.
Results
The proposed regularizations produce sparse or group-sparse transportation plans, while the paper bounds approximation error and showcases the framework on color transfer.
Takeaways & Limitations
Squared 2-norm regularization can provide smaller approximation error than entropic regularization for the regularized primal while retaining sparse plans.
Takeaways & Limitations
The paper notes that its group-sparsity choice does not achieve true group sparsity and assumes strong convexity over the relevant domain.
Abstract
from arXiv · showhide
Entropic regularization is quickly emerging as a new standard in optimal transport (OT). It enables to cast the OT computation as a differentiable and unconstrained convex optimization problem, which can be efficiently solved using the Sinkhorn algorithm. However, entropy keeps the transportation plan strictly positive and therefore completely dense, unlike unregularized OT. This lack of sparsity can be problematic in applications where the transportation plan itself is of interest. In this paper, we explore regularizing the primal and dual OT formulations with a strongly convex term, which corresponds to relaxing the dual and primal constraints with smooth approximations. We show how to incorporate squared $2$-norm and group lasso regularizations within that framework, leading to sparse and group-sparse transportation plans. On the theoretical side, we bound the approximation error introduced by regularizing the primal and dual formulations. Our results suggest that, for the regularized primal, the approximation error can often be smaller with squared $2$-norm than with entropic regularization. We showcase our proposed framework on the task of color transfer.
1 Introduction
The paper targets the density and computational drawbacks of entropy-regularized optimal transport by developing smooth formulations that retain sparse transportation plans. It introduces strongly convex primal and dual regularization schemes, derives approximation bounds, and demonstrates the approach on color transfer.
- Motivation: Entropy regularization makes transportation plans strictly positive and completely dense, which is problematic when the plan itself matters.The paper highlights color transfer, domain adaptation, and ecological inference as applications where sparsity is useful.
- Contributions: The framework regularizes the primal with an arbitrary strongly convex term and derives corresponding smoothed dual and semi-dual formulations.The derivations abstract away regularization-specific terms.
- Contributions: Replacing primal marginal constraints with smooth approximate constraints yields formulations that also produce sparse transportation plans.The approach can be applied to one or both marginal constraints.
- Theory and application: The paper bounds approximation error for regularized primal and dual formulations and reports that squared 2-norm error can be smaller than entropic error for the regularized primal.The proposed methods are empirically showcased on color transfer.
2 Background
The background introduces optimal transport as a geometry-aware comparison of discrete probability distributions and presents its primal linear program and dual formulation. It also reviews convex-analytic concepts used to connect strong convexity with smoothness.
- Convex analysis: Strong convexity and smoothness are dual properties, while Danskin's theorem links unique conjugate maximizers to gradients.These concepts motivate the paper's smooth optimization framework.
- Optimal transport: Optimal transport compares discrete probability distributions by minimizing the ground-cost effort required to move one distribution's mass to the other.The formulation uses distributions a ∈△m and b ∈△n.
- Optimal transport: The modern Kantorovich formulation casts optimal transport as a linear program over the transportation polytope.The transportation polytope contains joint distributions with prescribed marginals.
- Optimal transport: The transportation polytope is the set of joint probability distributions whose marginals are a and b.This interpretation explains the role of the primal feasibility constraints.
- Optimal transport: The paper assumes positive marginals without loss of generality because a zero marginal makes the corresponding row or column of the optimal plan zero.The assumption is stated for a > 0 and b > 0.
- Optimal transport: The dual feasible set consists of potentials satisfying α_i + β_j ≤ c_i,j, and fixing α permits an optimal β solution through a c-transform.The dual formulation is paired with a semi-dual expression.
3 Strong primal ↔Relaxed dual
The paper adds strongly convex regularization to the primal OT problem, yielding smooth dual and semi-dual formulations. Squared 2-norm and group-lasso choices produce sparse or group-sparse transportation plans, with closed-form operators for key cases.
- Strong primal and relaxed dual: Adding a strongly convex term to the primal makes the corresponding dual formulation smooth and unconstrained.The smoothed dual uses a regularized conjugate to replace hard dual constraints with soft ones.
- Smoothed semi-dual formulation: The smoothed semi-dual eliminates one dual variable and replaces the max operator with a smoothed counterpart.The resulting optimization is smooth in α and supports gradient-based learning with OT as a loss.
- Regularizer choices: The framework presents new sparsity-inducing choices of regularizer while retaining differentiable dual and semi-dual optimization.Entropy remains differentiable but does not provide smoothness of the relaxed dual in the same way.
- Squared 2-norm: Squared 2-norm regularization provides closed-form operators, 1/γ-smoothness, exact simplex projection, and exactly sparse transportation plans.Simplex projection is available in worst-case O(m log m) time or expected O(m) time.
- Group lasso: Group-lasso regularization yields truly group-sparse transportation plans, addressing a limitation of entropy-plus-group-lasso regularization.The alternative choice admits a closed-form solution and preserves group sparsity.
4 Relaxed primal ↔Strong dual
The paper also smooths OT by replacing one or both primal marginal constraints with approximate constraints. These relaxed primal formulations remain easier to project onto than the original transportation polytope and induce sparse plans.
- Relaxed primal formulations: Replacing one or both primal marginal constraints with smooth approximate constraints produces relaxed primal OT formulations.The approximation is expressed through a smooth divergence measure Φ.
- Optimization: The relaxed and semi-relaxed primals remain constrained, but their domains are easier to project onto than U(a, b).The experiments use L-BFGS-B for the relaxed primal and FISTA for the semi-relaxed primal.
5 Theoretical bounds
The theoretical analysis bounds approximation errors for smoothed OT formulations and compares their convergence and fidelity trade-offs. Squared 2-norm regularization is often tighter than entropy, while smoothed dual formulations offer the strongest approximation guarantees among the compared approaches.
- Convergence rates: The relaxed and semi-relaxed primals are 1/γ-smooth, while their non-strongly-convex optimization requires O(1/γϵ) iterations or O(1/√γϵ) with acceleration.The dual and semi-dual have formulation-dependent smoothness constants.
- Approximation error: The smoothed problems approach unregularized OT as γ → 0, creating a trade-off between optimization convergence and approximation error.The paper bounds errors for both regularized primal and dual formulations.
- Relaxed formulations: Both relaxed primal formulations typically produce sparse transportation plans and can support partial displacement or unnormalized input measures.Relaxing only one constraint is useful for color transfer when all source mass should be accounted for but not necessarily reference mass.
- Approximation error: Squared 2-norm regularization can often have smaller approximation error than entropic regularization at the same γ.The paper identifies min{H(a), H(b)} > 1 as a sufficient condition for one such comparison.
- Approximation error: The bounds for relaxed primal formulations are worse than those for regularized primal OT, favoring smoothed dual formulations when low approximation error matters.This comparison is stated for squared Euclidean divergence-based relaxation.
6 Experimental results
The experiments evaluate the proposed smoothed OT formulations on color transfer, comparing their output sparsity, solver behavior, and approximation error against unregularized OT.
- 6.1 Application to color transfer: Color transfer represents quantized RGB images as color histograms and applies the proposed OT methods using centroid distances.Images are reduced to m = n = 4096 colors, and barycentric projections transfer colors between images.
- 6.1 Application to color transfer: All formulations outperformed unregularized OT, while all except the entropy-smoothed semi-dual produced extremely sparse transportation plans.The semi-relaxed primal with squared Euclidean distance was the only formulation producing darker-toned transferred colors.
- 6.2 Solver and objective comparison: L-BFGS converged much faster for the semi-dual than the dual under loose regularization, whereas alternating minimization converged extremely slowly.With larger regularization, L-BFGS appeared slightly faster on the dual, likely because its gradients were cheaper to compute.
- 6.3 Approximation error comparison: The approximation comparison evaluates transportation-plan, marginal-constraint, value, and regularized-value errors relative to unregularized OT.The smoothed semi-dual objective was used for dual approaches because entropic and squared 2-norm regularization have the same theoretical smoothness constant there.
- 6.3 Approximation error comparison: 100 times smaller γ was required by entropic regularization to match squared 2-norm regularization on transportation-plan and value errors.The findings support squared 2-norm regularization as typically tighter; the semi-relaxed primal was tighter than the relaxed primal on all four criteria.
7 Related work
The paper relates its smoothed OT formulations to regularized OT, relaxed OT, and smoothed linear programs while distinguishing its dual derivations and approximation-error bounds.
- Regularized OT: Prior work reformulated regularized OT with strictly convex differentiable penalties as Bregman projections solvable by Dykstra’s algorithm, without deriving dual or semi-dual expressions.The paper’s dual and semi-dual expressions provide the missing formulations highlighted in this comparison.
- Relaxed OT: KL-based relaxed OT formulations add entropy to enable Sinkhorn-like algorithms, but that entropy prevents sparse transportation plans and introduces an additional hyper-parameter.The paper instead relaxes marginal constraints without entropic regularization on T.
- Relaxed OT: The semi-relaxed primal with squared Euclidean penalty is equivalent to a related inequality-constrained formulation.This equivalence follows because the cited formulation matches the paper’s semi-relaxed primal penalty.
- Novelty: The paper states that its approximation-error bounds are new relative to related formulations using group-lasso penalties.A similar group-lasso formulation had been studied in convex clustering, but not with the same bounds.
- Smoothed LPs: Compared with smoothed LP work for MAP inference, the paper abstracts regularization through the δΩ and maxΩ functions.This abstraction is presented as one innovation relative to the closest prior works.
8 Conclusion
The paper concludes that strongly convex regularization smooths primal and dual OT formulations while retaining sparse transportation plans, and identifies several directions for extending the theory and algorithms.
- 8 Conclusion: Strongly convex regularization of primal and dual OT corresponds to relaxing the dual and primal constraints with smooth approximations.The framework includes squared 2-norm and group-lasso regularizations that yield sparse or group-sparse plans.
- Future work: The conjugate expression may support barycenter computation and dictionary learning with squared 2-norm instead of entropic regularization.These applications are identified as future uses of the derived formulation.
- Future work: The theoretical guarantees concern convergence of the OT distance value as regularization vanishes, leaving convergence of the transportation plan for future study.The paper contrasts this open direction with existing convergence results for entropic regularization.
- Future work: Large-scale optimization algorithms remain an important future direction, with SAGA proposed as a candidate because it supports stochasticity, proximity operators, adaptivity, and parallelization.The paper does not report a completed large-scale algorithmic study.
A.5 Proof of Theorem 2
The proof derives approximation bounds by controlling dual variables and regularization terms, then applies these bounds to the relaxed and semi-relaxed primal formulations.
- Dual-variable bounds: Dual feasibility is used to bound the 1-norms of α and β after imposing normalization and nonnegative objective constraints.The proof constructs feasible primal points through weak duality to obtain bounds independent of auxiliary variables.
- Primal construction: The proof uses Lagrangian duality to construct primal problems with marginal expressions involving νa + r + µ1_m and νb + s.Choices of µ and ν ensure nonnegativity and feasibility for the constructed transportation plan.
- Approximation bound: The resulting inequality bounds the relaxed-primal value between OT(a, b) and a lower expression involving γ and the squared norms of optimal dual variables.The proof then applies the same reasoning to the semi-relaxed primal.
B Alternating minimization with exact block updates
The smoothed dual can be solved by alternating exact block updates, with coordinate solutions derived from first-order conditions. For entropic regularization these updates recover Sinkhorn, while squared 2-norm regularization reduces each block update to simplex projection.
- Exact block updates: Exact block updates derive β(α) and α(β) from first-order optimality conditions.The expression for α(β) is symmetric, and the inverse-map formulation applies when Ω is differentiable and y > 0.
- Entropic regularization: Entropic block updates recover the iterates of the Sinkhorn algorithm.The same update structure is applied symmetrically to α given β fixed.
- Squared 2-norm regularization: Squared 2-norm regularization makes the β(α) optimality condition identical to Euclidean projection onto the simplex.The projection can be computed using sorted coordinates, and each coordinate-wise solution can be computed in parallel.
- Alternating minimization: Alternating between β ← β(α) and α ← α(β) gives a two-block coordinate-descent algorithm.A greedy coordinate-descent variant can avoid updating coordinates that may already be near-optimal.
C Additional experiments
The paper repeats the Figure 2 and Figure 3 experiments on an additional image pair. The resulting Figures 5 and 6 confirm the empirical findings reported earlier.
- Additional experiments: The additional experiments use “Grafiti” and “Rainbow Bridge National Monument Utah,” both public-domain images.The images are available in the paper’s smooth-ot repository.
- Figure 6: Figure 6 repeats the Figure 2 experiment on one additional image pair.The results are reported as confirming the empirical findings described in §6.2.