Adversarially Robust Distributed Count Tracking via Partial Differential Privacy
Authors: Zhongzheng Xiong
Xiaoyi Zhu
Zengfeng Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: Distributed Tracking
Adaptive Robustness
Differential Privacy
Generalization

Abstract: We study the distributed tracking model, also known as distributed functional monitoring. This model involves $k$ sites each receiving a stream of items and communicating with the central server. The server's task is to track a function of all items received thus far continuously, with minimum communication cost. For count tracking, it is known that there is a $\sqrt{k}$ gap in communication between deterministic and randomized algorithms. However, existing randomized algorithms assume an "oblivious adversary" who constructs the entire input streams before the algorithm starts. Here we consider adaptive adversaries who can choose new items based on previous answers from the algorithm. Deterministic algorithms are trivially robust to adaptive adversaries, while randomized ones may not. Therefore, we investigate whether the $\sqrt{k}$ advantage of randomized algorithms is from randomness itself or the oblivious adversary assumption. We provide an affirmative answer to this question by giving a robust algorithm with optimal communication. Existing robustification techniques do not yield optimal bounds due to the inherent challenges of the distributed nature of the problem. To address this, we extend the differential privacy framework by introducing "partial differential privacy" and proving a new generalization theorem. This theorem may have broader applications beyond robust count tracking, making it of independent interest.

Adversarially Robust Distributed Count Tracking via Partial Differential Privacy
Zhongzheng Xiong
Xiaoyi Zhu
School of Data Science
School of Data Science Fudan University zhuxy220m, fudan edu.
Fudan University
zzxiong21 @m. mudan.edu..o cn
Zengfeng Huang*
School Data Science
Fudan University
h fudan cecddannedu.ccm cn
Abstract
We study the distributed tracking model, also known as distributed functional monitoring. This model involves & sites each receiving stream of items and communicating with the central server. The server's task to track a function all items received thus far continuously, with minimum communication cost. For count tracking, is known that there is v gap in communication between de- terministic and randomized algorithms. However, existing randomized algorithms assume an "oblivious adversary" who constructs the entire input streams before the algorithm starts. Here we consider adaptive adversaries who can choose new items based on previous answers from the algorithm. Deterministic algorithms are trivially robust to adaptive adversaries, while randomized ones may not. Therefore, we investigate whether the vk advantage of randomized algorithms is from ran- domness itself or the oblivious adversary assumption. We provide an affirmative answer to this question by giving a robust algorithm with optimal communication. Existing robustification techniques do not yield optimal bounds due to the inherent challenges of the distributed nature of the problem. To address this, we extend the differential privacy framework by introducing "partial differential privacy" and proving new generalization theorem. This theorem may have broader applications beyond robust count tracking, making independent interest.
Introduction
In the distributed tracking model there are k sites and single central server. Each site receives items over time in a streaming fashion and can communicate with the server. Let St(() be the stream that site i observes up to time The the multiset union of (S) i = 1, .)) at all times. The goal is to minimize the communication cost, which is defined as the total number of words communicated between the server and all sites. Due to strong motivations from distributed system applications, this model has been extensively investigated, e.g.,
wants track the value of a function f that is defined over
[2]. The theoretical study of communication complexity was initiated by [.] Count tracking is the most basic problem in distributed tracking. where ff is simply the total number of items received so far. Since exact tracking requires sites to
communicate every time an item arrives, incurring too much communication, the objective is to track
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

