Extending Gossip Algorithms to Distributed Estimation of U-statistics

Igor Colin, Aurélien Bellet, Joseph Salmon, Stéphan Clémençon

Introduction

In decentralized networks—such as sensor arrays, peer-to-peer systems, or IoT device clusters—nodes often need to compute global properties of the data they hold collectively without relying on a central server. Standard "gossip algorithms" excel at computing simple averages (sample means), where each node contributes a single value.

However, this paper introduces GoSta (Gossip for U-Statistics), a new family of algorithms designed to estimate more complex metrics known as U-statistics across decentralized networks. By combining data propagation with estimate averaging, GoSta achieves faster convergence and lower memory requirements than previous methods, offering both synchronous and asynchronous versions with proven theoretical guarantees.

The Challenge of U-Statistics

While standard gossip algorithms handle simple averages well, many important statistical measures are U-statistics. These are calculated by averaging a function over pairs (or larger subsets) of observations rather than individual data points. Common examples include:

  • Area Under the Curve (AUC): A standard metric for evaluating classifier performance.
  • Sample Variance: A measure of data spread.
  • Gini Mean Difference: A metric for statistical dispersion.

Computing U-statistics is inherently challenging in a decentralized setting because a node would theoretically need to observe every other node's data to form all possible pairs. Previous attempts to solve this, such as "U2-gossip," were memory-intensive, required global clocks, or suffered from slow convergence. The authors aim to make these computations efficient, robust, and truly asynchronous.

The GoSta Algorithm

The core innovation of GoSta is a dual-process approach that runs simultaneously on each node:

  1. Data Propagation: Each node maintains an "auxiliary observation." When two nodes communicate, they swap these observations. This effectively creates a random walk of data points across the network, ensuring that over time, every node "meets" a representative sample of data pairs.
  2. Estimate Averaging: Simultaneously, nodes maintain a local estimate of the U-statistic. When they communicate, they average their local estimates—leveraging the standard gossip approach to reach a network-wide consensus.

The authors propose two key versions of the algorithm:

  • GoSta-sync: Requires a global clock. Every node updates its estimate at every step based on its current auxiliary observation, then a random pair of nodes averages their estimates and swaps data.
  • GoSta-async: More practical for real-world networks. Nodes have independent local clocks (modeled as Poisson processes). Updates only happen for the two nodes currently communicating.

To mathematically prove the convergence of these algorithms, the authors employ a clever theoretical trick involving "phantom nodes." They model the data propagation as if the data were moving through a larger, virtual network, allowing them to apply spectral graph theory to establish convergence bounds.

Illustration of the phantom nodes concept used for theoretical proofs.

Key Insights and Results

The algorithms were evaluated on real-world datasets, including SVMguide3 (for AUC estimation) and Wine Quality (for within-cluster point scatter), across different network topologies like Complete graphs, 2D grids, and Watts-Strogatz (small-world) networks.

  • Averaging is the Secret Sauce: Unlike previous methods that merely tracked running totals, GoSta uses an "averaging" step. This significantly reduces the variance of estimates across the network, ensuring all nodes reach a consensus much more quickly.
  • Efficiency Gains: GoSta requires nodes to store only one auxiliary observation (compared to two in U2-gossip), effectively halving the memory and communication load for high-dimensional data.
  • Superiority over U2-gossip: In numerical experiments, GoSta-sync consistently reached a lower relative error faster than the state-of-the-art U2-gossip algorithm across all tested network topologies.
Performance comparison of GoSta-sync and U2-gossip.
  • Theoretical vs. Practical Performance: The authors proved a convergence rate of $O(1/t)$ for the synchronous case and $O(\log t / t)$ for the asynchronous case. While the asynchronous version has a slightly worse theoretical bound, experiments showed it performs nearly as well as the synchronous version in practice.
  • Network Connectivity Matters: Convergence speed is explicitly linked to the network's spectral gap. Well-connected networks (like complete graphs) converge much faster than sparse ones (like 2D grids).

Limitations and Future Work

While GoSta represents a significant step forward, its performance remains heavily dependent on the network's connectivity; in very sparse networks, convergence may still be slow. Additionally, the current model assumes static data. Adapting GoSta to handle streaming data or dynamic networks—where nodes frequently join and leave—is a promising direction for future research. Finally, the authors suggest that GoSta could serve as a foundational building block for decentralized optimization tasks, such as directly training a classifier to maximize AUC in a distributed manner.

Summary updated

Abstract

Efficient and robust algorithms for decentralized estimation in networks are essential to many distributed systems. Whereas distributed estimation of sample mean statistics has been the subject of a good deal of attention, computation of U-statistics, relying on more expensive averaging over pairs of observations, is a less investigated area. Yet, such data functionals are essential to describe global properties of a statistical population, with important examples including Area Under the Curve, empirical variance, Gini mean difference and within-cluster point scatter. This paper proposes new synchronous and asynchronous randomized gossip algorithms which simultaneously propagate data across the network and maintain local estimates of the U-statistic of interest. We establish convergence rate bounds of O(1 / t) and O(log t / t) for the synchronous and asynchronous cases respectively, where t is the number of iterations, with explicit data and network dependent terms. Beyond favorable comparisons in terms of rate analysis, numerical experiments provide empirical evidence the proposed algorithms surpasses the previously introduced approach.
BibTeX
@inproceedings{colin2015extending,
  author = {Igor Colin and Aurélien Bellet and Joseph Salmon and Stéphan Clémençon},
  title = {{Extending Gossip Algorithms to Distributed Estimation of U-statistics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=rkZACPW_-B},
}
Figure