Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
This paper deals with the differentially private facility location problem. The facility location problem is a Lagrangian formulation of the metric clustering problem. Given a set of points in a metric space (for example Euclidean space), the goal is to find a set of cluster centers that minimizes the sum of distances from the points to their closest cluster center, plus a regularization parameter times the number of centers. Traditionally, this problem has attracted a lot of attention in the algorithms community, given that it captures well the clustering problem, and tools developed for this problem have transferred well to several other formulations of clustering. This work studies the differentially private version of this clustering problem. This problem is studied in a version of privacy that has been studied for this problem, known as Joint Differential Privacy. The previous work for this problem derived an polylog approximation to this problem, by reducing the problem to a class of metrics known as HSTs, and deriving a polylog approximation ratio for that problem. The current work improves the approximation factor to O(1) for HSTs and O(log n) for arbitrary metric spaces. Further the author give the first lower bounds for this problem. The algorithm builds on the previous work of Gupta et al., and shows that few small changes to the algorithm, and more sophisticated analysis, one can get an O(1) approximation (for constant privacy parameter) on HSTs. The reviewers agreed that this is a fundamental combinatorial optimization problem, variants of which arrive in clustering problems in ML. Given the importance of private Machine Learning algorithms, new tools and analyses are of interest. This paper makes significant progress on this important question. The reviewers would be happier with the lower bound matching in dependence on epsilon. They also hope that the writing clarity will be improved based on the feedback. Overall, the technical novelty and the importance of the question convinced the reviewers and the meta-reviewer to support acceptance for this work.