Extending Gossip Algorithms to Distributed Estimation of U-Statistics

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

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.

Introduction

In decentralized networks such as sensor swarms or peer-to-peer systems, calculating global properties without a central coordinator is a fundamental challenge. While gossip algorithms are well-established for computing simple averages (separable functions), many critical metrics are non-separable. These are known as $U$-statistics, which depend on pairs of observations rather than individual data points. Examples include the Area Under the Curve (AUC) for classifiers, empirical variance, and the Gini coefficient.

Distributed Estimation of U-Statistics

A $U$-statistic of degree two is defined as: $$\hat{U}_n(H) = \frac{1}{n^2} \sum_{i,j=1}^{n} H(X_i, X_j)$$ where $H$ is a symmetric kernel function. Computing this in a distributed setting is difficult because no single node initially possesses the pairs $(X_i, X_j)$ required for the summation. Previous methods often required high memory overhead or were limited to synchronous environments.

The GoSta Framework

The authors introduce GoSta (Gossip for $U$-Statistics), featuring two variants: GoSta-sync and GoSta-async. The algorithms utilize a dual-action iteration:

  1. Data Propagation: Nodes maintain and swap "auxiliary" observations, creating a random walk of data across the network. This ensures that over time, each node "meets" a diverse set of pairs.
  2. Estimate Averaging: Nodes maintain local estimates of the $U$-statistic and average them during communication to reach consensus.

To analyze convergence, the authors employ a "phantom node" construction, modeling data movement on a virtual network layer.

The phantom node construction used to analyze data propagation on a virtual layer.

This theoretical framework allows the application of spectral graph theory to prove that GoSta achieves convergence rates of $O(1/t)$ for synchronous and $O(\log t / t)$ for asynchronous settings.

Empirical Results

The performance of GoSta was evaluated using real-world datasets: SVMguide3 (for AUC estimation) and Wine Quality (for within-cluster scatter). These were tested across three topologies: complete graphs, 2D grids, and Watts-Strogatz random graphs.

Empirical comparison of GoSta-sync and U2-gossip across different network topologies.

As shown in the experimental results, GoSta-sync consistently outperforms the previous state-of-the-art "U2-gossip" algorithm. The improvement is particularly significant in the early iterations. Furthermore, the algorithm demonstrates high memory efficiency, requiring only one auxiliary observation per node, which is critical for high-dimensional data.

Conclusion

GoSta provides a robust framework for decentralized $U$-statistic estimation with provable convergence and superior empirical performance. Future work includes extending these techniques to decentralized optimization, such as directly maximizing AUC in a distributed fashion, and improving performance on highly sparse networks.

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