acceptodds
Under review as a conference paper at ICLR 2027

Efficient Algorithms for Computing a Partial -Wasserstein Barycenter in Metric Spaces

Abstract

Given a collection of probability distributions over a total of points in a space equipped with a pairwise distance function , the task of computing an average probability distribution with respect to the optimal transport cost is known in the literature as the *Wasserstein barycenter problem*. However, like OT plans, Wasserstein barycenters are also sensitive to the presence of outliers in each distribution. The *-partial Wasserstein barycenter problem* for , which addresses this issue, asks to compute a measure of mass for which the average unbalanced OT cost from the input distributions to this measure is minimized. In this paper, we design provably efficient approximation algorithms for the -partial Wasserstein barycenter problem. Our first algorithm computes an approximate fixed-support -partial Wasserstein barycenter in arbitrary spaces in roughly time, where is the size of the fixed support and is a small approximation error in the mass. The second algorithm improves the run time in the free-support setting for metric spaces by a factor of at the expense of an additional approximation error in the cost of the OT plans. We additionally prove that an exact solution to the -partial Wasserstein barycenter problem can be computed in roughly time.

Primary area:
optimization
Keywords:
Optimal Transport, p-Wasserstein Barycenter, Robust Optimal Transport

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_NvsCOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the partial p-Wasserstein Barycenter problem for general/Euclidean metrics. Here we are given a given k sets of points in a metric space X1,…,XkX_1, \dots, X_k and a distributions μ1,…,μk\mu_1, \dots, \mu_k over each. (Informally) The p-Wasserstein barycenter problem asks us to a measure ν\nu over a set of points YY as well as mappings from each input point set/distribution pairs to Y,νY,\nu minimizing the cost of the (average) of these maps. The α\alpha-partial variant of the problem expects the measure ν\nu to have mass α≤1\alpha \leq 1, that is for each map to transport an α\alpha fraction of the mass of the respective XiX_i to YY. The paper considers (δ,ϵ)(\delta,\epsilon)-approximate algorithms, where ϵ\epsilon stands for multiplicative slack and we expect ν\nu to have at least α−δ\alpha-\delta mass.

The main contribution of the paper is in presenting a (δ,0)(\delta,0)-approximate α\alpha-partial p-Wasserstein barycenter for a fix support in O(n(m+k)δ−2log⁡O(1)(Δ))O(n(m+k)\delta^{-2} \log^{O(1)}(\Delta)) time (n is the total number of inputs points, k is the number of input sets, m is the size of the fixed support, Δ\Delta is the spread of the input points).

The authors also show, assuming the support is not fixed, for d-dimensional Eucledian spaces 1) a (δ,ϵ)(\delta,\epsilon)-approximation in O(nkpoly(ϵ−dδ−1log⁡Δ))O(nk poly(\epsilon^{-d}\delta^{-1} \log \Delta)) time, (δ,c)(\delta,c)-approximation in O(n1+1/Ω(c2)kpoly(δ−1log⁡Δ))O(n^{1+1/\Omega(c^2)} k poly(\delta^{-1} \log \Delta)) time for c>1c>1; a 2) (δ,O(c))(\delta, O(c))-approximation in O(n2poly(Δ)+n1+1/Ω(c)kpoly(δ−1log⁡Δ))O(n^2 poly(\Delta) + n^{1+1/\Omega(c)} k poly(\delta^{-1} \log \Delta)) time. They also show that an exact solution can be computed in O(poly(ndlog⁡Δ))O(poly(n^d \log \Delta)) time.

The first approximate algorithm works through completing a binary search for the cost of the optimal solution. The decision problem in each step of the binary search can be formulated as a linear program, which is then approximately solved using multiplicative weight updates. The approximate results restricted to Euclidean metrics simmiliarly complete a binary search. The algorithm chooses a support of O~(n)\tilde{O}(n) points and represents each input distribution with a single point through clustering, accelerating the LP-solver. The exact algorithm relies on the ellipsoid algorithm. Overall, the algorithms are natural in terms of the overall approach, but the details are technically involved.

Critical strengths

