# On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clustering

arXiv: https://arxiv.org/abs/2603.26963 · HTML: https://mlsanity.com/paper/2603.26963/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 47 references that are in the map.
- First posted on arXiv 27 Mar 2026.

## Builds on (most cited first, 15 of 15)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Diffprivlib: The IBM Differential Privacy Library](https://mlsanity.com/paper/1907.02444/) (2019)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Differentially Private Clustering via Maximum Coverage](https://mlsanity.com/paper/2008.12388/) (2020)
- [k-variates++: more pluses in the k-means++](https://mlsanity.com/paper/1602.01198/) (2016)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime](https://mlsanity.com/paper/2207.00420/) (2022)
- [Grafting Laplace and Gaussian distributions: A new noise mechanism for differential privacy](https://mlsanity.com/paper/2212.09657/) (2022)
- [Offset-Symmetric Gaussians for Differential Privacy](https://mlsanity.com/paper/2110.06412/) (2021)
- [Differentially Private k-Means Clustering with Guaranteed Convergence](https://mlsanity.com/paper/2002.01043/) (2020)
- [Differentially Private Explanations for Clusters](https://mlsanity.com/paper/2506.05900/) (2025)

## Abstract (arXiv)

Differentially private K-means clustering enables releasing cluster centers derived from a dataset while protecting the privacy of the individuals. Non-interactive clustering techniques based on privatized histograms are attractive because the released data synopsis can be reused for other downstream tasks without additional privacy loss. The choice of the number of grids for discretizing the data points is crucial, as it directly controls the quantization bias and the amount of noise injected to preserve privacy. The widely adopted strategy selects a grid size that is independent of the number of clusters and also relies on empirical tuning. In this work, we revisit this choice and propose a refined grid-size selection rule derived by minimizing an upper bound on the expected deviation in the K-means objective function, leading to a more principled discretization strategy for non-interactive private clustering. Compared to prior work, our grid resolution differs both in its dependence on the number of clusters and in the scaling with dataset size and privacy budget. Extensive numerical results elucidate that the proposed strategy results in accurate clustering compared to the state-of-the-art techniques, even under tight privacy budgets.