Research map / Federated learning and privacy / Differential privacy

Online Differentially Private Consistent Clustering

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Differentially private clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a DP online reduction that turns a sensitive stream into a private semi-coreset stream via a private Meyerson sketch with DP dense-ball subroutines, enabling DP online k-means/median with consistency k·polylog(nd) and near-optimal additive error.

Problem

Differentially private online (streaming) k-means and k-median clustering that outputs k centers for all prefixes while being efficient and temporally consistent.

Approach

A private version of Meyerson's sampling sketch in which sampled points are fed to a DP dense-ball algorithm only when a privately counted sketch size grows (via continual counting); the resulting private semi-coreset stream is post-processed by a non-private consistent online clustering algorithm.

Key results

• Achieves constant approximation with additive error (sqrt(d)/eps)·(k log(nd/delta))^O(1) and (k·polylog(nd))-consistency for DP online k-clustering.
• For k, d, log(1/delta) ≤ n^{o(1)}, runs in n^{1+o(1)} total time and n^{o(1)} space.
• Additive error k^{2.5}√d versus k^{2.5}d^{3.51} for Dupré la Tour et al. (per the comparison table); prior Epasto et al. algorithm requires n^{O(log k)} time and space.

Limitations

• Utility analysis assumes an oblivious input stream; adversarial utility is open.
• Multiplicative approximation is a constant (semi-coreset, not (1+o(1)) coreset) and the output is only a semi-coreset with additive error.
• Dense-ball DP algorithms are theoretical and not practically implemented; dependence on k in additive error is suboptimal.

Experimental setup

Metrics: additive error approximation ratio consistency space running time

Baselines: Epasto et al. DP online clustering Dupré la Tour et al. DP online clustering

Builds on: Meyerson's sketch 1-Cluster (DP) continual counting (binary mechanism) consistent clustering (Fichtenberger et al.)

Closest papers by meaning

• Differentially Private Clustering: Tight Approximation Ratios (NeurIPS 2020 · similarity 0.92)
• Differentially Private Federated $k$-Means Clustering with Server-Side Data (ICML 2025 · similarity 0.90)
• Making Old Things New: A Unified Algorithm for Differentially Private Clustering (ICML 2024 · similarity 0.89)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.89)
• Fair Clustering in the Sliding Window Model (ICLR 2025 · similarity 0.88)
• On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.87)