Differential Privacy on Fully Dynamic Streams

This paper is about answering linear queries on a fully dynamic stream while preserving differential privacy. Previous work has only worked on insertion only streams where an element is never deleted. Moreover, the insertion only algorithms can be extended to fully dynamic but with a rather high error: their error is a function of $|D_t|$, the size of the dataset at time t. In a fully dynamic stream, if the number of elements ever inserted until time t is $N_t$, naively using insertion only algorithms gives an error that is a function of $N_t$ and not $|D_t|$, while $|D_t|$ can be much smaller than $N_t$.

This work shows how to use an insertion only algorithm in a blackbox way and get same errors in terms of the size of the dataset at time t. Their approach consists of many interesting components. First they introduce a dynamic interval tree that can cope with deletions and any query can be answered by only inspecting log t nodes. If $D^+_t$ is the set of nodes ever inserted up to time t and $D^-_t$ is the set of nodes deleted on or before t, they compute a linear query by computing it on $D^+_t$ minus its value on $D^-_t$. Their second component is "restarts", where they compute a query from scratch on $D_t$ using a static algorithm instead of computing it on $D^+_t$ and $D^-_t$. They do these restarts when almost half of the elements in a tree node are deleted, and this way they can control the error to be in a function of $|D_t|$. Their third component is a clever distribution of privacy budget which is not novel on its own but is nicely used.

This paper studies privately answering linear queries that are union-preserving (i.e., $f(D_1\cup D_2)=f(D_1)+f(D_2)$) in the turnstile streaming model. Prior works mainly focus on insertion-only streams, as most of the DP tools can be naturally attuned in this model. Note that simply treats a turnstile stream as two insertion-only streams is not enough, as popular private mechanisms have square root dependencies on the size of the set, doing so would lead to undesirable bound on the error. Thus, to obtain reasonable error bound on turnstile streams, the authors use a novel online interval tree to keep track of the lifespan of elements. This is significantly different from classical interval trees, where all intervals are known in advance. Authors show that it is possible to maintain the intervals in an online fashion while not blowing up the complexity of the data structure significantly. Using this data structure, authors show that the problem is then reduced to a deletion-only problem, but running an insertion-only algorithm is not enough, so the proposed algorithm restarts the data structure when half of the elements are deleted. With some extra caveats being taken care of, the authors arrive at a private algorithm for linear queries over turnstile streams.

The paper tackles continual release of differentially-private answers for fully dynamic (turnstile) data streams, where elements may be both inserted and deleted. While previous work handled insertion-only streams or the static setting, the authors design a black-box transformation that turns any static DP mechanism for a union-preserving family of queries (e.g. linear queries) into a mechanism that operates on fully dynamic streams with only a polylogarithmic loss in accuracy and running-time.

The core technical contribution is an online interval tree that stores each item in at most one node per tree level, permitting a decomposition of the data set at time $t$ into $O(\log t)$ disjoint parts that can each be handled by an insertion-only sub-mechanism .

A careful choice of parameters bounds the cumulative privacy loss while keeping the error blow-up within polylogarithmic factors. In particular, plugging private multiplicative weights as the static algorithm, they achieve $\tilde O(\sqrt{|D_t|})$ error for approximate DP and $\tilde O(|D_t|^{3/4})$ for pure-DP. Here $|D_t|$ is the size of the current dataset $D_t$. Notably, there is no dependence on the number of queries for linear queries, whereas straightforward extensions of prior insertion-only works would result in polynomial dependence on the number of queries.

