TY - JOUR
AU - Nguyen, Huy L.
AU - Chaturvedi, Anamay
AU - Xu, Eric Z
PY - 2021/05/18
Y2 - 2022/01/24
TI - Differentially Private k-Means via Exponential Mechanism and Max Cover
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 35
IS - 10
SE - AAAI Technical Track on Machine Learning III
DO -
UR - https://ojs.aaai.org/index.php/AAAI/article/view/17099
SP - 9101-9108
AB - We introduce a new (ϵₚ, δₚ)-differentially private algorithm for the k-means clustering problem. Given a dataset in Euclidean space, the k-means clustering problem requires one to find k points in that space such that the sum of squares of Euclidean distances between each data point and its closest respective point among the k returned is minimised. Although there exist privacy-preserving methods with good theoretical guarantees to solve this problem, in practice it is seen that it is the additive error which dictates the practical performance of these methods. By reducing the problem to a sequence of instances of maximum coverage on a grid, we are able to derive a new method that achieves lower additive error than previous works. For input datasets with cardinality n and diameter Δ, our algorithm has an O(Δ² (k log² n log(1/δₚ)/ϵₚ + k √(d log(1/δₚ))/ϵₚ)) additive error whilst maintaining constant multiplicative error. We conclude with some experiments and find an improvement over previously implemented work for this problem.
ER -