arXiv:2409.00848cs.LGcs.DC2024-09被引 1

首次提出联邦排名聚合的布多与莱默编码方法,解决隐私保护下的分布式排序融合问题。

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

  • 采用布多计分与莱默编码,结合量化和隐私协议实现分布式排序聚合。
  • 在马洛斯分布下,仅需每客户端少量本地排名即可高概率恢复真实排序,通信开销可控。
  • 适用于医疗数据共享等需隐私保护的场景,为联邦学习中的排序任务提供理论支持。

排名聚合将多个排序列表合并为一致的共识排序。在生物医学数据共享等领域,排序数据可能分散分布且需保护隐私,这促使了联邦排名聚合协议的发展,支持跨多个客户端的分布式、私密且通信高效的联合学习。本文首次提出基于布多计分与莱默码的联邦排名聚合方法,聚焦于马洛斯分布(已知缩放因子ϕ,未知中心排列σ₀)下的样本复杂度分析。联邦布多方法包括本地评分、非平凡量化及隐私保护协议:当ϕ∈[0,1)且任意σ₀长度为N时,每个L个客户端只需本地聚合max{C₁(ϕ), C₂(ϕ)·(1/L)log(N/δ)}个排名,经量化后上传至服务器,即可以≥1−δ的概率恢复σ₀,通信复杂度为NL log N。首次给出了布多法在集中式与分布式环境下基于马洛斯模型的严格分析。联邦莱默编码方法则为每个客户端生成局部莱默码,采用坐标多数聚合与专用量化提升效率与隐私性。当ϕ+ϕ²<1+ϕᴺ且任意σ₀长度为N时,每个客户端只需聚合max{C₃(ϕ), C₄(ϕ)·(1/L)log(N/δ)}个排名,发送截断的莱默坐标直方图至服务器,亦可以≥1−δ概率恢复σ₀,通信复杂度约为O(N log NL log L)。

原文摘要 · Abstract (English)

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

联邦学习排名聚合隐私计算马洛斯模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。