Online Differentially Private Consistent Clustering

Online Differentially Private Consistent Clustering Edith Cohen∗

Vadym Doroshenko†

Alexander Knop§

Ravi Kumar§

Ethan Leeman§

Adam Sealfon§

arXiv:2608.27896v1 [cs.DS] 28 Aug 2026

Badih Ghazi‡

Pritish Kamath§ Pasin Manurangsi§

Marika Swanberg§

August 31, 2026

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.

1

Introduction

Differential Privacy (DP) [Dwork et al., 2006a,b] has emerged as the mathematically rigorous, widely used gold standard for privacy-preserving large-scale data analysis. By injecting carefully calibrated statistical noise into computations, DP provides a formal, quantifiable guarantee that limits the information an adversary can infer about any single data point, making it a foundational tool for government agencies and technology companies alike (e.g., Abowd [2018], Erlingsson et al. [2014]). Within the domain of large-scale data analysis, clustering remains one of the most basic unsupervised learning tasks. In this work, we focus on the (k, p)-clustering objective: given a dataset X =P(x1 , . . . , xn ) ∈ (Rd )n , the goal is to output a set C of k centers that minimizes costpX (C) := i∈[n] dist(xi , C)p , where dist(xi , C) denotes the (Euclidean) distance from xi to its closest point in C. When p = 1 (resp., 2), this corresponds to the k-median (resp., k-means) clustering, which are among the most well-studied objectives. Since finding the exact minimizer is NP-hard, clustering algorithms focus on providing a small multiplicative approximation ratio [Matousek, 2000, Kanungo et al., 2004, Har-Peled and Mazumdar, 2004, Awasthi et al., 2015, Lee et al., 2017, Cohen-Addad and Karthik C. S., 2019, Friggstad et al., 2019, Ahmadian et al., 2020]. We ∗

Google Research and Tel Aviv University. edith@cohenwang.com Google. dvadym@google.com ‡ Google Deepmind. badihghazi@gmail.com § Google Research. pritish@alum.mit.edu, alexanderknop@google.com, ravi.k53@gmail.com, ethanleeman@google.com, pasin@google.com, adamsealfon@google.com, marikaswanberg@google.com †

1

assume throughout that p ≥ 1 is a fixed constant and we will omit the dependency on p in notations and bounds for brevity. Traditionally, clustering algorithms were designed for static datasets, where x1 , . . . , xn are processed simultaneously. However, in modern applications, continuous data generation and collection are prevalent. Online clustering is a natural task that arises in analyzing dynamically changing data streams. In the streaming (a.k.a. continuous release) model, the data points x1 , . . . , xn arrive sequentially and after the arrival of each xt , the algorithm must return a set Ct of k centers for all the data points seen so far, i.e., x1 , . . . , xt . Non-private algorithms with small approximation ratios and low space complexity are known in this model, e.g., [Guha et al., 2000, Charikar et al., 2003, Har-Peled and Mazumdar, 2004]. DP Clustering. Given the significance of clustering, a vast body of literature has explored DP clustering algorithms [Blum et al., 2005, Gupta et al., 2010, Balcan et al., 2017, Feldman et al., 2017, Nissim et al., 2016, Nissim and Stemmer, 2018, Huang and Liu, 2018, Stemmer, 2020, Ghazi et al., 2020, Chang et al., 2021, Ghazi et al., 2023, Dupré la Tour et al., 2024]. In particular, significant progress has been made in the static setting, where efficient DP clustering algorithms with constant approximation ratios and nearly-optimal additive errors are known [Ghazi et al., 2020, Dupré la Tour et al., 2024]. Unfortunately, the same cannot be said in the streaming model. Specifically, while Dupré la Tour et al. [2024] proposed a DP online (k, p)-clustering algorithm with nearly optimal approximation ratios and additive errors, their algorithm is inefficient, requiring super-polynomial time and space. Meanwhile, Epasto et al. [2026] proposed an efficient algorithm—based on the merge-and-reduce framework for coresets [Agarwal et al., 2004, Feldman et al., 2020]—but with suboptimal additive errors in terms of the dimension d. Furthermore, neither algorithm is designed to preserve desirable properties (such as consistency) of their underlying non-private counterpart, as explained next. Consistency in Online Clustering. While online clustering algorithms must adapt to changing data, this can cause a volatile output sequence. For example, if an algorithm blindly recalculates cluster centers based on x1 , . . . , xt for every t ∈ [n], the cluster centers can vary wildly even across consecutive time steps. The need for a temporally stable output sequence motivated the definition of consistency [Lattanzi and Vassilvitskii, 2017]: An output sequence (C1 , . . . , Cn ) is said to be P m-consistent if t∈[n] |Ct ∖ Ct−1 | ≤ m where we use the convention C0 = ∅, i.e., the total number of centers removed/added throughout the entire sequence is at most m = m(n). Consistency ensures that the clusters do not change unpredictably at every time step. Maintaining consistency is preferred because temporal instability can be undesirable in many real-world scenarios. Since the notion was formalized, many consistent clustering algorithms have been proposed in the literature [Lattanzi and Vassilvitskii, 2017, Guo et al., 2021, Fichtenberger et al., 2021, Chan et al., 2025]. In particular, Fichtenberger et al. [2021] devised a non-private algorithm for clustering in arbitrary metric space that achieves O(1)-approximation and Õ(k)-consistency (which is known to be nearly optimal [Lattanzi and Vassilvitskii, 2017]). Unfortunately, as mentioned earlier, neither of the previous DP online clustering algorithms [Dupré la Tour et al., 2024, Epasto et al., 2026] provides non-trivial guarantees on the consistency of their output sequence.

1.1

Our Contributions

Our primary contribution is a novel generic reduction that transforms a sensitive stream to a privatized stream that approximately preserves the clustering objective value on any input prefix. As a key corollary, we obtain the first DP algorithm that has a nearly optimal consistency guarantee. 2

Table 1: Comparison of online (ε, δ)-DP clustering algorithms. For brevity, we hide polylog (nd/δ) terms in all bounds and assume ε = Θ(1). All algorithms have constant approximation ratio. While Dupré la Tour et al. [2024] do not specify the complexity of their algorithm, the bottleneck in their algorithm is the use of an O(1/n)-net in RO(log k) , which requires nΘ(log k) time and space. We note however that their algorithm supports stream with both insertions and deletions, whereas Epasto et al. [2026] and ours only support insertions. Note that ok,d (n) consistency cannot be achieved for streams with both insertions and deletions even non-privately and when Ok,d (1) additive error is allowed. Algorithm Dupré la Tour et al. [2024] Epasto et al. [2026] This paper (Corollary 11)

Additive Err. √ k O(1) d 3.51 k 2.5 d√ 2.5 d k

Space

Time

Consistency

nO(log k) dO(1) (kd)O(1) (kd)O(1)

nO(log k) dO(1) n(dk)O(1) ndk 2 + (dk)O(1)

— — k

Furthermore, our algorithm obtains a constant approximation ratio, nearly optimal additive error in terms of the dimension d, and almost linear time and sublinear space for d, k = no(1) , as stated below. Theorem 1 (Informal version of Corollary 11). There is an (ε, δ)-DP online (k, p)-clustering algorithm that, given a stream X = (x1 , . . . , xn ) of points, outputs a stream C = (C1 , . . . , Cn ) of center multisets such that for each t ∈ [n], |Ct | = k and with high probability, Ct is an approximate √ d solution for x1 , . . . , xt with constant approximation ratio and ε · (k log(nd/δ))O(1) -additive error. Moreover, the output is (k · polylog (nd))-consistent. Furthermore, when k, d, log(1/δ) ≤ no(1) , the algorithm runs in n1+o(1) time over the entire stream and uses no(1) space. √ As mentioned above, both the dependency of d · polylog (d) in the additive error, and the consistency bound k · polylog (nd) are nearly optimal, matching the known lower bounds [Peter et al., 2024, Lattanzi and Vassilvitskii, 2017] up to polylogarithmic factors. A detailed comparison between our algorithm and those in Dupré la Tour et al. [2024], Epasto et al. [2026] can be found in Table 1. We now state our generic reduction. Recall that for a given multiset X, a semi-coreset X̃ is its “compressed” version such that for any set of cluster centers, the clustering objective on X and X̃ are close to each other, up to a multiplicative error in the approximation factor and an additive error in the cost (see Definition 4.) Our reduction is an online algorithm that produces an output stream X̃ = (x̃1 , . . . , x̃n ) of points1 such that, for any t ∈ [n], the output prefix x̃1 , . . . , x̃t is a semi-coreset of the input prefix x1 , . . . , xt , as stated below; furthermore, our algorithm is DP. Theorem 2 (Informal version of Theorem 9). There is an (ε, δ)-DP algorithm that, given a stream X = (x1 , . . . , xn ), produces another stream X̃ = (x̃1 , . . . , x̃n ) such that, with high proba√ bility, {x̃1 , . . . , x̃t } is a semi-coreset for {x1 , . . . , xt } with constant multiplicative error and εd · (k log(nd/δ))O(1) -additive error for all t ∈ [n]. Furthermore, when k, d, log(1/δ) ≤ no(1) , the algorithm runs in n1+o(1) time over the entire stream and uses no(1) space. 1 As stated our algorithm outputs a stream of multisets of points rather than individual points, i.e., multiple points may be released in each step. See Theorem 9 for the formal statement. We note that it is possible to modify the reduction so that at most one point is released in each step, but this distinction is not important in downstream applications.

3

Since DP is preserved under post-processing, we can run any non-private online clustering algorithm on the output X̃. Indeed, our DP consistent clustering algorithm (Corollary 11) simply runs the (non-private) algorithm by Fichtenberger et al. [2021] as a post-processing step on X̃.

1.2

Technical Overview

