betaFeedback

WorksMathematics

Transport Less, Solve Faster: Exploiting sparsity in algorithm design for Unbalanced Optimal Transport

Abstract

In this paper, we study the computational aspects of the Unbalanced Optimal Transport (UOT) problem between two given positive measures μμ and νν. The UOT is a variant to the classic Optimal Transportation problem in which the linear constraints modeling mass preservation are relaxed and replaced by a convex penalty \Dphi in the objective function. First, we show that any UOT problem admits a discrete solution as long as μμ and νν are discrete, allowing us to express the optimality conditions characterizing the solution to the UOT problem in an easy-to-handle form. By exploiting the optimality conditions we provide an upper and lower bound on the marginals of the solution as well as a bound on the mass that any solution assigns to any couple of points. The bounds on the mass assigned to each couple of points reveal that, under suitable conditions, the support of any solution to the UOT is contained within a compact set that does not depend on the measures μμ and νν, but only on the penalty function \Dphi and the cost function cc. We then introduce a truncated version of the UOT problem that fully leverages the sparsity of the optimal solution by introducing a parameter RR that saturates cc. We show that any solution to the truncated problem naturally yields an approximation of the optimal solution for the standard UOT problem and bound the primal sub-optimality gap between the real solution and the solution induced by the truncated problem via a decreasing power-like function of RR. Lastly, we study the convergence speed of the Pairwise Frank-Wolfe algorithm when applied to the truncated UOT problem and show that such routine is able to identify the support of the solution within a finite number of iterations.

Introduction

