- 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 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
-
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.
-
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
-
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.
-
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.
-
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
-
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?
-
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?
-
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?
-
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
Official Comment by Authors (2/3)
W2&Q2 (Part2): what convergence or stationarity guarantees can be established for the fixed-depth gossip scheme?
-
Strong convergence rate guarantees are challenging for general -Wasserstein Barycenters. Establishing strong convergence-rate guarantees for nonconvex and nonsmooth optimization of arbitrary -Wasserstein barycenters, which is NP-hard in general [R4], is particularly challenging without imposing regularity conditions and decentralized setting.
-
Nevertheless, we can establish a stronger convergence guarantee by introducing a mild additional assumptions. For instance,
-
Assumption: 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 and a constant , independent of , such that, For , the support sequence stabilizes after finitely many iterations.
-
-
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 points, with atom masses initialized by a single aggregation, and for fixed-depth gossip.
-
Result: Here, denotes the global minimum over both support locations and atom masses.
- 2-approximation under fully connected aggregation
- ()-approximation under sufficiently large but fixed gossip depth
-
Comparison with [R5] and [R6]: [R5] establishes a -approximation using a near-optimal k-means subroutine, while [R6] provides a -approximation (approximately for ) for the standard k-sparse case, where is the clustering approximation factor. Our result achieves a smaller approximation factor while explicitly accounting for finite-depth decentralized communication.
-
📍§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 ()-approximation under sufficiently large but fixed gossip (Theorem 6).
W3&Q3: The method requires common ordered initialization and consistent atom labels across agents.
- 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.
- 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).
- 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.
📍§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).
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.
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.
[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
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 in the manuscript.
(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 p-Wasserstein barycenters for arbitrary p, and provides the corresponding theoretical analysis (both our method and theoretical analysis are also applicable to non-decentralized settings.
Revisions in the manuscript:
📍§A Page17, We further highlight our contributions in the main contributions section, emphasizing our contribution for general p-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,10, demonstrating substantially better performance than existing decentralized fixed-support methods (Table1).
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.
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,