(Non-Private) Meyerson’s Sketch. The starting point of our work is the so-called Meyerson’s sketch [Meyerson, 2001]. To describe the sketch, it is simpler to consider the setting where, instead of keeping a semi-coreset, we only aim for an end-stream bi-criteria approximation. Here, we need to output a set S of points at the end of the input stream X = (x1 , . . . , xn ) such that (i) costpX (S) is at most O(1) times the optimum and (ii) |S| ≤ O(k log n). We use the nomenclature “bi-criteria” since we allow S to be (slightly) larger than k. Standard techniques exist for turning such an endstream bi-criteria approximation into an end-stream semi-coreset, even with DP; see § C for details. We now describe the Meyerson sketch. Initially, S = ∅. After a point xt arrives, we compute its distance to its Algorithm 1: Meyerson’s Sketch [Meyclosest point in S, denoted by dist(xt , S). Then, with erson, 2001] probability λt , we add it to S; otherwise, we simply disRequire: Stream X = (x1 , . . . , xn ) card it. Here, λt is set based on dist(xt , S) so that the Parameters: Estimated optimum opt est larger the distance, the more likely it is to be included 1: S = ∅ in S. The full description is in § 1.2, which also uses 2: for t = 1, . . .n, n do o an estimate (i.e., “guess”) of the optimum value optest . 3: λt ← min 1, k log n · dist(xt , S)p optest Standard analysis shows that if optest is within a constant {If S = ∅, let dist(xt , S) = ∞} factor of the true optimum, then the output S is a bi- 4: Sample Zt ∼ Ber(λt ) criteria approximation with constant probability [Meyer- 5: if Zt = 1 then S ← S ∪ {xt } son, 2001, Lattanzi and Vassilvitskii, 2017, Fichtenberger 6: 7: Output S et al., 2021]. Privacy via DP Dense Balls. A naive attempt to make Meyerson’s sketch (in fact, any sampling-based sketch) DP faces the following issue: The output contains (raw) input points, rendering it blatantly non-private. To overcome this challenge, we do not return the set S directly. Instead, we maintain another set R, which serves as a proxy for S but is DP, and use the distance dist(xt , R) instead of dist(xt , S) in each step. Our main observation is that the analysis of the Meyerson’s sketch is quite flexible: as long as R contains a “representative point” in every “dense ball” of S, it is already sufficient to obtain a bi-criteria approximation (with some small additive error) while still ensuring that S remains not “too large”. We formulate this requirement for the proxy set R as the dense ball problem (Definition 7) and show that known algorithms from the literature [Nissim et al., 2016, Nissim and Stemmer, 2018, Ghazi et al., 2020] can be adapted to solve this problem privately. With this formulation, we then compute R by running a DP dense ball algorithm on S. However, doing so at every time step t ∈ [n] would mean we need to apply the DP composition theorem on the privacy budget across all the steps, resulting in excessive error (that is polynomial in n). To overcome this, we observe that since S remains small, it suffices to invoke the DP dense ball algorithm only when S is updated. However, we cannot naively perform this check since S contains sensitive data; hence, we use the continual counting mechanism [Dwork et al., 2010, Chan et al., 2011] to provide a DP estimate of |S| after every time step. We then invoke the DP dense ball algorithm on S only when the (privately estimated) size of S is sufficiently larger than what it was when the DP dense ball was last invoked. This concludes our high-level technical overview. Sampling is the most popular method for finding a (semi-)coreset for (non-private) clustering 4

problems and beyond (e.g., Chen [2009], Feldman and Langberg [2011], Feldman et al. [2020], Cohen-Addad et al. [2021]). We believe our work is the first to naturally integrate sampling-based algorithms with DP, and hope that our techniques will be useful for future research on this topic.

2

Preliminaries

For any metric space M = (U, dist), let B(u, r) denote the ball of radius r centered at u, i.e., B(u, r) := {u′ ∈ U | dist(u, u′ ) ≤ r}. For any S ⊆ U , let dist(u, S) = inf u′ ∈S dist(u, u′ ). Throughout this work, we assume that we work with the Euclidean space2 with unit diameter3 .
Assumption 3. M is the Euclidean space in Rd with U = B 0, 21 . A stream (of points) is a sequence X = (x1 , . . . , xn ), where each xt belongs to U ∪ {⊥}. Here ⊥ should be interpreted as “no point”; for convenience, we abuse the notation and write dist(⊥, S) = 0 for any set S ⊆ U . For every t ∈ [n], we write X≤t to denote the multiset {xi | i ∈ [t], xi ̸=⊥}. We also define a multiset stream S Y = (y1 , . . . , yn ), where each yi is a multiset of U . Again, we write Y≤t to denote the multiset i∈[t] yi . The size of Y is |Y≤n |. An online algorithm A is an algorithm that receives the points in the stream X = (x1 , . . . , xn ) one point per time step, and, immediately after receiving xt at time step t, it must output ot . The final output released over the execution is A(X ) = (o1 , . . . , on ).

2.1

(Online) (k, p)-Clustering

Static Clustering. For a given multiset XP= {x1 , . . . , xn } ⊆ U of input points, the cost for a set C ⊆ U of centers is given by costpX (C) := i∈[n] dist(xi , C)p , where p ≥ 1 is a constant. In the (k, p)-clustering problem, the goal is to find a set C of k centers that minimizes costpX (C). It will be p convenient to define the optimum as optk,p X := minC∈(U ) costX (C). k

Online Clustering. For a given stream X = (x1 , . . . , xn ), a multiset stream C = (C1 , . . . , Cn ) is an (α, β)-approximation if costpX≤t (Ct ) ≤ α · optk,p X≤t + β

∀t ∈ [n].

An online (k, p)-clustering algorithm takes in an input stream X = (x1 , . . . , xn ) and outputs a multiset stream C = (C1 , . . . , Cn ) such that |Ct | = k for all t ∈ [n]. We say that it is an (α, β)approximation algorithm for online k-clustering if for every input stream, the output stream of the algorithm is an (α, β)-approximation (with probability 1 − γ). Prefix-Approximation. For our Meyerson’s sketch construction, it will be helpful to define the following notion. We say that a multiset stream Y = (y1 , . . . , yn ) is an (α, β)-prefix-approximation (w.r.t. (k, p)-clustering) of a stream X = (x1 , . . . , xn ) if X dist(xt , Y≤t )p ≤ α · optk,p X≤n + β. t∈[n] 2

Our DP Meyerson’s sketch (Algorithm 2) works for any metric space as long as there is an efficient DP dense ball algorithm for that space. However, we are only aware of existing work for the Euclidean space. 3 The bounded diameter assumption is necessary to obtain finite additive error [Nissim et al., 2016]. By scaling, our algorithm works for any diameter bound ∆, incurring a multiplicative factor of ∆p in the additive error.

5

Note that prefix-approximation is stronger than requiring Y≤n to be an (α, β)-approximation of X≤n , since prefix-approximation computes the cost using dist(xt , Y≤t ). In other words, we only allow xt to be connected to the point closest to it only up until that point in the stream (or, equivalently, the points in yt+1 , . . . , yn cannot be used). On the other hand, we do not restrict the size of Y (which will be stated explicitly in the theorem statements, e.g., Theorem 31). 2.1.1

Semi-Coreset

Next, we recall the definition of a semi-coreset [Epasto et al., 2026]. Unlike a standard coreset [HarPeled and Mazumdar, 2004], which provides a purely multiplicative approximation, a semi-coreset allows additional additive error terms. Definition 4 (Semi-Coreset [Epasto et
al., 2026]). A multiset X̃ is a (κ, η1 , η2 )-semi-coreset for (k, p)-clustering of X if, for all C ∈ Uk , we have p k,p 1 κ · costX (C) − η1 · optX − η2

≤ costpX̃ (C) ≤ κ · costpX (C) + η2 .

When k, p are clear from context, we often drop them from the notation for brevity. We say that a multiset stream X̃ = (x̃1 , . . . , x̃n ) is a (κ, η1 , η2 )-semi-coreset for another multiset stream X = (x1 , . . . , xn ) if X̃≤t is a (κ, η1 , η2 )-semi-coreset of X≤t for all t ∈ [n]. While the semi-coreset definition is more relaxed than the original coreset definition, it still maintains the most crucial property of coreset: Any good approximation for the semi-coreset is also a good approximation for the original dataset. This is stated more precisely below4 . Lemma 5 (Approximation from Semi-Coreset). Let X be a multiset of points and let X̃ be a
U (κ, η1 , η2 )-semi-coreset for X. If a set C ∈ k of centers is an (α, β)-approximation for X̃, then C is an (α′ , β ′ )-approximation for X, where α′ = ακ2 + η1 κ and β ′ = κ(α + 1)η2 + κβ.

2.2

Consistent Clustering

For an online (k,P p)-clustering algorithm, we say that an output stream C = (C1 , . . . , Cn ) of centers is m-consistent if t∈[n] |Ct ∖ Ct−1 | ≤ m, where m = m(n). We say that the algorithm is m-consistent if its output is always m-consistent. We use the following result by Fichtenberger et al. [2021], which yields a nearly optimal consistency bound in the non-private setting. Theorem 6 (Consistent k-Clustering with Constant Additive Error [Fichtenberger et al., 2021]). There is an online (k, p)-clustering (k · polylog (nd))-consistent algorithm whose output is an (O(1), O(1))approximation with high probability. Moreover, its time and space complexity is polynomial in the number of distinct points in the input stream and the number of dimensions d. We remark that the above result is slightly different than the one originally stated by Fichtenberger et al. [2021], whose bound depends on the “aspect ratio” of the metric space. However, there is a simple reduction between the two versions. See § A.2 for more details.

2.3

Dense Balls

As mentioned in § 1.2, a central problem in our algorithm is the dense ball problem, which is parameterized by rmin , the smallest target radius, and τ , the target number of points per ball. The input to the problem is a multiset S of points and the output is another multiset O. (Let 𭟋 = 3 be a factor that is fixed throughout.) The problem is formalized as follows. 4

Missing proofs in this section (including Lemma 5) and additional preliminaries can be found in Appendix A.

6

Definition 7 (Dense Ball). We say that an algorithm solves the (rmin , τ )-dense ball (with probability 1 − γ) if the following coverage constraint holds for any input multiset S of at most N points (with probability 1 − γ): dist (u, O) ≤ 𭟋 · r for all u ∈ U, r ≥ rmin such that |S ∩ B(u, r)| ≥ τ . Moreover, we say that the algorithm has size blow-up Υ with size capacity N if, for any input S of size at most N , the output O (always) satisfies |O| ≤ Υ · Nτ .

2.4

DP and Continual Counting

