acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Free-Support Wasserstein Barycenter

14 views

Abstract

We study the decentralized computation of free-support Wasserstein barycenters (WBs) problem over arbitrary connected undirected graphs. Existing decentralized WB methods typically prescribe a shared support and optimize only its associated weights. Although this formulation leads to a tractable convex consensus problem, it prevents the WB support from adapting to the geometry of the input measures. We instead propose a decentralized free-support WB solver that learns continuously movable locations for an equal-mass atomic barycenter within a majorization-minimization (MM) framework. We establish theoretical guarantees under two distinct aggregation schemes: under exact aggregation, we prove monotone MM descent and a best-iterate Clarke-stationarity guarantee; under gossip-based aggregation, we characterize two regimes: using a fixed gossip depth yields topology-dependent bounds on disagreement and the network-average update, whereas increasing gossip sufficiently over rounds ensures that disagreement vanishes and every accumulation point of the exact-transport iterates is Clarke stationary. To our knowledge, this is the first fully decentralized, peer-to-peer neighbor-gossip framework for WB computation with continuously movable support locations. Experiments on synthetic measures, image distributions, and 3D point clouds show that learning movable supports improves both barycenter quality and resource efficiency. Compared with representative fixed-support decentralized solvers, our method achieves lower WB objectives and better geometric fidelity while reducing computation and communication by up to three orders of magnitude, with reductions exceeding three orders of magnitude in selected settings. The resulting WBs also provide effective nominal distributions for cooperative data-driven distributionally robust optimization (DRO), achieving the lowest validation loss among the decentralized-DRO baselines. Code available at [**Anonymous GitHub**](https://anonymous.4open.science/r/Decentralized-Free-Support-Wasserstein-Barycenter-FED9/README.md).

Primary area:
optimization
Keywords:
Nonconvex and Nonsmooth Optimization, Optimal Transport, Wasserstein Barycenter, Gossip Communication

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_R4iYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies decentralized free-support Wasserstein barycenter computation over connected undirected networks. Rather than optimizing weights on predefined supports, the proposed method learns the locations of a fixed number of equal-mass atoms. The authors develop an interpolation-then-gossip algorithm within a majorization-minimization (MM) framework, where each agent computes local optimal transport plans, constructs barycentric projections, updates support locations, and exchanges information with neighboring agents through gossip averaging. The theoretical analysis considers three communication regimes: exact aggregation guarantees monotone descent and an O(1/R)\mathcal{O}(1/R) best-iterate bound on the squared norm of a selected Clarke subgradient; fixed-depth gossip yields topology-dependent bounds on consensus disagreement and network-average updates; and sufficiently increasing gossip depth ensures that all accumulation points are Clarke stationary. Experiments on synthetic distributions, MNIST, 3D point clouds, and cooperative distributionally robust optimization evaluate the proposed method against centralized and decentralized baselines in terms of solution quality, computational efficiency, and communication costs.

Critical strengths
  1. The paper provides a systematic convergence analysis across different communication regimes, carefully distinguishing consensus disagreement from stationarity. The treatment of nonunique optimal transport plans without assuming continuity is technically meaningful.

  2. The experiments cover diverse datasets and network configurations, demonstrating promising improvements in solution quality and communication efficiency. The inclusion of node-local evaluations and terminal-gossip costs further strengthens the empirical validation.

Critical weaknesses
  1. The proposed method primarily combines existing free-support barycentric updates [1] with standard gossip averaging. Prior work on decentralized displacement interpolation [2] also raises questions about the claimed novelty of peer-to-peer movable-support computation.

  2. The theoretical analysis largely builds on standard MM and consensus arguments, while the fixed-depth gossip scheme used in experiments only provides bounds on disagreement and average updates, rather than approximate Clarke stationarity.

  3. The method requires common ordered initialization and consistent atom labels across agents, reducing support coordination to row-wise Euclidean consensus and limiting its applicability to independently initialized or unaligned supports.

References

[1] M. Cuturi and A. Doucet. Fast Computation of Wasserstein Barycenters. ICML, 2014.

[2] P. Cisneros-Velarde and F. Bullo. Distributed Wasserstein Barycenters via Displacement Interpolation. IEEE Transactions on Control of Network Systems.

Questions for authors
  1. Could the authors clarify the key methodological differences from Cuturi and Doucet (2014) and Cisneros-Velarde and Bullo (2023), particularly what novel algorithmic insights arise from combining free-support updates with decentralized gossip?

  2. Can the authors further clarify the theoretical novelty beyond standard MM and consensus analyses? In particular, what convergence or stationarity guarantees can be established for the fixed-depth gossip scheme used in practice?

  3. How sensitive is the proposed method to the common ordered initialization and consistent atom correspondence assumptions? Could independently initialized or misaligned supports significantly affect convergence and solution quality?

  4. Could the authors reconcile the stabilization statistics in Table 6 with the round-10 objective reported in Table 18, which appears inconsistent with the stated 0.1% stability criterion?

12 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/3)

