FastLloyd: Federated, Accurate, Secure, and Tunable $k$-Means Clustering with Differential Privacy
<|reference_start|>FastLloyd: Federated, Accurate, Secure, and Tunable $k$-Means Clustering with Differential Privacy: 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 computation components, resulting in a design that is faster, more private, and more accurate than previous work. By utilizing the computational DP model, we design a lightweight, secure aggregation-based approach that achieves four orders of magnitude speed-up over state-of-the-art related work. Furthermore, we not only maintain the utility of the state-of-the-art in the central model of DP, but we improve the utility further by taking advantage of constrained clustering techniques.<|reference_end|>
@article{diaa2024fastlloyd:,
    title={FastLloyd: Federated, Accurate, Secure, and Tunable $k$-Means Clustering
  with Differential Privacy},
    author={Abdulrahman Diaa, Thomas Humphries, Florian Kerschbaum},
    journal={arXiv preprint arXiv:2405.02437},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.02437},
    primaryClass={cs.CR cs.LG}
}