While the Wasserstein barycenter problem has received significant attention and is widely applied in practice, the particular relaxation (α\alpha-partial) was only known to admit efficient algorithms for additive approximation (multiplicative approximation required poly(n)poly(n) time). The α\alpha-partial notion is introduced to handle outlier solutions. While there are further variations of the problem designed to handle such cases, the authors make a compelling case of the usefullnes of this definition.

Critical weaknesses

Previous results for the α\alpha-partial setting appear to not rely on the δ\delta-relaxation. It is unclear if additive slack would not be preferable to relaxation in the objective.

Compared to how standard MWU is for solving LP-s its quite challenging to parse what modification compared to say the well known Arora et al. experts setting are needed to obtain the results. I would advise the authors to aim to make the LP solving part as black-box based on standard approaches as possible, improving readability.

Questions for authors

No questions.

2 comments
AuthorsOpenReview ↗

Response to Reviewer NvsC

We thank the reviewer for their thoughtful feedback and address their main concerns below.

Accuracy of approximation algorithms: We clarify the definitions of different approximations discussed in the paper.

  • Relative vs. Relaxed: A (1+ϵ)(1+\epsilon)-relative approximate solution ff satisfies wp(f)≤(1+ϵ)wp(f∗)w_p(f) \leq (1+\epsilon)w_p(f^*). Greedily removing the most expensive ϵ\epsilon fraction of mass from ff yields a δ\delta-relaxed solution (transporting α−δ\alpha-\delta mass at cost ≤wp(f∗)\leq w_p(f^*)). Thus, the relative guarantee is stronger than the relaxed guarantee.

  • Relaxed vs. Additive: A δ\delta-relaxed solution transports α−δ\alpha-\delta mass at cost ≤wp(f∗)\leq w_p(f^*). Arbitrarily adding the unrouted mass incurs at most a δ\delta-additive error (assuming p=1p=1 for simplicity), yielding a δ\delta-additive approximation. Thus, the relaxed guarantee is stronger than the ϵ\epsilon-additive approximation.

While standard ML optimal transport papers (e.g., Sinkhorn-based) typically guarantee additive approximation, we use (1+ϵ)(1+\epsilon)-relative and δ\delta-relaxed solutions because their guarantees are stronger. We agree that mixing approximation types can be confusing, and we will clarify this distinction more explicitly in the revised text (building on lines 108–114).

Comparison with experts MWU algorithm: Our algorithm is similar to the multicommodity flow approach from Section 3.3 of Arora et al. [1], rather than the classical experts MWU. Directly applying the experts MWU algorithm to Wasserstein barycenters causes two issues: (a) updating every weight every iteration is computationally expensive, and (b) overcommitting mass to fixed centroids requires many iterations, constrained by the LP width. Our algorithm circumvents these issues for the partial Wasserstein barycenter problem with three new ideas over the multicommodity flow algorithm, which are some of the main contributions:

  • Reformulating the problem as binary search over a collection of packing-like LPs, as partial Wasserstein barycenters do not form a standard packing LP. The LP we solve is not a packing LP, but since the equality ("non-packing") constraints are always satisfied by construction of the oracle, we prove that it behaves like one from the perspective of MWU.

  • Designing an efficient oracle for low weighted-cost kk-tuples using lazy weight updates (where weight updates affect the oracle only after accumulating sufficiently).

  • Developing a two-level MWU structure in Section 3, featuring distinct inner and outer MWU algorithms tailored to solve the oracle efficiently.

This is the reason why we cannot present the MWU algorithm as an LP black box. In view of the reviewer's comments, we will emphasize this point and say why we cannot use the LP algorithm as a black box.

[1] The multiplicative weights update method: a meta-algorithm and applications, Arora, Hazan, Kale

I thank the authors for the detailed response. I maintain my review of leaning towards acceptance. I understand that the LP solving part (as its the case in many applications) doesn't follow from the black-box. I suggest to the authors to present that part based on the standard LP formulation and then what modifications are required. This might come down to personal taste, but i think since LP solving via MWU is well known, most readers would likely be convinced by just seeing what needs to be done on top of standard solvers (such as described in the rebuttal response but more in-depth).