We sincerely thank the reviewer for the valuable comments and the time devoted to reviewing our manuscript. In the following, W denotes Weakness, Q denotes Question, and R denotes Reference. All revisions are highlighted in blue\textcolor{blue}{blue} in the manuscript.


W1&Q1: Clarify the key methodological differences from Cuturi (2014) [R1] and Cisneros (2023) [R2]

(1) R1 and R2 only consider the free-support 2-Wasserstein barycenter. The 2-Wasserstein barycenter is commonly regarded as a generalization of k-means. Therefore, methods for 2-Wasserstein barycenters naturally share similarities in their high-level designs, since the squared Euclidean cost admits closed-form support updates. Importantly, these methods still differ substantially from ours in their underlying algorithmic mechanisms and implementation details. We summarize the key differences as follows:

(2) Our solver can handle free-support pp-Wasserstein barycenters for arbitrary pp, and provides the corresponding theoretical analysis (both our method and theoretical analysis are also applicable to non-decentralized settings.

  • (i) As stated in §3 Page5 Remark1, within our methodological framework, the methods of [R1] can be regarded as special cases of our framework for the 2-Wasserstein barycenter, and [R1] only can solve centralized WBs problem with a heuristic algorithmic approach.. (ii) [R2] randomly selects only one edge (i,j)(i,j) and computes OT between the two agents' current distributions. Importantly, [R2] convergence to the original WB is guaranteed only under restrictive conditions. In our attempts to reproduce [R2], we observed higher communication costs than fixed-support methods and extreme difficulties in achieving convergence for most setting. Thus, [R2] is primarily a theoretical consensus analysis rather than an efficient WBs solver. (iii) In contrast, our method computes OT between each agent's current barycenter estimate and its fixed local data distribution, followed by neighbor gossip and support interpolation for exponential moving average.
  • We further provide in additional numerical results for p≠2p\neq2 in §5 Page10 to highlight the advantage of our method in solving free-support pp-WBs for arbitrary pp.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}}

📍§A Page17, We further highlight our contributions in the main contributions section, emphasizing our contribution for general pp-Wasserstein barycenters and for decentralized WBs solvers. we also expand the literature review by providing more detailed descriptions of the related works.

📍§5 Page10, we provided additional results for p=1.5,3,10p=1.5, 3, 10, demonstrating substantially better performance than existing decentralized fixed-support methods (Table1).


W2&Q2 (Part1): The theoretical analysis largely builds on standard MM and consensus arguments.&Can the authors further clarify the theoretical novelty beyond standard MM

  1. Majorization-minimization (MM) is a general optimization framework. The basic idea of MM is general: construct an easy-to-optimize surrogate upper bound and optimize this bound to improve the original objective. Using the same proof technique for different problems does not imply that they share the same algorithms, objective functions, update mechanisms, or convergence properties.

  2. We address the challenges of free-support Wasserstein barycenters problem in decentrealized setting, where free-support WBs computation is described as notoriously difficult to optimiz [R3]. We do not propose a new MM analysis technique. Instead, we develop a general methodology and convergence theory for WBs that handles nonunique OT couplings, movable supports, nonconvex and nonsmooth objectives, and finite neighbor communication. Specifically,

    • Our method is specific to the WB problem: By freezing the optimal transport plans, we transform the nonconvex and nonsmooth free-support Wasserstein barycenter problem into a tractable support-update problem.
    • Our theory addresses the specific challenges of OT: In our WB problem, optimal transport plans may be nonunique and can change discontinuously as the support moves. Therefore, standard distributed optimization proofs that require smooth gradients cannot be directly applied.
    • Our framework handles general pp: When p=2p=2, the update admits a closed-form weighted mean. When p≠2p\neq2, it becomes a convex pp-Fréchet inner optimization problem, for which we further analyze the solution errors arising from finite communication in §3 Page 5 Remark.
AuthorsOpenReview ↗

Official Comment by Authors (2/3)

