Federated Aggregation of Mallows Rankings: A Comparative Analysis of Borda and Lehmer Coding

• DOI: 10.48550/arxiv.2409.00848
• Publication Date: 2024-09-01
• Authors: Jin Sima; Vishal Rana; Olgica Milenković
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Computer Science - Distributed, Parallel, and Cluster Computing; Distributed, Parallel, and Cluster Computing (cs.DC); Machine Learning (cs.LG)

Rank aggregation combines multiple ranked lists into a consensus ranking. In fields like biomedical data sharing, rankings may be distributed and require privacy. This motivates the need for federated rank protocols, which support distributed, private, communication-efficient learning across clients with local data. We present first known methods using Borda scoring Lehmer codes, focusing on sample complexity algorithms Mallows distributions scaling factor $\phi$ an unknown centroid permutation $\sigma_0$. Federated approach involves client scoring, nontrivial quantization, privacy-preserving protocols. show that $\phi \in [0,1)$, arbitrary $\sigma_0$ of length $N$, it suffices each $L$ to locally aggregate $\max\{C_1(\phi), C_2(\phi)\frac{1}{L}\log \frac{N}{\delta}\}$ rankings, where $C_1(\phi)$ $C_2(\phi)$ are constants, quantize result, send server who can then recover probability $\geq 1-\delta$. Communication scales as $NL \log N$. Our results represent rigorous analysis Borda's method in centralized settings under model. coding creates code client, coordinate-majority specialized quantization efficiency $\phi+\phi^2<1+\phi^N$, $\max\{C_3(\phi), C_4(\phi)\frac{1}{L}\log $C_3(\phi)$ $C_4(\phi)$ constants. Clients truncated coordinate histograms server, is $\sim O(N\log NL\log L)$.