Reviewer_HzCQOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the partial Wasserstein barycenter problem: each input distribution transports α\alpha mass to the same target measure. The authors develop a fixed-support algorithm based on synchronized kk-tuple flow updates and multiplicative weights. Theorem 1 gives a runtime of n(m+k)δ−2log⁡O(1)Δn(m+k)\delta^{-2}\log^{O(1)}\Delta, with at most δ\delta mass loss and transport cost bounded by the optimal cost for mass α\alpha. For free support, the algorithm constructs candidate locations and compresses transport connections using pair decompositions, then reduces the resulting congestion through a second MWU procedure. The paper also extends an ellipsoid method to exact computation in fixed dimension.

Critical strengths
  1. The synchronized updates preserve equal incoming mass from every input distribution at each barycenter point. This gives a direct construction for the partial-barycenter packing LP and a useful approach to handling its multimarginal constraints. The compact formulation avoids the full transport tensor used by Le et al. (2022).
  2. The paper covers fixed and free supports, Euclidean and general metric spaces, and several cost-versus-runtime tradeoffs. The examples in Appendix A make the motivation for requiring a shared partial barycenter easy to understand.
Critical weaknesses
  1. Lemma 10 needs a valid feasibility argument. It states that every feasible flow in Figure 2(i) remains feasible in Figure 2(ii), while Appendix F, Eqs. (12)–(13), evaluates the weighted constraint using arbitrary representatives. Consider a distribution with mass 1/21/2 at each of two nearby points at unit distance from a target yy, and a second distribution concentrated at yy. Assign penalty weights 40,3440,34 to the first two points and 6363 to the second input. The original LP admits mass 11 with weighted cost 100100. Taking the weight-4040 point as representative raises the full-mass weighted cost to 103103. With g=1/2g=1/2 and δ=0.005\delta=0.005, the budget g/δ=100g/\delta=100 permits only 100/103≈0.9709100/103\approx0.9709 mass after compression, below α−δ=0.985\alpha-\delta=0.985 for α=0.99\alpha=0.99. The two weights can share a permitted bucket. The proof needs to account for this distortion before using the compressed LP to reject a cost guess or prove Theorem 2's mass bound.

  2. Theorem 3 needs additional computational assumptions. Appendix G.2 uses the condition on unweighted bisectors to bound the complexity of additively weighted Voronoi diagrams; the condition does not supply that bound. Lines 1525–1527 also count each pp-centroid computation as O(dk)O(dk), although Euclidean p=1p=1 requires a geometric-median computation. The authors should specify how these operations are performed for the stated distance class. The exact runtime also needs an encoding-length parameter: the spread Δ\Delta does not bound the coefficient precision required by the ellipsoid result in Theorem 4.

  3. Minor issues in the binary-search reduction. Sec. 2 needs an initial cost bound that includes the prescribed support YY. Two unit-mass inputs at 0,10,1 have Δ=2\Delta=2, while Y={10}Y=\{10\} gives squared cost 90.590.5, outside [0,Δ][0,\Delta]. The decision tolerance and final rescaling also need separate error budgets, since (α−δ)/(1+δ)<α−δ(\alpha-\delta)/(1+\delta)<\alpha-\delta.

  4. Formula corrections. In Lemma 16, the individual dual variable should be ωi(y)=min⁡x∈Xi{dp(x,y)+πi(x)}\omega_i(y)=\min_{x\in X_i}\{d^p(x,y)+\pi_i(x)\}. The separating hyperplane in Appendix G.2, lines 1537–1540, needs its λ′\lambda' term.

Questions for authors

Clarify the weakness.

6 comments
AuthorsOpenReview ↗

Response to Reviewer HzCQ

We thank the reviewer for their meticulous and insightful reading of our work. Below, we address their concerns in detail and outline corresponding revisions for the final manuscript.

Lemma 10 and feasibility argument: We thank the reviewer for identifying the issue that the statement in Lemma 10 was imprecise in the sense that a feasible solution for Figure 2(i) does not have the same size as a feasible solution for Figure 2(ii). The lemma statement should indeed be modified to state (at a high level): "Any feasible flow in Figure 2(i) can be modified to a feasible solution in Figure 2(ii)." However, we emphasize that the counterexample described by the reviewer is not a concern since, by the construction of the pair decomposition over weighted distances, we note that two points x1,x2∈Xix_1, x_2 \in X_i can only be in the set AjA_j for some pair (Aj,Bj)∈Πi(A_j, B_j) \in \Pi_i if the weights of x1x_1 and x2x_2 differ by a factor of at most (1+δ)(1+\delta). The reviewer observes precisely the kind of error that is possible if we were not careful with the point weights. This is why we bucket points by weights in lines 405-410; see also lines 1142-1158.