W2&Q2 (Part2): what convergence or stationarity guarantees can be established for the fixed-depth gossip scheme?

  1. Strong convergence rate guarantees are challenging for general pp-Wasserstein Barycenters. Establishing strong convergence-rate guarantees for nonconvex and nonsmooth optimization of arbitrary pp-Wasserstein barycenters, which is NP-hard in general [R4], is particularly challenging without imposing regularity conditions and decentralized setting.

  2. Nevertheless, we can establish a stronger convergence guarantee by introducing a mild additional assumptions. For instance,

    • Assumption: WS⪰0\mathbf W^S\succeq0 and 2-Wasserstein Barycenter problem,

    • Result: With fixed gossip depth, the support sequence eventually converges linearly, and the WB objective converges geometrically to its limiting value asshown in §4 Page7 and §C.3 Page39. Specifically, there exists a sufficiently large but finite r0r_0 and a constant C>0C>0, independent of tt, such that, ∣F(Bˉ(r0+t))−F(Bˉ∞)∣≤C(1−η)t.|F(\bar{\mathbf B}^{(r_0+t)}) -F(\bar{\mathbf B}^{\infty})| \le C(1-\eta)^t. For η=1\eta=1, the support sequence stabilizes after finitely many iterations.

  3. Stronger global approximation guarantees inspired by [R5] and [R6]. Suggested by reviewer qWMt, we further establish global approximation guarantees for our decentralized free-support 2-Wasserstein barycenter framework.

    • Assumption: Under a shared public support of at most mm points, with atom masses initialized by a single aggregation, and WS⪰0\mathbf W^S\succeq0 for fixed-depth gossip.

    • Result: Here, Fm⋆F_m^\star denotes the global minimum over both support locations and atom masses.

      • 2-approximation under fully connected aggregation F(B(r);a)≤2Fm⋆,F(\mathbf B^{(r)};\mathbf a)\le 2F_m^\star,
      • (2+ϵ2+\epsilon)-approximation under sufficiently large but fixed gossip depth F(Bˉ(r);a)≤2(1+ηρS1−ρS)Fm⋆.F(\bar{\mathbf B}^{(r)};\mathbf a)\le 2(1+\frac{\eta\rho^S}{1-\rho^S})F_m^\star.
    • Comparison with [R5] and [R6]: [R5] establishes a (5+O(ε))(5+O(\varepsilon))-approximation using a near-optimal k-means subroutine, while [R6] provides a (2+β)2(2+\sqrt{\beta})^2-approximation (approximately 99 for β≈1\beta\approx1) for the standard k-sparse case, where β\beta is the clustering approximation factor. Our result achieves a smaller approximation factor while explicitly accounting for finite-depth decentralized communication.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}}

📍§4 Page 7 and §D.2 Page 39, we provided stronger linear convergence guarantees for fixed-depth gossip under a few mild additional assumptions (Theorem 5).

📍§4 Page 7 and §D.5 Page 47, we provided 2-approximation under fully connected aggregation and (2+ϵ2+\epsilon)-approximation under sufficiently large but fixed gossip (Theorem 6).


W3&Q3: The method requires common ordered initialization and consistent atom labels across agents.

  1. Our method does not depend on common ordered initialization. We adopt common ordered initialization to ensure a fair comparison with fixed-support methods, as these methods inherently require the same support locations across agents, which remain fixed throughout the entire optimization process.
  2. Another reason we choose common ordered initialization is to facilitate theoretical analysis. Since we aim to provide a general theoretical framework, we adopt common ordered initialization to avoid introducing additional regularity conditions. However, our method itself does not depend on same initialization, and using the same initialization in practice is very easy to achieve (e.g., by same random seed).
  3. We additionally provide experiments comparing shared and random initializations to address the reviewer's concern. As shown in §5, P10, Fig. 8, both settings exhibit comparable convergence trends and initial disagreement contributes a geometrically decaying transient and arbitrary initialization has almost no effect on the convergence results.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}}

📍§3 Page5, we clarified the description from shared ordered initialization to arbitrary initialization.

📍§5 Page10, we additionally provided a numerical comparison between arbitrary support initialization and fixed-support initialization (Fig.8).


AuthorsOpenReview ↗

Official Comment by Authors (3/3)

Q4: stabilization statistics in Table 6 with the round-10 objective reported in Table 18.

We thank the reviewer for carefully checking these numerical results. Table 18 was obtained from a separate rerun conducted at a later stage under a different CPU computing environment. Although the experimental settings remained unchanged, differences in CPU architectures, numerical libraries, floating-point accumulation, and the internal operations of exact OT solvers may lead to slightly different optimal transport plans and subsequent optimization trajectories. These numerical variations can account for the small difference between the reported objectives (0.09085 vs. 0.090115 WB obj.).

Importantly, the objective improvements over all fixed-support baselines (e.g. 0.18351 WB obj.) remain in the range of 40.2%–50.5%. This minor numerical correction does not affect our conclusions or the previously reported approximately 99% reductions in optimization rounds and computational cost.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}} To ensure consistency, we have rerun the Gaussian experiments under a unified computational environment, ensuring that the revised results are obtained from the same runs.


Referece:\boldsymbol{\textbf{Referece:}}

[R1]: Fast Computation of Wasserstein Barycenters. ICML 2014

[R2]: Distributed Wasserstein Barycenters via Displacement Interpolation. IEEE Transactions on Control of Network Systems 2023

[R3]: Fixed-support wasserstein barycenters: Computational hardness and fast algorithm. NeurIPS 2020.

[R4]: Wasserstein Barycenters Are NP-Hard to Compute. SIAM Journal on Mathematics of Data Science, 2022.

[R5]: Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-Sparse Wasserstein Barycenter Problems. ICLR 2025

[R6]: Approximate Algorithms for k-Sparse Wasserstein Barycenter with Outliers. IJCAI 2024

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

