Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error

Authors

  • Anamay Chaturvedi Northeastern University
  • Matthew Jones Northeastern University
  • Huy Lê Nguyễn Northeastern University

DOI:

https://doi.org/10.1609/aaai.v36i6.20565

Keywords:

Machine Learning (ML), Constraint Satisfaction And Optimization (CSO)

Abstract

Given a data set of size n in d'-dimensional Euclidean space, the k-means problem asks for a set of k points (called centers) such that the sum of the l_2^2-distances between the data points and the set of centers is minimized. Previous work on this problem in the local differential privacy setting shows how to achieve multiplicative approximation factors arbitrarily close to optimal, but suffers high additive error. The additive error has also been seen to be an issue in implementations of differentially private k-means clustering algorithms in both the central and local settings. In this work, we introduce a new locally private k-means clustering algorithm that achieves near-optimal additive error whilst retaining constant multiplicative approximation factors and round complexity. Concretely, given any c>√2, our algorithm achieves O(k^(1 + O(1/(2c^2-1))) √(d' n) log d' poly log n) additive error with an O(c^2) multiplicative approximation factor.

Downloads

Published

2022-06-28

How to Cite

Chaturvedi, A., Jones, M., & Nguyễn, H. L. (2022). Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error. Proceedings of the AAAI Conference on Artificial Intelligence, 36(6), 6167-6174. https://doi.org/10.1609/aaai.v36i6.20565

Issue

Section

AAAI Technical Track on Machine Learning I