Theorem 3 computational assumptions and bit complexity: For the purposes of exposition, we had decided to highlight the combinatorial complexity of the algorithm and hide some of the details on its algebraic complexity. In retrospect, this meant the following three details were treated imprecisely and caused unintentional confusion in the description and analysis of the algorithm. We address them here and will make the statement of Theorem 3 more precise:

  • To keep the runtime bound simple, we assumed the bit complexity of the input, i.e. total number of bits used to represent the input, is L=poly(n,log⁡Δ)L = \text{poly}(n, \log \Delta). To be precise, the ellipsoid method is a weakly polynomial time algorithm with complexity that depends on LL. We will make a more formal treatment of the bit complexity in revisions.

  • For p=1,2p=1, 2, and ∞\infty, bisectors are piecewise-linear, so any standard model of computation works. For other values of pp, bisectors are algebraic varieties of fixed degree assuming pp is constant. We will explicitly state that the algorithm is described under the real RAM model of computation, which assumes that roots of a fixed degree polynomial can be computed in O(1)O(1) time [1,2]. Assuming the bisector is an algebraic variety of constant degree ensures that the lower envelope of the distance functions can be computed in nO(d)n^{O(d)} time under the real RAM model [3]. The Voronoi diagram is simply the projection of the graph of the lower envelope of the distance functions, so the Voronoi diagram can also be computed in nO(d)n^{O(d)} time.

  • Regarding the pp-centroid computations, we clarify that while p=2p=2 admits an O(dk)O(dk) time closed-form solution, the reviewer is correct that p=1p=1 (geometric median) and p>2p > 2 require more care to compute algebraically. It is known that for a given ϵ>0\epsilon > 0, the geometric median can be computed in dklog⁡3(k/ϵ)dk \log^3(k/\epsilon) time [4]. Moreover, for any p>1p > 1, the centroid can be approximated up to ϵ\epsilon-precision in poly$(d, k, L, \log(1/\epsilon))$ time using convex optimization, where LL is the bit complexity of the points [5]. As such, we can compute an ϵ\epsilon-additive approximation of the barycenter in (ndlog⁡Δlog⁡(1/ϵ))O(1)(n^d \log \Delta \log(1/\epsilon))^{O(1)} time (again n≥kn \geq k is the sum of the sizes of input supports), which is what we often mean by a weakly polynomial-time exact algorithm when the output may have large precision. We will amend the manuscript to more precisely state the polynomial dependence on nn, kk, dimension dd, and log-precision.

Binary search reduction and initial cost bound: We appreciate the reviewer's careful check of the binary search setup. In Section 2, we will make the assumption that there exists a point of YY close to XX explicit. Otherwise, any distribution over YY is worse than choosing any distribution over XX. Additionally, we will explicitly apply the appropriate rescaling of δ\delta to guarantee the desired error bound. Since this is only a small constant factor, we ignored the rescaling in the analysis.

Formula corrections: We thank the reviewer for catching these specific typos.

  • In Lemma 16, the dual variable formula will be corrected to ωi(y)=min⁡x∈Xidp(x,y)+πi(x)\omega_i(y) = \min_{x \in X_i} \mathrm{d}^p(x, y) + \pi_i(x) (removing the incorrect summation over ii).

  • In Appendix G.2 (lines 1537--1540), the separating hyperplane equation will be updated to correctly include λ′\lambda' term.

[1] Computational geometry: an introduction, Preparata and Shamos

[2] Arrangements and their applications, Agarwal and Sharir

[3] On the number of cells defined by a family of polynomials on a variety, Basu, Pollack, Roy

[4] Geometric median in nearly linear time, Cohen et al.

[5] Geometric algorithms and combinatorial optimization, Grötschel, Lovász, Schrijver