While differential privacy (DP) oftentimes imposes a challenging trade-off between utility and privacy in the static setting, dynamic algorithms add another factor tearing this trade off apart, which is time (or number of updates). The authors of the submission present a construction for a dynamic, $(\epsilon, \delta)$-DP algorithm for any union-preserving query (e.g., linear queries), given a static, $(\epsilon', \delta')$-DP algorithm. A query $f$ is union preserving on multisets $D_1, D_2$ if $f(D_1 \cup D_2) = f(D_1) + f(D_2)$. For linear queries, using the DP multiplicative weights mechanism, their fully dynamic algorithm achieves an error of $\tilde{O}(n_t^{2/3})$ for pure DP ($\delta=0$), and $\tilde{O}(\sqrt{n_t})$ for approximate DP with a multiplicative $O(\log^2 t)$ blow-up in time, where $n_t$ is the size of the dynamic dataset at time $t$. This improves over existing constructions with similar error bounds but which are only partially dynamic (insertions or deletions), and fully dynamic constructions with error bounds that that are linear in $t$. For union-preserving queries, the bound is a bit more complex: Given a static DP mechanism with an of error $\alpha^{(k)}$ when transformed into an insert-only mechanism via appropriate standard techniques, roughly speaking, the resulting dynamic error bound is $\alpha^{(\log^2 t)}$, and dependencies on $\epsilon, \delta$, size of the dataset are substituted by themselves multiplied by a $O(\log^3 t)$ or $O(1/\log^3 t)$ factor. The running time is claimed as the running time of the static black-box algorithm on $n_t$ times $O(\log^2 t)$.

This paper introduces a new black-box mechanism that integrates any given algorithm for the private linear query problem with the binary tree mechanism to construct an algorithm for private query release under continual observation. This method achieves lower additive error for the streaming turnstile model than that indicated by prior work. For context, the private linear query problem simply asks the data curator to return the result of an arbitrary set of linear (counting) queries under the constraints of $\varepsilon$-differential privacy - prior work shows that this is possible with additive error $\sqrt{n}/\varepsilon$, where $n$ is the size of the private data set. The continual observation setting requires the data curator to accept modifications to the data set (insertions, deletions, or no change) in a stream, and respond to the set of queries after every update. A general-purpose technique in the privacy literature to deal with queries with an additive structure (union-preserving, as mentioned by the authors) is to use the binary mechanism of Chan et. al., that essentially allows one to use batch algorithms for the query release problem and suffer additive error that is inflated by a factor that is only polylogarithmic in the length of the stream, despite making a release after each new stream element (naive privacy accounting would lead to a $\sqrt{T}$ additive error when the stream is of length $T$ instead which is much worse).

It is observed by the authors that for the turnstile setting, this general purpose method suffers the drawback that the net error is not $\sqrt{n}\log^c T$ for some $c$ but instead on the order of $(\sqrt{n_+} + \sqrt{n_{-}}) \log^c T$, where $n_+$ s the number of insertions and $n_-$ is the number of deletions. For long streams, clearly this is much (potentially arbitrarily) worse than the former. The main contribution of this paper is a new algorithm that achieves additive error with only a $\sqrt{n}$ term.

Methods: The algorithm suggested is essentially a modification of the binary tree mechanism (maintaining a copy of the batch algorithm at each internal node of a binary tree over the stream), where one backtracks to tag nodes with 'liveness' interval endpoints when deletions are made. Just as in the binary tree mechanism, multiple copies of an element are maintained at each level, so are they here, but instead of each element only being added to the nodes corresponding to the dyadic intervals in which it lies, it is added to all nodes whose interval happens to lie within the liveness interval of that element. This leads to the possibility of double counting when a query is made, to deal with this one considers only the responses from the batch algorithm at `left' nodes.

To achieve the main improvement, the algorithm refreshes the privacy budget of each internal node when half the elements it carried previously are deleted, which ensures that the additive error remains on the order of $\sqrt{n}$. The restart points themselves can be privatized with the Sparse Vector Technique (SVT). Refreshing the budget in this manner is not too wasteful because this can happen only logarithmically many times for any node over the course of the stream.

This paper gives a black-box method that can be used to go from a private linear query algorithm to a private query release algorithm that works in dynamic streams where elements may be inserted or deleted. The construction presented improves better parameters than existing algorithms and works on fully dynamic streams in contrast with insertion-only streams. The paper achieves nearly optimal dependence on the length of the stream (up to polylog factors). The reviews do not identify any significant weakness except recognizing that these techniques are unlikely to work beyond linear (or more specifically, a union-preserving family) or queries. I think this paper is quite impressive because of the generality and (near) optimality of the result, resolving questions that several papers had looked at. In addition, some reviewers thought that the paper was well written. Because of these reasons, I would like to recommend this paper for a spotlight. The discussion was collegial. The issues identified by the reviewers were very minor, and addressed well by the authors.