Optimal Transport (OT) is a standard way to lift any distance defined over a Polish space (Ω,d)(\Omega,d) to the space of probability measures defined over Ω\Omega [57, 45]. Due to their geometrical properties the distances induced by OT problems, i.e., the Wasserstein distances, have been proven to be a valuable tool to address several key sub-tasks in central computer science problems, e.g., Machine Learning [47, 19, 24, 2, 41], Computer Vision [43, 44, 40, 3], and Natural Language Processing [31, 42]. Owing to the growing interest for OT-related distances, the demand for fast and efficient computation methods grew accordingly. Indeed, in its modern formulation, Wasserstein Distance induced by a cost function c:X×Y→[0,+∞[c:\mathcal{X}\times\mathcal{Y}\to[0,+\infty[ between two probability measures μ∈P(X)\mu\in\mathcal{P}(\mathcal{X}) and ν∈P(Y)\nu\in\mathcal{P}(\mathcal{Y}) is defined as the minimum of the following linear problem

min⁡π∈Π(μ,ν)∫X×Yc(x,y) π(dx,dy),(1)\min_{\pi\in\Pi(\mu,\nu)} \int_{\mathcal{X}\times\mathcal{Y}} c(x,y)\,\pi(dx,dy), \tag*{(1)}

where Π(μ,ν)={π∈P(X×Y)∣π(1)=μ, π(2)=ν}\Pi(\mu,\nu)=\{\pi\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\mid\pi^{(1)}=\mu,\ \pi^{(2)}=\nu\} with π(1)\pi^{(1)} and π(2)\pi^{(2)} being the marginal of π\pi over X\mathcal{X} and the marginal of π\pi over Y\mathcal{Y}, respectively. For discrete probability measures, problem (1.1) becomes a Linear Programming (LP) problem, whose computational cost becomes prohibitive when the dimension of the problem increases [29]. The demand for fast algorithms capable of solving the OT problem has spurred extensive research aimed at reducing the computational cost of these methods by considering a Linear Programming problem that exploits the structure of the problem [37, 4] or by approaching an entropic regularization version of the problem [18, 54, 1].

Despite the success of the Wasserstein Distances, they are limited as they compare only positive measures with the same total mass. This factor represents a flaw in any application where the total mass of the object under study is important, e.g., in shape analysis [16, 54] or in persistence diagrams comparison [56, 32]. Moreover, since the OT problem imposes the conservation of the mass, the resulting Wasserstein Distances are sensitive to noise [46], hindering the applicability of the Wasserstein Distances to fields such as robust learning [6], domain adaptation [21], imaging [34], biology [49], and text matching [55]. To overcome these shortcomings, there have been several proposals to extend the Wasserstein Distances to the set of positive measures, such as partial optimal transport [22], the Wasserstein Fisher-Rao distance [28, 16], or the Kantorovich Rubinstein distance [34]. In this paper, we focus on the proposal presented by Liero, Mielke and Savaré, where the hard constraint on the marginal of the transportation plan between the two probability measures is replaced by a suitable Csiszár penalty term in the objective function [36]. More formally, given two positive measures μ\mu and ν\nu, the problem we consider is as follows

min⁡π∈M+(X×Y)UTϕ,c(π):=min⁡π∈M+(X×Y)∫X×Yc(x,y)π(dx,dy)+Dϕ(π(1)∣μ)+Dϕ(π(2)∣ν),\min_{\pi\in\mathcal{M}_{+}(\mathcal{X}\times\mathcal{Y})}\mathrm{UT}_{\phi,c}(\pi):=\min_{\pi\in\mathcal{M}_{+}(\mathcal{X}\times\mathcal{Y})}\int_{\mathcal{X}\times\mathcal{Y}}c(x,y)\pi(\mathrm{d}x,\mathrm{d}y)+D_{\phi}(\pi^{(1)}\mid\mu)+D_{\phi}(\pi^{(2)}\mid\nu),

where DϕD_{\phi} is the Csiszár divergence induced by a convex function ϕ\phi. Unlike the classic Wasserstein Distance, the unbalanced optimal transportation problem proposed in [36] can be naturally formulated as the minimization of a convex function over a convex set, enabling the use of classic routines for convex programming.

Related Works

As per the standard OT problem, most approaches for the UOT rely on a convex relaxation of the objective function that is then handled through the Sinkhorn algorithm [18, 53]. The first Sinkhorn-like algorithm for unbalanced optimal transport was proposed in [17], where the authors showed how to extend the entropic regularization techniques used for the classic OT problem. This approach was subsequently improved in [50], where the authors enhanced the numerical stability of the method. For the one dimensional case, the state-of-the-art solver of the UOT was introduced in [52], where the authors considered a translation-invariant version of the dual UOT problem that can be efficiently solved using the Frank-Wolfe algorithm. The results presented in [52] have led to the study of a Sliced Unbalanced Wasserstein Distances [12] in which the UOT distance is computed by taking the average over all the UOT distances computed over all the possible one-dimensional projections. A different approach based on entropic regularization is presented in [48], where the authors impose an additional low-rank constraint to the UOT problem, enabling a more compact representation of the feasible set of transport plans.

An alternative regularization approach was presented in [8, 39], where the authors define a UOT problem regularization via an ℓ2\ell_2 penalty on the transport plan rather than an entropic one, yielding a strongly convex objective function that can be tackled via standard gradient schemes [39]. In [15], the authors approach the solution of the UOT problem by recasting it as a convex penalized linear regression problem, which has been proven to be efficient when handling specific Csiszár divergences. Lastly, in [25], the authors consider a semi-unbalanced problem in which the penalty is imposed only on one of the two marginals [38].

To the best of our knowledge, most of the works within this field are based on approaching the problem from the dual point of view and by adding a regularization term to the objective function, be it the Kullback Leibler divergence [17] or be it an ℓ2\ell_2 penalization term [39]. A relatively under-explored research direction is to leverage some well-established algorithm for constrained optimization, such as the Frank-Wolfe (FW) algorithm, to retrieve the optimal solution for the primal formulation. Indeed, to the best of our knowledge, the only papers that use the FW routine to retrieve the solution to the UOT problem are [52], where the authors use the FW routine to approach the dual formulation induced by the one dimensional UOT problem, and [25], where the authors define a block-coordinate version of the algorithm that exploits the structure of their semi-unbalanced problem. Both papers showed that it is possible to define fast and efficient Frank-Wolfe routines for the UOT whenever one can harness the structure of the problem: in [52] they do so by showing that the Linear Minimization Oracle associated with each iteration can be performed in closed form, while in [25] it is done by decomposing the feasible set into the direct product of small simplex sets.

The Frank-Wolfe algorithm, also known as the conditional gradient method, is a classic optimization algorithm for constrained problems introduced by Frank and Wolfe [23]. Classical convergence guarantees have been extensively studied [14] along with the conditions that guarantee linear convergence [35, 20] and enable to identify the solution support in a finite number of steps [11]. To ease the conditions needed to make the standard FW algorithm converge linearly, several variants, including away-step [58], pairwise [20], and fully corrective Frank-Wolfe, have been proposed to improve convergence rates under suitable geometric assumptions [33]. In recent years, the interest for the Frank-Wolfe algorithm and its variants has renewed due to its applications in sub-modular optimization problems [5], variational inference problems [30], traffic routing [26], clustering [10], and sparse neural network training [27]. We refer the reader to [9] and [13] for a survey on the family of Frank-Wolfe algorithms.

Our Contribution

In this paper, we propose a novel approach to solve the Unbalanced Optimal Transportation (UOT) problem presented in [36] that hinges on a clever exploitation of the structure of the UOT solutions. Our paper is structured as follows.

First, we study the properties of the solution to the UOT problem. In particular, given any couple of discrete positive measures μ\mu and ν\nu, we show that there exists at least an optimal transportation plan between μ\mu and ν\nu that is discrete and characterize the finite set of points on which such solution is supported. Building on this preliminary result, we show that any solution has finite measure and provide an upper and lower bound on the marginals of any solution that depend only on the specific of the problem. In particular, we provide an upper bound on the measure that any solution assigns to any couple of points in its support. These upper bounds reveal that, under suitable assumptions, the maximum distance between couples of points that belong to the support is bounded by a global constant depending on the cost function and the Csiszár divergence defining the problem. While a similar characterization was known for the Total Variation case [51], our approach can be applied to any UOT problem following the formulation presented in [36].

We then propose a truncated version of the UOT problem that is obtained by introducing a parameter RR that saturates the cost function cc. We show that the truncated problem admits a simple formulation, reducing the total number of variables needed to describe the associated UOT problem. Moreover, any truncated problem naturally yields a feasible point for the original UOT problem that acts as an approximated solution of the problem. We provide an upper bound on the primal sub-optimality gap between the real solution and the approximated solution retrieved from the truncated formulation, revealing that the gap decreases as a polynomial function of RR. Noticeably, all of our proposed bounds on the optimal solution apply to general framework.

We then specialize our study to the case in which the Csiszár divergence belongs to the class of powerlike entropies, a class of entropies that includes the Kullback Leibler and the quadratic penalty function as specific sub-cases. To approach this class of problems, we define an efficient implementation of the Pairwise Frank-Wolfe routine capable of solving the UOT problem for any powerlike entropy and any couple of positive measures. Our routine cleverly combines our theoretical results to save the iterates of the problem in a fast and efficient way. As a by product, we also study the convergence speed of the Pairwise Frank-Wolfe algorithm under the assumptions that the objective has local Hölder continuous gradient and is pp-uniformly convex. Moreover, we provide a support identifiability property for the Pairwise Frank-Wolfe algorithm, which ensures that our routine finds the support of the optimal solution within a finite number of steps.

Notation and problem formulation

We collect the notation and assumptions used throughout the paper.

Basic notation

We write R+=[0,+∞[\mathbb{R}_{+} = [0,+\infty[, R++=]0,+∞[\mathbb{R}_{++} = ]0,+\infty[, and [d]={1,…,d}[d] = \{1,\ldots,d\}. The class Γ0(Rd)\Gamma_{0}(\mathbb{R}^{d}) consists of proper, lower semicontinuous convex functions from Rd\mathbb{R}^{d} to ]−∞,+∞]]-\infty,+\infty]. For a set CC, ιC\iota_{C} denotes its indicator function, equal to zero on CC and +∞+\infty elsewhere. We use ∂f\partial f for the convex subdifferential and NC=∂ιCN_{C} = \partial\iota_{C} for the normal cone of a closed convex set. Interior and relative interior are denoted by int⁡\operatorname{int} and ri⁡\operatorname{ri}, respectively.

For a finite-dimensional vector zz, ∥z∥p\lVert z\rVert_{p} is its usual ℓp\ell_{p} norm; ∥z∥\lVert z\rVert denotes the Euclidean norm and ∥z∥∞:=max⁡i∈[d]∣zi∣\lVert z\rVert_{\infty} := \max_{i\in[d]} |z_{i}| denotes the maximum norm. Under these notations, we set Bh,p(z)={w:∥w−z∥p≤h}B_{h,p}(z) = \{w : \lVert w-z\rVert_{p} \le h\}. The inner product on matrices is ⟨a,b⟩=∑i,jaijbij\langle a,b\rangle= \sum_{i,j} a_{ij}b_{ij}, and 1d\mathbf{1}_{d} is the vector of dd ones. For a nonnegative vector or matrix, ∥x∥1\lVert x\rVert_{1} is the sum of its entries. For a real number tt, put t+=max⁡{t,0}t_{+} = \max\{t,0\}.

For a compact metric space Z\mathcal{Z}, M+(Z)\mathcal{M}_{+}(\mathcal{Z}) is the set of finite nonnegative Borel measures and C(Z)C(\mathcal{Z}) is the space of continuous real functions. Given Z′⊆Z\mathcal{Z}' \subseteq\mathcal{Z} and μ∈M+(Z)\mu\in\mathcal{M}_{+}(\mathcal{Z}), we denote by μ∣Z′\mu|_{\mathcal{Z}'} the restriction of μ\mu to Z′\mathcal{Z}', that is μ∣Z′(A)=μ(A∩Z′)\mu|_{\mathcal{Z}'}(A) = \mu(A \cap\mathcal{Z}') for every measurable A⊆ZA \subseteq\mathcal{Z}. The support of a measure μ\mu is denoted by supp⁡(μ)\operatorname{supp}(\mu). In what follows, we say that a measure is a discrete measure if it has finite support. If TT is measurable, T#μ(E)=μ(T−1(E))T_{\#}\mu(E) = \mu(T^{-1}(E)) denotes the pushforward. For a measure π∈M+(X×Y)\pi\in\mathcal{M}_{+}(\mathcal{X}\times\mathcal{Y}), its marginals are π(1)=(pr⁡X)#π\pi^{(1)} = (\operatorname{pr}_{\mathcal{X}})_{\#}\pi and π(2)=(pr⁡Y)#π\pi^{(2)} = (\operatorname{pr}_{\mathcal{Y}})_{\#}\pi.

Let ff be real-valued and differentiable on an open set containing Ω⊂Rd\Omega\subset\mathbb{R}^{d}. Its gradient is α\alpha-Hölder continuous on Ω\Omega, with α∈]0,1]\alpha\in]0,1], if there is a finite Hα≥0H_{\alpha} \ge0 such that

