PaperlayerView exact revision on arXiv

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

arXiv:2608.27896v1cs.DScs.CR

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.

    Source: §1 · p. 2

  • 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.

    Source: §1.1 · p. 2, §1.2 · p. 4, §2.1.1 · p. 6

  • Results

    The framework yields the first DP online clustering algorithm with nearly optimal consistency, constant approximation ratio, and nearly optimal dimension-dependent additive error.

    Source: §5 · p. 11

  • Takeaways & Limitations

    The reduction can transfer desirable properties of non-private online clustering algorithms, including consistency, to the differentially private setting.

    Source: §1.1 · p. 2, §5 · p. 11

    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.

    Source: §2.4 · p. 7, §5 · p. 11

Abstract

from arXiv · show

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.Source: §1 · pp. 1–2

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.Source: §1 · p. 2

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.Source: §1 · p. 2

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.Source: §1.1 · pp. 2–4

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.Source: §1.1 · p. 3

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.Source: §1.1 · p. 3, Table 1 · p. 3

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.Source: §2 · p. 5, §2.1 · p. 5, §2.3 · pp. 6–7

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.Source: §2 · p. 5, §2.1 · p. 5

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.Source: §2.1 · p. 5

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.Source: §2.1 · pp. 5–6

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.Source: §2.1.1 · p. 6

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.Source: §2.2 · p. 6

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.Source: §2.4 · p. 7

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.Source: §3 · p. 7

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.Source: §3.1 · p. 8, §3 · p. 8

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.Source: §3.1 · p. 8

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.Source: §3.1 · p. 8

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.Source: §3.1 · p. 10

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.Source: §4 · pp. 10–11

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.Source: §4 · p. 10

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.Source: §4 · p. 11

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.Source: §5 · p. 11
  • 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.Source: §5 · p. 11

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.Source: §5 · p. 11
  • 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.Source: §5 · p. 11
  • 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.Source: §5 · pp. 11–12
  • 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.Source: §5 · p. 11

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

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.Source: §A.1.1 · p. 15

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(β).Source: §A.1.1 · p. 15

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.Source: §A.2 · p. 17

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.Source: §A.2 · p. 17

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).Source: §A.2 · p. 18

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.Source: §A.2 · pp. 17–18

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.Source: §A.4 · pp. 20–21

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.Source: §A.4 · pp. 20–21

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.Source: §A.4 · p. 21

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.Source: §B.1 · pp. 22–23

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.Source: §B.1 · pp. 22–23

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.Source: §B.1 · p. 23

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.Source: §B.1 · p. 23

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).Source: §B.2 · pp. 23–24

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.Source: §B.2 · p. 23

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).Source: §B.2 · pp. 24–25

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.Source: §B.2 · p. 24

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).Source: §B.2 · p. 25

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.Source: §B.3 · pp. 25–26

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.Source: §B.3 · pp. 25–26

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).Source: §B.3 · p. 26
  • O(k2 · polylog(n/γ)) bounds the total number of output centers after amplification.Repetition increases the single-run size bound by the amplification factor.Source: §B.3 · pp. 25–26

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.Source: §B.3 · p. 26

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.Source: C From Prefix-Approximation to DP… · p. 26

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.Source: §C.1 · pp. 26–27

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.Source: §C.1 · p. 27

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.Source: §C.2 · p. 28

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.Source: §C.2 · p. 28

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.Source: §C.3 · p. 29

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.Source: §C.3 · p. 29

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.Source: §C.3 · p. 29

Related papers

Loading 2608.27896v1…