This paper studies free-support Wasserstein Barycenter problem in decentralized fashion. Given several probability distributions, Wasserstein Barycenter is some "center" probability among all given distributions, while minimizing the sum of Wasserstein distance. "Decentralized" fashion restricts that each distribution (or so called agent) can only transport its mass to its neighbour defined by an undirected graph and there is no central server that can handle all information in global level. Free support means the support locations of the barycenter is not fixed, but we know the number of supports and each support carries equal mass, according to this paper's setting. They propose so called majorization-minimization (MM) framework, which learns and moves support locations forwards to "centroid" iteratively. They claimed the iteration will converge to a first-order stationary. Finally, they conduct experiments to verify their methods with baselines.

Critical strengths
  1. The problem they study is classic and important. Wasserstein Barycenter is one of the most important problems in the area of theory of machine learning and optimization. It also has broad implementations in practice.
  2. The theoretical and practical contributions are solid and clear.
Critical weaknesses
  1. Novelty is overstated and poorly positioned. With exact aggregation, the algorithm is Cuturi–Doucet’s free-support iteration. The decentralized version is adapt-then-combine decentralized gradient descent with multi-step mixing. Besides, The novelty claim of being “first decentralized free support WB” should be carefully checked. Bishop & Doucet (IFAC 2014; SICON 2021) and Cisneros-Velarde & Bullo (“Distributed Wasserstein Barycenters via Displacement Interpolation,” arXiv:2012.08610) also discussed the similar setting for free support WB. I suggest the authors to add some extra discussions.
  2. The theoretical guarantee is weak. The major guarantee is the first-order stationary, without global approximation. Although free-support WB is NP-hard, approximating it is possible. (Song et al. Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems. ICLR' 25) and (Yang et al. Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers IJCAI' 24) provided global approximation ratio for free-support WB. Maybe their idea also works for this paper.
  3. The symbol system is so complicated, which makes the paper hard to follow through. For example, Closely related quantities multiply without a clear system: Δ,Δ^,Δˉτ,Δτ,Δp,Δ(B)\Delta, \hat\Delta, \bar\Delta_\tau, \Delta_\tau, \Delta_p, \Delta(B); Ti,T,T~,Tˉτ,Tp,T^pT_i, T, \tilde T, \bar T_\tau, T_p, \hat T_p; Q,Q~r,Qp,Qτ,Q^τQ, \tilde Q_r, Q_p, Q_\tau, \hat Q_\tau.
Questions for authors

I am curious about the relation with k-means. I feel that the proposed algorithm is very similar to Lloyd k-means method, move the current center to its centroid in each iteration. In fact, (Song et al. Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems. ICLR' 25) used k-means perspective to analyse WB. Is there any global approximation using the similar analysis?

5 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

We sincerely thank the reviewer for the thoughtful and constructive comments and the time devoted to reviewing our manuscript. In the following, W denotes Weakness, Q denotes Question, and R denotes Reference. All revisions are highlighted in blue\textcolor{blue}{blue} in the manuscript.


W1: Add some extra discussions of Cuturi (2014) [R1] and Cisneros (2023) [R2]

(1). R1 and R2 only consider the free-support 2-Wasserstein barycenter. The 2-Wasserstein barycenter is commonly regarded as a generalization of k-means. Therefore, methods for 2-Wasserstein barycenters naturally share similarities in their high-level designs, since the squared Euclidean cost admits closed-form support updates. Importantly, these methods still differ substantially from ours in their underlying algorithmic mechanisms and implementation details. We summarize the key differences as follows:

(2). Our solver can handle free-support pp-Wasserstein barycenters for arbitrary pp, and provides the corresponding theoretical analysis (both our method and theoretical analysis are applicable to non-decentralized settings.

  • (i) As stated in §3 Page5 Remark1, within our methodological framework, the methods of [R1] can be regarded as special cases of our framework for the 2-Wasserstein barycenter, and [R1] only can solve centralized WBs problem with a heuristic algorithmic approach.. (ii) [R2] randomly selects only one edge each round and computes OT between the two agents' current distributions. Importantly, [R2] convergence to the original WB is guaranteed only under restrictive conditions. In our attempts to reproduce [R2], we observed higher communication costs than fixed-support methods and extreme difficulties in achieving convergence for most setting. Thus, [R2] is primarily a theoretical consensus analysis rather than an efficient WBs solver. (iii) In contrast, our method computes OT between each agent's current barycenter estimate and its fixed local data distribution, followed by neighbor gossip and support interpolation for exponential moving average.
  • We further provide in additional numerical results for p≠2p\neq2 in §5 Page10 to highlight the advantage of our work in solving free-support pp-Wasserstein barycenters for arbitrary pp.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}}

📍§A Page17, We further highlight our contributions in the main contributions section, emphasizing our contribution for general decentralized pp-Wasserstein barycenters solver. we also expand the literature review by providing more detailed descriptions of the related works.

📍§5 Page10, we provided additional numerical results for p=1.5,3,10p=1.5, 3, 10, demonstrating substantially better performance than existing decentralized fixed-support methods.


W3: The symbol system is so complicated.

We apologize for the additional reading burden caused by our notation, and sincerely thank the reviewer for the time and effort devoted to reviewing our manuscript. We would like to explain that the complexity of our notation arises from considering three different settings, each involving either an exact optimal transport solver or an entropy-regularized optimal transport solver.