∥∇f(x)−∇f(y)∥≤Hα∥x−y∥α(x,y∈Ω).\lVert\nabla f(x) - \nabla f(y)\rVert\le H_{\alpha}\lVert x-y\rVert^{\alpha} \qquad(x,y \in\Omega).

The case α=1\alpha= 1 is Lipschitz continuity of the gradient. For p≥2p \ge2, ff is pp-uniformly convex on Ω\Omega with constant κp>0\kappa_{p} > 0 if

f(y)≥f(x)+⟨∇f(x),y−x⟩+κpp∥y−x∥p(x,y∈Ω).(2)f(y) \ge f(x) + \langle\nabla f(x), y-x\rangle+ \frac{\kappa_{p}}{p}\lVert y-x\rVert^{p} \qquad(x,y \in\Omega). \tag*{(2)}

For p=2p=2, this is strong convexity. Notice that these constants may depend on Ω\Omega; a global assertion requires the estimate on the whole set under consideration with one constant.

Finally, if ff has nonempty minimizer set X⋆\mathcal{X}^{\star} and minimum f⋆f^{\star}, it is pp-conditioned on Ω⊃X⋆\Omega\supset\mathcal{X}^{\star} if there is a constant vp>0v_p > 0 such that

f(x)−f⋆≥vpdist⁡(x,X⋆)p(x∈Ω),(3)f(x)-f^{\star} \ge v_p \operatorname{dist}(x,\mathcal{X}^{\star})^p \qquad(x \in\Omega), \tag*{(3)}

