⚡ electrical engineering

Geometry-Aware Decentralized Sinkhorn for Wasserstein Barycenters

This paper proposes a fully decentralized, geometry-aware Sinkhorn algorithm that computes Wasserstein barycenters over sparse networks by reformulating the problem as a log-domain arithmetic average, enhanced with event-triggered and quantized communication to achieve near-centralized accuracy with significantly reduced bandwidth usage.

Original authors: Ali Baheri, David Millard, Alireza Vahid

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ali Baheri, David Millard, Alireza Vahid

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to agree on the "average" location of a hidden treasure. However, they aren't just standing in a flat field; they are navigating a complex, hilly landscape where the rules of distance are strange. If two friends guess the treasure is on opposite sides of a mountain, a simple "middle point" calculation might land them right in the middle of the mountain—a place where the treasure can't possibly be.

This paper solves a problem where computers (called "agents") need to combine their different guesses about probability (like where a target is) without a boss telling them what to do. Here is how they did it, explained simply:

The Problem: The "Wrong" Average

In the old way, computers treated these guesses like simple numbers on a flat sheet of paper. They would just add them up and divide by two. But probability guesses live on a curved, bumpy surface (like the surface of a sphere). Averaging them on a flat sheet gives misleading results, like placing the treasure inside a mountain.

To fix this, mathematicians use something called a Wasserstein Barycenter. Think of this as a "smart average" that respects the hills and valleys of the landscape. It calculates the cost of moving one guess to another, ensuring the final result stays on the valid path.

The Bottleneck: The "All-Hands Meeting"

The best way to calculate this "smart average" is an algorithm called Sinkhorn. However, traditionally, this algorithm requires a central coordinator. Imagine a team where everyone has to send their notes to a single leader, who does the math, and then sends the answer back.

The Issue: In real-world networks (like a swarm of drones or sensors), there is often no leader, or the connection to a leader is spotty and slow. Sending all the data to a central point clogs the network.

The Solution: The "Log-Message Gossip"

The authors invented a way to do this math without a leader. Here is their clever trick:

The Log-Transformation: They realized that the complex "geometric average" (the hard math part) looks exactly like a simple "arithmetic average" (just adding and dividing) if you first convert the numbers into logarithms.
- Analogy: It's like realizing that if you want to find the average growth rate of a plant, it's easier to add up the logs of the heights and then convert back, rather than trying to multiply the heights directly.
The Gossip Protocol: Once the numbers are in "log-form," the agents don't need a leader. They just whisper to their immediate neighbors.
- Analogy: Imagine a game of "Telephone," but instead of distorting the message, everyone is trying to agree on the average. Each person tells their neighbor, "Here is my number." They swap numbers, average them, and pass the new average along. Eventually, everyone holds the same number, which represents the global average.

Making it Efficient: The "Lazy" Messenger

Even with gossip, sending messages constantly uses too much battery and bandwidth. The authors added two smart features to save energy:

Event-Triggered Transmission: Instead of shouting their number every second, an agent only speaks up if their number has changed significantly. If their number is stable, they stay silent and let their neighbors use the last number they heard.
- Analogy: You don't call your friend every minute to say, "I'm still sitting on the couch." You only call when you get up and move to the kitchen.
Quantization (Rough Drafts): When they do speak, they don't send a perfect, high-definition number. They send a "rough draft" using fewer bits (like rounding 3.14159 to 3.14).
- Analogy: Instead of sending a detailed map, you just say, "It's roughly North." It's not perfect, but it's enough to get the job done and saves a lot of paper.

The Results: "Good Enough" and Fast

The paper proves mathematically that even with these shortcuts (staying silent sometimes and sending rough numbers), the group still converges to the correct answer.

Accuracy: The final result is almost identical to what a central boss would have calculated.
Speed: The number of messages sent grows very slowly as the group gets bigger (linear growth), whereas older methods would explode in traffic.
Robustness: It works even if messages are lost or if agents talk at different times (asynchrony).

Summary

The authors took a complex math problem that usually requires a central boss, turned the numbers into a format that allows for simple "whispering" between neighbors, and added "lazy" rules to stop people from talking too much. The result is a system where a network of devices can agree on a perfect, geometry-aware average without needing a leader, without clogging the network, and without running out of battery.

Technical Summary: Geometry-Aware Decentralized Sinkhorn for Wasserstein Barycenters

1. Problem Statement

Distributed systems often face the challenge of fusing heterogeneous local probability distributions into a global summary over sparse and unreliable communication networks. Traditional consensus algorithms typically treat distributions as Euclidean vectors and compute arithmetic averages. The authors argue this approach ignores the inherent geometric structure of probability spaces, potentially leading to misleading results (e.g., averaging two distributions with support at opposite locations yields a midpoint that may be an impossible location).