Nevertheless, during the rebuttal period, we have simplified some of the notation and provided a notation table in the Appendix. Although a relatively detailed notation system is necessary to distinguish these settings, we will continue refining it to reduce the reading burden and improve the clarity of our manuscript.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}} 📍§Page15,we summarized the notations used in this paper along with their descriptions.

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

W2&Q1: The theoretical guarantee is weak & Although free-support WB is NP-hard, approximating it is possible in Song et al. (2025) [R3] and Yang et al. (2024) [R4].

We sincerely thank the reviewer for these constructive comments. The suggestions of approximation guarantees have been very helpful to us.

Our original theoretical analysis primarily focused on convergence rates, as faster convergence can substantially reduce communication costs in decentralized settings. Furthermore, in our response below, we clarify our existing theoretical results in (1) and (2). Inspired by the approximation guarantees established in [R3] and [R4], we also extend our theoretical analysis and establish additional results in (3).

(1) Strong convergence rate guarantees are challenging for general pp-Wasserstein barycenters. Establishing strong convergence-rate guarantees for nonconvex and nonsmooth optimization of arbitrary pp-Wasserstein barycenters, is particularly challenging without imposing regularity conditions and decentralized setting.

(2) Nevertheless, we can establish a stronger convergence guarantee by introducing a mild additional assumptions. For instance,

  • Assumption: WS⪰0\mathbf W^S\succeq0 and 2-WB problem,

  • Result: With fixed gossip depth, the support sequence eventually converges linearly, and the WB objective converges geometrically to its limiting value asshown in §4 Page7 & §C.3 Page39. Specifically, there exists a sufficiently large but finite r0r_0 and a constant C>0C>0, independent of tt, such that, ∣F(Bˉ(r0+t))−F(Bˉ∞)∣≤C(1−η)t.|F(\bar{\mathbf B}^{(r_0+t)}) -F(\bar{\mathbf B}^{\infty})| \le C(1-\eta)^t.

(3) Stronger global approximation guarantees inspired by [R3] and [R4]. We further establish global approximation guarantees for our decentralized free-support 2-Wasserstein barycenter framework.

  • Assumption: Under a shared public support of at most mm points, with atom masses initialized by a single aggregation, and WS⪰0\mathbf W^S\succeq0 for fixed-depth gossip.

  • Result: Here, Fm⋆F_m^\star denotes the global minimum over both support locations and atom masses.

    • 2-approximation under fully connected aggregation F(B(r);a)≤2Fm⋆,F(\mathbf B^{(r)};\mathbf a)\le 2F_m^\star,
    • (2+ϵ2+\epsilon)-approximation under sufficiently large but fixed gossip depth F(Bˉ(r);a)≤2(1+ηρS1−ρS)Fm⋆.F(\bar{\mathbf B}^{(r)};\mathbf a)\le 2(1+\frac{\eta\rho^S}{1-\rho^S})F_m^\star.
    • Comparison with [R3] and [R4]: [R3] establishes a (5+O(ε))(5+O(\varepsilon))-approximation using a near-optimal k-means subroutine, while [R4] provides a (2+β)2(2+\sqrt{\beta})^2-approximation (approximately 99 for β≈1\beta\approx1) for the standard k-sparse case, where β\beta is the clustering approximation factor. Our result achieves a smaller approximation factor while explicitly accounting for finite-depth decentralized communication.

The approximation guarantees in [R3] and [R4] are developed using k-means-based techniques and focus on the 2-WB problem. As discussed earlier, the 2-WB is commonly regarded as a generalization of k-means. This connection also helps explain the reviewer's observation in Q1 that our proposed algorithm resembles Lloyd's k-means method. Both approaches share a similar alternating optimization structure, while our method employs optimal transport couplings and decentralized gossip to update the barycenter support. Accordingly, our additional linear convergence and global approximation guarantees focus on the 2-WB setting, whereas our general framework extends to arbitrary pp.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}}

📍§4 Page 7 and §D.2 Page 39, we provided stronger linear convergence guarantees for fixed-depth gossip under a few mild additional assumptions.

📍§4 Page 7 and §D.5 Page 47, we provided 2-approximation under fully connected aggregation and (2+ϵ2+\epsilon)-approximation under sufficiently large but fixed gossip depth .


Referece:\boldsymbol{\textbf{Referece:}}

[R1]: Fast Computation of Wasserstein Barycenters. ICML 2014

[R2]: Distributed Wasserstein Barycenters via Displacement Interpolation. IEEE Transactions on Control of Network Systems 2023

[R3]: Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-Sparse Wasserstein Barycenter Problems. ICLR 2025

[R4]: Approximate Algorithms for k-Sparse Wasserstein Barycenter with Outliers. IJCAI 2024

AuthorsOpenReview ↗

