CS Paper Radar

Online Differentially Private Consistent Clustering

Edith Cohen, Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Alexander Knop, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Adam Sealfon, Marika Swanberg

cs.DS cs.CR ·submitted 2026-08-28 04:03 UTC · v1

Abstract

We study differentially private (DP) $k$-means and $k$-median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need to output a set of $k$ centers that optimizes the clustering objective for all points seen so far. We give a generic reduction that transforms the (sensitive) input stream into a private stream, which is a semi-coreset of the input stream. This implies that any (non-private) online clustering algorithm, run as a post-processing step, can achieve good utility for the original clustering objective. Our algorithm matches or improves upon the approximation ratio, space usage, and running time of existing algorithms [Epasto et al., 2026, Dupré la Tour et al., 2024]. A key aspect of our reduction is that it inherits desirable properties of the underlying non-private clustering algorithm, such as consistency [Lattanzi and Vassilvitskii, 2017]--a property not satisfied by previous DP algorithms.

Closest papers

Nearest neighbours by meaning across the whole index.

Competitive Online Clustering with Movement Cost

cs.DS ·2026-10-16 ·Christian Coester, Yichen Huang, Michael Mitzenmacher
top venue similarity 0.70
Abstract · To appear in SODA 2027

We study the problem of online clustering with movement cost, which generalizes the fundamental $k$-server problem. At each time step, the algorithm is given a set of points in a metric space and must choose $k$ cluster centers. The cost incurred is the sum of the clustering cost at each time step and the total distance that the centers move over time. Prior work established competitive algorithms for the case $k\in\{1,2\}$ on the line metric with the $k$-median clustering objective; under the $k$-median objective, this problem is also known as facility reallocation. We substantially generalize these results to arbitrary $k$, general metric spaces, and a broad class of clustering objectives. Specifically, we consider clustering costs defined as a norm of the distance vector from points to their nearest center, which subsumes the $k$-median, $k$-center, and (square root of) $k$-means objectives, and provide an asymptotically optimal $O(k)$-competitive randomized algorithm against adaptive online adversaries. The algorithm is based on a reduction to the $k$-server problem, establishing a tight connection between the problems. In this reduction, $k$-server requests are generated by Poisson processes, whose arrival rates evolve in continuous time and are driven by a dual representation of the clustering costs. Our method of using Poissonization in this context may also be of independent interest. We demonstrate another use of the idea by deriving similar reductions for batched set chasing problems. We also consider a different family of clustering objectives defined as a norm of the vector of cluster radii, which subsumes the sum-$k$-radii and the $k$-center objectives, and give a tight $O(k)$-competitive deterministic algorithm on the line.

0.62

Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering

cs.DS ·2026-11-05 ·Chengzhi Guo, Shaofeng H. C. Jiang, Robert Krauthgamer, David P. Woodruff, Shenghao Xie +1 more
similarity 0.67
Abstract