While Wasserstein barycenters offer a geometry-aware alternative by minimizing optimal transport costs, their standard computation via the Sinkhorn algorithm relies on a centralized geometric mean step. Existing decentralized approaches either retain a coordinator, exchange dense dual information through general optimization routines, or fail to directly decentralize the specific Sinkhorn geometric-mean step. The paper addresses the need for a fully decentralized, bandwidth-efficient method that preserves the geometric properties of the barycenter without a central coordinator.

2. Methodology

The proposed solution is a fully decentralized Sinkhorn algorithm that reformulates the centralized geometric mean as an arithmetic average in the log-domain. The methodology proceeds through three core mechanisms:

Log-Domain Reformulation: The standard Sinkhorn update for the shared scaling vector $v$ involves a geometric mean of local terms $K^\top u_i$ . By defining a log-message $s_i = \log(K^\top u_i)$ , the geometric mean becomes an arithmetic mean: $\log v = \frac{1}{N} \sum s_i$ . This transformation allows the global aggregation step to be replaced by local averaging.
Decentralized Gossip: Agents approximate the global arithmetic mean of log-messages through weighted gossip protocols. Each agent maintains a local estimate $z_i$ and updates it using the most recent packets from neighbors. This interleaves local scaling updates (computing $u_i$ ) with consensus phases to mimic the centralized iterations.
Bandwidth Optimization: To address communication constraints, the algorithm integrates:
- Event-Triggered Transmission: Agents transmit messages only when the change in their log-message exceeds a threshold $\delta$ ( $\|s_i - s_{i, last}\|_\infty > \delta$ ).
- Quantization and Clipping: Messages are clipped to a finite range $[s_{min}, s_{max}]$ and quantized to $b$ bits before transmission. Local computations retain full precision, while only the transmitted packets are quantized.
- Asynchrony and Packet Loss: The protocol is designed to accommodate asynchronous updates and packet loss by reusing cached packets until new ones arrive.

3. Key Contributions

The paper claims three primary contributions:

Algorithmic: A fully decentralized Sinkhorn algorithm that eliminates central coordination by reformulating geometric means as distributed arithmetic consensus in log-space.
Communication: The design of event-triggered and quantized protocols that reduce bandwidth usage by orders of magnitude while preserving convergence guarantees.
Theoretical: A proof of convergence to a neighborhood of the centralized entropic barycenter. The analysis establishes that the bias (error) is linearly dependent on the consensus tolerance ( $\tau$ ), trigger threshold ( $\delta$ ), and quantization error ( $\Delta_q$ ). The convergence rate is shown to be linear (geometric) with a factor dependent on the entropic regularization parameter $\varepsilon$ .

4. Results

The authors evaluated the algorithm on a 4x4 grid network ( $N=16$ ) with a support size of $d=64$ .

Accuracy: Simulations demonstrate that the decentralized iterates remain in a small $\ell_1$ -neighborhood of the centralized solution. The decentralized barycenter is visually indistinguishable from the centralized one over dominant modes.
Convergence Behavior: The inner-loop consensus exhibits the expected sawtooth profile (rapid contraction followed by small jumps at outer updates). Event triggering introduces bounded perturbations but does not alter the contraction regime.
Complexity: The total message count scales near-linearly ( $O(N)$ ) with network size in grid graphs, significantly outperforming quadratic scaling ( $O(N^2)$ ) baselines. Runtime increases monotonically with network size as predicted by the per-iteration cost analysis.
Trade-offs: The results confirm that the algorithm achieves near-centralized accuracy with significantly fewer messages across various topologies and conditions.

5. Significance and Claims

The paper positions its work as a solution to the fundamental limitation of Euclidean averaging in distributed probability fusion. By leveraging the log-domain identity, the authors claim to have successfully implemented the Sinkhorn geometric-mean step as a peer-to-peer log-average, a capability not previously achieved in decentralized settings without a coordinator.

The significance lies in the explicit trade-off control: the method provides tunable parameters (trigger thresholds, quantization bits) to balance accuracy against communication costs, making it suitable for networks with sparse and unreliable links. Theoretical guarantees ensure that the deviation from the optimal centralized solution is bounded and predictable based on system parameters. The authors conclude that this approach enables geometry-aware averaging in distributed systems (such as autonomous robots or sensor networks) without the need for raw data sharing or central infrastructure, while maintaining robustness to asynchrony and packet loss.