Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper gives improved guarantees for differential private computation of $k$-means and $k$-median clustering of $n$ points in the unit ball of $d$-dimensional Euclidean space. There are three concerns: the approximation guarantee, the additive error, and the parallel runtime and work. This work achieves simultaneously the best (or comparable to the best) known guarantees for all three: $O(1)$ approximation, $\hbox{poly}(k,d)$ additive error, running in $O(1)$ parallel rounds and total work nearly linear in $n$ and polynomial in $k$. The method is to compute a bicriteria approximation using quad trees (embedded into HSTs), then apply to the excess number of centers any constant factor approximation private algorithm. To eliminate the dependence on $\hbox{exp}(d)$, these steps are preceded by dimension reduction to $O(\log k)$ dimensions.
strengths_and_weaknesses: It's an interesting result on a problem that has been studied recently quite intensively. The results are somewhat incremental, mostly with respect to the techniques used, but the bottom line, especially the efficient parallel computation, seems very interesting.
questions: None.
limitations: None.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors address the problem of differentially-private clustering in the massively parallel computation model. They provide the first algorithms that simultaneously achieve
- differential privacy,
- constant factor approximation,
- near-optimal additive error of poly(k,d) or poly(kd),
- near-linear running time.
The algorithms need a constant number of rounds in the MPC model.

As I understand it, the key to the improved running time is devising a distributed algorithm that can manage with the local $n^\theta$ memory of the $n^{1-\theta}$ available machines.


strengths_and_weaknesses: The paper is well written and presented, even featuring brief discussions of why straightforward ideas do not work, which is appreciated.

The results are a clear improvement with respect to the state of the art. In particular, they improve substantially w.r.t. previous results in the MPC model. 

I do not have any strong objections, bearing in mind that I have not read the appendix.


questions: One thing to note is that the authors might want to devote more space to the intuition of the charging argument, which seems to be one of the most innovative elements. Other parts of the algorithms rely heavily on known data structures and DP tricks.
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work?
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers differentially private clustering in the massively parallel computation (MPC) model. In particular, this paper gives two private algorithms for $k$-means and $k$-median clustering that achieve constant-factor multiplicative and $\text{poly}(k,d)$ additive error, using a constant number of parallel computation rounds and near-linear runtime in $n$. The algorithms provide a trade-off between the relative approximation and the additive error.
strengths_and_weaknesses: Strengths: Previous private algorithms achieve either (1) constant factor multiplicative approximation and $\Gamma^p\cdot\text{poly}(k)$ additive error using $n^{1+\Omega(1)}$ time, where $\Gamma$ is the radius of the input space or (2) $\Omega(\log n)$ multiplicative and $\Gamma^p\cdot n^{\Omega(1)}$ approximation using near-linear time, i.e., roughly $O(nd)$ time, but not both simultaneously. The first algorithm given in this paper manages to achieve "the best of both worlds", getting both constant factor multiplicative approximation and $\Gamma^p\cdot\text{poly}(k)$ additive error using near-linear time, i.e., roughly $O(nd)$ time. Further achieving these results in the MPC model seems like an added bonus. 

Weaknesses: The additive error of the algorithms in this paper have worse dependencies in $k$ than the state-of-the-art (when the latter is permitted polynomial time, which is perhaps an unfair comparison). The abstract also mentions "a novel charging argument which might be of independent interest" that I would have liked to hear more about. I understand that details of the analysis may be challenging to describe due to the space limits but given that the techniques are highlighted in the abstract, even a pointer in the first 9 pages to where the charging argument is described in the supplementary material would have been nice. 
questions: 1. Do the techniques/results have any implications for local differential privacy?

2. Can the results be adjusted to give a coreset with $(1+\gamma)$ multiplicative approximation rather than $(1+\gamma)$ multiplicative approximation to the optimal non-private algorithm? That is, if determining the actual centers/clustering is not restricted to polynomial time, can the multiplicative approximation of the algorithm be boosted to $(1+\gamma)$, perhaps at a cost of additional $\frac{1}{\gamma}$ factors in the number $T$ of points sampled in each ring $\mathcal{X}_{j,r}$ in Algorithm 1?

3. Could you please elaborate more on the novel charging argument and potential applications of the techniques (the latter perhaps at an optimistic level)?

4. It seems the main reason for the roughly $O(nkd)$ runtime for the second algorithm is due to line 1092 mapping each point $x\in X$ to its region $\mathcal{T}_{j,r}$, which is a set of rings of growing radius around a set of centers. Can this assignment be done in $\tilde{O}(nd)$ time by using terminal embeddings, e.g., [MMR19,NN19,EFS+22]?

[MMR19] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn: Performance of Johnson-Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering. STOC 2019

[NN19] Shyam Narayanan, Jelani Nelson: Optimal terminal dimensionality reduction in Euclidean space. STOC 2019

[EFS+22] Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Learning-Augmented $k$-means Clustering. ICLR 2022

Post-response update: Thanks for the follow-up explanation. In light of the improved runtime (as well as the responses to the questions raised by other reviewers), I have increased my score from 6 to 8. If space or time permits, please include a similar discussion/analysis/comparison of these works in the full version of the updated manuscript. 
limitations: I do not foresee concerns about the limitations and potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors develop near-optimal private algorithms for k-means and k-median. Their algorithms boast either better approximation guarantees, or better additive error or they are more efficient, when compared with previous works. Moreover, they can be implemented in the MPC model with constant rounds of communication. The problem is relevant to the machine learning community, while the theoretical results are interesting and non-trivial. 
strengths_and_weaknesses: + the problem is relevant to the Neurips community, while the paper is well written
+ their algorithms boast either better approximation guarantees, or better additive error or they are more efficient, when compared with previous works. They can also be implemented in the MPC model with constant number of rounds. The charging argument developed in the paper might be of independent interest. 

- the paper would have benefited from an experimental evaluation assessing the efficiency of their algorithms on real-world data
questions: -
limitations: -
review_title: null

Meta-review: metareview: The paper gives new algorithms for k-means and k-median clustering with differential privacy in the massively parallel computation (MPC) model. These are fundamental clustering problems and the MPC model is a common abstraction for relevant distributed systems such as Hadoop, Spark. The new algorithms have approximation factors and additive errors close to those of best known algorithms for the single machine setting, with a constant number of rounds of communication and near linear total work. All of these parameters are close to optimal, except for possibly a few factors of k, the number of clusters. All reviewers appreciate the new solution to important problems in a relevant setting, especially the near optimality in several dimensions at once: the number of rounds, the total work, the approximation factor, and the additive error.
confidence: Certain
Decision: Accept