Authors: Asilata Karandikar
On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clustering
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.
Journal/Conference
SPCOM 2026
The concept of consent is pervasive in discussions on privacy rights and laws in the digital sphere. Consent refers to the agreement between two or more parties on the meaning and purport of terms governing their interaction. Drawing on notions of the morally transformative capacity of informed consent [7], this paper asserts that the concept of informed consent stands to gain from an understanding of political theories of Social Contract and the institutional mechanisms which follow from it. At the core of the Social Contract theories is the idea of popular consent as the basis for the establishment and continuing legitimacy of the state [1]. Consent, therefore, plays a constitutive role in establishing and validating the existence of an agreement – from interpersonal contracts to something as broad-based as the social contract.
How then, do we conceptualise meaningful consent in a way which encompasses the myriad ways in which it underpins interactions? While existing literature outlines pathological consent interactions [14, 15] deriving from the ways in which consent is obtained, this paper proposes delving into the structure of consent transactions to highlight pathologies of consent embedded within. This structure is obtained by mapping the objects of consent – in private or collective realms – onto the modes by which consent is granted or mediated. This mapping results in four quadrants of consent transactions and enables us to understand their resultant pathologies. By bringing together the relevance of consent in interpersonal interactions as well as broader collective decisions, this paper argues that a structural view of consent transactions and its resultant pathologies improves on existing literature and better informs the conceptualisation of meaningful consent.