We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(ε^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.

0.29

Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering

cs.LG cs.AI ·2026-09-06 ·Zeyu Lin, Chaoqi Jia, Longkun Guo, Chao Chen
top venue similarity 0.66
Abstract

Motivated by the growing importance of fairness in machine learning, fair $k$-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into $m$ disjoint groups, and the objective is to select $k$ data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair $k$-center with an approximation ratio of $2.732$. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of $4.464$. These ratios can be further respectively improved to $2.414$ and $3.828$ with a runtime exponential on $k$. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of $4.732$, which can be further improved to $4.42$, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.

0.40

Machine Unlearning for Federated Socially Fair k-Means Clustering

cs.LG cs.DS ·2026-10-09 ·Aravind Reddy, Deeraj S K, Mohd Wasif Raza, Saurav Prakash
theorycode/data similarity 0.62
Abstract · 53 pages, 7 figures, including appendices. The first three authors contributed equally. Supplementary code, data and scoped Lean proofs (v1.…

Federated clustering can support applications such as patient stratification across hospitals and customer segmentation across distributed financial datasets. Responsible AI calls for fair representation of demographic groups and support for data deletion, motivated in part by rights such as the GDPR's right to erasure. These goals interact: deleting records can change the balance between groups and alter the clustering of the remaining population. We study exact machine unlearning for federated socially fair $k$-means, whose objective is to minimize the largest group-average squared distance to the nearest center. Our approach keeps separate local summaries for each group, so summaries at unaffected institutions remain valid as global fairness weights change. For two groups, we prove an initialization approximation guarantee independent of client group proportions under ideal sampling, and we show that same-seed replay reproduces retraining exactly. Reuse pays off most when a whole client withdraws: across three datasets, replay is $35.8\times$ faster than retraining for the initialization-only model and remains $2.4\times$ and $1.7\times$ faster with one and two fair-refinement rounds, which improve worst-group cost. For individual record deletions, gains are modest (about $1.06\times$), and certifying cached assignments can cost more than it saves. These results map where exact unlearning can profitably reuse computation. Code and reproducibility materials are available at https://github.com/arareddy/mufsc.

0.39

Evolving Federated Density Peak Clustering with Shuffler-Based Anonymization

cs.LG cs.CRcs.DCeess.SY ·2026-10-22 ·Miha Ožbot, Seiichi Ozawa, Igor Škrjanc
publishedbenchmarkcode/data similarity 0.61
Abstract · 30 pages, 4 figures. Published open access (CC BY 4.0) in Evolving Systems 17, 123 (2026). Code: https://github.com/mihaozbot/eFDPC

In this paper, we present a novel one-shot federated clustering approach based on evolving fuzzy clustering and shuffler-based anonymization. In federated clustering, each round reveals additional model information to the server and can increase the opportunity to infer properties of local datasets, even when raw samples are never shared. Consequently, fewer client-server exchanges and unlinkability are important, so transmitted information cannot be attributed to any single client. Data-stream clustering algorithms, which learn in a single pass over the data, align well with the one-shot federated learning paradigm, where a single communication round can be sufficient. The proposed Evolving Federated Density Peak Clustering (eFDPC) method combines evolving fuzzy data-stream clustering and density peak clustering in a federated setting. Each client independently evolves micro-clusters from private data mini-batches through cluster addition and merging. To limit communication, density peak clustering is applied to the learned micro-clusters and only the selected peaks are transmitted, rather than the full local models. A shuffler-based layer is introduced between the clients and the server to anonymize contributions prior to reconstruction and global peak selection. We consider a peak-only variant, eFDPC-P, as well as eFDPC-G with server-side label propagation. Experiments on synthetic and real-world benchmark datasets show that eFDPC outperforms recent federated clustering baselines in one-shot settings and scales to higher-dimensional, non-IID data.

0.41

Differentially Private Continual Release with Relative Error

cs.DS ·2026-08-20 ·Bo Li, Wei Wang, Peng Ye
theory similarity 0.61
Abstract

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

0.16

Privacy-Preserving Clustering Algorithm and Parameter Selection for Collaborative Population Stratification Using Distributed PCA

cs.CR cs.LG ·2026-11-13 ·Maryam Ghasemian, Lynette Hammond Gerido, Erman Ayday
similarity 0.61
Abstract

We propose a privacy-preserving selection layer for collaborative population stratification workflows, enabling an honest-but-curious server to recommend a strong clustering algorithm-hyperparameter configuration from privacy protected shares. Instead of using a fixed workflow such as PCA followed by K-Means with a preset number of clusters, the framework compares multiple clustering methods and parameter settings under privacy constraints. To avoid relying on a public reference basis, we construct a shared low-dimensional representation through a distributed-PCA (DPCA) procedure in which each party computes local top-$r$ principal-component information and the server aggregates only low-rank summaries to recover a global basis. Building on this representation, the framework supports three LDP-protected pipelines: PCA then Noise, Noise then PCA, and Noise-Only. The server evaluates clustering methods and parameter settings using internal validation metrics and recommends a top-performing configuration from the perturbed data; this step is pure post-processing. Experiments on openSNP and 1000 Genomes show that the server-side selection layer reliably identifies strong settings from LDP-protected data. Across both datasets, the PCA-based pipelines outperform Noise-Only in clustering utility, communication cost, and runtime, and show lower membership-inference attack (MIA) power at small privacy budgets. Overall, they provide the best utility--scalability trade-off in our setting.

0.45

Coresets for Capacitated Clustering via Dual Concentration

cs.DS cs.CGcs.LG ·2026-11-06 ·Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam, Erik Waingarten
similarity 0.61
Abstract

We study coresets for clustering problems, focusing on the classical $k$-median and $k$-means objectives. A coreset is a small weighted summary of the input data that approximately preserves the clustering cost for every choice of centers. Such summaries are a central tool for scaling clustering algorithms to large datasets. In this work, we consider the capacitated setting, where the clustering is subject not only to choosing centers but also to respecting prescribed cluster-size constraints. This model is a natural generalization of standard clustering and has been widely studied, but its coreset complexity is less well understood. For finite metric spaces, we obtain optimal-size coresets; surprisingly, these match the best-known bounds for unconstrained clustering. We also give improved coreset bounds in Euclidean space, notably the first coresets with near-linear dependence in $k$ while being independent of the dimension and input size. The main new technical ingredients are concentration bounds for the dual solutions of min-cost flow problems, which allow for both significantly simpler and tighter analyses of the underlying sampling distribution used in the coreset construction.

0.12