We quickly recall the definition of DP. For online clustering algorithms, two input streams X = (x1 , . . . , xn ), X ′ = (x′1 , . . . , x′n ) are (add-remove) neighbors 5 iff there exists i∗ ∈ [n] such that xi = x′i for all i = ̸ i∗ , and ⊥∈ {xi∗ , x′i∗ }. In words, one stream can be obtained from the other by changing a single point to ⊥. Definition 8 (Differential Privacy (DP) [Dwork et al., 2006a,b]). An online algorithm A that takes in a stream is said to be (ε, δ)-DP if, for all sets S of possible outputs and all pairs X, X ′ of neighboring input streams, it holds that Pr[A(X) ∈ S] ≤ eε · Pr[A(X ′ ) ∈ S] + δ. The case δ = 0 is known as pure-DP (written as ε-DP) and δ > 0 is known as approximate-DP. Throughout this work, we will assume that ε ∈ (0, 1) and δ ∈ (0, 1/2). We remark that the above model is the so-called non-adaptive (aka oblivious) model where the adversary fixes the neighboring input streams at the start of the algorithm. Our privacy proof however works even with the stronger adaptive (aka adversarial ) model where the adversary may choose to adapt the streams based on the outputs so far. Due to the extra notations required, we defer the formal definition of this adaptive model to the appendix. However, we stress that our utility proof assumes the oblivious model, and it remains an interesting question to extend the utility guarantees to the adversarial setting. (See § 5 for more discussion.) Continual Counting. In DP continual counting [Dwork et al., 2010, Chan et al., 2011], P the input stream is Y = (y1 , . . . , yn ) ∈ {0, 1}n . The goal is to output a private estimate et of t′ ∈[t] yt′ after P receiving yt . We say that the estimate is α-accurate if et − t′ ∈[t] yt′ ≤ α for all t ∈ [n]

3

Private Semi-Coreset Construction

Our main DP online semi-coreset construction (a formal version of Theorem 2) is stated below. Theorem 9 (DP Online Semi-Coreset). There is an online (ε, δ)-DP algorithm whose output is an (O(1), O(1), β)-semi-coreset of the input with probability 1 − γ, and the algorithm runs in time
Õ ndk 2 · log(1/γ) + ΛO(1) and uses space ΛO(1) where  3   • β = O d·kε · polylog nd and Λ = kd log(n/γ) for pure-DP. εγ ε • β=O

√

d·k2.5 · polylog ε



nd εδγ



and Λ =

kd log



ε

n γδ



for approximate-DP.

Note that one may consider the substitution neighbors, in which we can change xi∗ to any other point x′i∗ (not necessarily ⊥). By standard group privacy, our algorithm also applies in this setting. 5

7

Algorithm 2 Private Meyerson’s Sketch: AMeyerson (optest , Ψ) Require: Stream X = (x1 , . . . , xn ) Parameters: Target sketch size Ψ; Dense ball algorithm Adense (τ, Ψ, Υ) with threshold τ , size capacity Ψ · τ and size blow-up Υ; Continual counting algorithm Acount ; Estimated optimum optest 1: (R0 , S0 ) ← ({0}, ∅) 2: j = 1 {Counter for when to call Adense } 3: for t = 1, . . . , n do 4: {Do the following upon receiving xt }o n 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:

τ kL λt ← min 1, opt · dist(xt , R≤t−1 )p est St ← St−1 Sample Zt ∼ Ber(λt ) if Zt = 1 and |St | < Ψ · τ then St ← St ∪ {xt } Feed Zt to Acount and let et be the output if et ≥ j · τ and j ≤ Ψ then Rt ← Adense (St ) j ←j+1 else Rt ← ∅ Output Rt

3.1

From Dense Ball to Prefix-Approximation: Private Meyerson’s Sketch

5:

{Probability of adding xt to St } {Should xt be added to St ?}

The main ingredient for Theorem 9 is a private version of Meyerson’s sketch (§ 1.2). As in the non-private version, we maintain a set St of sampled input points, but instead of using these directly we periodically feed them to the DP dense ball algorithm to get Rt , whichSwe actually output. For notational convenience, let R0 = {0} contain the origin, and write R≤t = ti=0 Ri to include R0 as well. Moreover, we use the convention dist(⊥, R≤t ) = 0 so that xt =⊥ is never included in the set St .  1/p l  m 1 Recall that optest is a guess of the optimum value. Let rmin := optnest and L := log2 rmin . Algorithm 2 follows the outline from § 1.2 except for additional checks to ensure that the size of St and the number of calls to the DP dense ball algorithm are bounded. A generic version of the approximation guarantee of Algorithm 2 is given below. Lemma 10 (Prefix-Approximation Guarantee). Assume that • Adense (τ, Ψ, Υ) solves (rmin , τ )-dense ball and has size blow-up Υ with size capacity Ψ · τ . • Acount solves continual counting with accuracy τ /2. !! k,p • Ψ≥D·

kL ·

optX

1 + opt ≤n est

for some sufficiently large constant D.

Then, the output stream (R1 , . . . , Rn ) is an (O(1), O (optest + τ kL))-prefix-approximation of (x1 , . . . , xn ) with probability 1/2. Furthermore, the output stream has size |R≤n | ≤ Ψ2 · Υ. Proof. The size bound immediately follows due to the checks j ≤ Ψ on line 11, |St | ≤ Ψ · τ on line 8 and the size blow-up guarantee of Adense . Next, we will prove the prefix-approximation claim. To do this, it will be more convenient to analyze a modified version of Algorithm 2, denoted Algorithm 2′ , removing the checks that |St | < Ψ · τ on line 8 and that j ≤ Ψ on line 11. For Algorithm 2′ , we will then show the following: hP i   p ≤ O optk,p + opt E dist(x , R ) + τ kL , (1) t ≤t−1 est t∈[n] X≤n 8

(2)

E [|S≤n |] ≤ Ψ·τ 8 .