Thank you for the response. The corrections to Lemma 16 and the separating hyperplane are fine, and so is the rescaling of δ\delta. For the initial bound, starting the search from max⁡x∈X, y∈Ydp(x,y)\max_{x\in X,\,y\in Y} d^p(x,y), with the spread taken over X∪YX\cup Y, would avoid the extra assumption on YY.

My main concern about Lemma 10 remains. The response says that points sharing a set AjA_j have weights within a factor of 1+δ1+\delta. The paper states 1+ε1+\varepsilon (lines 405–410 and 1148–1150), and the construction in lines 1161–1164 uses dyadic buckets as written. Since ε\varepsilon is independent of δ\delta in Theorem 2, the weights 34 and 40 can share a group, so the example does apply to the submitted version. Grouping within a factor of 1+δ1+\delta is the right fix, but it changes the construction, and the revised lemma ("can be modified to a feasible solution") still does not say how much mass is kept.

The same distortion affects Lemma 4 in the other direction. The LP constraint used in lines 1110–1114 charges each group at the weight of its representative, whereas Lemma 12 charges the redistributed flow at the weights of the individual points. With (1+ε)(1+\varepsilon) groups, the congestion bound becomes roughly (1+ε)(1+δ)(1+\varepsilon)(1+\delta).

Could you state the corrected Lemma 10 with an explicit bound on the retained mass (I would expect ν(Y)/(1+δ)\nu(Y)/(1+\delta)) and confirm that Lemma 4 and the α−δ\alpha-\delta guarantee of Theorem 2 then go through? A short statement in this thread is enough.

On Theorem 3, once the pp-centroids are only approximated, the algorithm returns an additive approximation of the barycenter and not an exact solution. Theorem 3 and the abstract should say so and claim exactness only where the centroids can be computed exactly, as in the squared Euclidean case. The bisector assumption should also be stated for the additively weighted bisectors, since those are the boundaries of the Voronoi cells.

I will keep my score for now and I will revisit my score after the Lemma 10 argument is made precise and Theorem 3 is restated.

AuthorsOpenReview ↗

Response to Reviewer HzCQ Part 1

We greatly thank the reviewer for their incredible attention to detail and insightful comments. To fully address the reviewer's comments, we break our response into three separate comments.

We misunderstood their original concern regarding Lemma 10 and agree with their assessment that δ\delta must be a factor in the bucketing. On lines 405-410, 1148-1150, and 1161-1164, we will bucket the weights in each AjA_j such that ϕi(x1)≤(1+min⁡(ε,δ))⋅ϕi(x2)\phi_i(x_1) \leq (1 + \min(\varepsilon, \delta)) \cdot \phi_i(x_2) for any x1,x2∈Ajx_1, x_2 \in A_j. We will revise the text in the final version to remove any unintended assumptions regarding the relationship between ε\varepsilon and δ\delta. The precise statement of Lemma 10 will proceed as follows:

Lemma 10. For any guess g>0g > 0 and any feasible solution f1,…,fk,νf_1, \dots, f_k, \nu to the LP in Figure 2(i) with respect to guess gg, there exists a guess g~≤(1+ε)p⋅g\tilde{g} \leq (1+\varepsilon)^p \cdot g and a feasible solution f~1,…,f~k,ν~\tilde{f}_1, \dots, \tilde{f}_k, \tilde{\nu} to the LP in Figure 2(ii) with respect to g~\tilde{g} such that ν~(y)≥11+δν(y)\tilde{\nu}(y) \geq \frac{1}{1+\delta} \nu(y) for all y∈Yy \in Y.

Here, we highlight the explicit construction and proof details for Lemma 10.

Proof. Suppose f1,…,fk,νf_1, \dots, f_k, \nu is a feasible solution to the LP of Figure 2(i). We construct a feasible solution to the LP of Figure 2(ii) as follows. For each (Aj,Bj)∈Πi(A_j, B_j) \in \Pi_i and each y∈Bjy \in B_j define f~i(x~j,y)\tilde{f}_i(\tilde{x}_j, y) to be

∑xi∈Ajfi(xi,y)\sum_{x_i \in A_j} f_i(x_i, y).

Since f1,…,fk,νf_1, \dots, f_k, \nu is feasible for Figure 2(i), we conclude:

f~i(x~j,Bj)\tilde{f}_i(\tilde{x}_j, B_j)