an (1 + approximaaaio. For this problem, there is a simple deterministic algorithm with Ô (k/a communication. Huang et al. [13 proposed randomized algorithm that achieves Ō( Ö(vk/a), but the correctness is under the assumption of an oblivious adversary, i.c., input streams are constructed in advance and are just given to sites one item at a time. In particular, the analysis assumes the input is independent of the algorithm's 's internal randomness. In interactive applications, this assumption is often unrealistic; the adversary can generate the next item based on previous answers from the server, making the independence assumption invalid. Moreover, the break of independence may occur unintentionally. For example, the tracking algorithm may be part of larger system; the output of the algorithm can change the environment, from which the future input to the algorithm is generated. In such cases, can no longer assume the independence between inputs and algorithm's 's internal state. The main question of this paper is: Whether the vi advantage of randomized count tracking algorithms is from randomness itself or the oblivious adversary assumption?
Designing robust randomized algorithms against adaptive adversaries has received much attention recently [14 [6 17 [8] 19 20 21 22],23]. Existing research focuses on centralized settings, and in this paper, we initiate the study of adversarial robustness for distributed tracking. We provide new randomized algorithm with communication Ö(VR/a), which provably tracks the count within an a relative error at all times, even in the presence of an adaptive adversary. As in 18], we utilize differential privacy (DP) to construct robust tracking algorithms. The main idea is to use DP to protect the internal randomness, so that the adversary cannot learn enough information about it to generate bad inputs. However, due the "event-driven nature" of distributed tracking algorithms, we cannot protect the randomess in the usual sense of DP (which will be elaborated in more details below). Thus, the DP framework of (T8] is not directly applicable.
To address this difficulty, a relaxed version of differential privacy, called partial differential privacy. is introduced. Moreover, new generalization theorem for partial DP is proved. In partial DP we allow an arbitrary small subset of the database to be revealed, and only require the privacy of the remaining dataset is protected. The power of the new definition comes from the fact that the privacy leaked set can be chosen by the algorithm after the interaction with the adversary and the set can depend on the actual transcript. Intuitively, an interactive mechanism satisfies partial DP as long as after the interaction, we can always find a large subset whose privacy is protected. On the other hand, since the set try protect is not fixed in advance, it is subtle give the right notion of "protecting the privacy of a large part of the data". Besides this new notion of DP, our algorithm deviates from the framework of [18] in many other details. For instance, our algorithm does not treat existing oblivious al algorithms as a black box; instead, we directly modify oblivious algorithms and perform a more fine-grained privacy analysis. The contributions of this paper are summarized as follows:
1. We initiate the study of adversarially robust distributed tracking and propose the first robust counting tracking algorithm with near optimal communication.
2. To overcome the inherent challenges that arise from the distributed nature of the problem, we introduce a relaxed (and more general) version of differential privacy and prove a new generalization theorem for this notion. We believe that this new generalization theorem can be of independent interest and may have broader applications beyond count tracking.
1.1 Problem Definitions and Previous Results
Throughout this paper, we use M to denote the tracking algorithm/mmechanism and A to denote the adversary. N is used to denote the total number of items.
The model and its event-driven nature We assume there exists a point-to-point communication channel between each site and the server, and communication is instantaneous with no delay. It is convenient to assume that the time is divided into discrete time steps. In each step, the adversary picks one site and sends it new item. The adversary is also allowed to skip the step and do nothing, and because of this, algorithms that can trigger new events based on the global time do not have an advantage over purely event-driven ones. For example, the server may have wanted to wait a random number of time steps before updating the output, but the adversary can always skip a large number of steps before sending the next item, which makes the waiting meaningless. That being said, is not a restriction to only consider event-driven algorithms: the internal state of each site changes only when
We use the Ô notation to suppress the dependency on all polylogarithmic factors.

---

it receives a new item or a new message from the server, and the server's state changes only if a new message from sites arrives.
Distributed count tracking The goal of count tracking algorithm M is to output (a, B)- approximation of the total number of items received by all sites. More specifically, with probability at least - B, the output of M is (1 = a)-accurate with respect to the true answer at all time steps sinultaneously. We measure the complexity of the algorithm by the total communication cost between the server and all sites. Consistent with prior research, communication cost is expressed in terms of words unless otherwise stated. We assume that any integer less than N can be represented by a single word. To simplify the presentation, we assume k S a The case k + can be solved with the same technique, with an extra additive (l: log N) term in the communication complexity?
The adversarial model The setting can be viewed as two-player game between the tracking algorithm MM and the adversary A. At each time step t,
1. A generates pair v4 (i, where x is the item and i is the site to send x to; and ut depends on the previous items and previous outputs of M
2. M processes u, and outputs its current answer de-
The interaction between A and M generates transcript (wi, U1, U2, 02 ..... The objective of A is to cause M to output an incorrect answer at some step L.
Existing results on count tracking Previous results and their main ideas are discussed here.
Deterministic complexity. There a simple deterministic solution to count tracking. Each site notifies the server every time their counter increases by factor of + Then, the server always maintains an a-approximation to each site's counter, and their sum is an a-approximation to the total count.
easy to see the communication complexity of this algorithm is O E -log N). We note deterministic algorithms are trivially robust to adaptive inputs. A deterministic communication lower bound of 9 & log N) was proved in 6
Randomized complexity. randomized algorithm with O log N) communication and constant error probability was proposed in [13,, which was shown to be optimal in the same paper. The main idea of their algorithm is as follows. Let N be the current number of items. Unlike the above deterministic algorithm, in which each site notifies its local count according to deterministic thresholds, now the thresholds are set randomly. Let e the discrepancy between the true local
count on site and its estimation on the server, and the total error is e = Σx e. For deterministic algorithms, all e; could have the same sign in the worst case, so on average, e; has to be less than aNN/k. On the other hand, in the randomized algorithm, each e; is a random variable. Suppose Varles] < (aN)2/1 k for each i, the total variance Var[e] (a.N), and it is sufficient to obtain an a-approximation with constant probability by standard concentration inequalities. Compared to deterministic estimators, now each local error e, may far exceed aN/k.
Robustness to adaptive inputs. In the randomized approach described above, the analysis crucially relies the independence assumption on e, ss since otherwise the variances do not add up and concentration inequalities cannot be applied. When the adversary is oblivious, the independence holds long each site uses independent random numbers. However, in the adaptive setting, this does not hold any more, and it becomes unclear whether the vTe improvement is still achievable.
1.2 Existing Robust Streaming Frameworks
Distributed tracking natural combination of streaming algorithms 24 and communication complexity (25). Robust streaming algorithms design has become a popular topic recently and several interesting techniques have been proposed. Next, we provide a brief overview on the existing frameworks for robust streaming algorithms. Let F be the target function, for example, the number of distinct elements.
NNoe that this extra additive Olklog N) term for k > 22 also exists in previous work 13 on oblivious distributed streams.
3

---

Sketch switching [1] Given a stream of length N and an accuracy parameter a, the flip number, denoted as Na,N. is the number of times that the target function F changes by factor of + a. For insertion-only streams and a monotone function F, À = log N. In sketch switching, we initialize A independent copies of an oblivious algorithm, and items in the stream are fed to all copies. The stream can be divided into O()) phases; in each phase JF increases roughly by a factor of 1 + a. During the jth phase, the output remains the same, and the jth copy is used for tracking the value. When the estimate (from the jth copy) has become larger than the last released output by a factor of (1 + a), the output is updated and < j + 1. The robustness holds because each copy is utilized no more than once, and once its randomness revealed, the algorithm switches to a new copy. The space complexity is Ả times the space of the oblivious algorithm. Applying sketch switching the algorithm of [13] results in a robust count tracking algorithm. However, the communication complexity increases by a factor of X, which can be worse than the deterministic bound.
Difference estimator Woodruff et al. [22 refined the sketch switching approach significantly and proposed the difference estimator (DE) framework. Informally, instead of using oblivious sketches as the switching unit, the DE framework divides the stream into blocks and uses sketches on each block as switching units. Consider a part of the stream, denoted by S, in which the value of F increases from F to 2F' A technique called difference estimator (DE) was proposed to estimate the difference between values of F. at current time t and some earlier time to. The estimator is generated by maintaining ( = log 1 levels of DEs. In level 1, S is divided into 1 blocks and the a value of F increases by oF in each block. In the jith level, S is divided into az1-r blocks, and the DEs produce estimators with additive error aF.. [22] proved that for many important problems. where (FF) is the space complexity of
the space complexity of such DEs is aSpace(F)22 F in the oblivious setting. Since there are -22-T DEs on the jth level, the total space of level is Space(F) and the space is (Space(F)) over all levels. Since blocks from all levels form a dyadic decomposition, the final estimator the sum of DEs, one from each level. Thus, the total error is F, and by adjusting a in the beginning by factor of f, this produces the desired error. Applying the DE framework to distributed tracking, the communication bottleneck from level 1, where there are 1/a DEs. It requires synchronization at the beginning of each block, so that all sites and the server are able to agree to start new DE, synchronization incurs & communication; thus, even ignoring other cost, the total cost is at least H, which is no better than the deterministic bound.
o²
Differential privacy Hassidim et al. 18 proposed a framework using tools from DP. Instead of switching fresh sketches, this framework protects the randomness in the sketch using DP. The random bits in each copy of the oblivious sketch are viewed as a data point in the database, and the adversary generates item (considered output. By the generalization theorem of DP, if the interaction transcript satisfies DP w.r.t. the random bits, then the error in the output is close to the error of an oblivious algorithm in the non-adaptive setting (the closeness depends on the magnitude of the noise injected). Similar as in sketch switching, the output is updated only when it changes by (1 + a) factor, and thus there are only time steps in which the adversary observes "useful information". Therefore. it is not surprising that the sparse vector technique [26] is applied. By the advanced composition theorem of DP (27). Ō(VA) independent copies of the oblivious algorithm is enough for À outputs. Therefore, compared with sketch switching, the space increases by only a factor of Vx. Attias et al. (3 gave an improvement by incorporating difference estimator to the DP framework.
query in DP) at each time and observes the privatized
However, there is fundamental challenge in applying the DP framework to distributed tracking. As discussed in Section T.T. all distributed tracking algorithms are essentially event-driven. Now let us focus on a time step where the server updates its output. Because of the event-driven nature, this update is triggered by the event that some site i just sent a message. Similarly, site i sending the message is also triggered by another event, and so on and so forth. The start of this event chain must be that the adversary sends an item to some site j, triggering to send the first message. This causes additional privacy leakage. For example, suppose whether to send a message is indicated by a binary function fnz. rT)) where ry is the random number used in the tracking algorithm and ny is the local count on site j. At time I, the adversary knows [[nn; r;) = 1, which makes the algorithm have no privacy guarantee. This problem is attributed to the fact that the server can update the output only after receives a message. So to achieve the desired level of privacy, one has to add noise to locally each site, but the total noise from all sites can be too large.

---

1.3 Our Method
Technical overview In our algorithm, each site divides its stream into continuous blocks of size
A Ō VE D(oN). For each block j. the site draws random integer ry with uniform distribution in [A]. The site sends message to the server when the number of items in a block j reaches the threshold r, The server output mA, where m is the number of messages received from all sites. By a similar analysis as in [3] the estimator has a:N additive error. To robustify this algorithm, we also use DP. To overcome the limitations of the existing DP framework, we make several critical changes. First, instead of running multiple independent copies of the oblivious algorithm, we run single copy of the above oblivious algorithm. Secondly, we perform a more refined privacy analysis, in which each random number ry is treated as the privacy unit. Therefore, the analysis framework quite different from [8]. Thirdly, and most importantly. we do not require the algorithm to have privacy guarantee in the traditional sense; instead, we privatize the algorithm so that, at any time, we can always find a large set of random numbers whose privacy is protected. However, it is unclear how to change the original DP definition to capture the meaning of "protecting a large subset of the dataset", since this set depends on the current transcript, and may change at each time step. Moreover, for this weaker DP, we need to prove that the generalization theorem still holds. To this end, we introduce partial DP and prove generalization theorem for it. We believe partial DP is quite general and will have more applications beyond robust distributed tracking. The main results of this paper is summarized in the next theorem.
Theorem (Main theorem). With probability 1 - 5, our mechanism M comprised of Algorithm 7 and oudputs an a-approximate the total count at all times in the adversarial setting. The
communication complexity is O CVVElog where C Caatee--V((i <=V((1eV())
1.5 +1). .log
(8v/ log N
a
ad
Compared to the optimal randomized bound in the oblivious setting, the cost of handling adaptive adversaries is at most an extra factor of C.
2 Preliminaries
Notation Let II be the space of all possible transcripts of the interaction between M and A. We use II to denote the transcript random variable, π E to denote realization II. The Laplace distribution with 0 mean and 26 variance is denoted by Lap(b). We use the notation S ~ pm to indicate that
is a dataset comprised of m i.i.d samples from distribution P. The conditional distribution of S given the transcript is represented by 2. The query function is denoted by q : x + [0, and qi denotes the query function at time step t. If q: a linear query, then (s( = 1 Σ (S.).
where Ør,i : X + [0, 1] is sub-query function on a single sample. The expectation of y over the distribution pm is denoted by (PPm) = Es-pp (s() And y(Q²) = Es-q., [s)].
m
Differential privacy Let S E n be the database that M needs to protect, for example our case, the random numbers (thresholds) in M. Denote the interaction between A and M by T(M, A: S). Definition (Differential Privacy). M is (e. -iifferrent private if for any A, any two neighbor- ing database S ~ S' E x differing only in one position, and any event E C II, we have
Pr
[II E S e
Pr I-I(M.A:S))
[ E
E] + 8.
IM.
Lemma 1 (Laplace Mechanism 28 Let x, x E R and Ix -2' < L. Let a ~ Lap(l/s) be Laplace random variable. For any measurable subset E S R. Pr|x E E S E Pria' + o e E).
Private continual counting Consider the continual counting problem: Given an input stream consists of {0. 1}, continual counting requires to output an approximate count of the number of 1 I's seen so far at every time step. Different techniques have been proposed to achieve differential privacy under continual observation 22 30) In this paper, we make use of the Binary Mechanism (BM) (30 (see appendix for its pseudo code).
Theorem 2. (330) BM is (s, diiffferrentially private with respect to the input stream. With probabil- ity at least 1 - 6, the additive emror is O (log 1.5 log( )) at all time steps e [T].
5

---

Remark. Note that although the input of BM is bits, it can directly extend to real numbers without any modification. The same privacy and utility guarantees hold.
Generalization by differential privacy The generalization guarantee of differential privacy arises from adaptive data analysis. Existing research 28
31 32 has shown that any mechanism for answering adaptively chosen queries that is differentially private and sample-accurate is also accurate out-of-sample.
Definition (Accuracy). M satisfies (a, (o.33)samm sammll accuracy for adversary A and distribution P iff
Pr Swpm (M.(S.
max (a q((5)) a < 3,
where at is the output of M and qi is the query given by A at time t. M satisfies (a, distrribbbt accuracy iff
Pr 8mppm IMM
max Ja, (e(m a s...
Recently, Jung et al. [32] discovered simplified analysis of the generalization theorem by introducing the posterior data distribution Qr as the key object of interest. Through natural resampling lemma, they showed that sample-accurate mechanism also accurate with respect to 2x.
Lemma 2
[32
Suppose that M is (a, -samle accurate. Then for every > 0 it also satisfies:
Pr S-Pm ITT(M..:)))
max (a, qt (2n) a
Thus, achieve distributional accuracy, it suffices to prove the closeness between 2x and p Then they showed that this can be guaranteed by differential privacy.
Lemma (322) If M is (e, d)-iifferenttilly private, then for any data distribution P, any analyst A, and any conslant > 0:
Pr SwpP (MM...))))
max (p di (QT) (c-- 20 S [
Partial Differential Privacy and Its Generalization Property
In the definition of partial DP, specify the set of data whose privacy is leaked via mapping fz II + 2 Given transcript æ, partial DP guarantees privacy only on S (T). Intuitively, this means that the transcripts on two database S, S' that differs only on a position have similar distributions. However, is not known in advance, which causes trouble to this direct definition. We remedy this by first fixing i; then we only consider S, S' that differs only on and only those events E whose elements do not contain i in their privacy leaked set.
S fz
Definition (Partial Differential Privacy). M (e, k))-partial differentially private, if there exists a privacy leak mapping fL II + 2[m) with max, [T)
] I K, the following holds: for any A any
any S. e xm that differs only the ith position, and any E C II such that i U fT( REB
Pr IMI(M.A.))
Pr EE I.I(M.ASS)
II +
A generalization theorem for partial DP is presented below. Generalization for linear queries suffices for our application, but this can be extended to general low-sensitivity queries.
Theorem 3. For linear queries, if M satisfies (e, 8, k) partial differential privacy and M is (a, B)- sample accurate, then for any data distribution P, any adversary A, and any constant c, d 0:
2x + c 2d
8
Pr Swppm (..Pm.IIIIMMA.S))
max la: qe (p(P))) a (e - -1)
<
Compared with existing results, it has an extra term in the error. This is intuitive, as the privacy leaked set contributes most error in the worst case. Following [32], suffices to establish the low discrepancy between Q, and Pm. To this end, we prove the following key lemma in the appendix.

---

Lemma 4. If M satisfies (5, k) partial differential privacy, then for any data distribution P, any adversary A, and any constant с 0:
2x S 8
Pr SwpPm IMM.
max (Qx) q((P"")) > (e" 11)
+ 20
m
The query function of interest in this paper only depends ri data points, with n < at each time step. For such queries, we expect the total error to be proportional to mn rather than m, which is formalized in the following refinement of Theorem the proof of which requires only slight modification and is included in the appendix.
Theorem 4. For linear queries, if M satisfies (e, 6, k) partial differential privacy and M is (a, B)- sample accurate. Further, if each linear query depends on at most rn data points, then for any data distribation P, any adversary A, and any constant c, d >>
2x
8
8
Pr S-Pm S.-Pm.TT-IMI.. IT.((M...)))
max az
(e(P" >a a+ m
-
+
2d
S
+
m
d
c
4 Robust Distributed Count Tracking Algorithm
Our algorithm has multiple rounds. In each round, N increases roughly by factor of 1+ Vka. After a round ends, the true count is computed and sent to all sites, and then, the algorithm is reinitialized with fresh randomness. Thus, we only focus on one round, and let No be the true count at the
beginning of the round. In the algorithm, C' C-V((1os vk
1.5 +1) log
8./
and A
o.No 8CVk"
The algorithm on site presented in Algorithm [ The site divides its own stream into blocks of size A, and exactly one bit will be sent to the server in each block. The actual time of sending the bit is determined by a random threshold raj. Let Nr, be the number of items received on site i from the beginning of the current round until time t. Let de,; = [Nr,i/A and εx,; Nr,; mod A. Thus, j = d + is the index of the current active block, and e,,; the offset this block. As per Algorithm [ the number of bits sent by site i up time t is B de,; + 1[rr, Ca,sl < de, 1. Since Taj Uni(0, A), E[B.,l = de,s + A meaning A Br,; is an unbiased estimate of No. Let k') the database comprised of all sites' random numbers, i.e., Dij = Tıj. considering the input generated by the adversary as queries, then the query at time & can be specified
ft.
D E (0, A nd (m
as:
gc(D) = m
1
Σ xE(R)
de,s +
Σ I(ri < ex,ll xE(R]
B.
where B. = Ei= B denotes the total number of bits received by the server at time The value of d: at each time step depends on & random numbers corresponding to the active blocks, which is much less than the size of D, which motivates the use of Theorem 4
Let B, be algorithm's 's estimate of By. Algorithm 2 consists of Vk phases; B, remains con- stant in each phase and a new estimate by is obtained at the end of the jth phase via the bi- nary mechanism. The times that the phases end are denoted by И ff. (.,,,, and for t E [6y, (5)), we have B, by. Therefore, the transcript generated by . and A is of the form ((1,0), O), (T, b,), (L.b)),... b,),.... (T, (T.b/))). We note, in addition to noise BM, the only noise added for the purpose of DP is the Laplace random variable added on T, and an independent noise is used in each phase.
4.1 Privacy Analysis
In this section, we analyze the privacy of M for single round, demonstrating that it satisfies (e, O, VP)--patial differential privacy with respect to the random numbers D used by all sites. To achieve this, we first provide the privacy leak mapping. Note that each time the output of M updates, ic. reporting T, A knows the site i it just accessed has sent bit to the server. Then the active random
7

---

Algorithm 1: Site for a round
Input: Accuracy parameter a, failure probability 3
Initialize: k'= Ck. Generate k' i.i.d random number frai, r12, ... Tike from the uniform distribution on [A]. Initialize &; count the number of received items.
When site receives an item:
4 - 2
j
+1
Gj
f G
mod
A
if k' then
Send a signal to the server to end current round.
7
Cij f C mod A
if Cij raj for the first time then
Send a bit to the server.
Algorithm 2: Server
Input: Accuracy parameter failure probability 3
Initialize: Set e C/Vk, 2C'V, =
T Lap( 1, a, No. Initialize vic
counters {C1, 0,, ... cvr) to Start Binary Mechanism instance denoted as BM with L vk and privacy parameter.
When receiving bit from some site: Cj + 0j +1 Cj counts the number of bits in the j-th phase. */
if cj < 7 then
Output (1.0)-1)
else
6, + BM(c)) /+ feeding Oj as the j-th input to BM. 0j + b, A+ No
Output (T.a;)
j > V then
10
Notify all sites end the current round, collect all local counters, calculate the total count, broadcast it to all sites, and start the next round.
-++1 j + T Lap(
12
number Tiy this moment exposed, which means there is no meaningful privacy guarantee" Therefore, we need to relax the DP constraint. Given a transcript the privacy leaked set consists of those riy that are exposed during the execution.
Definition (Privacy Leaked Set). For a given transcript n. let A be the set time steps when output updates, Lee. A = {t T. (T.))) where is the output time t. Let ig be the site A chooses at time t. Then, fI(T) = {(te,.e) ((()))
[N A] 1}.
Since there one data point exposed in each phase, x S Vk. The privacy guarantee with this privacy leak mapping is presented below.
Lemma 5. For any two neighboring databases D ~ D' that differ only (i,j), any transcript
satisfying (i, & (T) our mechanism (Algorithm 7 Mand(2 satisfies the following inequality,
= Pr = n-I(M..::'
Pr T-J(M.A.))
II J| e
Pr
= TT,
T~I(M.A::')
i.e., it satisfies (s, -krrtiaa differential privacy.
'Note approximate DP is also not satisfied, since the indices i, are not random and can be manipulated by the adversary.

---

4.2 Accuracy and Communication
Observe that the size of D is m k W', and each query qi depends only on m k of them. In the algorithm de () estimated by Be/m. Suppose is (a,, -sample accurate, then by Lemma and Theorem we have
Be m
2 -
8 c
Pr Drupm HMI(M.A..)
max
2o (Pm))
a + m
m
Note that E = C/VK. By setting c 1/Vk, we get the following lemma.
Lemma 6. For query function qt defined in equation [ if our mechanism M is (a, -)smpee
accurate for qt, it is (ACVR + a. (4.3)ddistrbbutional accurate.
By Theorem 2. with probability 1 - 2. for all 12 E H, we have that:
Br, - Bi, - -. (log vk)
1.5 -log
22
S SCVE,
(2)
B
where the second inequality from & = C/VV and the definition of C. Denote the Laplace variables used in Algorithm as ,0, By the union bound, with probability 2
|ay1 I log(4vR/3) for all E Vi Consider the (j + 1 1)th phase. For every time step t E (ty, 1z+1),
since B. Br, <T 5T+ 0j+1 2C log(Avk/0) and B Br.. we have
B. - Bi = Br, B. BB, Bd + Br B, s 3CVV- Log(AVk/B) <ACV.. (3)
Then B./m is LLC/k//m, -)mmppe accurate with respect to qi (D). By Lemma 6 it follows that Be/m is (8Cvk/m, -aceurace w.r.t. EDwpm (gc(()) = Ni/mA. We establish the following lemma of the accuracy guarantee.
Lemma 7. With probability VkB. for all in round starting from No. we have LA B, No
(N, + No) S 8CVK A a.o.
For the Communication complexity, in one round, the total number of received bits by the server is By analysis above, with probability -322, for all j E [VTi, we have
C1 + 02 +.... + CVR.
Vl
Vi
Σ
Cj
$
TT
+
1)
Σ
(T (T+ Jy 1) - Σ 2C vk 2Ck,
(4)
/=1
j=1
Ø=1
Vk
V 2 Σ 3=1
Σ
9
2
Σ
Σ (T-
CVk Ch.
(5)
1=1
1=1
1=1
Therefore, one round, the communication cost is upper bounded by O(Ck). By (5). there are at least Ck = aNv/k/ items received this round, which means increases by an O(1 + av kk/8)) factor after one round. It follows that there are at most O [ rounds. Combined this with the communication cost in one round, we can conclude the final communication complexity is O log Now we are ready to prove Theorem
ovk
Proof of Theorem 7 Since Ng is the exact count at the beginning of round, the Lemma guarantees an o-relative error in the round. Since the lemma holds for any round, the correctness is established.
We set the failure probability as 3 6/(vk: O log )). Since there are 0 logg N
rounds, by the union bound and Lemma 7 it can be concluded that with probability 1 - 6, the output of M is an a-approximate to N at all times. The communication complexity is O CCC log
avE
ooVE
rounds. For l: > 22 there are at most log N rounds. The communication complexity is OCCk log N). Therefore the communication complexity for all regimes of & is OCCk log N + CvE log
Note that we assume that & < 22 and thus there are at most O log N

---

5 Conclusion
In this paper, we study the robustmess of distributed count tracking to adaptive inputs. We present new randomized algorithm that employs differential privacy to achieve robustness. Our new algorithm has near optimal communication complexity. Besides, we introduce a relaxed version of differential privacy, which allows privacy leak of some data points. Based on this definition, we prove new generalization theorem differential privacy, which we believe can be of independent interest and have broader applications.
Acknowledgments and Disclosure of Funding
This work is supported by National Natural Science Foundation of China No. U2241212, No. 62276066.
References
[1] M Dilman and D Raz. Efficient reactive monitoring. In Proceedings IEEE INFOCOM 2001., volume 2, pages 1012-1019. IEEE, 2001.
[2] Brian Babcock and Chris Olston. Distributed top-k monitoring. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 28-39, 2003.
[3] Graham Cormode, Minos Garofalakis, Shanmugavelayuthan Muthukrishhan, and Rajeev Rastogi. Holistic aggregates in networked world: Distributed tracking of approximate quantiles. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 25-36, 2005.
[4] Ram Keralapura, Graham Cormode, and Jeyashankher Ramamirtham. Communication-efficinnn distributed monitoring of thresholded counts. In Proceedings of the 2006 ACM SIGMOD international conference on Munagement of data, pages 289-300, 2006.
[5] Graham Cormode, S Muthukrishnan, and Ke Yi. Algorithms for distributed functional mon- itoring. In 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1076-1085, 2008.
[6] Ke Yi and Qin Zhang. Optimal tracking of distributed heavy hitters and quantiles. In Proceedings of the twenty-eighth ACM SIGMOD-SIGACTTSIGI symposium on Principles of database systems, pages 167-174, 2009.
[7] Chrisil Arackaparambil, Joshua Brody, and Amit Chakrabarti. Functional monitoring without monotonicity. In Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I 36, pages 95-106. Springer, 2009.
[8] Srikanta Tirthapura and David P Woodruff. Optimal random sampling from distributed streams revisited. In Distributed Computing: 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011. Proceedings 25, pages 283-297. Springer, 2011.
[9] Graham Cormode, Shanmugavclayutham Muthukrishnan, Ke Yi, and Qin Zhang. Continuous sampling from distributed streams. Journal of the ACM (JACM), 59(2):1-25, 2012.
[10] David P Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the fouth-fourth annual ACM symposium on Theory of computing, pages 941-960, 2012.
[11] Jiecao Chen and Qin Zhang. Improved algorithms for distributed entropy monitoring. Algorith- mica, 78: 1041-106,,, 2017.
[12] Hao Wu, Junhao Gan, and Rui Zhang. Learning based distributed tracking. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2040-2050, 2020.
10

---

[13] Zengfeng Huang, Ke Yi, and Qin Zhang. Randomized algorithms for tracking distributed count, frequencies. and ranks. In Proceedings of the 31st ACM (CGMOD-SIGACT-SIE symposium on Principles of Database Systems, pages 295-306, 2012.
[14] Omri Ben-Eliezer and Eylon Yogev. The adversarial robustness of sampling. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGA Symposium on Principles of Databuse Systems, pages 49-62, 2020.
[15] Omri Ben-Eliezee Rajesh Jayaram, David P Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. ACM Journal of the ACM (JACM), 69(2):1-33, 2022.
[16] Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense- sparse trade-offs. In Symposium on Simplicity in Algorithms (SOSA), pages 214-227, SIAM, 2022.
[17] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. In Pruceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1671 2022.
[18] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adver- sarially robust streaming algorithms via differential privacy. Advances in Neural Information Processing Systems, 33:147-158, 2020.
[19] Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. Advances in Neural Information Processing Systems, 33:11178-11 17771111900 190, 2020.
[20] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In International Conference on Machine Learning, pages 4112-4140. PMLR, 2022.
[21] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. Advances in Neural Information Processing Systems, 54:3544-3557, 2021.
[22] David P Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1183-1196, IEEE, 2022.
[23] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPles), pages 8:1-8:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl- Leibniz-Zentrum für Informatik.
[24] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20 29, 1996.
[25] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (prelimi- nary report). In Proceedings of the eleventh annual ACM symposium Theory of computing. pages 209-213, 1979.
[26] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 381-390, 2009.
[27] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2010.
[28] Cynthia Dwork, Aaron Roth, et The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4):211-400 407, 2014.
11

---

[29] Cynthia Dwork. Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. Proceedings of the forty-second ACM symposium Theory of computing, pages 715-724, 2010.
[30] T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics, ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
[31] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1046-1059, 2016.
[32] Christopher Jung and Katrina Ligett. A new analysis of differential privacy's generalization guarantees. Innovations in Theoretical Computer Science (ITCS), 2020.
12


Reviews:
[{"review_id": "bQDZRnI5tq", "reviewer": "Reviewer_5Raw", "summary": "The paper considers a distributed count tracking problem introduced at PODS 2012: k parties receive (possibly adversarial) updates to a common counter, and need to communicate with a server to maintain an approximation of the total number of updates received. The goal is to minimize communication from the parties to the server. In PODS 2012 it was shown that communication proportional to $\\sqrt{k}$ is sufficient, improving on a simple deterministic algorithm for which communication is proportional to $k$. The $\\sqrt{k}$ bound was also shown optimal up to polylogarithmic factors. However, the upper bound crucially assumes an oblivious adversary, such that the inputs to the parties may not depend on the estimates reported so far. The present paper shows that this assumption can be removed. The idea is to use techniques from differential privacy, but existing techniques do not apply, so the paper proposes a new version of these techniques that is applicable in the distributed setting.\n\nUPDATE: After reading the review of MMAV and the corresponding rebuttal I am increasing my score slightly.", "questions": "- Can you elaborate on why the results of the paper are of interest for a machine learning audience? Are there, for example, potential implications for federated learning?\n", "limitations": "I would have liked the model to be described more clearly. If my understanding is correct, only communication from sites to the server is counted, while the server is able to broadcast estimates \"for free\" to the sites. It is unclear in what settings this kind of asymmetry in accounting for communication is a good model.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Resolves a decade-old open problem regarding one of the most natural problems in distributed functional monitoring\n- Introduces interesting new techniques for dealing with adaptive, adversarial inputs, which should arguably be the standard model for any dynamic algorithm claiming to be robust\n", "weaknesses": "- The paper does not really try to argue for relevance to machine learning. Unless this is addressed, it would probably be of interest to only a small fraction of NeurIPS attendees.\n- Though adversarial robustness and the connection to differential privacy has been studied in NeurIPS before, this has been in the context of streaming algorithms, which are probably closer to machine learning applications. The paper feels more like a database theory paper than a NeurIPS paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The paper does not really try to argue for relevance to machine learning.  Can you elaborate on why the results of the paper are of interest for a machine learning audience?\n    * First, as we have repeatedly emphasized in our paper, a key contribution of this paper is introducing a new notion of differential privacy and proving a new generalization theorem, which are both highly relevant topics in machine learning. In particular, as we all know, the study of generalization is a central topic in machine learning research. \n     * Second, as another reviewer said, adversarial robustness on streams is a relevant topic for the machine learning community. Recently, a lot of research papers, e.g., [1, 2, 3], on this topic have been published in machine learning conferences like NeurIPS and ICML. We extend centralized streaming to the distributed streaming setting, which is no less relevant, since many real world machine learning scenarios are inherently distributed and the data are received as multiple streams. Moreover, the counting problem studied in this paper is even more basic and ubiquitous than many other problems studied in prior work.\n\n   [1] Hassidim A, Kaplan H, Mansour Y, et al. Adversarially robust streaming algorithms via differential privacy[J]. Advances in Neural Information Processing Systems, 2020, 33: 147-158.\n\n   [2] Cherapanamjeri Y, Nelson J. On adaptive distance estimation[J]. Advances in Neural Information Processing Systems, 2020, 33: 11178-11190.\n\n   [3] Cohen E, Lyu X, Nelson J, et al. On the robustness of countsketch to adaptive inputs[C]//International Conference on Machine Learning. PMLR, 2022: 4112-4140.\n\n2. Only communication from sites to the server is counted. while the server is able to broadcast estimates 'for free' to the sites. \n   \n   * We do count the communication from the server. The communication cost is defined in Section 1.1 (Problem Definitions and Previous Results), which is the **total communication cost between the the server and all sites** (line 88). In fact, we only assume there is a point-to-point communication channel between each site and the server (line 73), so each broadcast is counted as $k$ point-to-point messages, which incur a cost of $O(k)$.\n\n   * Our algorithm has $O(\\log N/\\alpha \\sqrt{k})$ rounds (see section 4.2 Accuracy and Communication , line 334), and there is only one broadcast in each round (see Algorithm 2, line 10), and thus the total communication cost for broadcasting is also $O(\\sqrt{k}\\log N)/\\alpha$, which is bounded by the total communication cost we claimed. We will add explicit explanations in the future version to make this clearer. Thanks for pointing it out.\n"}, {"review_id": "BZScAB9K5Y", "reviewer": "Reviewer_8gDd", "summary": "This work studies adversarially robust count tracking in a distributed computation setting. In particular the work considers a setting with an adaptive adversary that can choose future inputs based on the outputs produced by the server so far. This is in contrast to prior work on distributed count tracking that considers only oblivious adversaries that must choose the entire input stream before the session begins. \n\nThis is the first work to consider robustness against active adversaries in the distributed setting. However, prior work in the central model [18] proves that a differentially private algorithm can be used to extend obliviously robust algorithms to ones that are robust against active adversaries while retaining similar accuracy guarantees. Taking inspiration from [18], this work uses a notion related to differential privacy, and a distributed algorithm that is robust against oblivious adversaries, to construct a distributed algorithm that is robust against active adversaries. Instead of a general black box reduction like in [18] (one that can be applied to any robust algorithm), this work directly modifies some oblivious algorithms to obtain algorithms that are robust against active adversaries. The work additionally argues that the communication complexity of their algorithms is near optimal.", "questions": "Regarding the claim: “the event driven nature of distributed tracking algorithms prevents them from protecting randomness in the DP sense.”\n\n - [With respect to the discussion on pg 4] Why does the fact that the server can update the output only after it receives an input imply that you cannot provide privacy against active attackers in the distributed setting? Why should we expect this to be different than in the central setting? \n\n- In the above claim, are you considering adaptive differential privacy as in  https://arxiv.org/abs/2112.00828? \n\n- Could you explain,  formally, what exactly your claim is?", "limitations": "This paper doesn’t provide a discussion of the privacy consequences of using their partial DP notion to provide privacy in distributed settings. Since this work defines a new notion that they call privacy, I believe it is essential to provide at least some discussion of:\n- the limitations of this new notion \n\n- whether the definition should be expected to provide real world privacy for computations\n\nFinally, if this notion does not indeed provide intuitive individual or group privacy in the setting the authors consider, this should be made very clear – perhaps by calling the notion something other than ’privacy’.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Like the authors mention in their manuscript, and support with a clear discussion: it is very important to study the robustness of streaming algorithms in the presence of  active adversaries since this is a more realistic model of the settings in which these algorithms operate. \n\nThis work provides a distributed count tracking algorithm that is robust against active adversaries while also achieving near optimal communication complexity and accuracy.", "weaknesses": "This work states that the event driven nature of distributed tracking algorithms prevents them from protecting randomness in the DP sense. However, they do not provide a concrete claim or any formal proof  of this fact. The only explanation of this claim is a brief paragraph on page 4 of the manuscript, making it difficult to understand what exactly the authors mean by the statement and also making it difficult to verify if their claim is true. Given that this claim is the central motivation for defining partial differential privacy, I would have hoped for a more thorough treatment of the claim. They also do not define differential privacy against adaptive attackers in the distributed setting.\n\nThis paper doesn’t provide a discussion of the privacy consequences of using their partial DP notion to provide privacy in distributed settings. Since this work defines a new notion that they call privacy, I believe it is essential to provide at least some discussion of:\n- the limitations of this new notion \n\n- whether the definition should be expected to provide real world privacy for computations\n\nMinor comments:\n- Despite switching between discussions of additive and multiplicative error throughout the manuscript, this work does not define accuracy anywhere and often uses the phrase accuracy without an ‘additive’ or ‘multiplicative’ quantifier.\n\n- This work often states that they use ‘differential privacy’ to achieve robustness against active adversaries in the distributed setting, therefore conflating differential privacy with the weaker notion defined in this work.\n\n- The way that the authors phrase the statement that their algorithm does not treat existing oblivious algorithms as a black-box is somewhat misleading. The statement seems to imply that a non black-box use of prior algorithms is generally desirable; However, while a non black-box use of algorithms is sometimes necessary to achieve optimal guarantees – a black-box use of prior algorithms often leads to a more generalizable result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. This paper doesn’t provide a discussion of the privacy consequences of using their partial DP notion to provide privacy in distributed settings. Since this work defines a new notion that they call privacy, I believe it is essential to provide at least some discussion of: the limitations of this new notion? whether the definition should be expected to provide real world privacy for computations?\n\n   * We emphasize that the robust tracking problem studied is not a privacy protection problem per se: we only want to track the answer accurately against an adaptive adversary, and there is *no* privacy concern. According to the framework of [1], what we really need is to prove the algorithm satisfies a generalization result; and informally speaking, DP implies generalization [1], which is the reason why DP is used. A key contribution of this paper is that we show DP is actually not necessary for this purpose, and a relaxed version, namely partial DP, is sufficient. \n\n\n   * So, whether partial DP is a good notion to provide privacy and what are its limitations in privacy sensitive applications are not so relevant to the theme of the paper, since we only care about its generalization performance, for which we provide a rigorous proof. One can call the new notion another name without using the word privacy, but we feel partial DP is appropriate because of its intimate connection to DP.\n\n   \n\n2. About the event driven claim: Why does the fact that the server can update the output only after it receives an input imply that you cannot provide privacy against active attackers in the distributed setting? Why should we expect this to be different than in the central setting?\n\n   * We only claim that, due to the event driven nature, running a centralized DP algorithm on the server does not necessarily provide DP guarantee for all sites; the paragraph on page 4 provide a counterexample. So the framework in [1] is not immediately applicable. However, we do not make a claim that \"this imply that you cannot provide privacy against active attackers in the distributed setting\". In fact, as we have discussed on page 4, sites can protect privacy by adding noise locally, except that this results in a bigger error. \n   * Basically, we provide intuitive reasons why achieving full DP and the same error as in the oblivious setting simultaneously is difficult. In line 171 of page 4, the statement is \"there is a fundamental challenge...\", where we do not claim that this is theoretically impossible; it could be achievable but seems extremely challenging. \n   * On the other hand, we show that partial DP with optimal error is achievable, and more importantly, partial DP has the same robustness guarantee as DP, and thus the fundamental challenge mentioned above is circumvented. To sum up, it is difficult, if not impossible, to apply the old method [1] in our setting (but we have never made this a mathematical statement); The contribution of this paper is that we provide a new method which circumvents this difficulty and solves the problem optimally.\n  \n3. Are you considering adaptive differential privacy as in https://arxiv.org/abs/2112.00828?\n   \n   No. The difference is twofold. First, in their setting, the sensitive dataset is received in a streaming fashion, while in our problem, the actual dataset we want to protect is the random bits used in the randomized tracking algorithm (not the data streams), which are all given in the beginning. Second, they only consider the centralized setting, which is quite different from our distributed setting.\n\n4. Multiplicative or additive error?\n\n   In Section 1.1 (line 86) of our paper, we introduce the objective of our problem, which is to output an estimate within $(1\\pm \\alpha)$ multiplicative error. Our analysis consider each round separately. In each round the count N increase by at most a factor of 2 (see line 273), and thus an $(1\\pm \\alpha)$ multiplicative error is equivalent to an $O(\\alpha) N$ additive error in this round. So we focus on additive error in each round, which is easier to analyze. We appreciate the feedback and will make this clearer in the revised version.\n\n5. Conflating differential privacy with the weaker notion. \n\n   Thanks for pointing it out. We will try to rephrase these statements to avoid such misunderstandings.\n\n6. Statements about non black-box use. \n\n   Sorry for the misunderstandings. We point out the non black-box use is only to emphasize that the techniques and analyses used in our work are very different from existing ones with black-box use.  We agree that a block-box use of priors algorithms is more generalizable. We will try to rephrase these statements in order to mitigate any potential misunderstandings.\n\n\n[1] Hassidim A, Kaplan H, Mansour Y, et al. Adversarially robust streaming algorithms via differential privacy[J]. Advances in Neural Information Processing Systems, 2020, 33: 147-158."}, {"review_id": "ipwQNBBc1i", "reviewer": "Reviewer_W7US", "summary": "The paper provides an algorithm or the distributed count tracking that both enjoys the communication advantage from randomization and is robust to adaptive adversaries. Another contribution of the paper is that it introduces a new *partial differential privacy* definition and completes related generalization theorem that can have potential broader implications.", "questions": "1. I am curious what are potential scenarios that your newly proposed partial DP may be important? It would be helpful to suggest some.\n\n2. Do you think it would be a great idea to briefly mention how the algorithm you propose can be easily adapted for other robust distributed tracking beyond the count tracking?", "limitations": "The authors do not discuss the limitations. \n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "**Originality** The proposed method is novel by creatively designing a new privacy criteria and randomizing the communication to account for adaptive adversaries.\nThe new definition *partial DP* and the generalization theorem will be useful for other stream data setting.\n\n**Quality**  The theoretical analysis looks sound; the authors can verify the efficient tradeoffs among privacy, accuracy, and communication of the proposed method.\n\n**Clarity** The problem is well-defined and clearly stated. The method and the analysis are connected smoothly.\n\n**Significance** The problem being solved is important. The new DP definition can have broader impact for other private ML tasks.", "weaknesses": "**No experiments** Could you please justify why you think experiments are not needed in your paper? Because you claim your proposed method is the first robust tracking algorithm in the domain, it seems important to offer some baseline experiments to help future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. No experiments.\n\n   Our primary focus is on the theoretical aspects of the problem. Since the robustness of an algorithm against all possible adversaries, which is a desirable property, can only be established by theoretical proofs, we think a thorough theoretical study is of higher priority. However, we acknowledge the value of incorporating experimental studies as a complementary perspective to our theoretical findings. We will make efforts to conduct experimental studies and make the code available to facilitate future work. \n\n2. What are the potential scenarios that your newly proposed partial DP may be important?\n\n   * Firstly, partial DP should be an important tool for designing robust distributed tracking algorithms, as the event-driven nature poses challenges in achieving differential privacy with a moderate level of noise. Even in the centralized streaming setting, where DP is achievable, partial DP could potentially simplify the design and analysis of robust algorithms, since it is always easier to satisfy partial DP than DP.\n  \n   * From a broader perspective, we believe that the generalization property of partial DP can find wider applications beyond robust algorithms design. In any application using the generalization property of differential privacy, one can consider replacing DP with the less stringent partial DP.  \n\n3. Do you think it would be a great idea to briefly mention how the algorithm you propose can be easily adapted for other robust tracking beyond the count tracking ?\n\n   Thank you for the suggestion. Count tracking is a key building block for tracking heavy hitters and quantiles [1], so we think by combining techniques from [1], it is not difficult to adapt our algorithm for such problems. On the other hand, many other tracking problems can differ significantly , it remains a good research problem whether the algorithm in this work can be directly applied to other tracking problems. However, the challenge of privacy protection posed by the event-driven nature is inherent in all tracking problems, and thus we believe that the generalization theorem of partial differential privacy developed in this work can be a helpful tool in general. We will provide a briefly discussion on this in the revision.\n\n[1] Zengfeng Huang, Ke Yi, and Qin Zhang. Randomized algorithms for tracking distributed count,\nfrequencies, and ranks. \n"}, {"review_id": "qsRAdQ5sk3", "reviewer": "Reviewer_MMAV", "summary": "This paper studies adversarial robustness for the problem of counting on distributed streams, where the input may be adaptive based on previous outputs by a protocol across $k$ sites and the objective is for a central server to output an additive $\\alpha m$ approximation to the stream of length $m$. When the input is oblivious, there is a randomized protocol that uses $\\tilde{O}(\\sqrt{k}/\\alpha)$ communication, which improves upon a deterministic protocol using $\\tilde{O}(k/\\alpha)$ communication. However, it is not clear how the protocol behaves when the input is adaptive. This paper gives a protocol that uses $\\tilde{O}(\\sqrt{k}/\\alpha)$ communication, showing there is essentially no overhead for adversarial inputs.\n\nThe algorithm works by having each site split its input into blocks and notify the central server if its number of updates within a server block surpasses a certain randomized threshold. Whereas a previous work in adversarially robust streaming used sparse vector technique and differential privacy to protect the internal randomness of the algorithm, the challenge is that distributed streams are event based, and so sparse vector technique will not work. Instead, this paper proposes a new notion of partial differential privacy and shows that not only does it handle generalization with respect to the sample accuracy, but also the distributional accuracy. Thus the output is close to its expectation, which circumvents a complicated analysis of the estimator.", "questions": "Is it possible to think of partial differential privacy to protect a certain set of elements in the manner of carefully distributing the privacy budget as in [20]?\n\nEDIT: I acknowledge receipt of the author response and am currently choosing to maintain my score.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "There are multiple solid contributions by this paper. \n- Firstly, it introduces the problem of adversarial robustness to distributed streams. \n- Secondly, it gives an algorithm that shows there is no overhead for the counting problem, which is not clear at all a priori. \n- Thirdly, the paper introduces the concept of partial differential privacy and proves interesting generalization properties of partial differential privacy. The paper notes that partial differential privacy may be of independent interest. \n- There is a good summary of related work for adversarial robustness, the central techniques in those works, and why they do not apply in this setting. \n- Adversarial robustness on streams is a relevant topic for both the machine learning and theory communities.", "weaknesses": "- The communication cost is actually $O(k+\\sqrt{k}(\\log N)/\\alpha)$ rather than $O(\\sqrt{k}(\\log N)/\\alpha)$, so the regime of improvement is for $k>\\frac{1}{\\alpha^2}$, though it should be noted that this same weakness is also present in previous work [13] on oblivious distributed streams. Nevertheless this should be corrected in the formal guarantees.\n\n- While there is a good summary of related work for adversarial robustness and why they do not apply in this setting, it is not clear why natural modifications to the techniques of [13] would not work. \n\nMinor comments:\n\n- It should be noted that $\\tilde{O}$ is being used to suppress polylogarithmic terms in $N$, rather than $\\tilde{O}(f)=O(f)\\cdot\\text{polylog(f)}$, due to the notation $\\tilde{\\sqrt{k}/\\alpha}$ to mean $O(\\sqrt{k}(\\log N)/\\alpha)$. \n\n- [18] is \"Hassidim\" rather than \"Hasidim\" (note the correct spelling in [21])\n\n- Line 294: \"the the\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n1. The communication cost is actually $O(k+ \\sqrt{k}(\\log⁡ N)/\\alpha)$ rather than $O(\\sqrt{k}(\\log⁡ N)/\\alpha)$,  so the regime of improvement is for $k > 1/\\alpha^2$, though it should be noted that this same weakness is also present in previous work [13] on oblivious distributed streams. Nevertheless this should be corrected in the formal guarantees.\n\n   It is true that the communication cost is $O(k\\log N + \\sqrt{k}\\log N/\\alpha )$; thanks for pointing this out and we will make this clear in the revision. However, $O(k\\log N + \\sqrt{k}\\log N/\\alpha )$ is still always better than $O({k}\\log N/\\alpha)$, which is the deterministic bound.\n\n2. While there is a good summary of related work for adversarial robustness and why they do not apply in this setting, it is not clear why natural modifications to the techniques of [13] would not work.\n\n   Thanks for the question. It is not impossible to obtain robust algorithms by applying natural modifications to oblivious algorithms. However, to prove such modifications actually achieve robustness can be very challenging, since we need to rule out all adaptive adversarial strategies and the posterior distribution of the random bits after adaptive interactions can be extremely difficult to analyze. This is a common challenge in both distributed and centralized streaming settings and is the main motivation behind techniques such as the DP framework, which provide analytical tools for proving robustness. \n\n3. Minor comments.\n\n   Thanks for your comments. We will correct them in the revision.\n\n4. Is it possible to think of partial differential privacy to protect a certain set of elements in the manner of carefully distributing the privacy budget as in [20]?\n\n   There are similarities between the two techniques. However, they are quite different in several aspects. First of all, the overall framework in [20] still require full DP to apply the \"DP to generalization\" theorem. On the contrary, our partial DP notion is a strict relaxation on that. The relaxation is essential, since it is difficult, if not impossible, to achieve full DP without sacrificing communication in our setting, due to the event-driven nature. \n\n   More technically, [20] applies the revised sparse vector technique of [KMS]: it removes data points participating in too many \"meaningful queries\" to protect their privacy. However, in our problem the privacy budget of each data point is not \"smooth\": a single query can make it completely revealed; and we cannot anticipate such events beforehand and remove the data before it is revealed. This motivates us to define partial DP which allows privacy leakage on a small subset. In some sense, the privacy leaked set plays the same role as the deleted set in their framework, except that the deleted set in their framework is still private while the privacy leaked set is not. \n\n   For applications of DP where only their generalization is concerned, partial DP can be an alternative tool to the revised sparse vector technique of [KMS]. It is easier to use since it doesn't need to do privacy budget control explicitly and there is no need to track which data points are compromised. For example, we may simply apply the standard sparse vector technique without removing data points and prove that it satisfies partial DP. This can potentially simplified the design and analysis of robust algorithms. \n\n\n [HKM+] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, Uri Stemmer. Adversarially robust streaming algorithms via differential privacy.\n\n[KMS] Haim Kaplan, Yishay Mansour, Uri Stemmer, The Sparse Vector Technique, Revisited."}]

Author rebuttal:

Meta-review: This paper studies adversarial robustness for the problem of counting on $k$ distributed streams, where the input may be adaptive based on previous outputs by a protocol across the streams sites and the objective is for a central server to output an additive approximation
Prior work handles the case when the adversary is oblivious. This paper gives a protocol for the adaptive adversary that uses $\tilde O(\sqrt{k})$ communication communication, matching the rate known for the oblivious case. This resolves a problem open since 2012. The analysis relies on techniques from differential privacy that have been introduced in the context of adaptive data analysis. In particular, it proposes a new notion of partial differential privacy and shows that not only does it handle generalization with respect to the sample accuracy, but also the distributional accuracy.
Decision: Accept (poster)