FastLloyd: Federated, Accurate, Secure, and Tunable $k$-Means Clustering with Differential Privacy

arXiv:2405.02437v1 Announce Type: new
Abstract: We study the problem of privacy-preserving $k$-means clustering in the horizontally federated setting. Existing federated approaches using secure computation, suffer from substantial overheads and do not offer output privacy. At the same time, differentially private (DP) $k$-means algorithms assume a trusted central curator and do not extend to federated settings. Naively combining the secure and DP solutions results in a protocol with impractical overhead. Instead, our work provides enhancements to both the DP and secure …

algorithms arxiv clustering computation cs.cr cs.lg differential privacy federated offer privacy private problem secure computation study