where dist⁡(x,X⋆):=min⁡x⋆∈X⋆∥x−x⋆∥\operatorname{dist}(x,\mathcal{X}^{\star}) := \min_{x^{\star} \in\mathcal{X}^{\star}} \lVert x-x^{\star}\rVert is the standard element-to-set distance.

Standing assumptions, marginal penalties, and problem formulation

Let X\mathcal{X} and Y\mathcal{Y} be nonempty compact metric spaces, let c:X×Y→[0,+∞[c:\mathcal{X} \times\mathcal{Y} \to[0,+\infty[ be continuous, and let μ∈M+(X)\mu\in\mathcal{M}_{+}(\mathcal{X}) and ν∈M+(Y)\nu\in\mathcal{M}_{+}(\mathcal{Y}) be finite nonnegative measures. Given x∈Xx \in\mathcal{X}, we denote by δx∈M+(X)\delta_x \in\mathcal{M}_{+}(\mathcal{X}) the Dirac delta centred in xx. In what follows, we always assume that the support of μ\mu and ν\nu are finite so that μ\mu and ν\nu are positive linear combination of different centred Dirac deltas. Moreover, ϕ:R→]−∞,+∞]\phi:\mathbb{R} \to]-\infty,+\infty] is proper, lower semicontinuous, and convex, and satisfies