Before we prove these, we show how they complete our main proof. By Markov’s inequality and a union bound, (1), (2) imply that, w.p. 3/4, both the prefix-approximation guarantee and |St | ≤ Ψ · τ holds in Algorithm 2′ . When the latter holds (and since Acount is (τ /2)-accurate), both checks on lines 8 and 11 in Algorithm 2 pass; this means that Algorithm 2 produces the same output (R1 , . . . , Rt ) as Algorithm 2′ . Thus, the prefix-approximation guarantee holds with probability 3/4 for Algorithm 2. To prove (1) and (2), let C ∗ = {c∗1 , . . . , c∗k } denote the optimal centers such that costpX≤n (C ∗ ) = ∗ optk,p X≤n . For each i ∈ [k], let Pi = {t ∈ [n] | xt is closest to ci , ties broken arbitrarily }. For every ℓ = 1, . . . , L, define the partitions ( {t ∈ Pi | dist(xt , c∗i ) ≤ 2 · rmin } if ℓ = 1, Pi,ℓ := ℓ−1 ∗ ℓ {t ∈ Pi | 2 · rmin ≤ dist(xt , ci ) ≤ 2 · rmin } otherwise.

S We note that ℓ∈[L] Pi,ℓ = Pi , since the diameter of M is at most one. Consider each Pi,ℓ . Referring back to Algorithm 2, recall that Zt is the outcome of the coin, determined by λt , that decides if xt should be added to St . For every j ∈ Pi,ℓ , we define Z<j := P ′ ′ j ∈Pi,ℓ Zj , i.e., the number of elements in this partition that has been added until before time step j ′ <j P j. Similarly, we define λ<j := j ′ ∈Pi,ℓ λj ′ . j ′ <j

Proof of (1). Let us define additional notation: ( et = Zt if Z<t < 3τ, Z 0 otherwise.

( e t = λt λ 0

if Z<t < 3τ, otherwise.

et ), then |St−1 ∩ B(c∗ , 2ℓ · rmin )| ≥ 3τ . Consider any t ∈ Pi,ℓ . Observe that, if Z<t ≥ 3τ (i.e., λt ̸= λ i Let t′ < t be the last time step Adense is called before time step t. Due to the guarantee of Acount , we must have |St ∖ St′ | ≤ τ + 2 · (τ /2) = 2τ . This implies that Z<t′ ≥ τ . By the guarantee of Adense , there must be a point f ∈ R≤t−1 such that dist(c∗i , f ) ≤ O(2ℓ · rmin ). This implies dist(xt , R≤t−1 ) ≤ dist(xt , c∗i ) + dist(c∗i , f ) ≤ dist(xt , c∗i ) + O(2ℓ · rmin ) ≤ O(dist(xt , c∗i ) + 1[ℓ = 1] · rmin ). Meanwhile, by definition of λt and since the diameter of M is at most one, we also have that   est dist(xt , R≤t−1 )p ≤ λt · 1 + opt . τ kL et and (4) when λt = λ et , we have Using (3) when λt ̸= λ    optest p p ∗ p e . dist(xt , R≤t−1 ) ≤ O dist(xt , ci ) + 1[ℓ = 1] · rmin + λt · 1 + τ kL Taking expectation, we thus get   h i  optest p ∗ p e E [dist(xt , R≤t−1 ) ] ≤ O dist(xt , ci ) + 1[ℓ = 1] · rmin + E Zt · 1 + . τ kL p

9

(3)

(4)

Summing over all t ∈ [n], we get  hP i  hP i  optest p ≤ O optk,p + n · r p e . E t∈[n] dist(xt , R≤t−1 ) t∈[n] Zt · 1 + τ kL min + E X≤n Finally, by definition,

t∈Pi,ℓ Zt ≤ 3τ regardless of the randomness of the algorithm. Summing over

P

e

i ∈ [k] and ℓ ∈ [L] gives t∈[n] Zet ≤ 3τ kL. Plugging this into the above gives hP i   p ≤ O optk,p + n · r p E dist(x , R ) + τ kL + opt t ≤t−1 est t∈[n] min X≤n   ≤ O optk,p X≤n + optest + τ kL , P

where the last inequality is due to our choice of rmin . This proves (1). et ̸= Zt . In this case, we have Proof of (2). First, recall that (3) holds if Z<t ≥ 3τ , i.e., Z
! h i ∗ )p + 1[ℓ = 1] · r p (3) τ kL · dist(x , c t i min et = E [Zt ] = λt ≤ O E Zt − Z . optest Thus, the expected total number of points sampled from Pi,ℓ is hP i hP i h i et + E P et ) E Z = E Z (Z − Z t t t∈Pi,ℓ t∈Pi,ℓ t∈Pi,ℓ 
 X τ kL · dist(xt , c∗i )p + 1[ℓ = 1] · rp min  ≤ 3τ + O  , optest t∈Pi,ℓ

P where in the first inequality we again use the fact that t∈Pi,ℓ Zet ≤ 3τ by definition. Summing this up over all i ∈ [k] and ℓ ∈ [L], we get      p k,p + n · r τ kL · optk,p τ kL · opt min X≤n X≤n  ≤ O τ kL + , E [|S≤n |] ≤ O τ kL + optest optest where the second inequality is due to our choice of rmin . Finally, the RHS is at most Ψ·τ 8 for sufficiently large constant D. Thus, (2) holds as desired. The privacy and efficiency analysis of the sketch is deferred to Appendix B.1. Finally, turning such a prefix-approximation into a coreset can be easily done via snapping each point xt to the closest center in the output so far. Again, we need use a continual counting algorithm to compute the weights in DP manner. This is a standard technique that has been applied before in the DP setting (e.g., Ghazi et al. [2020]). The full argument is deferred to Appendix C.

4

From DP Semi-Coreset to DP Consistent Clustering

As mentioned earlier, we can simply invoke the non-private online consistent clustering algorithm (Theorem 6) on the private semi-coreset (Theorem 9) to obtain the desired result. Corollary 11. There is an (ε, δ)-DP online (k, p)-clustering (k · polylog (nd))-consistent algorithm whose output is an (O(1), β)-approximation with high probability, and the algorithm runs in time
2 O(1) Õ ndk + Λ and uses space ΛO(1) where 10

• β=O • β=O



nd ε



n and Λ = kd log for pure-DP. ε

d·k2.5 · polylog ε

nd εδ



d·k3 ε · polylog

√

and Λ = kd log(n/δ) for approximate-DP. ε

Proof. We run the (ε, δ)-DP semi-coreset algorithm from Theorem 9 on input stream X to get a multiset stream X̃ = (x̃1 , . . . , x̃n ). We then feed the points in x̃1 , . . . , x̃n to the online consistent (k, p)-clustering algorithm in Theorem 6; the final output Ct is the output from this algorithm after feeding it x̃t . The consistency claim and time/space bounds immediately follow. The privacy guarantee holds because of the post-processing property of DP, as we only post-process (x̃1 , . . . , x̃n ). Finally, since Ct is an (O(1), O(1))-approximation of X̃≤t and X̃≤t is an (O(1), O(1), β)-semicoreset of X≤t , Lemma 5 implies that Ct is also an (O(1), O(β))-approximation of X≤t .

5

Conclusion and Open Questions

In this work, we presented a generic reduction that transforms a sensitive data stream into a privatized semi-coreset stream. By allowing any non-private online clustering algorithm to be executed as a post-processing step, our framework yields the first DP online clustering algorithm that achieves a nearly optimal consistency guarantee, alongside a constant approximation ratio and a nearly optimal additive error in terms of the dimension. Despite these advances, several open questions and directions for future work remain: • Practicality: While our private adaptation of Meyerson’s sketch (Algorithm 2) is straightforward to implement and practical, the underlying DP dense ball algorithms it relies upon are theoretical. To our knowledge, there are currently no practical implementations of these algorithms, which poses a barrier to real-world deployment. • Error Dependency on k: While our additive error dependency on dimension d is nearly optimal, the dependency on k leaves room for improvement. In our private Meyerson’s sketch (Algorithm 2), this sub-optimality is partly due to DP composition across all runs of the dense ball algorithm; it might be possible to improve on this by deriving an “online” version of DP dense ball. More generally, while efficient DP algorithms with tight additive errors in terms of k are known in the offline setting [Nguyen et al., 2021, Ghazi et al., 2024], none is known for the online setting. • Coreset with (1 ± o(1))-Multiplicative Error: Our online construction (and that of Epasto et al. [2026]) only yields a semi-coreset, which naturally leaves the question of whether an online DP coreset construction (i.e., obtaining η1 = 0 in Definition 4) is possible. Another interesting question is whether one can reduce the multiplicative error κ to 1 + o(1). We remark that the latter question is still open even in the offline setting, although there is some evidence that this might be hard [Ghazi et al., 2026]. • Adversarial Streaming Models: While our privacy analysis holds for the adversarial setting (where the adversary sees outputs up to time i − 1 before selecting xi ), our current utility analysis assumes an oblivious data stream. There are several challenges. For instance, it has not yet been established whether the non-private Meyerson’s sketch maintains its utility guarantee in the adversarial model. In fact, we are not aware of any analysis of the (non-private) consistent k-means/median clustering in this model. • Running Time Optimization: Although our algorithm achieves n1+o(1) time complexity over the entire stream for k, d ≤ no(1) , the running time could be optimized further, e.g., by employing approximate nearest neighbor data structures. Furthermore, it also seems plausible that the Λ term in our main theorem (Theorem 9) can be optimized further. Currently, the 11

polynomial dependency on k, d through Λ is due to the use of the 1-Cluster algorithm by Ghazi et al. [2020] as a blackbox (see Appendix A.4). It remains an interesting question whether this can be sped up further, e.g., to nearly linear time in k. AI Disclosure. While all the main algorithms and proofs in this work were discovered by the authors, we used AI, including Gemini (Google) and Claude (Anthropic), to assist in preparing this paper. In particular, we used AI to flesh out proof sketches to first drafts of full proofs, and to help with drafting the introduction and conclusion. These drafts are heavily edited and verified by the authors, and we take full responsibility for all claims in this work.

References John M. Abowd. The U.S. Census Bureau adopts differential privacy. In KDD, pages 6353–6356, 2018. Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. ACM, 51(4):606–635, 2004. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. SIAM J. Comput., 49(4), 2020. Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of Euclidean k-means. In SoCG, pages 754–767, 2015. Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differentially private clustering in high-dimensional Euclidean spaces. In ICML, pages 322–331, 2017. Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the SuLQ framework. In PODS, pages 128–138, 2005. T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011. T.-H. Hubert Chan, Shaofeng H.-C. Jiang, Tianyi Wu, and Mengshi Zhao. Online clustering with nearly optimal consistency. In ICLR, 2025. Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. In ICML, pages 1441–1451, 2021. Moses Charikar, Liadan O’Callaghan, and Rina Panigrahy. Better streaming algorithms for clustering problems. In STOC, pages 30–39, 2003. Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SICOMP, 39(3):923–947, 2009. Vincent Cohen-Addad and Karthik C. S. Inapproximability of clustering in Lp metrics. In FOCS, pages 519–539, 2019. Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In STOC, pages 169–182, 2021. Damien Desfontaines and Balázs Pejó. SoK: Differential privacies. PETS, 2020(2):288–313, 2020. 12

Max Dupré la Tour, Monika Henzinger, and David Saulpic. Making old things new: A unified algorithm for differentially private clustering. In ICML, 2024. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486–503, 2006a. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265–284, 2006b. Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In STOC, pages 715–724, 2010. Alessandro Epasto, Tamalika Mukherjee, and Peilin Zhong. Differentially private clustering in data streams. In AISTATS, 2026. Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In CCS, pages 1054–1067, 2014. Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In STOC, pages 569–578, 2011. Dan Feldman, Chongyuan Xiang, Ruihao Zhu, and Daniela Rus. Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks. In IPSN, pages 3–16, 2017. Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, PCA, and projective clustering. SIAM J. Comput., 49(3):601–657, 2020. Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Consistent kclustering for general metrics. In SODA, pages 2660–2678, 2021. Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS for k-means in doubling metrics. SIAM J. Comput., 48(2):452–480, 2019. Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In NeurIPS, 2020. Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, and Nachiappan Valliappan. Differentially private heatmaps. In AAAI, pages 7696–7704, 2023. Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Adam Sealfon. Individualized privacy accounting via subsampling with applications in combinatorial optimization. In ICML, 2024. Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, and Pasin Manurangsi. Computational hardness of private coreset. In FORC, 2026. Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan. Clustering data streams. In FOCS, pages 359–366, 2000. Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. Consistent k-median: Simpler, better and robust. In AISTATS, pages 1135–1143, 2021.

13

Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In SODA, pages 1106–1125, 2010. Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In STOC, pages 291–300, 2004. Monika Henzinger, Roodabeh Safavi, and Salil P. Vadhan. Concurrent composition for differentially private continual mechanisms. SIGMOD, 4(2):99:1–99:26, 2026. Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In PODS, pages 395–408, 2018. Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of differential privacy under continual observation. In ICML, pages 14654–14678, 2023. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3):89–112, 2004. Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In ICML, pages 1975–1984, 2017. Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Inf. Process. Lett., 120:40–43, 2017. Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of JohnsonLindenstrauss transform for k-means and k-medians clustering. SIAM J. Comput., 52:269–297, 2019. Jirí Matousek. On approximate geometric k-clustering. Discret. Comput. Geom., 24(1):61–84, 2000. Adam Meyerson. Online facility location. In FOCS, pages 426–431, 2001. Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. De l’Imprimerie Royale, 1781. Huy L. Nguyen, Anamay Chaturvedi, and Eric Z. Xu. Differentially private k-means via exponential mechanism and max cover. In AAAI, pages 9101–9108, 2021. Kobbi Nissim and Uri Stemmer. Clustering algorithms for the centralized and local models. In ALT, pages 619–653, 2018. Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Locating a small cluster privately. In PODS, pages 413–427, 2016. Naty Peter, Eliad Tsfadia, and Jonathan R. Ullman. Smooth lower bounds for differentially private algorithms via padding-and-permuting fingerprinting codes. In COLT, pages 4207–4239, 2024. Uri Stemmer. Locally private k -means clustering. In SODA, pages 548–559, 2020. Abhradeep Guha Thakurta and Adam D. Smith. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In NeurIPS, 2013.

14

A

Additional Background and Missing Proofs from § 2

When we state the running time and space complexity of an algorithm, we always assume that each coordinate of xi fits in a single word of memory and arithmetic operations on them take constant time. This, in particular, means that reading each xi takes O(d) time and storing each xi uses O(d) space. Approximate Triangle Inequality. The following “approximate triangle inequality” for the pth power will be useful in our proofs. Lemma 12 (Approximate Triangle Inequality, [Makarychev et al., 2019]). For any p ≥ 1 and ξ ∈ (0, 1], there exists a constant ϑp,ξ > 0 that depends only on p and ξ such that for any a, b, c in a metric space, dist(a, b)p ≤ (1 + ξ) · dist(a, c)p + ϑp,ξ · dist(c, b)p .

A.1

Properties of Semi-Coreset

A.1.1

Monge’s Optimal Transport and Semi-Coreset

We use a generalization of the optimal transport [Monge, 1781], as defined in [Chang et al., 2021]. Definition 13 (Generalized Transport Cost, [Chang et al., 2021]). Let X and X̃ be weighted point sets over a metric space U . For a mapping Ψ : U → U , the generalized p-transport cost is defined as: X X mt(Ψ, X, X̃) := wX (x) · dist(x, Ψ(x))p + |wX (Ψ−1 (y)) − wX̃ (y)|, (5) x∈U

y∈U

where we use the notation wX (x) to denote the weight of point x in X and wX (S) =

P

x∈S wX (x).

In other words, instead of allowing just the distance error (first term), we also allow weight mismatch (second term). This make it convenient for DP, which naturally produces noisy weights. In Chang et al. [2021], it was shown that if two sets have “small” optimal transport cost, then one is a good coreset of the other. However, the “small” cost requirement in Chang et al. [2021] is restrictive: It requires mt(Ψ, X, X̃) ≤ α · optk,p X + β for α < 1. On the other hand, our proof will use α > 1. Nevertheless, we show that the statement is still true for α > 1, albeit with semi-coreset instead of coreset. This is formalized in the lemma below, which will be handy in our proofs. Lemma 14 (Transport =⇒ Semi-Coreset). Assume that all points in U have a pairwise distance bounded by 1 (i.e., diameter ≤ 1). Let X and X̃ be weighted point sets over U . If there exists a mapping Ψ : X → U such that mt(Ψ, X, X̃) ≤ α · optk,p X + β, then X̃ is a (κ, η1 , η2 )-semi-coreset for X with parameters κ = O(1 + α), η1 = O(α), and η2 = O(β).
Proof. Consider any set C ∈ Uk of k centers. For any point y ∈ U , since the diameter of the metric space is bounded by 1, we have dist(y, C)p ≤ 1. By applying the approximate triangle inequality (Lemma 12) with ξ = 1, we can bound the cost of C on the estimated set X̃: costpX̃ (C) X = wX̃ (y) · dist(y, C)p y∈U

15

≤

X

wX (Ψ−1 (y)) · dist(y, C)p +

y∈U

≤

X

≤

|wX̃ (y) − wX (Ψ−1 (y))| · dist(y, C)p

y∈U p

wX (x) · dist(Ψ(x), C) +

x∈U

X

X

X

|wX̃ (y) − wX (Ψ−1 (y))|

y∈U p

wX (x) · (2 · dist(x, C) + ϑp,1 · dist(x, Ψ(x))p ) +

x∈U

X

|wX̃ (y) − wX (Ψ−1 (y))|

y∈U

≤ 2costpX (C) + max(ϑp,1 , 1) · mt(Ψ, X, X̃). k,p p Using the bounds mt(Ψ, X, X̃) ≤ α · optk,p X + β and optX ≤ costX (C), we obtain the upper bound:   costpX̃ (C) ≤ 2costpX (C) + max(ϑp,1 , 1) α · optk,p + β X

≤ (2 + max(ϑp,1 , 1) · α) costpX (C) + max(ϑp,1 , 1)β. A symmetric argument upper bounds the true cost:   costpX (C) ≤ 2costpX̃ (C) + max(ϑp,1 , 1) α · optk,p + β . X Rearranging this to isolate costpX̃ (C) yields the lower bound: max(ϑp,1 , 1) · α max(ϑp,1 , 1) 1 costpX̃ (C) ≥ costpX (C) − optk,p · β. X − 2 2 2 max(ϑ

,1)·α

p,1 By defining κ = max(2 + max(ϑp,1 , 1) · α, 2) = O(1 + α), η1 = = O(α), and η2 = 2 max(ϑp,1 , 1) · β = O(β), both the upper and lower bounds of the semi-coreset definition are satisfied.

A.1.2

Proof of Lemma 5

∗ denote the optimal set of k centers for X such that costp (C ∗ ) = optk,p . Proof of Lemma 5. Let CX X X X ∗ , we have the upper bound By the definition of a (κ, η1 , η2 )-semi-coreset applied to CX ∗ ∗ costpX̃ (CX ) ≤ κ · costpX (CX ) + η2 = κ · optk,p X + η2 .

Since optk,p ≤ costpX̃ (C) for any C ∈ X̃

U k

∗ ). By assumption, , it follows that optk,p ≤ costpX̃ (CX X̃

the set C of centers is an (α, β)-approximation for X̃. Therefore, costpX̃ (C) ≤ α · optk,p +β X̃

∗ ≤ α · costpX̃ (CX )+β   ≤ α · κ · optk,p + η +β 2 X

= ακ · optk,p X + αη2 + β.

(6)

Now, we apply the lower bound property of the (κ, η1 , η2 )-semi-coreset to the centers C: 1 p · costpX (C) − η1 · optk,p X − η2 ≤ costX̃ (C). κ

16

(7)

Substituting the upper bound from (6) into (7), we obtain: 1 k,p · costpX (C) − η1 · optk,p X − η2 ≤ ακ · optX + αη2 + β. κ Rearranging to isolate costpX (C) yields: 1 · costpX (C) ≤ (ακ + η1 ) · optk,p X + (α + 1)η2 + β κ costpX (C) ≤ (ακ2 + η1 κ) · optk,p X + κ(α + 1)η2 + κβ. This completes the proof.

A.2

Consistent k-Clustering via Grid Snapping: Proof of Theorem 6

As mentioned in § 2.2, the original consistency bound in Fichtenberger et al. [2021] depends on the aspect ratio of the metric space, which is defined as the ratio between the largest distance and the smallest non-zero distance. Their result can be stated as follows: Theorem 15 (Fichtenberger et al. [2021]). Let M = (U, d) be any metric space with aspect ratio ∆. There is an online (k, p)-clustering (k · polylog (n∆))-consistent algorithm for metric space M whose output is an (O(1), 0)-approximation with high probability. Moreover, the algorithm has time and space complexity at most polynomial in the number of distinct points in the input stream and the time needed to compute distances between points. To bypass the aspect ratio assumption in consistent clustering, we transform the input stream by snapping points to a fine grid. We show that this transformation controls the aspect ratio of the active metric space while incurring only a constant additive error, which we can formalize via the generalized transport cost. Definition 16 (Grid-Snapped Stream). Let X = (x1 , . . . , xn ) be a stream of points in Rd with a 1 metric diameter at most 1. Define the grid G = ( nd Z)d . Let the snapped stream be X̂ = (x̂1 , . . . , x̂n ), 1 where each x̂t is obtained by rounding each coordinate of xt to a multiple of nd in such a way that its absolute value does not increase. Lemma 17 (Snapped Stream as a Semi-Coreset). For any t ∈ [n], the snapped multiset X̂≤t is a (κ, 0, η2 )-semi-coreset for X≤t for the (k, p)-clustering objective, where κ = O(1) and η2 = O(1). Proof. Consider the natural mapping Ψ : X≤t → X̂≤t given by Ψ(xi ) = x̂i . Because the point weights match perfectly, the weight difference term in the generalized transport cost (5) is 0. 1 For the distance term in (5), rounding each coordinate to displaces a point by at most nd along any dimension. The ℓ2 displacement is therefore bounded by: s   √ 1 2 d 1 1 dist(xi , x̂i ) ≤ d = ≤ √ ≤ . nd nd n n d For the (k, p)-clustering objective, the generalized p-transport cost is: mt(Ψ, X≤t , X̂≤t ) =

t X

dist(xi , x̂i )p ≤ t ·

i=1

1 ≤ 1. n

By applying Lemma 14, X̂≤t is an (O(1), 0, O(1))-semi-coreset for X≤t . 17

We are now ready to prove Theorem 6. Proof of Theorem 6. Instead of clustering the original stream X, we maintain and cluster the gridsnapped stream X̂ as defined above (Definition 16). Since all points in X̂ are restricted to the grid 1 G = ( nd Z)d and the overall diameter is at most 1, the maximum distance between any two points in X̂ is 1. Conversely, the minimum non-zero distance between any two distinct grid points is at least 1 nd . Therefore, the aspect ratio ∆ of the active points in X̂ is strictly bounded by nd. We run the consistent k-clustering algorithm from Theorem 15 over the snapped stream X̂. Because ∆ ≤ nd, this guarantees a total consistency cost of k · polylog (n∆) ≤ k · polylog (nd). For the utility guarantee, Theorem 15 ensures that with high probability, for all t ∈ [n], Ct is an (O(1), 0)-approximation on the snapped points X̂≤t . By Lemma 17, X̂≤t is a (O(1), 0, O(1))-semicoreset for X≤t . Applying Lemma 5, we can thus conclude that Ct is an (O(1), O(1))-approximation for the original set X≤t , which concludes our proof.

A.3

Differential Privacy

As mentioned in § 2.4, our privacy proof holds in the stronger adaptive model as well. Here we follow terminologies from Jain et al. [2023], although similar models were considered even before (e.g. Thakurta and Smith [2013]). The adaptive setting can be defined using a game between the adversary and the algorithm as follows. Definition 18 (Adaptive continual release game). Let B be an adversary and b ∈ {0, 1}. The game Gameb (B, M) proceeds as follows. 1. For t = 1, . . . , n, given the transcript πt−1 = (o1 , . . . , ot−1 ), the adversary declares typet ∈ {regular, challenge}, where challenge is declared at most once over the whole game. • If typet = regular, B outputs a single xt , which is sent to M in both worlds. • If typet = challenge, set i∗ ← t; B outputs a pair (x0t , x1t ) with ⊥∈ {x0t , x1t }, and xbt is sent to M. 2. M releases ot , which is appended to the transcript. 3. The game outputs πn . Definition 19 (DP under adaptive inputs). M is (ε, δ)-DP in the adaptive continual release model if for every adversary B and every measurable set T of transcripts,     Pr Game0 (B, M) ∈ T ≤ eε Pr Game1 (B, M) ∈ T + δ. It is clear that Definition 19 is no weaker than that in Definition 8: For a fixed pair neighboring streams X = (x1 , . . . , xn ), X ′ = (x′1 , . . . , x′n ), the adaptive adversary can always simply set x0t = xt and x1t = x′t for all t ∈ [n] and recovers the non-adaptive guarantee. Henceforth, for online algorithms, we will always consider privacy in the stronger adaptive continual release model (Definition 19). For brevity, we will sometimes not state this explicitly. A.3.1

Tools from Differential Privacy

We next state two lemmas which will be helpful in the privacy proofs. First is the so-called “post-processing” property of DP, specialized to the adaptive continual release model below.

18

Lemma 20 (Online post-processing). Let M be (ε, δ)-DP in the adaptive continual release model, and let M′ be the online mechanism that runs M internally and, at step t, releases gt (πt ; σ), where πt = (o1 , . . . , ot ) is M’s transcript prefix, gt is a fixed function, and σ is randomness independent of the input. Then M′ is (ε, δ)-DP in the adaptive continual release model. We also need composition properties of DP. Since we employ multiple online DP subroutines which are interleaved, we require a “concurrent” version of DP composition, as stated below. Lemma 21 (Concurrent composition; Henzinger et al. [2026]). Let M1 , . . . , Mm be continual mechanisms run concurrently, where each Mi is (εi , δi )-DP in the adaptive model, with respect to a neighbor relation ∼i on its input streams. Consider an adversary that interacts with all m mechanisms concurrently, interleaving its interactions arbitrarily and choosing each input to each mechanism adaptively as a function of all outputs received so far from all mechanisms. Then the
P P ε , δ composition is -DP with respect to any pair of adaptive strategies whose induced input i i i i streams satisfy ∼i for every i. We also need a “parallel” composition theorem for continual mechanisms, in which the neighbor relation on the composed input is restricted so that the two worlds differ only in the inputs to a single mechanism. Under this restriction, the privacy loss does not grow with m. We state this for the pure-DP case, which is all we need. Lemma 22 (Parallel composition; Henzinger et al. [2026]). Consider the setting of Lemma 21, with the neighbor relation restricted as follows: the input streams induced by the two strategies are identical for all but one mechanism Mi∗ , and neighboring for Mi∗ . If ε1 = · · · = εm = ε′ and δ1 = · · · = δm = 0, then the composed mechanism is ε′ -DP with respect to this relation. A.3.2

Differentially Private Continual Counting

For continual counting, two input streams Y = (y1 , . . . , yn ) ∈ {0, 1}n and Y ′ = (y1′ , . . . , yn′ ) ∈ {0, 1}n are neighbors iff they differ on a single coordinate. P Throughout, we will assume that the estimates et of i∈[t] yi are monotone, i.e., e1 ≤ · · · ≤ en , and that they are integers. (If this does not hold, it can be easily achieved by taking ⌈maxi∈[t] ei ⌉ instead of et .) The seminal work of Dwork et al. [2010], Chan et al. [2011] gives a DP algorithm that is O(polylog (n))-accurate with high probability. This is stated more formally below. Theorem 23 (Dwork et al. [2010], Chan et al. [2011]).
There exists an ε-DP6 continual counting algorithm that, for any γ > 0, is O 1ε · log1.5 n · log(1/γ) -accurate with probability 1 − γ. The total running time of the algorithm is O(n log n) and its space complexity is O(log n).

A.4

Dense Ball Algorithm

For the dense ball problem (Definition 7), we consider two input datasets S, S ′ neighbors iff |S∆S ′ | ≤ 1, where ∆ denote the symmetric difference between the two sets. Our definition of the dense ball problem is closely related to the 1-Cluster and the densest ball problems previously studied in DP literature [Nissim et al., 2016, Nissim and Stemmer, 2018, Ghazi et al., 2020]. By repeatedly applying a known algorithm for this problem, it is simple to derive the following result for the dense ball problem. 6

Here the DP definition as in Definition 19 with 0 being treated as ⊥.

19

Theorem 24. Let N ∈ N and suppose that the input S has size at most N . Then, there exists an (ε, δ)-DP algorithm with time and space complexity (N d · log(1/rmin ))O(1) and size blow-up of O(1), which solves the (rmin , τ )-dense ball with probability 1 − γ where   
1/2 Nd · polylog • τ = O d·N for δ = 0, and, ε εrmin • τ =O



d·N 1/3 · polylog ε2



Nd εδrmin



for δ > 0.

Our construction builds upon the DP 1-Cluster algorithms of Ghazi et al. [2020]. We formally define the problem and recall their result below. Definition 25 (1-Cluster, [Nissim et al., 2016]). Given a multiset S of size at most N in a metric space, a target number of points τ , a minimum radius, and an approximation ratio α ≥ 1, the 1-Cluster problem asks to output a center c and a radius r such that the ball B(c, r) contains at least τ − t points from S (where t is the additive error), and r ≤ α · max{rmin , ropt }, where ropt is the minimum radius of a ball containing at least τ points in S. Theorem 26 (DP 1-Cluster, [Ghazi et al., 2020]). There exist (ε, δ)-DP algorithms for the 1-Cluster problem in the Euclidean space with approximation ratio α ∈ (1, 2) that succeed with probability 1 − β and have an additive error bounded by:    d for pure-DP (δ = 0). • t = O dε · polylog εrN min β • t=O

√

d ε · polylog



Nd εδrmin β



for approximate-DP (δ > 0).

The time and space complexities are bounded by (N d · log(1/rmin ))O(1) . We quickly note that, in the case of approximate-DP, the algorithm from [Ghazi et al., 2020] in fact has an even better dependency on rmin . However, we choose to state this coarser error bound since it does not effect our final guarantee anyway as we only choose rmin = n1 in the subsequent step. We formalize our procedure in Algorithm 3. The algorithm iteratively extracts dense balls from the dataset by repeatedly invoking the DP 1-Cluster subroutine. Algorithm 3 Dense Ball via Iterative 1-Cluster Require: Multiset S of size at most N , minimum target radius rmin , target points τ , privacy parameters (ε, δ), failure probability γ. 1: O ← ∅ 2: S1 ← S 3: K ← ⌈2N/τ ⌉ {Number of iterations} 4: Set per-run privacy parameters (ε′ , δ ′ ) based on composition over K total invocations. 5: for i = 1, . . . , K do 6: (ci , ri ) ← Result of running the 1-Cluster algorithm of (Theorem 26) on Si target τ , approximation ratio α = O(1), failure probability β = γ/K, and privacy (ε′ , δ ′ ). 7: O ← O ∪ {ci } 8: Si+1 ← Si ∖ B(ci , ri ) 9: return O Proof of Theorem 24. We analyze Algorithm 3 by establishing its privacy, accuracy (size bound and coverage), and matching the required parameter bounds for τ . 20

Privacy. Algorithm 3 invokes the base 1-Cluster algorithm a total of K times. We distribute the total privacy budget (ε, δ) across all K = O(N/τ ) invocations using composition theorems: • Pure-DP: By basic composition, setting ε′ = ε/K ensures that Algorithm 3 is ε-DP. • Approximate-DP: By advanced composition, to achieve overall (ε, δ)-DP, it is sufficient to set  
δ ′ = Θ Kδ and ε′ = Θ √ ε . K ln(1/δ)

Size Bound. The algorithm runs for exactly K steps, outputting exactly one center per step. Thus, the output set O has size |O| = K ≤ 4N/τ . This satisfies the size bound property with blow-up factor Υ = 4. Coverage. Let t denote the additive error of the 1-Cluster algorithm. As specified in more detail below, we will parameterize the noise such that t ≤ τ /2. Since each run of the 1-Cluster algorithm is successful with probability 1 − β, all the runs succeed with probability at least 1 − β · K = 1 − γ. Conditioned on this, we will show that the coverage constraint is satisfied. Suppose there exist u ∈ Rd , r ≥ rmin such that |S ∩ B(u, r)| ≥ τ . We must show that dist(u, O) ≤ 𭟋 · r. First, let us assume for contradiction that no removed ball B(ci , ri ) intersects B(u, r). If this were true, none of the points in S ∩ B(u, r) would ever be removed. Thus, at every step i, the remaining set Si would contain all ≥ τ points of S ∩ B(u, r). Because the algorithm succeeds at every step and t ≤ τ /2, each of the K steps removes at least τ /2 points from the dataset. Across K steps, the algorithm would remove K · (τ /2) = ⌈2N/τ ⌉ · (τ /2) ≥ N points. Since the total dataset has size at most N , this implies all points are eventually removed, contradicting the assumption that the points in B(u, r) remain untouched. Therefore, there must be at least one step where the removed ball B(ci , ri ) intersects B(u, r). Let j be the first such step. At the start of step j, none of the points in B(u, r) have been removed, meaning |Sj ∩ B(u, r)| ≥ τ . This implies that the optimal radius ropt for capturing τ points in Sj is bounded by r (i.e., ropt ≤ r). Since we ran 1-Cluster with approximation ratio α = O(1), the output radius guarantees rj ≤ α · max{rmin , ropt } ≤ α · r. Since B(cj , rj ) intersects B(u, r), let x be a point in their intersection. By the triangle inequality, we have: dist(u, cj ) ≤ dist(u, x) + dist(x, cj ) ≤ r + rj ≤ 3r. Since cj ∈ O, this proves the required coverage. Parameter Settings. To complete the proof, we select the parameters to ensure t ≤ τ /2. For Pure-DP: By Theorem 26, the additive error of 1-Cluster is t = O



d ε′ · polylog



Substituting ε′ = ε/K, we get:  t=O

dN · polylog ετ



Nd εrmin γ





1/2

Nd

ε′ rmin γ

Enforcing t ≤ τ /2 yields the requirement: 2

τ ≥Θ



dN · polylog ε



Nd εrmin γ

 ⇐⇒ τ ≥ Θ 21

dN ε

 · polylog

Nd εrmin γ

! .



.

  √ d For Approximate-DP: By Theorem 26, the additive error is t = O ε′d · polylog εδrNmin . γ     √ Substituting our advanced composition parameter ε′ = Θ √ ε =Θ √ ε τ , we get: K log(1/δ)

t=O

N log(1/δ)

√  ! dN Nd √ · polylog εδrmin γ ε τ

Enforcing t ≤ τ /2 yields the requirement: √ τ 3/2 ≥ Θ

dN polylog ε



Nd εδrmin γ

!

 ⇐⇒ τ ≥ Θ

dN ε2

1/3

 polylog

Nd εδrmin γ

! .

Time and Space Complexity. The 1-Cluster subroutine is called K ≤ N times. Each run takes (N d log(1/rmin ))O(1) time and space. Thus, the total time and space complexity is bounded by (N d log(1/rmin ))O(1) .

B

Missing Proofs from § 3.1

B.1

Private Meyerson’s Sketch: Privacy and Efficiency

In this section, we state generic bounds on the privacy and efficiency guarantees of our DP Meyerson’s sketch (Algorithm 2). Lemma 27 (Privacy). If Adense
is (εd , δd )-DP and Acount is (εc , δc )-DP, then Algorithm 2 is 2 · Ψ · εd + εc , 2 · e2εd · Ψ · δd + δc -DP. Proof. Fix an adversary B. Recall that we use i∗ to denote the challenge index. b which is exactly the same First, it will be more convenient to consider a modified algorithm A, as Algorithm 2, except it releases (et , Rt ) at each step
(instead of just Rt ). By Lemma 20, it suffice to prove that Ab is 2 · Ψ · εd + εc , 2 · e2εd · Ψ · δd + δc -DP. Moreover, in Algorithm 2, we write Zt ∼ Ber(λt ). For our purpose, it will be more transparent to instead think of this as setting Zt = 1[Ut ≤ λt ] where U = (U1 , . . . , Un ) is drawn i.i.d. uniform on [0, 1]. Let Abu denote Ab with U fixed to u. By the convexity of DP (see, e.g., Desfontaines and Pejó [2020]), it suffices to prove the bound for every fixed u. Fix u = (u1 , . . . , un ) and a transcript prefix πt−1 = ((e1 , R1 ), . . . , (et−1 , Rt−1 )). Given πt−1 , the τ kL set R≤t−1 and the counter j are determined, hence so is the map λ(·) = min{1, opt dist(·, R≤t−1 )p }. est The adversary is also a function of πt−1 , so it submits the same xt in both worlds for t = ̸ i∗ . Therefore, the bit fed to Acount at step t is the deterministic function zt = 1[ut ≤ λ(xt )] of the submitted point, and we have the following. (We use the superscript b ∈ {0, 1} to denote the execution on (xb1 , . . . , xbn ).) (a) The counting streams are neighbors. For t ̸= i∗ , we have x0t = x1t and hence zt0 = zt1 . So the two streams differ in at most the coordinate i∗ . (b) The dense-ball inputs are 2-neighbors. Assume w.l.o.g. that x1i∗ =⊥. Both executions insert points in stream order, skipping an arrival once |S| = Ψτ . We thus have St0 ∖ St1 ⊆ {x0i∗ } and |St1 ∖ St0 | ≤ 1, Hence, |St0 ∆ St1 | ≤ 2.

22

Note that Abu is the concurrent composition of Acount , run on a bit stream generated adaptively from the transcript, with at most Ψ invocations of Adense , each on an input determined by the transcript, u and the submitted points. By (a), the first component is (εc , δc )-DP; by (b) and group privacy for groups of size 2, each invocation of Adense is (2εd , 2e2εd δd )-DP. Lemma 21 then gives the claimed privacy guarantee. Lemma 28 (Efficiency). Suppose that Acount runs in Tc (n) time and uses Sc (n) space, and Adense runs in Td (n) time and uses Sd (n) space. Furthermore, suppose that the output stream O≤n has size at most K. Then, Algorithm 2 runs in O (ndK + Tc (n) + Ψ · Td (Ψ · τ )) time and uses O (Ψ · (τ + Ψ · Υ) · d + Sc (n) + Sd (Ψ · τ )) space. Proof. For the running time, observe that all calculations outside the calls to Acount , Adense takes O(d) time per point except for the computation of the closest point (Line 5) which may take up to O(K · d) time. Furthermore, we only invoke Adense at most O(Ψ) times, and each time the input St has size at most Ψ · τ . The total running time thus follows. As for the space complexity, outside of Acount , Adense , the only thing needed to be kept by our algorithm are St , Rt . The former has size at most Ψ · τ and the latter has size at most Ψ2 · Υ (due to the size blow-up guarantee of Adense ). Finally, note that each element in St , Rt are points in Rd so it requires O(d) space.

B.2

Combined Prefix-Approximation Guarantee via Guessing

By using a randomized guessing strategy for the estimated optimum cost, we can eliminate the dependence on optest in the error bounds of the Private Meyerson’s Sketch. This allows us to strictly parameterize the capacity bound Ψ and the density threshold τ in terms of k, d, n. Algorithm 4 Random-Guess DP Meyerson’s Sketch Aguess-bicri Require: Stream X = (x1 , . . . , xn ) of points in a metric space M = (U, d) with diameter ≤ 1. 1: Parameters: Target centers k, Privacy budgets (ε, δ). 2: Define the set of possible guesses: G = {2⌈log2 n⌉−1 , 2⌈log2 n⌉−2 , . . . , 2−⌈log2 n⌉ } 3: Sample an estimated optimum optest uniformly at random from G. 4: Set the target sketch capacity: Ψ = Θ(k log n) 5: Set the density threshold τ depending on the privacy model:  2
 d·k nd • For pure-DP: τ = Θ ε polylog ε • For approximate-DP: τ = Θ

√

d·k1.5 polylog ε

nd εδ



6: Instantiate Acount as the (ε/2, δ/2)-DP continual counting algorithm. ε 7: Instantiate Adense as the ( 4Ψ ,

δ )-DP dense ball algorithm. 8Ψeε/(2Ψ)

8: Run AMeyerson (optest , Ψ) on X using the configured parameters. 9: return

Output stream (O1 , . . . , On ) from the sketch.

Lemma 29 (DP Prefix-Approximation). Given a stream X = (x1 , . . . , xn ) of n points and a target number of centers k, Algorithm 4 is (ε, δ)-DP. Furthermore, it outputs a multiset-stream (O1 , . . . , On ) satisfying:   1. Accuracy: For a fixed t ∈ [n], with probability at least Ω log1 n , (O1 , . . . , Ot ) is an (O(1), β)prefix-approximation of (x1 , . . . , xt ), where the additive error β is bounded by: 23





d·k3 nd for pure-DP. ε polylog ε  √ 2.5 
d·k nd • β=O polylog for approximate-DP. ε εδ

• β=O

2. Size Bound: The total number of output centers is bounded by |O≤n | ≤ O(k 2 log2 n).
The algorithm processes the stream in total time Õ ndk 2 + ΛO(1) and uses space ΛO(1) , where n • Λ = kd log for pure-DP. ε

• Λ = kd log(n/δ) for approximate-DP. ε Proof. The privacy guarantee of Algorithm 4 immediately follows from that of AMeyerson (Lemma 27). Accuracy Guarantee (Conditioning on a Correct Guess). Fix t ∈ [n]. Let opt := optk,p X≤t denote the true optimal cost. Since the metric space has diameter ≤ 1 and there are t ≤ n points, opt ≤ n. Let us define the “correct guess” g ∗ ∈ G as follows: • If opt > 1/n, let g ∗ be the unique power of 2 in G such that g ∗ < opt ≤ 2g ∗ . • If opt ≤ 1/n, let g ∗ = 2−⌈log2 n⌉ ≤ 1/n. ∗ Since G contains exactly 2⌈log   2 n⌉ elements, the algorithm selects optest = g with probability exactly 2⌈log1 n⌉ = Ω log1 n . Conditioned on the event that optest = g ∗ , we now verify that the 2 parameters assigned strictly satisfy the prerequisites for the prefix-approximation guarantee of the private Meyerson’s sketch in Lemma 10:   opt 1. Capacity Ψ: The prerequisite is Ψ ≥ D · kL 1 + opt where L = Θ (log2 (n/optest )). est

opt opt Because g ∗ is the correct guess, we have opt ≤ opt g ∗ ≤ 2 (or 1/n ≤ 1). Since optest ≥ 1/n, est L ≤ Θ(log n). Thus, it suffices to choose Ψ = Θ(k log n) where Θ(·) hides a sufficiently large constant.

2. Threshold τ : We require both Acount and Adense to succeed with failure probability γ ≤ 1/(4n). • Acount requires an additive error
of ≤ τ /2. Given εc = ε/2, by Theorem 23, it suffices to satisfy τ ≥ Ω 1ε · polylog (n) . • Adense processes datasets of size up to N = Ψ · τ . – For pure-DP: By Theorem 24, the subroutine requires τ ≥ Θ



d·(Ψτ ) εd

1/2

· polylog



nd εd

 .

Since εd = ε/(4Ψ), this resolves to:     2   dΨτ nd dΨ nd 2 τ ≥Θ · polylog ⇐⇒ τ ≥ Ω · polylog ε/Ψ ε ε ε  2
 dk nd Substituting Ψ = Θ(k log n), it suffices to take τ = Θ ε · polylog ε .  1/3   d·(Ψτ ) . – For approximate-DP: By Theorem 24, this requires τ ≥ Θ · polylog εnd ε2 dδ d

This resolves to:       3 dΨτ nd dΨ nd 3 2 τ ≥Θ · polylog ⇐⇒ τ ≥ Θ · polylog 2 2 (ε/Ψ) εδ ε εδ 24

√ ⇐⇒ τ ≥ Θ Substituting Ψ = Θ(k log n), it suffices to take τ = Θ

dΨ1.5 · polylog ε

√



dk1.5 · polylog ε

nd εδ

nd εδ

!



.

Since all parameter prerequisites are met, the private Meyerson’s sketch guarantees that with probability at least 1/2, the output (O1 , . . . , Ot ) is an (O(1), β)-prefix-approximation of (x1 , . . . , xt ), where the additive error bound is given by: βbicri = O(optest + τ kL). Recall that optest ≤ max(opt, 1/n); thus, the term O(optest ) scales as O(opt) + O(1/n). The O(opt) component acts as a constant multiplier absorbing directly into the O(1)-multiplicative approximation factor. The O(1/n) term is strictly subsumed by the dominant term O(τ kL). Thus, the final additive error is purely β = O(τ kL) = O(τ k log n). Substituting our values for τ :  2   3

 nd dk • Pure-DP: β = O dkε · polylog nd · k log n = O · polylog . ε ε ε • Approximate-DP: β = O

√

dk1.5 · polylog ε

nd εδ

  √ 2.5 dk · k log n = O · polylog ε

nd εδ



.

Conditioned on guessing g ∗ , the algorithm succeeds with probability 1/2. Thus, the overall uncondi 1 1 tional success probability is strictly Ω(1/ log n) · 2 = Ω log n . Size Bound and Complexity. By the constraints of the private Meyerson’s sketch, the total number of output centers K is bounded by Ψ2 · Υ. Because Υ = O(1) for the 1-Cluster to dense ball reduction, we have K ≤ O(Ψ2 ) = O(k 2 log2 n). The time and space complexity follows by plugging the above parameters into Lemma 28 with Tc (n) = O(n log n), Sc (n) = O(n) (from Theorem 23) and Td (N ) = Sc (N ) = N O(1) (from Theorem 24) with N ≤ Ψ · τ .

B.3

Boosting Probability via Repetition

Since Lemma 29 only yields a low-probability guarantee for a single t ∈ [n], we need to boost its success probability. Fortunately, this can be easily accomplished by repeatedly running the algorithm multiple times. We start by describing the generic reduction below. Lemma 30. Suppose that there is an (ε̃, δ̃)-DP algorithm that satisfies the following: • Its output stream size is bounded by B. • Its space and time complexity are S(n) and T (n). • For each fixed t ∈ [n], the output stream (O1 , . . . , Ot ) is an (α, β)-prefix-approximation of the input stream (x1 , . . . , xt ) with probability at least q.     Then, for some R = O log(n/γ) there is an R · ε̃, R · δ̃ -DP algorithm that satisfies the following: q • Its output stream size is bounded by R · B. • Its space and time complexity are O(R) · S(n) and O(R) · T (n). 25

• With probability 1 − γ, for all t ∈ [n], the output stream (O1 , . . . , Ot ) is an (α, β)-prefixapproximation of the input stream (x1 , . . . , xt ). l m Proof. This follows by simply running the algorithm R = ln(n/γ) times, and outputting the union q of all the output. The output size bound, and space and time complexity obviously grows by a factor of R. As for the (α, β)-prefix-approximation guarantee, observe that it holds if at least one of the repetition satisfies the (α, β)-prefix-approximation. Thus, by a union bound, the probability that it satisfies (α, β)-prefix-approximation for all t ∈ [n] is at least 1 − n · (1 − q)R ≥ 1 − γ. Combining Lemma 30 with Lemma 29 (where q = Ω(1/ log n)), we immediately get the following: Theorem 31 (High-Probability DP Prefix-Approximation). Given a stream X = (x1 , . . . , xn ) of n points and a target number of centers k, there is an (ε, δ)-DP algorithm whose multiset-stream (O1 , . . . , On ) satisfies: 1. Accuracy: With probability at least 1 − γ, for all t ∈ [n], the output stream (O1 , . . . , Ot ) is an (O(1), β)-prefix-approximation of the input stream (x1 , . . . , xt ), where the additive error β is bounded by:  3   • β = O d·kε polylog nd for pure-DP. εγ  √ 2.5   d·k nd • β=O polylog εδγ for approximate-DP. ε 2. Size Bound: The total number of output centers is bounded by |O≤n | ≤ O(k 2 · polylog (n/γ)).
The algorithm processes the stream in total time Õ ndk 2 · log(1/γ) + ΛO(1) and uses space ΛO(1) , where • Λ = kd log(n/γ) for pure-DP. ε • Λ=

C

kd log



ε

n γδ



for approximate-DP.

From Prefix-Approximation to DP (Semi-)Coreset: Proof of Theorem 9

In this section, we present our algorithm for constructing semi-coreset and prove our main theorem (Theorem 9). As explained in § 3.1, we simply run the online prefix-approximation algorithm and then snap xt to the closest centers among those produced by the algorithm. We use DP continual counting algorithm to estimate the weight of each center.

C.1

Properties of the DP Semi-Coreset Algorithm: Privacy and Efficiency

The privacy and efficiency guarantee of Algorithm 5 are fairly simple to derive and are stated more formally below. Lemma 32 (Privacy). If Apref is (εb , δb )-DP and Acount is εc -DP, then Algorithm 5 is (εb +εc , δb )-DP. Proof. Fix an adversary B. Recall that we use i∗ to denote the challenge index. b which is exactly the same First, it will be more convenient to consider a modified algorithm A, as Algorithm 5, except it releases (x̃t , yt ) at each step (instead of just x̃t ). By Lemma 20, it suffice to prove that Ab is (εb + εc , δb )-DP. 26

Algorithm 5 Private Semi-Coreset Adpcoreset Require: Stream X = (x1 , . . . , xn ) Parameters: Online Prefix-Approximation Algorithm Apref ; Continual Counting Algorithm Acount 1: for t = 1, . . . , n do 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:

{Do the following upon receiving xt } Feed xt to Apref and let yt ⊆ U be the output for u ∈ yt ∖ Y≤t−1 do Aucount ← start Acount instance for u eut−1 ← 0 x̃t ← ∅ if xt ̸=⊥ then ft ← closest point to xt in Y≤t else ft ←⊥ for u ∈ Y≤t do if u = ft then Feed 1 to Aucount and let eut be the output else Feed 0 to Aucount and let eut be the output Add (eut − eut−1 ) copies of u to x̃t return x̃t

{Output in this time step} {Ties broken arbitrarily}

We view Ab as the concurrent composition of Apref and another mechanism Ab′ that handles the counters {Aucount }u∈Y≤n . • For Apref , the submitted stream differs only at i∗ . Thus, this is (εb , δb )-DP. b conditioned on a transcript prefix πt−1 = ((x̃1 , y1 ), . . . , (x̃t−1 , yt−1 )) and the output yt • For A, S from Apref , Y≤t = t′ ≤t yt′ agrees in the two runs. Thus, for t = ̸ i∗ the submitted inputs to {Aucount }u∈Y≤t agree. For t = i∗ , assume w.l.o.g. that x1i∗ =⊥. For the run b = 1, all the inputs f0

t to the counters are 0. Meanwhile, for b = 0, all the inputs remain 0, except for Acount . Hence, we may apply Lemma 22 to conclude that this is εc -DP.

Finally, applying Lemma 21 over these two components gives the claimed privacy guarantee. Lemma 33 (Efficiency). Let K be the maximum number of centers produced by Apref (i.e., |Y≤n | ≤ K). If Apref runs in time Tb (n) and space Sb (n), and each instance of Acount runs in time Tc (n) and space Sc (n), then Algorithm 5 runs in time O(Tb (n) + nKd + K · Tc (n)) and uses space O(Sb (n) + K · Sc (n) + Kd). Proof. Algorithm 5 runs Apref across the stream, taking Tb (n) time and Sb (n) space. It maintains a set S of at most K points in Rd , requiring O(Kd) space. At each of the n time steps, it computes the distance from xt to all points currently in S, taking O(Kd) time per step. It then feeds an indicator bit to each of the |Y≤t | ≤ K active instances of Acount . Running K counters takes O(K · Tc (n)) time and O(K · Sc (n)) space over the stream. Summing these bounds yields the stated efficiency.

27

C.2

Semi-Coreset Guarantee

Next, we prove that the output of Algorithm 5 provides an output that is a semi-coreset of the input stream. We state the lemma with generic parameters below. Lemma 34 (Semi-Coreset Guarantee). Suppose that with high probability, Apref provides an (α1 , β1 )prefix-approximation for all time steps t ∈ [n], and Acount is β2 -accurate for all instances and all time steps. Then, with high probability, the output multiset stream X̃ = (x̃1 , . . . , x̃n ) forms a (κ, η1 , η2 )semi-coreset of the input X where κ = O(1 + α1 ), η1 = O(α1 ), and η2 = O(β1 + Kβ2 ), with K = |S| representing the total number of centers generated up to time t. Proof. Fix a time step t ∈ [n]. Algorithm 5 constructs the multiset X̃≤t , which consists of points from Y≤t where the multiplicity of each center u ∈ S is eut , the estimate provided by the respective instance Aucount . We define a natural mapping Ψ : X≤t → Y≤t that maps each point xi (i ≤ t) directly to the closest available Pt center fi ∈ Y≤i at the time of its arrival: Ψ(xi ) = fi . u Let ct = i=1 1[fi = u] be the exact number of points in X≤t that were mapped to center u. The generalized transport cost from the original points X≤t to the estimated coreset U≤t under mapping Ψ is exactly: mt(Ψ, X≤t , X̃≤t ) =

t X

dist(xi , fi )p +

i=1

X

|cut − eut |.

u∈Y≤t

We bound the two terms separately: 1. Distance Term: Since fi is chosen as the closest point to xi from the active centers Y≤i output by Apref , the distance dist(xi , fi )p is exactly d(xi , Y≤i )p . By the prefix-approximation guarantee of Apref , we sum this over time to get: t X

dist(xi , fi )p ≤ α1 · optk,p X≤t + β1 .

i=1

2. Weight Difference Term: The true frequency of assignment is cut , while the constructed coreset uses the estimated frequency eut . By the assumed accuracy guarantee of Acount , we have |cut − eut | ≤ β2 for all u ∈ Y≤t . Summing this bounded error over all K = |Y≤t | active centers yields: X |cut − eut | ≤ Kβ2 . u∈Y≤t

Combining these bounds, the total transport cost strictly satisfies: mt(Ψ, X≤t , U≤t ) ≤ α1 optk,p X≤t + (β1 + Kβ2 ). Because the metric space has diameter ≤ 1, we can directly apply Lemma 14 to this result. Substituting α = α1 and β = β1 + Kβ2 , it follows immediately that U≤t is a valid (κ, η1 , η2 )-semicoreset for X≤t with parameters κ = O(1 + α1 ), η1 = O(α1 ), and η2 = O(β1 + Kβ2 ).

28

C.3

Putting Things Together: Proof of Theorem 9

Proof of Theorem 9. The algorithm is simply to run Algorithm 5 using Apref and Acount from Theorem 31 and Theorem 23 respectively, where the privacy parameters are set to εb = εc = 2ε and δb = δ. The privacy guarantee immediately follows from Lemma 32. Recall also that the size bound by Theorem 31 is K = O(k 2 · polylog (n/γ)). Plugging this (and the complexity bounds from Theorems 23 and 31) into Lemma 33 yields the claimed time and space complexity. Finally, plugging K = O(k 2 · polylog (n/γ)) and the accuracy guarantees from Theorems 23 and 31 into Lemma 34 yields the semi-coreset guarantee. (Note that the error term is dominated by β1 in both pure-DP and approximate-DP.) Finally, the number of distinct points in the output is at most K.

29

Related documents

• Online Differentially Private Consistent Clustering#781178
• Online Differentially Private Consistent Clustering#779803
• PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution#259621
• Privacy Leakage via Output Label Space and Differentially Private Continual Learning#163068
• Differentially Private Sampling from Distributions via Wasserstein Projection#175142