=∑y∈Bjf~i(x~j,y)= \sum_{y \in B_j} \tilde{f}_i(\tilde{x}_j, y)

=∑y∈Bj∑xi∈Ajfi(xi,y)= \sum_{y \in B_j} \sum_{x_i \in A_j} f_i(x_i, y)

≤∑xi∈Ajμi(xi)\leq \sum_{x_i \in A_j} \mu_i(x_i)

=μi(x~j)= \mu_i(\tilde{x}_j).

Moreover, by the construction of Πi\Pi_i, for every (Aj,Bj)∈Πi(A_j, B_j) \in \Pi_i, x1,x2∈Ajx_1, x_2 \in A_j, and y1,y2∈Bjy_1, y_2 \in B_j, we have dp(x1,y1)≤(1+ε)p⋅dp(x2,y2)\mathrm{d}^p(x_1, y_1) \leq (1 + \varepsilon)^p \cdot \mathrm{d}^p(x_2, y_2) and ϕi(x1)≤(1+min⁡(ε,δ))⋅ϕi(x2)\phi_i(x_1) \leq (1+\min(\varepsilon, \delta)) \cdot \phi_i(x_2). We conclude that

&cent;_p(\tilde{f}_1, \dots, \tilde{f}_k) \leq (1 + \varepsilon)^p \cdot &cent;_p(f_1, \dots, f_k).

Furthermore, since &THORN;(\phi_1, \dots, \phi_k, f_1, \dots, f_k) \leq &THORN;(\phi_1, \dots, \phi_k) = \frac{g}{\delta} for any feasible set of flows f1,…,fkf_1, \dots, f_k (by assumption on ϕ1,…,ϕk\phi_1, \dots, \phi_k and the demand constraints), we also have &THORN;(\phi_1, \dots, \phi_k, \tilde{f}_1, \dots, \tilde{f}_k) \leq (1 + \min(\varepsilon, \delta)) \cdot \frac{g}{\delta}. As the reviewer suggested, this reduction incurs an extra (1+min⁡(ε,δ))(1 + \min(\varepsilon, \delta)) distortion in the dual constraints, so rescaling the flow by a (1+min⁡(ε,δ))−1(1 + \min(\varepsilon, \delta))^{-1} factor suffices. ◻

In the initial submission, we omitted constant rescalings of δ\delta since they only incur an additional constant factor in the runtime; we will also clarify this precise constant rescaling in the final version of the paper. Finally, we are content with a (1+ε)p(1+\varepsilon)^p distortion in the cost &cent;_p because the barycenter objective function raises this cost to the power 1/p1/p.

Reviewer_tVUaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the α\alpha-partial Wasserstein barycenter $(\alpha $-PWB) problem, a formulation designed to build outlier-robust average probability distributions by forcing multiple unbalanced optimal transport (OT) plans to share a single target measure restricted to mass α\alpha While this approach better preserves the geometric centroid nature of standard barycenters compared to methods that select outliers independently per distribution, its complex multimarginal constraints have historically made it computationally intractable. To resolve this, the authors introduce the first provably efficient approximation algorithms for the α\alphaPWB problem. Their fixed-support algorithm operates in arbitrary spaces within quadratic time or less—parameterized by support size and mass approximation error—while their free-support version speeds up execution in metric spaces at the cost of an additional approximation error on the OT plans. Additionally, they establish that an exact solution to the α\alpha-PWB problem can be computed in polynomial time.