ϕ≥0,]0,+∞[⊆dom⁡(ϕ)⊆[0,+∞[,and0∈∂ϕ(1),(4)\phi\ge0,\qquad]0,+\infty[ \subseteq\operatorname{dom}(\phi) \subseteq[0,+\infty[,\qquad\text{and}\qquad0 \in\partial\phi(1), \tag*{(4)}

where dom⁡(ϕ)\operatorname{dom}(\phi) denotes the domain of ϕ\phi. In particular, ϕ\phi is finite on ]0,+∞[]0,+\infty[, whereas ϕ(0)\phi(0) may be infinite. In what follows, we assume that

References

  1. [1]J. Altschuler, J. Niles-Weed, and P. Rigollet. “Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration”. In: Advances in Neural Information Processing Systems. Vol. 30. Curran Associates, Inc., 2017, pp. 1964–1974.arxiv.org/abs/1705.09634
  2. [2]M. Arjovsky, S. Chintala, and L. Bottou. “Wasserstein Generative Adversarial Networks”. In: Proceedings of the 34th International Conference on Machine Learning. Vol. 70. Proceedings of Machine Learning Research. International Convention Centre, Sydney, Australia: PMLR, 2017, pp. 214–223.
  3. [3]M. H. Aslam, M. O. Zeeshan, S. Belharbi, M. Pedersoli, A. L. Koerich, S. Bacon, and E. Granger. “Distilling Privileged Multimodal Information for Expression Recognition using Optimal Transport”. In: 2024 IEEE 18th International Conference on Automatic Face and Gesture Recognition (FG). IEEE, 2024, pp. 1–10. DOI: 10.1109/FG59268.2024.10582047.DOI
  4. [4]G. Auricchio, F. Bassetti, S. Gualandi, and M. Veneroni. “Computing Kantorovich–Wasserstein distances on d-dimensional histograms using (d + 1)-partite graphs”. In: Advances in Neural Information Processing Systems. Vol. 31. Curran Associates, Inc., 2018, pp. 5793–5803.arxiv.org/abs/1805.07416
  5. [5]F. Bach. “Learning with submodular functions: A convex optimization perspective”. In: Foundations and Trends in Machine Learning 6.2–3 (2013), pp. 145–373. DOI: 10.1561/2200000039.DOI
  6. [6]Y. Balaji, R. Chellappa, and S. Feizi. “Robust optimal transport with applications in generative modeling and domain adaptation”. In: Advances in Neural Information Processing Systems. Vol. 33. Curran Associates, Inc., 2020, pp. 12934–12944.arxiv.org/abs/2010.05862
  7. [7]A. Beck and S. Shtem. “Linearly convergent away-step conditional gradient for non-strongly convex functions”. In: Mathematical Programming 164.1–2 (2017), pp. 1–27. DOI: 10.1007/s10107-016-1069-4.DOI
  8. [8]M. Blondel, V. Seguy, and A. Rolet. “Smooth and sparse optimal transport”. In: Proceedings of the 21st International Conference on Artificial Intelligence and Statistics. Vol. 84. Proceedings of Machine Learning Research. PMLR, 2018, pp. 880–889.arxiv.org/abs/1710.06276
  9. [9]I. M. Bomze, F. Rinaldi, and D. Zeffiro. “Frank–Wolfe and friends: a journey into projection-free first-order optimization methods”. In: 4OR 19.3 (2021), pp. 313–345. DOI: 10.1007/s10288-021-00493-y.DOI
  10. [10]I. M. Bomze. “Evolution towards the maximum clique”. In: Journal of Global Optimization 10.2 (1997), pp. 143–164. DOI: 10.1023/A:1008230200610.DOI
  11. [11]I. M. Bomze, F. Rinaldi, and D. Zeffiro. “Active set complexity of the away-step Frank–Wolfe algorithm”. In: SIAM Journal on Optimization 30.3 (2020), pp. 2470–2500. DOI: 10.1137/19M1309419.DOI
  12. [12]C. Bonet, K. Nadjahi, T. Séjourné, K. Fatrás, and N. Courty. “Slicing unbalanced optimal transport”. In: Transactions on Machine Learning Research (Dec. 2024).arxiv.org/abs/2306.07176
  13. [13]G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokhtari, and S. Pokutta. Conditional Gradient Methods: From Core Principles to AI Applications. MOS-SIAM Series on Optimization 35. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2025. DOI: 10.1137/1.9781611978568. arXiv: 2211.14103.DOI
  14. [14]M. D. Canon and C. D. Cullum. “A tight upper bound on the rate of convergence of Frank–Wolfe algorithm”. In: SIAM Journal on Control 6.4 (1968), pp. 509–516. DOI: 10.1137/0306032.DOI
  15. [15]L. Chapel, R. Flamary, H. Wu, C. Févotte, and G. Gasso. “Unbalanced optimal transport through non-negative penalized linear regression”. In: Advances in Neural Information Processing Systems. Vol. 34. Curran Associates, Inc., 2021, pp. 23270–23282.arxiv.org/abs/2106.04145
  16. [16]L. Chizat, G. Peyré, B. Schmitzer, and F.-X. Vialard. “An interpolating distance between optimal transport and Fisher–Rao metrics”. In: Foundations of Computational Mathematics 18.1 (2018), pp. 1–44. DOI: 10.1007/s10208-016-9331-y.
  17. [17]L. Chizat, G. Peyré, B. Schmitzer, and F.-X. Vialard. “Scaling algorithms for unbalanced optimal transport problems”. In: Mathematics of Computation 87.314 (2018), pp. 2563–2609. DOI: 10.1090/mcom/3303.DOI
  18. [18]M. Cuturi. “Sinkhorn distances: Lightspeed computation of optimal transport”. In: Advances in Neural Information Processing Systems. Vol. 26. Curran Associates, Inc., 2013, pp. 2292–2300.
  19. [19]M. Cuturi and A. Doucet. “Fast Computation of Wasserstein Barycenters”. In: Proceedings of the 31st International Conference on Machine Learning. Vol. 32. Proceedings of Machine Learning Research 2. Beijing, China: PMLR, 2014, pp. 685–693.arxiv.org/abs/1310.4375
  20. [20]V. F. Demianov and A. M. Rubinov. Approximate methods in optimization problems. Modern Analytic and Computational Methods in Science and Mathematics 32. New York: American Elsevier Publishing Company, 1970.
  21. [21]K. Fatras, T. Séjourné, R. Flamary, and N. Courty. “Unbalanced minibatch optimal transport; applications to domain adaptation”. In: Proceedings of the 38th International Conference on Machine Learning. Vol. 139. Proceedings of Machine Learning Research. PMLR, 2021, pp. 3186–3197.arxiv.org/abs/2103.03606
  22. [22]A. Figalli. “The optimal partial transport problem”. In: Archive for Rational Mechanics and Analysis 195.2 (2010), pp. 533–560. DOI: 10.1007/s00205-008-0212-7.DOI
  23. [23]M. Frank and P. Wolfe. “An algorithm for quadratic programming”. In: Naval Research Logistics Quarterly 3.1–2 (1956), pp. 95–110. DOI: 10.1002/nav.3800030109.DOI
  24. [24]C. Frogner, C. Zhang, H. Mobahi, M. Araya, and T. A. Poggio. “Learning with a Wasserstein loss”. In: Advances in Neural Information Processing Systems. Vol. 28. Curran Associates, Inc., 2015, pp. 2053–2061.arxiv.org/abs/1506.05439
  25. [25]T. Fukunaga and H. Kasai. “Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem”. In: ICASSP 2022 – 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 5433–5437. DOI: 10.1109/ICASSP43922.2022.9746032.DOI
  26. [26]M. Fukushima. “A modified Frank-Wolfe algorithm for solving the traffic assignment problem”. In: Transportation Research Part B: Methodological 18.2 (1984), pp. 169–177. DOI: 10.1016/0191-2615(84)90029-8.DOI
  27. [27]P. Grigas, A. Lobos, and N. Vermeersch. Stochastic in-face Frank-Wolfe methods for non-convex optimization and sparse neural network training. arXiv preprint. 2019. DOI: 10.48550/arXiv.1906.03580. arXiv: 1906.03580.DOI
  28. [28]L. G. Hanin. “Kantorovich–Rubinstein norm and its application in the theory of Lipschitz spaces”. In: Proceedings of the American Mathematical Society 115.2 (1992), pp. 345–352. DOI: 10.1090/S0002-9939-1992-1097344-5.DOI
  29. [29]L. V. Kantorovich. “On the translocation of masses”. In: Journal of Mathematical Sciences 133.4 (2006), pp. 1381–1382. DOI: 10.1007/s10958-006-0049-2.DOI
  30. [30]R. G. Krishnan, S. Lacoste-Julien, and D. Sontag. “Barrier Frank-Wolfe for marginal inference”. In: Advances in Neural Information Processing Systems. Vol. 28. Curran Associates, Inc., 2015, pp. 532–540.arxiv.org/abs/1511.02124
  31. [31]M. J. Kusner, Y. Sun, N. I. Kolkin, and K. Q. Weinberger. “From word embeddings to document distances”. In: Proceedings of the 32nd International Conference on Machine Learning. Vol. 37. Proceedings of Machine Learning Research. Lille, France: PMLR, 2015, pp. 957–966.
  32. [32]T. Lacombe, M. Cuturi, and S. Oudot. “Large scale computation of means and clusters for persistence diagrams using optimal transport”. In: Advances in Neural Information Processing Systems. Vol. 31. Curran Associates, Inc., 2018, pp. 9770–9780.arxiv.org/abs/1805.08331
  33. [33]S. Lacoste-Julien and M. Jaggi. “On the global linear convergence of Frank-Wolfe optimization variants”. In: Advances in Neural Information Processing Systems. Vol. 28. Curran Associates, Inc., 2015, pp. 496–504.
  34. [34]J. Lellmann, D. A. Lorenz, C. Schönlieb, and T. Valkonen. “Imaging with Kantorovich–Rubinstein Discrepancy”. In: SIAM Journal on Imaging Sciences 7.4 (2014), pp. 2833–2859. DOI: 10.1137/140975528.DOI
  35. [35]E. S. Levitin and B. T. Polyak. “Constrained minimization methods”. In: USSR Computational Mathematics and Mathematical Physics 6.5 (1966), pp. 1–50. DOI: 10.1016/0041-5553(66)90114-5.DOI
  36. [36]M. Liero, A. Mielke, and G. Savaré. “Optimal entropy-transport problems and a new Hellinger–Kantorovich distance between positive measures”. In: Inventiones mathematicae 211.3 (2018), pp. 969–1117. DOI: 10.1007/s00222-017-0759-8.DOI
  37. [37]H. Ling and K. Okada. “An efficient Earth Mover’s Distance algorithm for robust histogram comparison”. In: IEEE Transactions on Pattern Analysis and Machine Intelligence 29.5 (2007), pp. 840–853. DOI: 10.1109/TPAMI.2007.1058.DOI
  38. [38]W. Liu, X. Liao, J. Dan, F. Wang, H. Yu, J. Dong, S. Dong, L. Qi, and Y.-S. Ong. “Solving discrete (semi) unbalanced optimal transport with equivalent transformation mechanism and KKT-multiplier regularization”. In: Advances in Neural Information Processing Systems. Vol. 38. Curran Associates, Inc., 2025, pp. 105330–105365. DOI: 10.52202/085713-3519.DOI
  39. [39]Q. M. Nguyen, H. H. Nguyen, Y. Zhou, and L. M. Nguyen. “On unbalanced optimal transport: Gradient methods, sparsity and approximation error”. In: Journal of Machine Learning Research 24.384 (2023), pp. 1–41.arxiv.org/abs/2202.03618
  40. [40]O. Pele and M. Werman. “Fast and robust Earth Mover’s Distances”. In: 2009 IEEE 12th International Conference on Computer Vision. IEEE, 2009, pp. 460–467. DOI: 10.1109/ICCV.2009.5459199.DOI
  41. [41]L. M. Pereira and M. H. Amini. “A survey on optimal transport for machine learning: Theory and applications”. In: IEEE Access 13 (2025), pp. 26506–26526. DOI: 10.1109/ACCESS.2025.3539926.DOI
  42. [42]A. Rolet, M. Cuturi, and G. Peyré. “Fast dictionary learning with a smoothed Wasserstein loss”. In: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. Vol. 51. Proceedings of Machine Learning Research. Cadiz, Spain: PMLR, 2016, pp. 630–638.
  43. [43]Y. Rubner, C. Tomasi, and L. J. Guibas. “A metric for distributions with applications to image databases”. In: Sixth International Conference on Computer Vision (IEEE Cat. No. 98CH36271). Bombay, India: Narosa Publishing House, 1998, pp. 59–66. DOI: 10.1109/ICCV.1998.710701.
  44. [44]Y. Rubner, C. Tomasi, and L. J. Guibas. “The Earth Mover’s Distance as a metric for image retrieval”. In: International Journal of Computer Vision 40.2 (2000), pp. 99–121. DOI: 10.1023/A:1026543900054.DOI
  45. [45]F. Santambrogio. Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling. Vol. 87. Progress in Nonlinear Differential Equations and Their Applications. Cham: Birkh"auser, 2015. DOI: 10.1007/978-3-319-20828-2.DOI
  46. [46]R. Sato, M. Yamada, and H. Kashima. “Fast unbalanced optimal transport on a tree”. In: Advances in Neural Information Processing Systems. Vol. 33. Curran Associates, Inc., 2020, pp. 19039–19051.arxiv.org/abs/2006.02703
  47. [47]A. Scagliotti and S. Farinelli. “Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs”. In: Nonlinear Analysis 257 (2025), p. 113811. DOI: 10.1016/j.na.2025.113811. arXiv: 2311.01404.DOI
  48. [48]M. Scetbon, M. Klein, G. Palla, and M. Cuturi. “Unbalanced low-rank optimal transport solvers”. In: Advances in Neural Information Processing Systems. Vol. 36. Curran Associates, Inc., 2023, pp. 52312–52325. DOI: 10.52202/075280-2277.DOI
  49. [49]G. Schiebinger, J. Shu, M. Tabaka, B. Cleary, V. Subramanian, A. Solomon, J. Gould, S. Liu, S. Lin, P. Berube, L. Lee, J. Chen, J. Brumbaugh, P. Rigollett, K. Hochedlinger, R. Jaenisch, A. Regev, and E. S. Lander. “Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming”. In: Cell 176.4 (2019), 928–943.e22. DOI: 10.1016/j.cell.2019.01.006.DOI
  50. [50]B. Schmitzer. “Stabilized sparse scaling algorithms for entropy regularized transport problems”. In: SIAM Journal on Scientific Computing 41.3 (2019), A1443–A1481. DOI: 10.1137/16M1106018.DOI
  51. [51]T. Séjourné, G. Peyré, and F.-X. Vialard. “Unbalanced optimal transport, from theory to numerics”. In: Numerical Control: Part B. Vol. 24. Handbook of Numerical Analysis. Elsevier, 2023. Chap. 12, pp. 407–471. DOI: 10.1016/bs.hna.2022.11.003.DOI
  52. [52]T. Séjourné, F.-X. Vialard, and G. Peyré. “Faster unbalanced optimal transport: Translation invariant Sinkhorn and 1-D Frank–Wolfe”. In: Proceedings of the 25th International Conference on Artificial Intelligence and Statistics. Vol. 151. Proceedings of Machine Learning Research. PMLR, 2022, pp. 4995–5021.arxiv.org/abs/2201.00730
  53. [53]R. Sinkhorn and P. Knopp. “Concerning nonnegative matrices and doubly stochastic matrices”. In: Pacific Journal of Mathematics 21.2 (1967), pp. 343–348. DOI: 10.2140/pjm.1967.21.343.DOI
  54. [54]J. Solomon, F. de Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas. “Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains”. In: ACM Transactions on Graphics 34.4 (2015), 66:1–66:11. DOI: 10.1145/27666963.
  55. [55]W. Tang, Z. Ma, H. Sun, and J. Wang. “Learning sparse alignments via optimal transport for cross-domain fake news detection”. In: ICASSP 2023 – 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2023, pp. 1–5. DOI: 10.1109/ICASSP49357.2023.10095281.DOI
  56. [56]J. Vidal, J. Budin, and J. Tierny. “Progressive Wasserstein barycenters of persistence diagrams”. In: IEEE Transactions on Visualization and Computer Graphics 26.1 (2020), pp. 151–161. DOI: 10.1109/TVCG.2019.2934256.DOI
  57. [57]C. Villani. Optimal Transport: Old and New. Vol. 338. Grundlehren der mathematischen Wissenschaften. Berlin, Heidelberg: Springer, 2009. DOI: 10.1007/978-3-540-71050-9.
  58. [58]P. Wolfe. “Convergence theory in nonlinear programming”. In: Integer and Nonlinear Programming. Amsterdam: North-Holland, 1970. Chap. 1, pp. 1–36.

Paper details

vlnc:W_semjzacu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents