Abstract
We study the problem of privacy-preserving $k$-means clustering in thehorizontally federated setting. Existing federated approaches using securecomputation suffer from substantial overheads and do not offer output privacy.At the same time, differentially private (DP) $k$-means algorithms eitherassume a trusted central curator or significantly degrade utility by addingnoise in the local DP model. Naively combining the secure and central DPsolutions results in a protocol with impractical overhead. Instead, our workprovides enhancements to both the DP and secure computation components,resulting in a design that is faster, more private, and more accurate thanprevious work. By utilizing the computational DP model, we design alightweight, secure aggregation-based approach that achieves five orders ofmagnitude speed-up over state-of-the-art related work. Furthermore, we not onlymaintain the utility of the state-of-the-art in the central model of DP, but weimprove the utility further by designing a new DP clustering mechanism.