Critical strengths
  • the primary contribution is providing the very first approximation algorithms for the α\alpha-partial Wasserstein barycenter problem with provable time complexities. Overcoming the complex multimarginal constraints in quadratic time or less (O~(m⋅n/ϵ2)(\tilde{O}(m \cdot n/\epsilon^2)) is a significant computational breakthrough.
  • the paper clearly articulates and illustratesthe core flaw in alternative robust Wasserstein barycenter methods, that decoupled transport plans can choose conflicting outlier regions. By forcing all input distributions to transport mass onto the exact same barycenter measure $\nu $, this work truer captures the foundational geometric centroid property of barycenters.
  • this work provided a toolkit by tackling multiple settings: offering a fixed-support algorithm for arbitrary spaces, a faster free-support refinement for metric spaces, and setting a theoretical baseline by demonstrating that an exact solution can be computed in roughly mO(k)m^{O(k)} time.
Critical weaknesses
  • While the approximation algorithms run efficiently, the exact algorithm's time complexity is roughly mO(k)m^{O(k)}, where k is the number of input distributions. This exponential scaling means finding exact solutions remains strictly impossible for large datasets with many input measures.
  • to drop the runtime complexity by a factor of mm in the free-support framework, the second algorithm introduces an additional approximation error specifically to the cost of the OT plans. The paper did not thoroughly unpack how severe this cost degradation is under highly skewed or non-uniform geometric setups.
Questions for authors

While the approximation algorithms show great performance relative to the point totals n and support size m how do their practical runtimes scale as the total number of input distributions k grows into the hundreds or thousands?

1 comment
AuthorsOpenReview ↗

Response to Reviewer tVUa

We thank the reviewer for their thoughtful feedback and address their main concerns below.

Time complexity of the exact algorithm: The reviewer notes a potential mO(k)m^{O(k)} exponential dependence on kk. There is some misunderstanding as stated in Theorem 3, our exact algorithm actually runs in (ndlog⁡Δ)O(1)(n^d \log \Delta)^{O(1)} time, up to bit complexity and ε\varepsilon-precision factors, where nn is the sum of support sizes, yielding polynomial dependence on kk assuming dd is independent of kk (d≪kd \ll k in many realistic datasets).

Accuracy of approximation algorithms: We clarify the definitions of different approximations discussed in the paper.

  • Relative vs. Relaxed: A (1+ϵ)(1+\epsilon)-relative approximate solution ff satisfies wp(f)≤(1+ϵ)wp(f∗)w_p(f) \leq (1+\epsilon)w_p(f^*). Greedily removing the most expensive ϵ\epsilon fraction of mass from ff yields a δ\delta-relaxed solution (transporting α−δ\alpha-\delta mass at cost ≤wp(f∗)\leq w_p(f^*)). Thus, the relative guarantee is stronger.

  • Relaxed vs. Additive: A δ\delta-relaxed solution transports α−δ\alpha-\delta mass at cost ≤wp(f∗)\leq w_p(f^*). Arbitrarily adding the unrouted mass incurs at most a δ\delta-additive error, yielding a δ\delta-additive approximation. Thus, the relaxed guarantee is stronger than the ϵ\epsilon-additive approximation.

While standard ML optimal transport papers (e.g., Sinkhorn-based) typically guarantee additive approximations, we use (1+ϵ)(1+\epsilon)-relative and δ\delta-relaxed solutions for their stronger guarantees. We make a remark in the paper that δ\delta-relaxation could be converted into δ\delta-additive approximation, so we also present the first δ\delta-additive approximation algorithm with O~(mnε−2)\tilde{O}(mn \varepsilon^{-2}) runtime. We realize that mixing approximation types can be confusing, and we will clarify this distinction more explicitly in the text (building on lines 108–114).

Dependence on the number of distributions: From a theoretical perspective, our algorithm has quadratic dependence on kk in the worst case and linear number of iterations with respect to kk (since nn, the sum of input support sizes, has linear dependence on kk implicitly). Practically speaking, obtaining high quality solutions in o(k2)o(k^2) time is highly nontrivial since the complexity of all the transport plans is typically Ω(k2)\Omega(k^2): even in simple instances, the optimal barycenter often has a support of size m>km > k, and every mass of the barycenter distribution is transported to at least kk different masses (one for each input distribution). In the revised version of the paper, we also include an experimental study exploring specifically the number of iterations our algorithm makes. On synthetically generated data, we find that the number of iterations the algorithm takes indeed scales only linearly with kk: for examples where d=2,∣Xi∣=15d=2, |X_i|=15 for each ii, small error δ=0.03\delta = 0.03, and k=5,10,15,20,25k=5, 10, 15, 20, 25, we find that the iteration counts per fixed guess call of the MWU algorithm in the binary search are t=2.34×105,5.16×105,8.18,×105,1.09×106,1.39×106t = 2.34 \times 10^5, 5.16 \times 10^5, 8.18, \times 10^5, 1.09 \times 10^6, 1.39 \times 10^6 on average.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.