Source-linked AI summary
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
TL;DR
The paper studies differentially private k-means and k-median clustering in online streams, where centers must be released for every data prefix while remaining temporally stable. It privately transforms the stream into a semi-coreset stream so any non-private online clustering algorithm can run as post-processing. The resulting algorithm provides nearly optimal consistency together with constant approximation, nearly optimal dimension-dependent additive error, and favorable time and space bounds.
Problem
Online DP clustering must optimize every arriving-data prefix, but prior DP online algorithms did not inherit the consistency guarantees of non-private online clustering.
Method
A generic reduction transforms the sensitive stream into a privatized stream whose prefixes are semi-coresets, then applies a non-private online clustering algorithm as post-processing.
Results
The framework yields the first DP online clustering algorithm with nearly optimal consistency, constant approximation ratio, and nearly optimal dimension-dependent additive error.
Takeaways & Limitations
The reduction can transfer desirable properties of non-private online clustering algorithms, including consistency, to the differentially private setting.
Takeaways & Limitations
Utility guarantees assume the oblivious adversarial model, while extending them to the stronger adaptive setting remains open; practical deployment is also limited by theoretical dense-ball algorithms.
Abstract
from arXiv · showhide
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.
1 Introduction
This work addresses differentially private clustering over sequential data streams, where outputs must remain useful and temporally stable as points arrive. It introduces a generic private semi-coreset reduction that preserves clustering utility while inheriting properties such as consistency from non-private online algorithms.
- Online clustering: Online clustering must output k centers after each arrival for all points seen so far, unlike static clustering, which processes the dataset simultaneously.The streaming model requires a center set C_t at every time step for the prefix x_1, ..., x_t.
- Consistency: Consistency limits total center changes across the output sequence, addressing volatility that can make online cluster assignments temporally unstable.An m-consistent sequence has at most m total centers removed or added, and temporal stability is desirable in real-world applications.
- Prior limitations: Previous DP online clustering algorithms did not provide the consistency property achieved by established non-private online methods.Fichtenberger et al. provide O(1)-approximation and nearly optimal consistency non-privately, while prior DP algorithms lacked consistency.
- Approach: The paper’s generic reduction converts a sensitive stream into a DP privatized semi-coreset stream whose prefixes approximately preserve clustering objective values.The construction supports any non-private online clustering algorithm as a post-processing step because differential privacy is preserved under post-processing.
- Guarantees: The resulting online (k, p)-clustering algorithm achieves a constant approximation ratio, d ε · (k log(nd/δ))O(1)-additive error, and (k · polylog (nd))-consistency.The consistency and dimension-dependent additive-error guarantees are nearly optimal up to polylogarithmic factors.
- Efficiency: When k, d, log(1/δ) ≤n^o(1), the algorithm uses n^o(1) space and runs in n^1+o(1) total time.The comparison covers online (ε, δ)-DP clustering algorithms with constant approximation ratios, while the paper’s method supports insertion-only streams.
2 Preliminaries
The paper formalizes online clustering, semi-coresets, dense-ball subroutines, and differential privacy. These definitions establish prefix-wise approximation, consistency, and the Euclidean bounded-diameter setting used later.
- Setting and primitives: The framework assumes Euclidean space with bounded diameter and uses a dense-ball algorithm that covers sufficiently populated balls with controlled output size.The dense-ball problem is parameterized by rmin and τ, with size blow-up Υ and capacity N.
- Online clustering: Online clustering processes points sequentially and outputs k centers after every arrival for the prefix seen so far.The output at time t contains k centers and is evaluated on the first t points.
- Clustering objectives: For p = 1 and p = 2, the (k, p)-clustering objective becomes k-median and k-means, respectively.The objective minimizes the sum of p-th powers of distances to the closest center.
- Prefix approximation: A prefix-approximation evaluates each point using only centers released by its arrival time, making it stronger than an end-of-stream approximation.Future output points cannot serve earlier inputs.
- Semi-coresets: A semi-coreset permits multiplicative and additive errors while preserving the property that a good solution for it approximates the original dataset.The online definition requires every output prefix to be a semi-coreset of the corresponding input prefix.
- Consistency: Consistency bounds the total number of center changes across the output sequence; prior non-private work gives a k · polylog(nd)-consistent constant-additive-error algorithm.The cited algorithm has time and space polynomial in the number of distinct points and dimension.
- Differential privacy: The online privacy model defines neighboring streams by changing one point to ⊥ and requires the standard (ε, δ)-DP output-distribution inequality.The privacy proof extends to adaptive streams, but the utility analysis assumes an oblivious stream.
3 Private Semi-Coreset Construction
The construction privately samples stream points, periodically applies a DP dense-ball routine, and releases a bounded private stream that approximates every input prefix. This stream supports a semi-coreset construction with controlled approximation and size.
- Main guarantee: Theorem 9 provides an online (ε, δ)-DP algorithm whose output is an (O(1), O(1), β)-semi-coreset with probability 1 −γ.The theorem also gives explicit running-time bounds, though the supplied passage truncates them.
- Construction: The private sketch maintains sampled points and periodically feeds them to a DP dense-ball algorithm, releasing its output rather than the sensitive sample.Continual counting controls when dense-ball calls occur, while capacity checks bound sampling and calls.
- Conditions: The prefix-approximation guarantee relies on a sufficiently accurate optimum estimate and assumptions on dense-ball coverage and continual-counting accuracy.The dense-ball routine must have capacity Ψ · τ and size blow-up Υ, while continual counting has accuracy τ/2.
- Space control: The released stream has size |R≤n| ≤ Ψ^2 · Υ.The bound follows from the sample capacity, the maximum number of dense-ball calls, and the dense-ball size blow-up.
- From sketch to semi-coreset: The prefix approximation is converted into a semi-coreset by snapping each input point to its closest released center and privately computing weights.The weighting step uses continual counting and is deferred to the appendix in the supplied passage.
4 From DP Semi-Coreset to DP Consistent Clustering
The private semi-coreset is post-processed by a non-private consistent clustering algorithm. Privacy is preserved, while consistency and approximation transfer from the semi-coreset to the original stream.
- Reduction: Running the non-private online consistent clustering algorithm on the private semi-coreset yields an (ε, δ)-DP online clustering algorithm.The privacy guarantee follows directly from DP post-processing.
- Guarantees: The resulting algorithm is k · polylog(nd)-consistent and achieves an (O(1), β)-approximation with high probability.The corollary also states time bounds, but the supplied passage truncates them.
- Utility transfer: Approximation transfers because a solution approximating each semi-coreset prefix also approximates the corresponding original prefix.The transfer is formalized by applying the semi-coreset approximation lemma.
5 Conclusion and Open Questions
The paper’s generic reduction delivers nearly optimal consistency together with constant approximation and near-optimal dimension-dependent additive error. Open questions concern practicality, k-dependence, adversarial utility, multiplicative error, and runtime.
- Conclusion: The reduction privatizes a sensitive stream into a semi-coreset stream while allowing any non-private online clustering algorithm as post-processing.This modularity yields the first DP online clustering algorithm with nearly optimal consistency.
- Conclusion: The resulting guarantees combine nearly optimal consistency, a constant approximation ratio, and nearly optimal additive error in dimension d.The conclusion presents these as the main paper-level outcomes.
- Open questions: Practical deployment is limited because the underlying DP dense-ball algorithms are theoretical and lack practical implementations.The private adaptation of Meyerson’s sketch itself is described as straightforward to implement.
- Open questions: The additive-error dependence on k remains suboptimal, partly because of DP composition across dense-ball runs.An online DP dense-ball algorithm is suggested as a possible route to improvement.
- Open questions: The construction leaves open online DP coresets with (1 ± o(1))-multiplicative error and faster dependence on k and d.The runtime’s polynomial dependence through Λ comes from using a 1-Cluster algorithm as a black box.
- Open questions: Utility guarantees currently assume an oblivious stream, leaving adversarial-stream utility unresolved.The privacy analysis already applies in the adversarial model, but utility does not.
A Additional Background and Missing Proofs from § 2
The paper extends generalized transport arguments to semi-coresets, accommodating weight mismatch and α > 1 while deriving the required approximation parameters.
- Proof Structure: The semi-coreset proof uses the approximate triangle inequality and separates upper and lower bounds on clustering cost.The construction defines κ, η1, and η2 from the transport and approximation parameters to satisfy both inequalities.
- Generalized Transport Cost: Generalized transport cost combines distance error with weight mismatch, making it suitable for noisy DP weights.This extends ordinary transport error to account for the weight perturbations produced by differential privacy.
- Transport-to-Semi-Coreset Reduction: For α > 1, small generalized transport cost implies a semi-coreset rather than the coreset guarantee available when α < 1.The resulting parameters are κ = O(1 + α), η1 = O(α), and η2 = O(β).
A.2 Consistent k-Clustering via Grid Snapping: Proof of Theorem 6
Grid snapping removes the aspect-ratio obstacle for consistent online clustering while preserving each prefix through a constant-error semi-coreset.
- Grid-Snapped Stream: Grid snapping rounds each coordinate to a multiple of 1/(nd), producing a discrete stream with matched point weights.The natural mapping from each original point to its snapped point has zero weight-difference cost.
- Semi-Coreset Guarantee: For every prefix, the snapped stream is an (O(1), 0, O(1))-semi-coreset of the original stream.Rounding contributes only a constant-order additive error under the bounded-diameter assumption.
- Aspect-Ratio Control: The snapped metric has aspect ratio at most nd, enabling the consistent clustering algorithm to incur consistency cost k · polylog(nd).The grid bounds the maximum distance by 1 and the minimum nonzero distance by at least 1/(nd).
- Utility Guarantee: With high probability, clustering the snapped prefix yields an (O(1), O(1))-approximation for the corresponding original prefix.The transfer follows by combining the snapped-stream semi-coreset guarantee with the semi-coreset approximation lemma.
A.4 Dense Ball Algorithm
The dense-ball construction repeatedly applies a DP 1-Cluster routine, using composition to provide privacy and guaranteeing bounded output size, coverage, and efficiency.
- Construction and Privacy: The algorithm extracts dense balls iteratively by invoking the DP 1-Cluster subroutine at most K = O(N/τ) times.Each invocation operates on the remaining dataset and uses per-run privacy parameters chosen for composition.
- Size Bound: The output contains exactly one center per iteration, giving size blow-up O(1) and specifically |O| = K ≤ 4N/τ.The construction runs for exactly K steps.
- Coverage: Setting the 1-Cluster additive error to t ≤ τ/2 ensures that every sufficiently dense ball is covered by a returned ball.The coverage proof shows that otherwise every iteration would remove at least τ/2 points, exhausting a dataset of size at most N.
B.1 Private Meyerson’s Sketch: Privacy and Efficiency
The private Meyerson sketch combines continual counting with DP dense-ball calls, and its privacy and efficiency follow from adaptive concurrent composition and bounded state.
- Privacy: Algorithm 2 has privacy parameters (2Ψεd + εc, 2e^(2εd)Ψδd + δc).The bound combines the continual-counting mechanism with at most Ψ dense-ball invocations and group privacy.
- Adaptive Privacy: The privacy proof remains valid when inputs are chosen adaptively from the transcript.The counting stream and dense-ball inputs are analyzed under concurrent adaptive composition.
- Running Time: The sketch runs in O(ndK + Tc(n) + Ψ · Td(Ψ · τ)) time.The closest-point computation contributes the K-dependent term, while dense-ball calls contribute at most Ψ subroutine executions.
- Space: Its space usage is O(Ψ(τ + ΨΥ)d + Sc(n) + Sd(Ψτ)).The stored state consists primarily of the active point set and released representatives, in addition to the subroutine states.
B.2 Combined Prefix-Approximation Guarantee via Guessing
The algorithm randomly guesses the optimum cost, configures a private Meyerson sketch, and obtains prefix-approximation, size, and complexity guarantees when the guess is correct.
- Random guessing: Randomly sampling optest from G removes its dependence from the capacity and density-threshold parameters, which can then be set using k, d, and n.The guess set contains 2⌈log2 n⌉ elements, so the correct guess is selected with probability Ω(1/log n).
- Algorithm: The sketch configures a DP dense-ball mechanism and runs DP Meyerson’s Sketch on the stream using the sampled optimum estimate.The density threshold τ depends on the privacy model, and the dense-ball mechanism receives allocated privacy parameters.
- Size: O(k2 log2 n) bounds the total number of output centers.This follows from the sketch constraint K ≤ O(Ψ2) with Ψ = Θ(k log n).
- Complexity: The algorithm processes the stream in total time ˜O with privacy-dependent parameters Λ = kd log n/ε for pure-DP and Λ = kd log(n/δ)/ε for approximate-DP.The supplied passages state the time form and the corresponding Λ values, but the time expression itself is truncated.
- Accuracy: O(1)-approximation with additive error β = O(τk log n) holds with probability 1/2 conditioned on the correct guess.The O(optest) term is absorbed into the multiplicative factor, while the O(1/n) term is dominated by O(τkL).
B.3 Boosting Probability via Repetition
The low-probability prefix guarantee is amplified by running independent copies and unioning their outputs, yielding simultaneous high-probability guarantees over all prefixes.
- Repetition: Repeating the DP algorithm R times and unioning outputs preserves privacy while multiplying output size, space, and time by R.The repeated construction uses the same per-run approximation guarantee and combines the resulting streams.
- Probability amplification: If each fixed prefix succeeds with probability q, then at least one of R repetitions succeeds for every t with probability at least 1 − n(1 − q)^R.The bound follows from a union bound over the n time steps.
- Final guarantee: With probability 1 − γ, the amplified output is an (O(1), β)-prefix-approximation for all t ∈ [n].The high-probability construction is obtained by combining the repetition lemma with q = Ω(1/log n).
- Final guarantee: O(k2 · polylog(n/γ)) bounds the total number of output centers after amplification.Repetition increases the single-run size bound by the amplification factor.
- Complexity: The amplified algorithm processes the stream in total time ˜O with Λ = kd log(n/γ)/ε for pure-DP.The supplied time expression is truncated, but the privacy-dependent parameter is stated explicitly.
C From Prefix-Approximation to DP (Semi-)Coreset: Proof of Theorem 9
The private semi-coreset reduction snaps each arriving point to a prefix center and privately estimates center weights, while composing privacy and bounding efficiency.
- Construction: The reduction runs an online prefix-approximation algorithm, snaps each point to its closest produced center, and estimates each center’s weight with continual counting.The resulting weighted center multiset forms the private stream used as a semi-coreset.
- Privacy: (εb + εc, δb)-DP follows when the prefix mechanism is (εb, δb)-DP and the counting mechanism is εc-DP.The proof treats the two components as a concurrent composition.
- Efficiency: O(Tb(n) + nKd + K · Tc(n)) time and O(Sb(n) + K · Sc(n) + Kd) space are sufficient for the private semi-coreset algorithm.K is the maximum number of centers produced by the prefix-approximation algorithm.
- Semi-coreset guarantee: κ = O(1 + α1), η1 = O(α1), and η2 = O(β1 + Kβ2) characterize the resulting semi-coreset guarantee.These parameters combine prefix-approximation error with cumulative counting error across K active centers.
- Proof structure: The construction maps each input point to its closest available prefix center and separates transport cost into distance and weight-difference terms.The distance term uses the prefix guarantee, while the weight term uses counting accuracy.
C.3 Putting Things Together: Proof of Theorem 9
Theorem 9 instantiates the semi-coreset reduction with the high-probability prefix approximation and continual counting mechanisms, yielding the claimed privacy, complexity, and accuracy guarantees.
- Privacy: Setting εb = εc = ε/2 and δb = δ gives the claimed (ε, δ)-DP guarantee by composition.The construction uses the prefix-approximation and counting mechanisms from Theorems 31 and 23.
- Complexity: K = O(k2 · polylog(n/γ)) bounds the number of generated centers and is substituted into the efficiency lemma to obtain the claimed time and space complexity.The same K bound controls the number of distinct output points.
- Accuracy: The semi-coreset error is dominated by β1 in both pure-DP and approximate-DP settings.This follows after substituting the prefix-approximation and counting accuracy guarantees into the semi-coreset lemma.