Gentle Reminder (Submission #116)

Dear Reviewer qWMt,

As the discussion period draws to a close, we would sincerely appreciate it if you could kindly revisit our rebuttal responses and share any further feedback or concerns, if your schedule permits. We fully understand the significant time constraints during the review process and greatly appreciate your time and efforts. We would be grateful for the opportunity to address any remaining questions or concerns before the discussion period concludes.

Thank you again for your valuable time and contributions to the review process.

Submission Number: 116

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

The paper studies decentralized computation of the Wasserstein barycenter with continuously movable support locations and prescribed equal atom masses. For the squared W2W_2 objective, the proposed interpolation-then-gossip algorithm alternates local optimal transport computations, damped updates toward atom-wise barycentric targets, and neighbor communication of support matrices. A common ordered initialization establishes the atom correspondence needed for these gossip updates.

The analysis distinguishes three communication regimes: exact aggregation gives monotone majorization-minimization descent and an O(1/R)O(1/R) best-iterate bound on a selected squared Clarke-subgradient norm; fixed-depth gossip gives bounds on disagreement and network-average motion; and increasing gossip depth with summable mixing errors yields Clarke-stationary accumulation points. The appendix also develops a general-pp extension through convex inner subproblems.

Validation includes synthetic distributions, MNIST, sharp geometric structures, synthetic 3D point clouds, and a downstream distributionally robust optimization task. Comparisons with fixed-support decentralized solvers and centralized free-support references, together with matched-budget and node-local evaluations, support the practical benefits of adapting support locations.

Critical strengths
  1. A useful decentralized formulation that removes the prescribed-grid restriction. Learning support locations address an important limitation of fixed-support barycenters: a shared grid can spend much of its representation budget on regions far from the relevant geometry. The proposed method allows support adaptation using only neighbor communication of m×dm \times d support matrices, while retaining local measures and transport plans at their respective agents. The closed-form quadratic surrogate update makes the construction particularly simple for W22W_2^2. Moreover, the analysis accommodates nonunique exact transport plans rather than assuming a globally smooth transport map. This combination of practical implementability and appropriately scoped theory is a substantive reason to support acceptance.

  2. Experimental controls that help explain the source of the gains. The Gaussian experiment includes a centrally optimized fixed-grid control, an exact-aggregation free-support reference, and the finite-gossip method. This is more informative than comparing only finite-run decentralized solvers, because it helps distinguish representation restrictions from residual optimization error. The matched-support and matched-communication comparisons, together with evaluations of node-held outputs after explicitly charged terminal gossip, further strengthen the evidence. These controls support the conclusion that support adaptation can yield useful improvements, rather than attributing every difference to a faster optimization algorithm or an evaluator-only network average.

Critical weaknesses
  1. The optimization accuracy of the practical fixed-depth regime remains insufficiently characterized. Theorem 2 controls disagreement and network-average motion, whereas Corollary 1 obtains Clarke-stationary accumulation points under increasing gossip depth satisfying ∑rρSr<∞\sum_r \rho^{S_r}<\infty. The authors clearly acknowledge this distinction and provide increasingly in-depth and terminal gossip experiments. However, those experiments primarily measure objective values and agreement, not a stationarity residual at the network-average support. This matters because directions computed at different local supports can cancel, and terminal gossip alone preserves the network average rather than improving its stationarity. Thus, the reported objective stabilization does not establish that the practical runs approach stationary solutions of the training objective. A diagnostic based on transport plans recomputed at the common network-average support would substantially strengthen the connection between the theory and the implemented regime.

  2. The representation cost of equal atom masses is not directly evaluated. The equal-mass restriction is explicit and legitimate, but its consequences are important when compact representation is a central benefit of the method. Equal masses do not preclude the representation of nonuniform distributions: different regions can receive different numbers of atoms. Nevertheless, at a fixed atom budget, this allocation has resolution 1/m1/m, which may create a trade-off between geometric fidelity and the accurate representation of strongly unequal mode weights. The current support-size studies do not directly isolate this effect. A controlled comparison between equal-mass and variable-mass free-support representations on an imbalanced mixture, using the same atom budget, would clarify when the proposed restriction is inexpensive and when additional atoms are required. This need not involve developing a new decentralized mass-optimization algorithm.

Questions for authors
  1. Stationarity diagnostic for the practical regime. Can you evaluate the fixed-depth runs using exact transport plans recomputed at the network-average support Bˉ(r)\bar B^{(r)}, on the measures used for optimization? Specifically, let T^(r)\widehat T^{(r)} be the average barycentric target obtained from these common-support plans. Proposition 2 gives the diagnostic sr=∥2m(Bˉ(r)−T^(r))∥F.s_r=\left\|\frac{2}{m}\left(\bar B^{(r)}-\widehat T^{(r)}\right)\right\|_F. This is the norm of a selected valid Clarke subgradient, rather than necessarily the minimum-norm Clarke residual, but small values would provide a meaningful stationarity certificate. How does it behave for fixed-depth gossip compared with increasing-depth gossip and exact aggregation? This would directly affect my assessment of whether the practical low-communication regime attains approximate stationarity rather than merely a stable objective.

  2. Clarification of Gaussian stabilization and resource accounting. Section E.1 defines stability as the first round after which the objective remains within 0.1%0.1\% of that run’s minimum. Table 6 reports 4.2±0.44.2\pm0.4 stable rounds for Algorithm 1, and Table 10 gives a network-average objective of approximately 0.0901340.090134 at the stable checkpoint. However, Table 18 reports a round-10 objective of 0.090850.09085. These values appear difficult to reconcile under the stated criterion if they describe the same trajectories and evaluation objective. Do the tables use different runs, evaluation measures, or stopping conventions, or does an entry require correction? Please clarify whether the resolution changes the stable-round resource comparisons.

  3. Evidence on the equal-mass restriction. How much objective or representation quality is lost by prescribing equal masses when the underlying distributions have strongly imbalanced modes? A small matched-atom-budget comparison with a variable-mass free-support reference, even a centralized one, would help establish the scope of the compact-support advantage. I am asking for evidence about the chosen representation, not for an extension of the decentralized algorithm to joint mass–location optimization.

5 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

We sincerely thank the reviewer for the thoughtful and constructive comments and the time devoted to reviewing our manuscript. In the following, W denotes Weakness, Q denotes Question, and R denotes Reference. All revisions are highlighted in blue\textcolor{blue}{blue} in the manuscript.

To address your concern, we have included additional experimental results in 📍§5 Page10.


W1&Q1. those experiments primarily measure objective values and agreement, not a stationarity residual at the network-average support.

We sincerely thank the reviewer for this constructive suggestion. We agree that reporting the first-order stationarity residual sr=∣2m(Bˉ(r)−T^(r))∣Fs_r = \left| \frac{2}{m}\left(\bar B^{(r)}-\widehat T^{(r)}\right)\right|_F provides valuable evidence of our algorithm's convergence behavior and stability.

To address this concern, we have added new experimental results in §5, Page 10, Fig. 8, evaluating the first-order stationarity residual on Gaussian, MNIST, and 3D point-cloud setting. We can conclude that,

  • Across all three settings, both increasing-depth gossip and exact aggregation consistently reduce the stationarity residual as optimization proceeds, demonstrating a clear trend toward stationary solutions.

  • Notably, both exact aggregation and increasing-depth gossip drive the stationarity residual srs_r to nearly machine precision after sufficiently many optimization rounds, providing strong empirical evidence of convergence to stationarity. In contrast, fixed-depth gossip may exhibit a nonzero residual floor due to persistent communication errors, consistent with the distinction between the theoretical guarantees for fixed-depth and increasing-depth gossip.

  • Furthermore, we have extended these experiments to include independently randomized local initializations. The results demonstrate convergence behavior comparable to that under shared initialization across all three benchmarks, further confirming the robustness of our method to heterogeneous initial supports.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}} 📍§5 Page10, we provide additional numerical results on the stationarity residual, further validating the convergence behavior of our method under different communication regimes. (Figure 8)


