# On Gossip Algorithms for Machine Learning with Pairwise Objectives

arXiv: https://arxiv.org/abs/2603.24128 · HTML: https://mlsanity.com/paper/2603.24128/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 72 references that are in the map.
- First posted on arXiv 25 Mar 2026.

## Builds on (most cited first, 30 of 31)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [Fairness-aware Agnostic Federated Learning](https://mlsanity.com/paper/2010.05057/) (2020)
- [Decentralized Collaborative Learning of Personalized Models over Networks](https://mlsanity.com/paper/1610.05202/) (2016)
- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [A Survey on Metric Learning for Feature Vectors and Structured Data](https://mlsanity.com/paper/1306.6709/) (2013)
- [Learning Fairness in Multi-Agent Systems](https://mlsanity.com/paper/1910.14472/) (2019)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [Optimal Gradient Compression for Distributed and Federated Learning](https://mlsanity.com/paper/2010.03246/) (2020)
- [Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs](https://mlsanity.com/paper/1901.08460/) (2019)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Beyond spectral gap: The role of the topology in decentralized learning](https://mlsanity.com/paper/2206.03093/) (2022)
- [Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions](https://mlsanity.com/paper/1606.02421/) (2016)
- [GossipGraD: Scalable Deep Learning using Gossip Communication based Asynchronous Gradient Descent](https://mlsanity.com/paper/1803.05880/) (2018)
- [Scaling-up Empirical Risk Minimization: Optimization of Incomplete U-statistics](https://mlsanity.com/paper/1501.02629/) (2015)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Dual-Free Stochastic Decentralized Optimization with Variance Reduction](https://mlsanity.com/paper/2006.14384/) (2020)
- [Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives](https://mlsanity.com/paper/1810.02660/) (2018)
- [Privacy-preserving Decentralized Aggregation for Federated Learning](https://mlsanity.com/paper/2012.07183/) (2020)
- [Communication-Efficient Distributionally Robust Decentralized Learning](https://mlsanity.com/paper/2205.15614/) (2022)
- [Private Protocols for U-Statistics in the Local Model and Beyond](https://mlsanity.com/paper/1910.03861/) (2019)
- [Can Decentralized Learning be more robust than Federated Learning?](https://mlsanity.com/paper/2303.03829/) (2023)
- [A New Perspective on Randomized Gossip Algorithms](https://mlsanity.com/paper/1610.04714/) (2016)
- [Extending Gossip Algorithms to Distributed Estimation of U-Statistics](https://mlsanity.com/paper/1511.05464/) (2015)
- [A Probabilistic Theory of Supervised Similarity Learning for Pointwise ROC Curve Optimization](https://mlsanity.com/paper/1807.06981/) (2018)
- [On Medians of (Randomized) Pairwise Means](https://mlsanity.com/paper/2211.00603/) (2022)
- [Re-Evaluating Privacy in Centralized and Decentralized Learning: An Information-Theoretical and Empirical Study](https://mlsanity.com/paper/2409.14261/) (2024)

## Abstract (arXiv)

In the IoT era, information is more and more frequently picked up by connected smart sensors with increasing, though limited, storage, communication and computation abilities. Whether due to privacy constraints or to the structure of the distributed system, the development of statistical learning methods dedicated to data that are shared over a network is now a major issue. Gossip-based algorithms have been developed for the purpose of solving a wide variety of statistical learning tasks, ranging from data aggregation over sensor networks to decentralized multi-agent optimization. Whereas the vast majority of contributions consider situations where the function to be estimated or optimized is a basic average of individual observations, it is the goal of this article to investigate the case where the latter is of pairwise nature, taking the form of a U -statistic of degree two. Motivated by various problems such as similarity learning, ranking or clustering for instance, we revisit gossip algorithms specifically designed for pairwise objective functions and provide a comprehensive theoretical framework for their convergence. This analysis fills a gap in the literature by establishing conditions under which these methods succeed, and by identifying the graph properties that critically affect their efficiency. In particular, a refined analysis of the convergence upper and lower bounds is performed.