Continual Counting with Gradual Privacy Expiration

This paper studies the continual counting problem, under a “relaxed” privacy notion, where the privacy budget is a function of time, aka differential privacy with expiration functions. This notion, proposed by Bolot et al.[2], captures the settings where data becomes less sensitive with time. The paper proposes an algorithm based on the pan-private tree-based mechanism of Dwork et al. [12]. They show that this algorithm verifies DP with expiration function $g(d) \sim 1 + \log^\lambda(d)$, which improves on the constant $g(d) = \log(T)$ expiration function of directly using the analysis of Chan et al [6], or the $g(d) = 2\log(d + 1) +2$ of directly analysing the pan private tree-based mechanism of Dwork et al. [12].

The paper studies differential privacy with gradual expiration models, gives upper and lower bounds for a large set of expriation functions $g$. The proposed algorithm can achieve an additive error of $O(log(T) / \epsilon)$, matching the lower bound. Empirical evaluationshows that the algorithm can achieve smaller privacy loss.

Modern DP solutions are often working in the setting where the new data is coming daily. However, DP doesn't allow querying the data indefinitely; therefore, all of these solutions are either treating database as partitioned by time, or refresh the budget on some schedule.

Both of these approaches are not ideal, this paper studies an alternative solution: it assumes that older data is less sensitive, therefore releasing more information about the past is ok. Using this definition, it proposes continual release schemes that gives better utility guarantees than solutions in the case where there is no privacy expiration.

This paper studies a variant of the continual release model of differential privacy where the privacy parameter degrades (potentially smoothly) with time, i.e., the $\epsilon$ associated with changing a datapoint at time $t$ is $\epsilon g(T-t)$ (the model was introduced by Bolot et al.). This model makes sense when a datapoint becomes less important to hide with time. This model also makes sense in the face of two facts about vanilla differential privacy under continual release: a) natural problems are subject to strong lower bounds, b) In practical implementations, it is often assumed that the privacy budget 'renews' each day, and a privacy expiration function could allow for a more smooth decay of the privacy of a datapoint.

The main results of the authors are as follows: a) They show that assuming a logarithmic privacy loss function ($g(d) \approx \log d$), a variant of the binary tree mechanism gives $O(\log T)$ error (absolute difference). In contrast, in the vanilla privacy model, the best known error is $O(\log^2 T)$ and a long open problem is whether $O(\log T)$ is achievable. This paper shows that under the weaker notion of privacy, this error is achievable. They use a variant of the binary tree mechanism inspired by pan-privacy (adding $Lap(1/\epsilon)$ noise to each interval). Intuitively, a change at tilmestep $t$ would only affect intervals between timestep $t$ and $T-t$ that include datapoint $t$, which is roughly $\log (T-t)$ intervals so composing over these intervals would give privacy degradation $g(d) \approx \log d$.

b) They also show a richer tradeoff between privacy degradation functions (which are roughly offset polylogarithmic functions) and error via a more careful variant of the binary tree mechanism.

c) They use a packing argument to argue that these tradeoffs are tight in the worst case.

This paper studies the DP counting problem in the continual release setting. The difference between the problem studied by this paper and the standard problem is that it allows earlier change of the element has a more relaxed privacy budget. The high level idea is to follow the previous pan-private continual counting framework but with different noise setup.

This paper considers a continual counting problem in the privacy expiration model of [Bolot et al., ICDT 2013]. The input here is a stream $x_1, \\dots$; the goal is to, after receiving each $x_t$, release an estimate of the sum $x_1 + \\dots + x_t$. The privacy expiration model states that, for each $x_i$, the privacy loss after step $t$ can increase as $t - i$ increases; namely, it can be $\\epsilon \\cdot g(t - i)$ for some non-decreasing function $g$. The main result of this paper is that, for a large class of function $g$, there is an algorithm with ($\\ell_{\\infty}$-)error $O(\\log T / \\epsilon)$, which improves on the standard model (where $g$ is a constant) whose best known error is $O(\\log^2 T / \\epsilon)$. The algorithm is based on the so-called binary tree mechanism [Dwork et al.; Chan et al.] with two main changes: (i) delaying the release of recent $x_i$ by ignoring them completely as long as $t \\leq i + B$ for some $B$ and (ii) adjusting the privacy budget allocation of each level of the tree. In addition to this, the authors also provide a lower bound which is tight for some setting of $g$.

Overall, even though the algorithm is a simple modification of a known algorithm, the algorithm is clean & practical and it demonstrates the power of the privacy expiration model, which might offer an alternative solution to the standard continual release setting. Furthermore, given that the continual counting algorithm is a subroutine for many algorithms, it is likely that the result in this paper can be used to build other algorithms in this model. Due to this, we recommend accepting this paper as a poster.