W2&Q3. How much objective or representation quality is lost by prescribing equal masses when the underlying distributions have strongly imbalanced modes?

We sincerely thank the reviewer for this constructive suggestions, which have significantly enriched the depth and quality of our work. Our method can be extended through a simple modification to a joint weight–support optimization variant, building on the alternating optimization of [R1]:

  • We have explored this variant and found it particularly effective under extreme distributional imbalance. However, since our work primarily focuses on comparisons with decentralized fixed-support WB solvers, and joint optimization offers limited additional benefits in standard benchmark settings while requiring approximately 50% more communication, we did not adopt this variant as our main method.

  • Nevertheless, we agree that imbalanced settings are practically relevant and worth investigating. Therefore, we provide additional experiments comparing support-only and joint weight–support optimization in §5, Page10, Table 2:

    • Joint weight–support optimization yields WB objective reductions of 29.11%–32.33% under extreme distributional imbalance.
    • In contrast, it provides only marginal or inconsistent improvements of 0.01% on standard benchmarks while incurring additional 50% communication costs.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}} 📍§5 Page10, we provided additional numerical results on imbalanced settings. (Table 2)

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

Q2. Clarification of Gaussian stabilization and resource accounting for Table 18.

We thank the reviewer for carefully checking these numerical results. Table 18 was obtained from a separate rerun conducted at a later stage under a different CPU computing environment. Although the experimental settings remained unchanged, differences in CPU architectures, numerical libraries, floating-point accumulation, and the internal operations of exact OT solvers may lead to slightly different optimal transport plans and subsequent optimization trajectories. These numerical variations can account for the small difference between the reported objectives (0.09085 vs. 0.090115 WB obj.).

Importantly, the objective improvements over all fixed-support baselines (e.g. 0.18351 WB obj.) remain in the range of 40.2%–50.5%. This minor numerical correction does not affect our conclusions or the previously reported approximately 99% reductions in optimization rounds and computational cost.

Revisions in the manuscript:\boldsymbol{\textbf{\textcolor{Blue}{Revisions in the manuscript:}}} To ensure consistency, we have rerun the Gaussian experiments under a unified computational environment, ensuring that the revised results are obtained from the same runs.


