  Differential privacy with gradual expiration models the setting where data
items arrive in a stream and at a given time $t$ the privacy loss guaranteed
for a data item seen at time $(t-d)$ is $\epsilon g(d)$, where $g$ is a
monotonically non-decreasing function. We study the fundamental
$\textit{continual (binary) counting}$ problem where each data item consists of
a bit, and the algorithm needs to output at each time step the sum of all the
bits streamed so far. For a stream of length $T$ and privacy $\textit{without}$
expiration continual counting is possible with maximum (over all time steps)
additive error $O(\log^2(T)/\varepsilon)$ and the best known lower bound is
$\Omega(\log(T)/\varepsilon)$; closing this gap is a challenging open problem.
  We show that the situation is very different for privacy with gradual
expiration by giving upper and lower bounds for a large set of expiration
functions $g$. Specifically, our algorithm achieves an additive error of $
O(\log(T)/\epsilon)$ for a large set of privacy expiration functions. We also
give a lower bound that shows that if $C$ is the additive error of any
$\epsilon$-DP algorithm for this problem, then the product of $C$ and the
privacy expiration function after $2C$ steps must be
$\Omega(\log(T)/\epsilon)$. Our algorithm matches this lower bound as its
additive error is $O(\log(T)/\epsilon)$, even when $g(2C) = O(1)$.
  Our empirical evaluation shows that we achieve a slowly growing privacy loss
with significantly smaller empirical privacy loss for large values of $d$ than
a natural baseline algorithm.