Reference\boldsymbol{\textbf{Reference}}

[R1]: Fast Computation of Wasserstein Barycenters. ICML 2014

AuthorsOpenReview ↗

Gentle Reminder (Submission #116)

Dear Reviewer ex2x,

As the discussion period draws to a close, we would sincerely appreciate it if you could kindly revisit our rebuttal responses and share any further feedback or concerns, if your schedule permits. We fully understand the significant time constraints during the review process and greatly appreciate your time and efforts. We would be grateful for the opportunity to address any remaining questions or concerns before the discussion period concludes.

Thank you again for your valuable time and contributions to the review process.

Submission Number: 116

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response to the Main Comments

Dear Reviewers, Area Chairs, Senior Area Chairs, and Program Chairs,

We sincerely thank the reviewers for their thoughtful and supportive evaluations, and for the time and effort devoted to reviewing our paper. We have provided detailed responses to each comment. Below, we summarize our responses and the corresponding revisions made to address main concerns.


Related Work:\boldsymbol{\textbf{{Related Work:}}} Reviewers R4iY and qWMt suggested providing more detailed discussions of [R1] and [R2].

Regarding [R1]: The main similarity between our method and [R1] lies in the closed-form quadratic surrogate update for free-support 2-WB. However, the problem settings and applicability are fundamentally different. Specifically,

  • [R1] is limited to free-support 2-WB. The 2-WB is commonly regarded as a generalization of k-means. Therefore, methods for 2-WB naturally share similarities in high-level designs, since the squared Euclidean cost admits closed-form updates. In contrast, our framework handles free-support pp-WBs.
  • [R1] only addresses centralized WB computation and follows a heuristic algorithmic approach. In contrast, we develop a principled methodology for decentralized WB computation, accompanied by theoretical guarantees.

Regarding [R2]: The main similarity between our method and [R2] lies in the use of displacement interpolation. However, their purposes and roles in the algorithms are fundamentally different. Specifically,

  • [R2] randomly selects a single edge in each round and computes OT between the two agents' current distributions, followed by displacement interpolation to update their distributions. However, these methods require sharing local probability measures with neighboring agents to compute OT between two distributions. Strictly speaking, this no longer satisfies the requirement that local probability measures remain at their respective agents in a decentralized setting, since the local measures have already been communicated to neighboring agents.

  • In contrast, our method performs interpolation on Wasserstein geodesic between agent ii's current barycenter BiB_i and the minimizer TiT_i of the surrogate function, using the update (1−η)Bi+ηTi(1-\eta)B_i+\eta T_i. This update can be viewed as an exponentially weighted moving average to promote smoother convergence with a fixed η\eta for theoretical convenience. This does not require sharing local probability measures or transport plans and only support-sized update vectors need to be exchanged with neighboring agents. Fundamentally, our method does not require the interpolation to be unique, since the subsequent update is determined by the newly computed TiT_i.

Revision:\boldsymbol{\textbf{\textcolor{Blue}{Revision:}}} 📍§A Page17 provides detailed descriptions of the aforementioned works.


Theory:\boldsymbol{\textbf{{Theory:}}} The reviewers suggested providing stronger guarantees. Specifically, we establish sublinear first-order stationarity convergence guarantees under fully connected aggregation and increasing-depth gossip schedules, and analyze the stationarity error under the resource-constrained fixed-depth gossip setting. Beyond these results, Reviewer R4iY suggested stronger convergence guarantees for fixed-depth gossip, while Reviewer qWMt suggested exploring global approximation guarantees for 2-WBs by leveraging the connection to k-means.

We show that, by introducing additional mild assumptions or more structured settings, stronger guarantees can be established. Specifically, under assumptions WS⪰0\mathbf{W}^S\succeq 0 and the 2-WB problem:

  • Convergence Rate: We establish a stronger linear convergence guarantee.
  • Global Approximation: We establish 2-approximation and $(2+\epsilon) $-approximation guarantees under specific initilization. These results provide better approximation factors than existing k-means approaches to approximating 2-WB, e.g., [R3] establishes a (5+O(ε))(5+O(\varepsilon))-approximation, while [R4] provides a (2+β)2(2+\sqrt{\beta})^2-approximation (approximately 9 when β≈1\beta\approx1).

Revision:\boldsymbol{\textbf{\textcolor{Blue}{Revision:}}} 📍§4 Page 7 presents additional theoretical results.


Experiments:\boldsymbol{\textbf{{Experiments:}}} Reviewer ex2x suggested that, in addition to comparing WB objective values against fixed-support baselines, we should provide first-order stationarity experiments for our free-support method to demonstrate its convergence behavior.

We agree thatincluding first-order stationarity results would provide stronger empirical support for our theoretical analysis. Accordingly, we have added the corresponding stationarity curves, which are consistent with our theoretical findings.

Revision:\boldsymbol{\textbf{\textcolor{Blue}{Revision:}}} 📍§5 Page10 provides additional experimental analysis.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.