Consider the last time step $T$. As $T \ge t > t(i)$, $K_{(i)}$ was not updated at time $T$. Since $j\leq k\cdot c_{\max}$, at time $T$ either the condition in line <ref> was false or the condition in line <ref> was false. Therefore $g_i(h^T)<K_{(i)}^{T}+\err{k\cdot c_{\max}}+\alpha_{U}+\alpha_{SV}$.
Then by <ref>, $ g_i(\histshort^{t(i)})\geq K_{(i)}^{T}-K-C-\alpha_{U}-\err{k\cdot c_{\max}} $. These two equations together give

\begin{equation}
\label{eq:hThti}
g_i(\histshort^{T}) - g_i(\histshort^{t(i)}) \le K + C + 2 \alpha_{U} + \alpha_{SV} + \errkcmax
\le K + 3C + \errkcmax
\end{equation}

The error for outputting $g_i$ at any timestep $t$ in an interval $[p_{j-1},p_j)\subseteq[t(i),T]$ and at $t=T$ is now bounded by

\begin{align*}
&\leq |g_i(\histshort^{T})-g_i(\histshort^{t(i)})|+\err{k\cdot c_{\max}}\\
&\leq K + 3C + 2\err{k\cdot c_{\max}} \tag*{(by Equation~\ref{eq:hThti})} \\
&=O(\epsilon^{-1}(k\ln(k\cdot c_{\max}/\beta)+\ln(T/\beta))+\err{k\cdot c_{\max}})
\numberthis \label{eq:topkoutputerror}
\end{align*}

Thus Equations <ref> and <ref> together give a bound on $|g_i(h^t) - g_i(s^{p_j-1})|$ in both cases.
For any time $t$ that belongs to interval $j$, the values of $g_i$ on the true histogram are $(g_1(h^{t}), g_2(h^t), \ldots, g_k(h^t))$, and the values output by Algorithm <ref> are $(g_1(s^{p_{j-1}}), g_2(s^{p_{j-1}}), \ldots, g_k(s^{p_{j-1}}))$. Thus the error of the algorithm is given by

\begin{align*}
\alpha
&= \max_{t \in T} \max_{i \in [k]} |g_i(h^t) - g_i(s^{p_{j-1}})| \tag*{(where $j$ is the interval that $t$ belongs to)} \\
&\le  \max_{t \in T} \max_{i \in [k]} O(\epsilon^{-1}(k\ln(k\cdot c_{\max}/\beta)+\ln(T/\beta))+\err{k\cdot c_{\max}}) \tag*{(by Equations~\ref{eq:topkacc3} and \ref{eq:topkoutputerror})} \\
&\le O(\epsilon^{-1}(k\ln(k\cdot c_{\max}/\beta)+\ln(T/\beta))+\err{k\cdot c_{\max}})
\end{align*}

This then gives us the following lemma.

Algorithm <ref> is $(\alpha, \beta)$-accurate, with $\alpha = O(\epsilon^{-1}(k\ln(k\cdot c_{\max}/\beta)+\ln(T/\beta))+\err{k\cdot c_{\max}})$.

§ DOUBLING MECHANISM FOR

In this section, we deal with $k$ queries from the same query class as in the last section. We show how to divide the stream into segments, such that within each segment, the value of $\max_i g_i(\histshort(t))$ approximately doubles.
Our algorithm outputs approximate answers to all $k$ queries at the end of each segment.
In the next section we will combine this with the algorithm from the previous section to get an algorithm for estimating $k$ queries without the requirement of being given an upper bound $c_{\max}$.

As earlier, the algorithm works by using the sparse vector technique for computing the partition, and “resetting" privacy at the end of each segment by computing a differentially private histogram.
In this algorithm, the $\epsilon/2$-differentially private histogram is computed using the Laplace mechanism (Fact <ref>), by adding fresh Laplace noise scaled with $2d/{\epsilon}$ to the running column sums every time a segment closes. The full algorithm is given in Algorithm <ref>.

Doubling Mechanism for $\kquery$

Stream $x^1, x^2, \ldots, x^T \in \{0,1\}^d$.
End of each segment together with an estimate of the histogram at that time step.
$p_0 \leftarrow 0$, $j \leftarrow 1$

$s_i \leftarrow 0$ for all $i \in [d]$

$\T_j \leftarrow 1$, $\tilde{\T}_j \leftarrow \T_j + \Lap(4/\epsilon)$

$t \in [T]$
$s_i = s_i + x_i^t$ for all $i \in [d]$

$s \leftarrow (s_1, s_2, \ldots, s_d)$

$\max g_i(s) + \Lap(8/\epsilon) > \tilde{\T}_j$ and $j < \log T$
$\cross_j \leftarrow t$, $j \leftarrow j+1$

$s_i \leftarrow s_i + \Lap(2d/\epsilon)$

$\T_j \leftarrow 2 \cdot \T_{j-1}$, $\tilde{\T}_j \leftarrow \T_j + \Lap(4/\epsilon)$

output $\left( t, s_1, s_2, \ldots, s_d \right) $

§.§ Privacy

We fix some notation. Let

* $\mu_t$ be the $\Lap(8/\epsilon)$ noise added to the maximum in <ref>,

* $\tau_j$ be the $\Lap(4/\epsilon)$ noise added to $\T_j$, and

* $\gamma_i^j$ be the $\Lap(2d/\epsilon)$ noise added to $s_i$ at the end of segment $j$ in <ref>.

Algorithm <ref> satisfies $\epsilon$-differential privacy.

Note that Algorithm <ref> can be seen as post-processing of Algorithm <ref> with $g=\max_i g_i$, $\Delta=\log T$, $K_j=2^{j-1}$, and $s_i=0$ for all $i\in [d]$ using as histogram mechanism $H$ the Laplacian mechanism that
computes a running sum of all inputs and adds fresh Laplace noise scaled with $\Lap(2d/\epsilon)$ to each coordinate. Then we only need to prove that  $H$  is an $(\epsilon/2)$-differentially private in the adaptive continual observation model.  By Fact <ref> this follows directly if $H$ is  $(\epsilon/2)$-differentially private.
Now note that $H$ is $(\epsilon/2)$-differentially private by parallel composition and the choice of parameter $2d/\epsilon$ for the Laplace mechanism, since the inputs to $H$ only differ at a single time step, and the $L_1$ norm of the difference is at most $d$.

§.§ Accuracy

Let $\ell$ be the total number of segments produced by the algorithm, which is a random variable that is upper bounded by $\log T$, and let $\Gamma_i^j = \sum_{k=1}^j \gamma_i^k$.

With probability $\ge 1 - \beta$, the following bounds hold simultaneously
for all $t \in [T]$, $j \in [\log T]$, and $i \in [d]$:

\begin{equation}
\label{eq:kmu_conc}
|\mu_t| \le \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) =: \alpha_{\mu}
\end{equation}

\begin{equation}
\label{eq:ktau_conc}
|\tau_j| \le \frac{4}{\epsilon} \cdot \log\left(\frac{3 \log T}{\beta}\right) =: \alpha_{\tau}
\end{equation}

\begin{equation}
\label{eq:kcross_conc}
|\Gamma_i^j| \le \frac{4d}{\epsilon} \cdot \sqrt{2j} \cdot \log\left(\frac{3 d\log T}{\beta}\right)
\end{equation}

In the algorithm, there are $T$ instances of $\mu_t \sim \Lap(8/\epsilon)$, and at most $\log T$ instances of $\tau_j \sim \Lap(4/\epsilon)$. Applying <ref> and <ref>, we obtain the first two bounds each with probability $\ge 1 - \beta/3$.

Thus, using the concentration bound for the sum of $j$ Laplace variables given in <ref> with $b = 2d/\epsilon$, $k = j$, $\beta_S = \beta/(3 d\log T)$  gives us the third bound with probability $\ge 1 - \beta/3$. Union bound over all three sets of bounds gives us the lemma.

* $\alpha_{\mu} = \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right)$,

* $\alpha_{\tau} = \frac{4}{\epsilon} \cdot \log\left(\frac{3 c_{\max}}{\beta}\right)$,

* $L = \Ldef$,

* $\alpha_{\Gamma} = \frac{4d}{\epsilon} \cdot \sqrt{2 L} \cdot \log\left(\frac{3d\log T}{\beta}\right)$, and

* $\alpha_{DM} = \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} + L$.

Let $c_{\max} = \max_i g_i(h^T)$ be the maximum query value on the entire stream.
We first upper bound  the number $\ell$ of segments generated (and for which an output was generated in <ref> by the algorithm by $L$,  which is roughly $\tO (\log c_{\max} + \log d)$. Note that there might be one more segment that ends because the stream terminates. We do not count it here as Algorithm <ref> does not generate any output for it.

If the random variables are bounded as in <ref>,
then Algorithm <ref> creates at most $L$ segments.

A trivial upper bound of $\log T$ on $\ell$ is obtained from the stopping condition of the algorithm in <ref>. At time $\cross_{\ell}$ when the last segment was closed
we have that for $i = \argmax_k g_k(s^{\cross_{\ell}})$,

\begin{align*}
g_i(s^{\cross_{\ell}}) + \mu_{\cross_{\ell}}
&\ge 2^{\ell} + \tau_{\ell}.
\end{align*}

Let $h^t$ be the true histogram at time $t$.
Assuming that the noises being bounded as stated in <ref> and taking $i^* = \argmax_k g_k(h^{\cross_{\ell}})$, we have that $g_i(h^{\cross_{\ell}}) \le g_{i^*}(h^{\cross_{\ell}})$.

\begin{align*}
&\le g_i(s^{\cross_{\ell}}) + \mu_{\cross_{\ell}} - \tau_{\ell} \\
&= g_i(h^{\cross_{\ell}}) + \Gamma_i^{\ell} + \mu_{\cross_{\ell}} - \tau_{\ell} \\
&\le g_{i^*}(h^{\cross_{\ell}}) + \Gamma_i^{\ell} + \mu_{\cross_{\ell}} - \tau_{\ell} \tag*{(by definition of $i^*$)}\\
&\le g_{i^*}(h^{\cross_{\ell}}) + \frac{4d}{\epsilon} \cdot \sqrt{2\ell} \cdot \log\left(\frac{3 d\log T}{\beta}\right)  + \alpha_{\mu} + \alpha_{\tau}. \numberthis \label{eq:koutput_error}
\end{align*}
We now get that

\begin{align*}
\ell
&\le \log \left[ c_{\max} + \frac{4d}{\epsilon} \cdot \sqrt{2\ell} \cdot \log\left(\frac{3 d \log T}{\beta}\right) + \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) + \frac{4}{\epsilon} \cdot \log\left(\frac{3\log T}{\beta}\right) \right] \\
&\le \log \left[ c_{\max} + \frac{4d}{\epsilon} \cdot \sqrt{2\ell} \cdot \log\left(\frac{3 d \log T}{\beta}\right) + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \right] \\
&\le \log \left[ c_{\max} + \frac{4\sqrt{2}}{\epsilon} \cdot d\sqrt{\log T} \cdot \log\left(\frac{3 d\log T}{\beta}\right) + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \right] \numberthis\label{eq:kLbound} \\
&\le \log c_{\max} + \log \frac{4\sqrt{2}}{\epsilon} + \log d + \frac{1}{2} \log {\log T} + \log \log\left(\frac{3 d\log T}{\beta}\right) + \log \frac{12}{\epsilon} + \log \log\left(\frac{3T}{\beta}\right) \tag*{(upper bounding log of sum by sum of logs)} \\
&\le \Lval \\
\end{align*}

as required, where the third inequality follows from $\ell \le \log T$.

We use this to show that the $s_i$ values in Algorithm <ref> are at most
$\alpha_{\Gamma} = \frac{4d}{\epsilon} \cdot \sqrt{2 L} \cdot \log\left(\frac{3d\log T}{\beta}\right)$
away from the true column sums at all times.

Assume that the random variables are bounded as in <ref>. Let $t \in [T]$ and $i \in [d]$. Then
$| s_i^t - h_i^t | \le \alpha_{\Gamma} = O\left(\frac{d \sqrt{L} \cdot \log ( d \log T/\beta)}{\epsilon}\right)$.

Assuming that the noises being bounded as stated in <ref> we get an upper bound of $L$ on the number of segments from <ref>.
Let $j$ be the segment to which time $t$ belongs. Then

\begin{align*}
| s_i^t - h_i^t |
&= | h_i^t + \Gamma_i^j - h_i^t|\\
&\le \frac{4d}{\epsilon} \cdot \sqrt{2j} \cdot \log\left(\frac{3 d\log T}{\beta}\right) \\
&\le \alpha_{\Gamma}
\end{align*}

as required.

We finally bound the true maximum query value increase in a single segment.

Assume that the random variables are bounded as in <ref>. Then in Algorithm <ref>, the true maximum query value $\max_i g_i(h)$ for segment $j$ increases by at most
$2^{j-1} + 2\alpha_{DM}$, where $\alpha_{DM} = \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} + L = O \left( \frac{d \sqrt{L} \log ( d\log T/\beta) + \log (T/\beta)}{\epsilon} \right)$.

We condition on the noises being bounded as in <ref>. Recall that the time interval $(p_{j-1}, p_j]$ is the $j^{th}$ segment.
First assume that either $j < \ell$ or otherwise  $j=\ell$ and the condition in <ref> was true at time $p_j$. Let $M_t= \max_i g_i(h^t)$ be the true maximum query value at time $t$, and $\T_j$ be the $j^{th}$ threshold value. Then

\begin{align*}
|M_{p_j} - M_{p_{j-1}}|
&\le |\T_j - \T_{j-1}| + |M_{p_j} - \T_j| + |M_{p_{j-1}} - \T_{j-1}|
\end{align*}

The definition of $\T_j$ directly gives us that $|\T_j - \T_{j-1}| = 2^{j-1}$. Thus our task reduces to bounding $|M_{p_j} - \T_j|$ for all $j$.
We do this in two parts. Let $g_{max}(s^t) = \max_i g_i(s^t)$ be the maximum query value on the noisy histogram at time $t$. First, using <ref> and the fact that $\max_i g_i$ is a sensitivity $1$ function, we get that for all $t$,

\begin{equation}
\label{eq:kLog_Mt_bound}
|M_{t} - g_{max}(s^{t})|
\le \alpha_{\Gamma}.
\end{equation}

As the random variables are bounded as in <ref>
and since at time $p_j$ the threshold was crossed, we have that

\begin{align*}
&> \T_j - \alpha_{\mu} - \alpha_{\tau}.
\end{align*}

Putting these two equations together, we get that

\begin{align*}
M_{p_j} - K_j
&> - \left( \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} \right).
\end{align*}

This gives us a lower bound on the value of $M_{p_j}$. Now we show an upper bound.
Let $t < p_j$ be the last time step in which a segment was not closed. If a segment was closed at every time step until $p_j$ of the algorithm, then let $t= 0$.
Since at every time step between $t$ and $p_j$ a segment must have been closed and the total number of segments is at most $\ell$, we get that $t \ge p_j - \ell$. Let $k$ be the segment that $t$ belonged to. If $t=0$, we set $k = s_{max}^0 = K_0 = 0$ in the following equation. Then at time $t$,

\begin{align*}
&\le K_k + \alpha_{\mu} + \alpha_{\tau}
\end{align*}

Using Equation <ref> and the above equation, we get

\begin{equation}
\label{eq:kLogMK}
M_t \le K_k + \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma}
\end{equation}

Since $t \ge p_j - \ell$ and the $\max_i g_i$ is a sensitivity one function,

\begin{equation*}
M_t \ge M_{p_j} - \ell
\end{equation*}

Since the thresholds do not decrease with time, $K_{j} \ge K_k$. Note that $\ell \le L$ by <ref>. Using these two facts, and substituting the above equation into Equation <ref>, we get that

\begin{align*}
M_{p_j} - K_j
&\le \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} + L
= \alpha_{DM}
\end{align*}

Thus putting it all together, we get that

\begin{align*}
|M_{p_j} - M_{p_{j-1}}|
&\le 2^{j-1} + 2 \cdot \alpha_{DM} \\
\end{align*}

as required.
Now, for $j=\ell$, if the condition in <ref> was false, we have two cases. First, assume $\ell=\log T$. Then at time $p_{l-1}$, we have

\begin{align*}
g_{max}(s^{p_{\ell-1}})+\mu_{p_{\ell-1}}> K_{\ell-1}+\tau_{\ell-1}=T/2+\tau_{\ell-1}
\end{align*}

and therefore

\begin{align*}
\end{align*}

Since $M_{p_{\ell}}\leq M_{T}\leq T$, we have

\begin{align*}
M_{p_{\ell}}-M_{p_{\ell-1}}\leq T/2+\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}=2^{\ell-1}+\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}.
\end{align*}

Second, assume $\ell< \log T$. Then

\begin{align*}
g_{max}(s^{p_j})\leq K_j+\alpha_{\mu}+\alpha_{\tau},
\end{align*}

and thus

\begin{align*}
M_{p_j}\leq K_j+\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}.
\end{align*}

Since the threshold was crossed at time $p_{j-1}$, we have

\begin{align*}
M_{p_{j-1}}\geq K_{j-1}-(\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}).
\end{align*}

\begin{align*}
|M_{p_j}-M_{p_{j-1}}|=M_{p_j}-M_{p_{j-1}}&\leq (K_j-K_{j-1})+2(\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma})\\
&\le 2^{j-1} + 2 \alpha_{DM}
\end{align*}

which proves the claim.

With probability at least $1 - \beta$, we simultaneously have the following guarantees from Algorithm <ref>.

* The total number of segments produced by the algorithm is upper bounded by $L = \Ldef$,

* The difference between the noisy and the true histogram at all times stored by the algorithm is upper bounded by $\alpha_{\Gamma} =O\left(\frac{d \sqrt{L} \cdot \log ( d \log T/\beta)}{\epsilon}\right)$, and

* The true maximum query value increase within segment $j$ is at most $2^{j-1} + 2\alpha_{DM}$, where $\alpha_{DM} = O \left( \frac{d \sqrt{L} \log ( d\log T/\beta) + \log (T/\beta)}{\epsilon} \right)$.

Assume that the Laplace random variables in Algorithm <ref> are bounded as in <ref>. Then the three points of the theorem follow from Lemmas <ref>, <ref>, and <ref> respectively.

§ TWO-LEVEL MECHANISM FOR

In this section, we combine the two mechanisms from the previous two sections to get an algorithm for . The first level of the mechanism is the same as Algorithm <ref>, which partitions the input stream into segments. For each such segment the second level algorithm is called, which is a modified version of Algorithm <ref> and is given in  Algorithm <ref>. The main difference  to Algorithm <ref> is that it does not start each column sum from 0, but instead it is given as input (1) a noisy histogram to initialize each column sum, (2) an upper bound on the amount of noise in the histogram, and (3) an upper bound on how much the maximum query value (with the given initial column sum values) can increase. The error of the input histogram has to be taken into account in the new partitioning algorithm, which results in a slightly more complicated algorithm than Algorithm <ref>. The full two-level algorithm is given in Algorithm <ref>.

Two-Level Mechanism for

Stream $x^1, x^2, \ldots, x^T \in \{0,1\}^d$.
Estimate of $g_i(\histshort(t))$ for all $i\in [k]$ and all $t\in[T]$
$L \leftarrow \Lval $

$\alpha_{\Gamma} \leftarrow \frac{4\sqrt{2}}{\epsilon} \cdot d\sqrt{L} \cdot \log \left( \frac{3 d \log T}{\beta} \right) $

$\alpha_{DM} \leftarrow \frac{12}{\epsilon} \cdot \log \left( \frac{3T}{\beta} \right) + \alpha_{\Gamma} + L $

$p_0 \leftarrow 0$, $j \leftarrow 1$

$s_i \leftarrow 0$ for all $i \in [d]$

$\T_j \leftarrow 1$, $\tilde{K}_j \leftarrow \T_j + \Lap(4/\epsilon)$

Initialize Alg <ref> with parameters $(0, s_1, s_2, \ldots, s_d, \alpha_{\Gamma}, \strlen, T)$

$t \in [T]$
$s_i = s_i + x_i^t$ for all $i \in [d]$

$s \leftarrow (s_1, s_2, \ldots, s_d)$

$\max g_i(s) + \Lap(8/\epsilon) > \tilde{\T}_j$ and $j < \log T$
$p_j\leftarrow t$, $j \leftarrow j+1$

$s_i \leftarrow s_i + \Lap(2d/\epsilon)$

$\T_j \leftarrow 2 \cdot \T_{j-1}$, $\tilde{\T}_j \leftarrow \T_j + \Lap(4/\epsilon)$

Terminate current Alg <ref>;

Initialize new Alg <ref> instance with parameters $(t, s_1, s_2, \ldots, s_d, \alpha_{\Gamma}, \strlen, T)$

output $(g_1(s), g_2(s), \ldots, g_k(s))$

feed $x^t$ to Alg <ref>

output returned value of Alg <ref>

Modified Mechanism for

Stream $x^{t_0+1}, x^{t_0+2}, \ldots, x^{t_{\infty}} \in \{0,1\}^d$, start time $t_0$, noisy estimates $s_i^{t_0}$ for $i \in [d]$ with error $\le \alpha_{\Gamma}$, error bound $\alpha_{\Gamma}$, max query value increase bound $\Delta$, stream length bound $T$, an adaptively $(\epsilon/2, \delta)$-DP continuous histogram mechanism $H$, additive error bound $\err{n}$ on all outputs of $H$ that holds with probability $\ge 1 - \beta/3$ when $H$ is run on a stream of length $n$
Estimate of the query values $g_i(\histshort(t))$ for all $i \in [k]$ at every time step $t \in [t_0, t_{\infty}]$.
Initialize an adaptively $(\epsilon/2,\delta)$-differentially private continuous histogram mechanism $H$ for stream length $k\Delta$

$p_0 \leftarrow 0$, $j \leftarrow 1$

$c_i = 0$, and $s_i = s_i^{t_0}$ for all $i \in [d]$$s_i$s are initialized with input noisy sums
$C\leftarrow 18\cdot \epsilon^{-1}\cdot\left(k\ln(6k\cdot \Delta/\beta)+\ln(6T/\beta)\right)$

$\T \leftarrow 3(C+\err{k\cdot\Delta}+\alpha_{\Gamma})$

$\tau\leftarrow \Lap(6/\epsilon)$

$\T_{(i)} \leftarrow g_i(s^{t_0}) + \T$, $\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau $ for all $i\in [k]$

$\textrm{out} \leftarrow \left( g_1(s^{t_0}), g_2(s^{t_0}), \ldots, g_k(s^{t_0}) \right) $

$t \in [t_0,T]$

$c_i \leftarrow c_i + x_i^t$, $s_i \leftarrow s_i + x_i^t$ for all $i \in [d]$

$\exists i\in[k]$: $g_i(s)+\mu>\tilde{\T}_{(i)}$ and $j\le k\Delta$
$p_j\leftarrow t$,
$j \leftarrow j+1$Close the current segment
insert $(c_1,\dots,c_d)$ into $H$, reset $c_i \leftarrow 0$ for all $i \in [d]$

$i\in [k]$
$\tilde{g_i}(s)\leftarrow g_i(s)+\Lap(3k/\epsilon)$

$\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau$ for all $i \in [k]$

$(s_1,\dots,s_d) \leftarrow$ output$(H)$ + $(s_1^{t_0}, s_2^{t_0}, \ldots, s_d^{t_0})$ Current count from the histogram mechanism
$\textrm{out} \leftarrow (g_1(s),\dots,g_k(s))$

output out

In this section we will refer to Algorithm <ref> without the lines referring to Algorithm <ref> as the doubling mechanism, and to Algorithm <ref> as the modified BoundedMaxQuery mechanism.

§.§ Privacy

Algorithm <ref> satisfies $2\epsilon$-differential privacy.

We deal with the outputs of the calls to Alg <ref> separately from the outputs of Alg <ref> in <ref>.

Let $x$ and $y$ be two neighboring input streams.
First, note that since the instantiations of the modified BoundedMaxQuery mechanism do not affect the outputs on <ref>, we can use <ref> to prove that the doubling mechanism (since the outputs in <ref> of the two-level mechanism are exactly the same as run on the doubling mechanism) is $\epsilon$-differentially private. Now we condition on all the internal random variables (namely, the Laplace random variables in Lines <ref>, <ref>, <ref>, and <ref>) of the two-level mechanism  being fixed such that both
$x$ and $y$ lead to the same sequence of segments, and argue about the privacy of the various modified BoundedMaxQuery mechanisms.
Since the segments produced by the doubling mechanism are fixed, all the modified BoundedMaxQuery mechanisms operate on disjoint parts of the stream. Each instantiation of the modified BoundedMaxQuery mechanism is $\epsilon$-dp by Lemma <ref>.

Since they operate on disjoint parts of the stream, by parallel composition, all instantiations of the modified BoundedMaxQuery mechanism together satisfy $\epsilon$-DP.
Naïve sequential composition now gives us the $2\epsilon$-DP guarantee.

§.§ Accuracy

§.§.§ Algorithm kKnownMod

We first analyze the accuracy of Algorithm <ref>, assuming that the input noisy column sums given to the algorithm are at most an additive error $\alpha_{\Gamma}$ away from the true column sums, and that the increase in the true maximum query value is bounded by $\Delta$. This property is shown to hold for the two-level algorithm with probability $\ge 1 - \beta$ in Lemmas <ref> and <ref>, and with $\Delta = 2^j + 2\alpha_{DM}$.

Let $t \in [T]$ be an arbitrary time step, let $s^{t}$ denote the value of $s$ at time $t$, and $\histshort^{t}$ be the value of the true histogram at time $t$.
In the following let $\alpha_{SV}:=12\epsilon^{-1}(\ln(6k\cdot \Delta/\beta)+\ln(6T/\beta))$ and
$\alpha_U := \epsilon^{-1}6k\ln(3k\cdot \Delta/\beta)$.
We condition on the following  upper bounds on the additive error, which together hold with probability $1-\beta$:

* The error of $H$ is bounded by $\err{k\cdot \Delta}$. By assumption, this holds with probability $1-\beta/3$.

* Adding the same random variable $\tau$ with $\Lap(6/\epsilon)$   distribution to all $K_{(i)}$  gives an additive error of at most  $\epsilon^{-1}6\ln(6k\cdot \Delta/\beta)$ with probability $1-\beta/6$ by Fact <ref> and the union bound, since  we sample for that variable at most $k\cdot \Delta$ times.

* The random variable $\mu$ with $\Lap(12/\epsilon)$ distribution drawn at every time steps gives an additive error of at most $\epsilon^{-1}12\ln(6T/\beta)$ by Fact <ref> and the union bound with probability $1-\beta/6$.

Together with the previous condition we have

* If the condition in line <ref> is true for $i$ at time $t$, then $g_i(s^t)>K_{(i)}-\alpha_{SV}$

* If the condition in line <ref> is false for $i$, then $g_i(s^t)<K_{(i)}+\alpha_{SV}$.

for $\alpha_{SV}=12\epsilon^{-1}(\ln(6k\cdot \Delta/\beta)+\ln(6T/\beta))$

* We add $\Lap(3k/\epsilon)$ noise  to $g_i$ in line <ref> at most $k\cdot \Delta$ times for each $i\in[k]$. Thus, by Fact <ref> and the union bound, with probability $1-\beta/3$
at most an additive error of
$\epsilon^{-1}3k\ln(3k^2\cdot \Delta/\beta)\leq \epsilon^{-1}6k\ln(3k\cdot \Delta/\beta)=\alpha_{U}$ is added to $g_i$ for any $i$ and any time step.

We now proceed as follows:
Recall that $p_j$ denotes the end of the $j$th time interval and that $p_0 = t_0$.
To prove accuracy we will first show an auxiliary lemma that says that $p_1 > t_0 + 1$. Next fix any $i \in [k]$ and let $p_l$ and $p_r$ be any two time steps such that $K_{(i)}$ is updated at $p_l$ and $p_r$ but not between them. Then  we show that
$g_i$ must have increased by more than 1 between $p_l$ and $p_r$. The latter fact implies that $K_{(i)}$ was not updated at time $p_r-1$, which can be used to get an upper bound on $g_i(h^{p_r-1})$ and, by the 1-sensitivity of $g_i$, also on $g_i(h^{p_r})$.
As $K_{(i)}$ was updated at time $p_l$, we also have a lower bound on $g_i(h^{p_l})$. Combining the two gives
an upper bound on
$|g_i(h^{p_r}) - g_i(h^{p_l})|$ of $O(K + \alpha_{SV} + \alpha_U)$,
which is the crucial bound needed to upper bound $|g_i(h^{t}) - g_i(s^t)|$.

In the rest of the section let $K_{(i)}^t$ denote the value of $K_{(i)}$ at time $t$ when we reach Line <ref> of Algorithm <ref>. To show that $p_1 > t_0 + 1$, we first show that whenever the $i$th threshold is updated, the true value of $g_i$ is not much smaller than the threshold that was crossed.

Suppose the $i$th threshold $K_{(i)}$ is updated at time $t$. Then

\[
g_i(\histshort^{t})\geq K_{(i)}^{t}-C-\alpha_{U}-\err{k\cdot \Delta} - \alpha_{\Gamma}.
\]

This follows from the sensitivity of $g_i$ and the fact that $K_{(i)}$ was updated at time $t$.

\begin{align*}
&\ge g_i(s^t) - \errkcmax - \alpha_{\Gamma} \tag*{(since $g_i$ has sensitivity $1$)} \\
&\ge \tilde{g_i}(s^{t})-\alpha_{U} - \errkcmax - \alpha_{\Gamma} \\
&\ge K_{(i)}^{t}-C-\alpha_{U} - \errkcmax - \alpha_{\Gamma} \tag*{(since $K_{(i)}$ is updated at time $t$)}
\end{align*}

as required.

It holds that $p_1 > 1$.

Note that variable $C$ in Algorithm <ref> is larger than $\alpha_{SV}+\alpha_{U}$.
Thus, if the condition in line <ref> is true for some $i$ at time $p_j$, then the condition in line <ref> is also true for the same $i$. Thus, whenever we close a segment, we also update at least one threshold, say the $i$th one. Using <ref> with $t = p_j$ gives us that

\[
g_i(h^{p_j}) \ge K_{(i)}^{p_j}-C-\alpha_{U} - \errkcmax - \alpha_{\Gamma}
\]

Note that since $K>C+\err{k\cdot \Delta}+\alpha_{U} + \alpha_{\Gamma}$,  this implies $g_i(\histshort^{p_1}) > 1$. As $g_i$ increases by at most $1$ per time step, it follows that $p_1>1$.

Next we show an upper bound on the true query values when a threshold is updated.

Let $i \in
Let $p_r$ be a timestep where threshold $K_{(i)}$ is updated. Then $g_i(\histshort^{p_r})<K_{(i)}^{p_r}+\err{k\cdot \Delta}+\alpha_{SV}+\alpha_U + \alpha_{\Gamma}+1$.
Further, let $l$ and $r$ be integers such that $p_l$ and $p_r$ are two consecutive time steps where threshold $K_{(i)}$
is updated. Then  $p_r - p_l > 1$ and $|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|>1$.

We show the claim by induction over the number of updates of $K_{(i)}$.
As $p_r$ is a time step where $K_{(i)}$ is updated,  the condition in line <ref> is true, and, thus $r\leq k\cdot \Delta$.

Case 1: If $p_r$ is the first time that threshold $K_{(i)}$ is updated, then $p_r\geq p_1>1$ by Lemma <ref>. As the threshold was not updated before, it was not updated at time $p_r-1$. This fact and the fact that $r\leq k\cdot \Delta$ imply that either the condition in line <ref> was false or the condition in line <ref> was false for $i$ at time $p_r-1$.
Thus, either

and hence,
$$g_i(\histshort^{p_r-1})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\errkcmax + \alpha_{\Gamma}.$$

As $g_i$ has sensitivity $1$ and $\histshort^{p_r}$ and $\histshort^{p_r-1}$ differ by at most 1 in each coordinate, it holds that $g_i(\histshort^{p_{r}})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_{\Gamma}+1$.

Case 2: If $p_r$ is not the first time threshold $K_{(i)}$ is updated, let $p_l$ be the last time at which threshold $K_{(i)}$ was updated before $p_r$. By induction, we have $g_i(\histshort^{p_{l}})<K_{(i)}^{p_l}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_\Gamma+1=K_{(i)}^{p_r}-K+\alpha_{SV}+\alpha_U+\err{k\cdot\Delta}+\alpha_\Gamma+1$. Since the threshold $K_{(i)}$ is updated at time $p_r$, we have $g_i(\histshort^{p_{r}})\geq K_{(i)}^{p_r}-C-\alpha_U-\err{k\cdot \Delta}-\alpha_\Gamma$ by <ref> for $t = p_r$. Thus,

\begin{align*}
|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|&>K_{(i)}^{p_j}-C-\alpha_{U}-\err{k\cdot \Delta}-\alpha_\Gamma\\
&\ \ -(K_{(i)}^{p_r}-K+\err{k\cdot \Delta}+\alpha_{SV}+\alpha_U+\alpha_\Gamma+1)\\
&=K-C-2\err{k\cdot \Delta}-\alpha_{SV}-2\alpha_{U}-2\alpha_\Gamma-1>1,
\end{align*}

since $K=3(C+\err{k\cdot \Delta}+\alpha_\Gamma)$ and $C>\alpha_{SV}+\alpha_U$. Thus, $p_r-p_l>1$, and as $g_i$ has sensitivity 1, the threshold $K_{(i)}$ was not updated at time $p_r-1$. Now by the same argument as before, $g_i(\histshort^{p_r-1})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_\Gamma$ and therefore $g_i(\histshort^{p_r})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_\Gamma+1$.

Let $t(i)$ be the last time in the whole input sequence that $K_{(i)}$ was updated,
let $p_l$ be the last time before $t$ that $K_{(i)}$ was updated, and let $p_r$ be the first time step at or after $t$  at which $K_{(i)}$ gets updated, i.e., $p_r \ge t$.

Case A:  $t \le t(i)$, i.e., there exists a time step $\ge t$ at which $K_{(i)}$ is updated.  First, we show by induction an upper bound on $g_i(\histshort^{p_r})$.

Now, by Lemma <ref> applied to $p_r$ and <ref> applied to $p_l$, we get

\begin{align*}
|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|&<K_{(i)}^{p_r}+\err{k\cdot \Delta}+\alpha_{SV}+\alpha_U+\alpha_\Gamma+1\\
&\ \ -(K_{(i)}^{p_l}-K-C-\alpha_{U}-\err{k\cdot \Delta}-\alpha_\Gamma)\\
&=K+C+2\err{k\cdot \Delta}+\alpha_{SV}+2\alpha_{U}+2\alpha_\Gamma+1.
\numberthis\label{eq:ktopkacc2}
\end{align*}

The error for outputting $g_i$ at any time step $t$ in an interval $[p_{j-1},p_j)\subseteq[p_{l},p_r)$ for any $j\leq k\cdot \Delta$ is now bounded by:

\begin{align}
\begin{split}
&\leq |g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|+\err{k\cdot \Delta}+\alpha_\Gamma\\
&\leq K+C+3\err{k\cdot \Delta}+\alpha_{SV}+2\alpha_{U}+3\alpha_\Gamma+1\\
\end{split}
\end{align}

Further, because of Lemma <ref>, every time we update $K_{(i)}$, $g_i(\histshort^{t})$ grows by at least $1$. Since all $g_i(\histshort^{t})$ are bounded by $\Delta$, and every time $j$ is updated at least one threshold is updated, this implies that $j<k\cdot \Delta$ is always true.

Case B:  $t > t(i)$.
Consider the last time step $t_{\infty}$. As $t_{\infty} \ge t > t(i)$, $K_{(i)}$ was not updated at time $t_{\infty}$. Since $j\leq k\cdot \Delta$, at time $t_{\infty}$ either the condition in line <ref> was false or the condition in line <ref> was false. Therefore $g_i(h^T)<K_{(i)}^{T}+\err{k\cdot \Delta}+\alpha_{U}+\alpha_{SV}+\alpha_\Gamma$.
Then by <ref>, $ g_i(\histshort^{t(i)})\geq K_{(i)}^{T}-K-C-\alpha_{U}-\err{k\cdot \Delta} - \alpha_\Gamma $. These two equations together give

\begin{equation}
\label{eq:khThti}
g_i(\histshort^{T}) - g_i(\histshort^{t(i)}) \le K + C + 2 \alpha_{U} + \alpha_{SV} + \errkcmax + 2 \alpha_\Gamma
\le K + 3C + \errkcmax + 2 \alpha_\Gamma
\end{equation}

The error for outputting $g_i$ at any timestep $t$ in an interval $[p_{j-1},p_j)\subseteq[t(i),T]$ and at $t=T$ is now bounded by

\begin{align*}
&\leq |g_i(\histshort^{T})-g_i(\histshort^{t(i)})|+\err{k\cdot \Delta}+\alpha_\Gamma\\
&\leq K + 3C + 2\err{k\cdot \Delta} + 3\alpha_\Gamma \tag*{(by Equation~\ref{eq:khThti})} \\
&=O(\epsilon^{-1}(k\ln(k\cdot \Delta/\beta)+\ln(T/\beta))+\err{k\cdot \Delta}+\alpha_\Gamma)
\numberthis \label{eq:ktopkoutputerror}
\end{align*}

Thus Equations <ref> and <ref> together give a bound on $|g_i(h^t) - g_i(s^{p_j-1})|$ in both cases.
For any time $t$ that belongs to interval $j$, the values of $g_i$ on the true histogram are $(g_1(h^{t}), g_2(h^t), \ldots, g_k(h^t))$, and the values output by Algorithm <ref> are $(g_1(s^{p_{j-1}}), g_2(s^{p_{j-1}}), \ldots, g_k(s^{p_{j-1}}))$. Thus the error of the algorithm is given by

\begin{align*}
\alpha
&= \max_{t \in T} \max_{i \in [k]} |g_i(h^t) - g_i(s^{p_{j-1}})| \tag*{(where $j$ is the interval that $t$ belongs to)} \\
&\le  \max_{t \in T} \max_{i \in [k]} O(\tkinsideo) \tag*{(by Equation~\ref{eq:topkoutputerror})} \\
&\le O(\tkinsideo)
\end{align*}

This then gives us the following lemma.

Algorithm <ref> is $(\alpha, \beta)$-accurate, with $\alpha = O(\tkinsideo)$.

§.§.§ Algorithm kTwo-Level

* $L = \Ldef$,

* $\alpha_{\Gamma} = \frac{4d}{\epsilon} \cdot \sqrt{2 L} \cdot \log\left(\frac{3d\log T}{\beta}\right)$,

* $\alpha_{DM} = \alpha_{\Gamma} + L + 8\epsilon^{-1} \log(3T/\beta)+ 4\epsilon^{-1} \log(3\log T/\beta)$,

We hide $O(\log \log (d, T, k, 1/\epsilon, 1/\beta))$ factors in $\Oll(\cdot)$.

Algorithm <ref> is $(\alpha, 2\beta)$-accurate for , with
$$\alpha = \Oll\left( \epsilon^{-1} \cdot \left( \epsilon \cdot \erractdbl + d\log d \cdot \sqrt{\log (dc_{\max}/\epsilon)} + \log(T/\beta) + k\log(kdc_{\max}/\epsilon\beta) \right)  \right).$$

We first argue about the doubling mechanism.
Using <ref>, we get that the following guarantees simultaneously hold with probability $\ge 1 - \beta$.

* the total number of segments produced by the doubling mechanism is upper bounded by $L$, where $L = \Ldef$,

* for every time step $t \in [T]$, the difference between the true histogram and the noisy histogram stored by the doubling mechanism is upper bounded by $\alpha_{\Gamma} =O\left(\frac{d \sqrt{L} \cdot \log ( d \log T/\beta)}{\epsilon}\right)$, and

* the true maximum query value increase within segment $j$ is at most $2^{j-1} + 2\alpha_{DM}$, where $\alpha_{DM} = O \left( \frac{d \sqrt{L} \log ( d\log T/\beta) + \log (T/\beta)}{\epsilon} \right)$.

We condition on these guarantees.
We now argue about the accuracy when the modified BoundedMaxQuery mechanism returns an output.
For the $j^{th}$ instantiation of the modified BoundedMaxQuery mechanism, the max query value increase bound $\Delta$ is defined as $2^{j-1} + 2 \alpha_{DM}$.
Taking $\beta' = \beta/3L$ in <ref> gives us that the $j^{th}$ modified BoundedMaxSum mechanism has the following accuracy with probability $\ge 1 - \beta/L$

\begin{equation}
\label{ex:kModBMSL}
\alpha =
O \left( \epsilon^{-1} \cdot d\sqrt{L} \cdot \log(d\log(TL/\beta)) +  \errdbl + \epsilon^{-1} \cdot \log (TL/\beta) + \epsilon^{-1} \cdot k \log (Lk\Delta/\beta) \right)
\end{equation}

In what follows, $\Oll$ hides $\log \log(d, k, T, 1/\epsilon, 1/\beta)$ terms.
We first upper bound $\Delta$. Since $j \le L$,

\begin{align*}
\Delta
&= 2^{j-1} + 2 \alpha_{DM}
\le 2^{L} + 2 \alpha_{DM}
\end{align*}

We show that $\alpha_{DM} \le 2^{L+1}$, which lets us obtain an upper bound of $\Delta \le 2^{L+2}$. Recall that
$\alpha_{DM} = L + \alpha_{\Gamma} +\frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) + \frac{4}{\epsilon} \cdot \log\left(\frac{3\log T}{\beta}\right)$.
We bound $L$ trivially by $2^L$. We now bound the rest of the term by $2^L$. First, we bound $\alpha_{\Gamma}$

\begin{align*}
\alpha_{\Gamma}
&= \frac{4d}{\epsilon} \cdot \sqrt{2 L} \cdot \log\left(\frac{3d\log T}{\beta}\right) \\
&\le \frac{4d}{\epsilon} \cdot \sqrt{2\log T} \cdot \log\left(\frac{3d\log T}{\beta}\right) \tag*{(since $L \le \log T$)}
\end{align*}

\begin{align*}
\alpha_{\Gamma} + \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) + \frac{4}{\epsilon} \cdot \log\left(\frac{3\log T}{\beta}\right)
&\le  \frac{4d}{\epsilon} \cdot \sqrt{2\log T} \cdot \log\left(\frac{3d\log T}{\beta}\right) + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \\
&\le c_{\max} + \frac{4d}{\epsilon} \cdot \sqrt{2\log T} \cdot \log\left(\frac{3d\log T}{\beta}\right) + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \\
&\le 2^L \tag*{(by definition of $L$ and (\ref{eq:kLbound}))}
\end{align*}

which gives $\alpha_{DM} \le 2^{L+1}$.
This gives us the required upper bound on $\Delta$ of $2^{L+2}$.
Next, we show that $\log L = \Oll(1)$. This follows, since

\begin{align*}
L &= \Lval
\end{align*}

and so

\begin{align*}
\log L &= \log\log \left( \Linside \right) = \tO(1).
\end{align*}

Plugging in $\Delta \le 2^{L+2}$, $\log L = \Oll(1)$, and $\log \log T = \Oll(1)$ into Equation <ref>, we get

\begin{equation}
\label{eq:kHtobound}
\alpha = \Oll \left( \epsilon^{-1} \cdot \left( d\sqrt{L}\log (d/\beta) + \epsilon \cdot \erractdbl + \log (T/\beta) + k \log (k2^{L+2}/\beta) \right) \right)
\end{equation}

For the last term in the summation,

\begin{align*}
\log 2^{L+2}
= L + 2
&= O(\Lval) \\
&= \Oll(\log (\epsilon^{-2} dc_{\max}))
\end{align*}

In the first term in Equation <ref>, we bound $\sqrt{L}$ as follows

\begin{align*}
\sqrt{L}
&\le \sqrt{\log (20\epsilon^{-2} dc_{\max})} + \sqrt{4\log \log(T/\beta)} + \sqrt{\log\log(3d\log(T/\beta))}
\end{align*}

Since the final two terms are $\Oll(1)$, this reduces to

\begin{align*}
\sqrt{L} \le \Oll\left( \sqrt{\log (dc_{\max}/\epsilon)}\right)
\end{align*}

Plugging these bounds on $d\sqrt{L}\log d$ and $\log 2^{L+2}$ in Equation <ref>, we get

\begin{equation*}
\alpha =
\Oll\left( \epsilon^{-1} \cdot \left( d\log (d/\beta) \cdot \sqrt{\log (dc_{\max}/\epsilon)} +\epsilon \cdot \erractdbl + \log(T/\beta) + k \log(kdc_{\max}/\epsilon\beta) \right) \right)
\end{equation*}

Since there are at most $L$ segments in the two-level mechanism, there are at most $L$ instantiations of Algorithm <ref>. Thus all the accuracy guarantees hold together with probability at least $1 - \beta$.

Combining the guarantees for the two-level mechanism and the modified BoundedMaxQuery mechanism, we get that Algorithm <ref> is $(\alpha, 2\beta)$-accurate for

\begin{align*}
\alpha
&= \Oll\left( \epsilon^{-1} \cdot \left( \epsilon \cdot \erractdbl + d\log (d/\beta) \cdot \sqrt{\log (dc_{\max}/\epsilon)} + \log(T/\beta) + k\log(kdc_{\max}/\epsilon\beta) \right)  \right)
\end{align*}

which proves the claimed accuracy guarantee.

Algorithm <ref> instantiated with the histogram mechanism from Fact <ref> is $(\alpha, 2\beta)$-accurate for , with
$$\alpha = \Oll\left( \epsilon^{-1} \cdot \left(d \log (d/\beta) \cdot \left( \log^2 (dc_{\max}/\epsilon^2) + \log^2 k \right) + \log(T/\beta) + k\log(kdc_{\max}/\epsilon\beta) \right) \right)$$

Using the histogram mechanism from Fact <ref>, we have $\erractdbl = O\left(\epsilon^{-1} \cdot \left( d \ln(dL/\beta)\log^2(k2^{L})\right)\right)$. We start by bounding $\log^2(k2^L)$.

\begin{align*}
\log^2 k2^L
&= \left(L+\log k\right)^2 \\
&\le \left( \Lval \right)^2 \\
&\ \ \ + \log^2 k + (\Lval) \cdot \log k \\
&\le \Oll \left( \log^2 (d c_{\max}/\epsilon^2) + \log^2 k \right)
\end{align*}

\begin{align*}
\erractdbl
&\le \Oll \left( \epsilon^{-1} \cdot d \log (d/\beta) \cdot \left( \log^2 (dc_{\max}/\epsilon^2) + \log^2 k \right) \right)
\end{align*}

Plugging this into the accuracy guarantee in <ref>, the $d \sqrt{\log c_{\max}}$ term is dominated by $\erractdbl$.
This gives

\begin{align*}
\alpha
&= \Oll \left( \epsilon^{-1} \cdot \left( d \log (d/\beta) \cdot \left( \log^2 (dc_{\max}/\epsilon^2) + \log^2 k \right) + \log(T/\beta) + k \log (kdc_{\max}/\epsilon\beta) \right) \right)
\end{align*}

as required.

This bound is
$\alpha= \tO \left(\left(d \log^2 c_{\max} + k\log c_{\max} +\log T\right)\epsilon^{-1}\right)$ as stated in Theorem <ref>.

§ (EPSILON,DELTA)-DIFFERENTIAL PRIVATE ALGORITHM FOR K QUERIES

In this section, we show how to answer $k$ monotone histogram queries with sensitivity $1$ with $(\epsilon, \delta)$-differential privacy, assuming that the maximum query answer on any of them is $c_{\max}$.

Mechanism for answering $k$ queries with $(\epsilon, \delta)$-DP

Stream $x^1, x^2, \ldots, x^T \in \{0,1\}^d$, upper bound $c_{\max}$ on any $g_i$,  an adaptively $\edee$-DP continuous histogram mechanism $H$, additive error bound $\err{n}$ on all outputs of $H$ that holds with probability $\ge 1 - \beta/3$ when $H$ is run on a stream of length $n$.
Estimate of $g_i(\histshort(t))$ for all $i\in [k]$ and all $t\in[T]$
Initialize an adaptively $\edee$-differentially private continuous histogram mechanism $H$ for stream length $k\cdot c_{\max}$

$p_0\leftarrow 0$, $j \leftarrow 1$

$c_i \leftarrow s_i \leftarrow 0$ for all $i \in [d]$

$\alpha_{SV} \leftarrow \edsv$, $\alpha_U \leftarrow \edu$

$C\leftarrow \alpha_{SV} + \alpha_U$

$\T \leftarrow 3(C+\err{k\cdot c_{\max}})$

$\tau\leftarrow \Lap(6/\epsilon)$

$\T_{(i)} \leftarrow \T$, $\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau $ for all $i\in [k]$

$\textrm{out} \leftarrow \left( g_1(\textbf{0}), g_2(\textbf{0}), \ldots, g_k(\textbf{0}) \right) $

$t \in \mathbb{N}$
$c_i \leftarrow c_i + x_i^t$, $s_i \leftarrow s_i + x_i^t$ for all $i \in [d]$

$\exists i\in[k]$: $g_i(s)+\mu>\tilde{\T}_{(i)}$ and $j\le k\cdot c_{\max}$
$p_j\leftarrow t$,
$j \leftarrow j+1$Close the current segment
insert $(c_1,\dots,c_d)$ into $H$, reset $c_i \leftarrow 0$ for all $i \in [d]$

$i\in [k]$
$\tilde{g_i}(s)\leftarrow g_i(s)+\edadd$

$\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau$ for all $i \in [k]$

$(s_1,\dots,s_d) \leftarrow$ output$(H)$ Current count from the histogram mechanism
$\textrm{out} \leftarrow (g_1(s),\dots,g_k(s))$

output out

Let $(g_1,\dots,g_k)$ be $k$ monotone histogram queries with sensitivity $1$. Given an upper bound $c_{\max}$ on the maximum output of any $g_i$ for $i\in[k]$, and an upper bound $T$ on the stream length, there exists an $(\alpha,\beta)$-accurate and $(\epsilon, \delta)$-differentially private algorithm for computing $g_1,\dots,g_k$ at every time step where $\alpha=O(\epsilon^{-1}\ederror+\err{k\cdot c_{\max}})$ and $\err{n}$ is the additive error bound that holds with probability $\ge 1 - \beta/3$ on all outputs of an $(\epsilon, \delta)$-dp continuous histogram mechanism $H$ when $H$ is run on a stream of length $n$.

§.§ Privacy

Let $\epsilon, \delta>0$. If $H$ is an $\edee$-differentially private continuous histogram mechanism, then
Algorithm <ref> satisfies $(\epsilon, \delta)$-differential privacy. This holds independently of the initial setting of $(s_1,\dots, s_d)$, $K$ and $C$.

Let $x$ and $y$ be two neighboring streams that differ at time $t^*$. Let $S$ be a subset of possible outputs of the algorithm
and let $\alg{x}$ be the output stream of Algorithm <ref> with input stream $x$. We show that

\[
\Pr\left[ \alg{x} \in S \right]
\le e^{\epsilon} \cdot \Pr\left[ \alg{y} \in S \right] + \delta
\]

The arguments also hold when swapping the identities of $x$ and $y$ since they are symmetric, which gives us the privacy guarantee. Thus we focus on proving the inequality above.

Privacy game $\Pi_{H,Adv(x,y)}$ for the adaptive continual release model and $k$ queries for histogram mechanism $H$

Streams $x=x^1, x^2, \ldots, x^T \in \{0,1\}^d$ and $y=y^1, y^2, \ldots, y^T \in \{0,1\}^d$ such that $x$ and $y$ are neighboring and differ in time $t^*$, partition bound $\Delta$, initial values $s_1,\dots,s_d$, $K$, $C$

$p_0 \leftarrow 0$, $j \leftarrow 1$

$c^x_i = 0$ for all $i \in [d]$,
$c^y_i = 0$ for all $i \in [d]$

ChallengeOver = False

$\tau\leftarrow \Lap(6/\epsilon)$

$\T_{(i)} \leftarrow \T$, $\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau $ for all $i\in [k]$

$t \in [T]$
$c^x_i = c^x_i + x_i^t$, $s_i = s_i + x_i^t$ for all $i \in [d]$

$c^y_i = c^y_i + y_i^t$ for all $i \in [d]$

$\exists i\in[k]$: $g_i(s)+\mu>\tilde{\T}_{(i)}$ and $j\le \Delta$

$p_j \leftarrow t$, $j \leftarrow j+1$Close the current interval
$p_j\geq t^{*}$ and ChallengeOver=False

output $(c^x,c^y)$

output $c^x$
$i\in [k]$
$\tilde{g_i}(s)\leftarrow g_i(s)+\edadd$

reset $c^x_i \leftarrow 0$, $c^y_i \leftarrow 0$ for all $i \in [d]$

$\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau$ for all $i \in [k]$

receive $(s_1,\dots,s_d) \leftarrow H$

$p_j \leftarrow T$

We use that the histogram mechanisms $H$ is $\edee$-differentially private in the adaptive continual release model. To argue privacy,
define an adversary to model the interaction between the partitioning algorithm and the counting mechanisms, see Algorithm <ref>: We define $Adv(x,y)$ to be Algorithm <ref> run with the setting of parameters corresponding to Algorithm <ref>. It is given as input two neighboring streams $x$ and $y$ differing at time $t^*$. It basically runs Algorithm <ref> on $x$, only for the interval including $t^*$, it outputs both the interval counts for $x$ and the interval counts for $y$. This is the  time step in the game defined in Algorithm <ref>. If $\side=L$, the counts for $x$ are sent to the counting mechanism, if $\side=R$, the counts for $y$ are sent. Note that for the partitioning of the stream, only $x$ and the outputs from $H$ are taken into account. Now, let $S$ be a subset of all possible outputs of Algorithm <ref>. Abusing notation, we say that a view $V$ of the adversary $Adv$ satisfies $V\in S$, if the streams of $(s_1,\dots,s_d)$ received from $H$ match the output sequences in $S$.
We then have

\begin{align*}
\Pr(\mathcal{A}(x)\in S)=\Pr(V_{H,Adv(x,y)}^{(L)}\in S)
\end{align*}

\begin{align*}
\Pr(\mathcal{A}(y)\in S)=\Pr(V_{H,Adv(y,x)}^{(L)}\in S)
\end{align*}

Since by assumption $H$ is adaptively $\edee$-differentially private, we have

\begin{align*}
\Pr(V_{H,Adv(y,x)}^{(R)}\in S)\leq e^{\epsilon/3}\Pr(V_{H,Adv(y,x)}^{(L)}\in S) + \delta/2e^{2\epsilon/3}
\end{align*}

It remains to prove

\begin{align}\label{eq:eviewsxyswitchedK}
\Pr(V_{H,Adv(x,y)}^{(L)}\in S)\leq e^{2\epsilon/3}\Pr(V_{H,Adv(y,x)}^{(R)}\in S) + \delta/2,
\end{align}

since then

\begin{align}\begin{split}\label{eq:efullprivacyK}
\Pr(\mathcal{A}(x)\in S)&=\Pr(V_{H,Adv(x,y)}^{(L)}\in S)\\
&\leq e^{2\epsilon/3}\Pr(V_{H,Adv(y,x)}^{(R)}\in S) + \delta/2\\
&\leq e^{\epsilon}\Pr(V_{H,Adv(y,x)}^{(L)}\in S) + \delta/2 + \delta/2\\
&=e^{\epsilon}\Pr(\mathcal{A}(y)\in S) + \delta
\end{split}
\end{align}

Note that when we run $Adv(x,y)$ on $\side=L$, we partition according to $x$ and the outputs of $H$, and for each interval we give the counts for $x$ as input to $H$. When we run $Adv(y,x)$ on $\side=R$, we partition according to $y$ and the outputs of $H$, and give the counts for $x$  as input to $H$ (since outside of the challenge time step, $c^x_i$ and $c^y_i$ are the same). So in order to prove (<ref>), we argue first that on both runs, the probabilities of getting a given partition into intervals are $e^{\epsilon/3}$-close, and that the probabilities of updating the same thresholds on <ref> are $\esamethresh$ close.
Call the time interval $(\cross_{j-1}, \cross_j]$ the $j^{th}$ interval. If $\ell$ is the value of $j$ when the processing of the input stream ends, set $p_{\ell}=T$.
Note that the probabilities of computing any sequence of intervals $(p_0,p_1],\dots, (p_{j-2},p_{j-1}]$ with $p_{j-1}<t^*$ and $j-1\leq \Delta$ are the same on both $x$ and $y$, since the streams are equal at all time steps before $t^*$.

We want to argue two things: first, that the probability of $p_j=\lambda$ is $e^{\epsilon/3}$-close on $x$ and $y$, for any $\lambda>t^*$, and second, that the probabilities of updating any subset of thresholds is $\esamethresh$-close on $x$ and $y$. First note that if $j>\Delta$, then the stream is ignored after $p_{j-1}$ for both $x$ and $y$, so  $e^{\epsilon/3}$-closeness follows trivially.
If $j \le \Delta$, we condition on all the noises added in the algorithm before time $p_{j-1}$ as well as the randomness of the histogram mechanism up until time $p_{j-1}$.

Fixing a particular time $\lambda > p_{j-1}$, we first show that the probability of interval $j$ ending at $\lambda$ (i.e., $\cross_j = \lambda$) is  $e^{\epsilon/3}$-close on $x$ and $y$. For this to happen, there must exist an $i\in [k]$ with $g_i(s) + \mu > \tilde K_{(i)}$ at time $\lambda$, and never before that in the time steps $(p_{j-1}, \lambda-1]$. We use $s^t(x)$ to denote the value of $s$ at time $t$ on stream $x$.

Let $\mu_t$ be the $\Lap(12/\epsilon)$ noise defined in line <ref> in iteration $t$, and let $\tau_j$ be the current value of $\tau$.
Further denote $s^{t}(x)$ the  vector of $(s_i)_{i\in[d]}$ at time $t$ for stream $x$.
Let $f_X$ be the density of the random variable $X$.
Note that conditioning on all the noises being the same on $x$ and $y$ before $p_{j-1}$, we have that any $s_i$ at time $t\leq p_j$ can differ by at most 1 on $x$ and $y$. Therefore $g_i(s^{t}(x))$ and $g_i(s^{t}(y))$ can also differ by at most 1.

We now have:

\begin{align*}
&\Pr[p_j=\lambda\textnormal{ on } x]=\Pr[g_i(s^{t}(x))+\mu_t\leq K_{(i)}+\tau_j \forall t\in(p_{j-1},\lambda),\forall i\in[k] \wedge \exists i: g_i(s^{\lambda}(x))+\mu_{\lambda}>K_{(i)}+\tau_j]\\
&=\int_{z}\int_c \Pr_{\mu_{p_{j-1}}, \ldots, \mu_{\lambda-1}}[g_i(s^{t}(x))+\mu_t\leq K_{(i)}+z \forall t\in(p_{j-1},\lambda)\forall i\in[k]\wedge \exists i: g_i(s^{\lambda}(x))+c>K_{(i)}+z]\\&\cdot f_{\tau_j}(z)\cdot f_{\mu_t}(c)\ dz\ dc\\
&\leq \int_{z}\int_c \Pr_{\mu_{p_{j-1}}, \ldots, \mu_{\lambda-1}}[g_i(s^{t}(y))+\mu_t\leq K_{(i)}+(z +1)\forall t\in(p_{j-1},\lambda) \forall i\in[k]\wedge \exists i: g_i(s^{\lambda}(y))+(c+2)>K_{(i)}+(z+1)]\\&\cdot f_{\tau_j}(z)\cdot f_{\mu_t}(c)\ dz\ dc\\
&\leq (e^{\epsilon/6})e^{2\epsilon/12}\int_{z}\int_c \Pr_{\mu_{p_{j-1}}, \ldots, \mu_{\lambda-1}}[g_i(s^{t}(y))+\mu_t\leq K_{(i)}+z \forall t\in(p_{j-1},\lambda) \forall i\in[k]\wedge \exists i: g_i(s^{\lambda}(y))+c>K_{(i)}+z]\\&\cdot f_{\tau_j}(z)\cdot f_{\mu_t}(c)\ dz\ dc\\
&=e^{\epsilon/3}\Pr[p_j=\lambda \textnormal{ on } y].
\end{align*}

Next, note that conditioned on all previous outputs of $H$ and $p_j$ being equal, $g_i(s^{p_j}(x))$ and $g_i(s^{p_j}(y))$ can differ by at most $1$ for each $i\in[k]$.
Thus the $L_2$ difference between the two vectors is at most $\sqrt{k}$.
By <ref>,
adding $\edadd$ noise
to each
${g_i}(s^{p_j}(y))$ to create $\tilde{g_i}(s^{p_j}(y))$
ensures that all distributions of $\tilde{g_i}(s^{p_j}(x))$ and $\tilde{g_i}(s^{p_j}(y))$ are $\esamethresh$-close. Since the updating of thresholds only depends on those, this implies that the probabilities of updating any subset of thresholds on $x$ and $y$ are $\esamethresh$-close.

Finally, recall that running $Adv(x,y)$ on $\side=L$ and $Adv(y,x)$ on $\side=R$ both insert the counts for $x$ into $H$, and only differ in the partitioning. Since we have shown that the probabilities that $t^*$ is in a segment $(p_{j-1},p_j]$ on the two runs are $e^{\epsilon/3}$-close, and the probabilities that we update the same thresholds for this interval are $\esamethresh$-close, and since the rest is identical on both runs we have shown (<ref>) and thus (<ref>).

§.§ Accuracy Proof

We analyze the additive error of Algorithm <ref>.
Let $t \in [T]$ be an arbitrary time step, let $s^{t}$ denote the value of $s$ at time $t$, and $\histshort^{t}$ be the value of the true histogram at time $t$.
In the following let $\alpha_{SV:}= \edsv$ and
$\alpha_U := \edu$.
We condition on the following  upper bounds on the additive error, which together hold with probability $1-\beta$:

* The error of $H$ is bounded by $\err{k\cdot c_{\max}}$. By assumption, this holds with probability $\ge 1-\beta/3$.

* Adding the same random variable $\tau$ with $\Lap(6/\epsilon)$   distribution to all $K_{(i)}$  gives an additive error of at most  $\epsilon^{-1}6\ln(6k\cdot c_{\max}/\beta)$ with probability $1-\beta/6$ by Fact <ref> and the union bound, since  we sample for that variable at most $k\cdot c_{\max}$ times.

* The random variable $\mu$ with $\Lap(12/\epsilon)$ distribution drawn at every time steps gives an additive error of at most $\epsilon^{-1}12\ln(6T/\beta)$ by Fact <ref> and the union bound with probability $1-\beta/6$.

Together with the previous condition we have

* If the condition in line <ref> is true for $i$ at time $t$, then $g_i(s^t)>K_{(i)}-\alpha_{SV}$

* If the condition in line <ref> is false for $i$, then $g_i(s^t)<K_{(i)}+\alpha_{SV}$.

for $\alpha_{SV}=12\epsilon^{-1}(\ln(6k\cdot c_{\max}/\beta)+\ln(6T/\beta))$

* We add $\edadd$ noise  to $g_i$ in line <ref> at most $k\cdot c_{\max}$ times for each $i\in[k]$. Thus, by Fact <ref> and the union bound, with probability $1-\beta/3$
at most an additive error of
$\edu=\alpha_{U}$ is added to $g_i$ for any $i$ and any time step.

We now proceed as follows:
Recall that $p_j$ denotes the end of the $j$th time interval and that $p_0 = 0$.
To prove accuracy we will first show an auxiliary lemma that says that $p_1 > 1$. Next fix any $i \in [k]$ and let $p_l$ and $p_r$ be any two time steps such that $K_{(i)}$ is updated at $p_l$ and $p_r$ but not between them. Then  we show that
$g_i$ must have increased by more than 1 between $p_l$ and $p_r$. The latter fact implies that $K_{(i)}$ was not updated at time $p_r-1$, which can be used to get an upper bound on $g_i(h^{p_r-1})$ and, by the 1-sensitivity of $g_i$, also on $g_i(h^{p_r})$.
As $K_{(i)}$ was updated at time $p_l$, we also have a lower bound on $g_i(h^{p_l})$. Combining the two gives
an upper bound on
$|g_i(h^{p_r}) - g_i(h^{p_l})|$ of $O(K + \alpha_{SV} + \alpha_U)$,
which is the crucial bound needed to upper bound $|g_i(h^{t}) - g_i(s^t)|$.

In the rest of the section let $K_{(i)}^t$ denote the value of $K_{(i)}$ at time $t$ when we reach Line <ref> of Algorithm <ref>. To show that $p_1 > 1$, we first show that whenever the $i$th threshold is updated, the true value of $g_i$ is not much smaller than the threshold that was crossed.

Suppose the $i$th threshold $K_{(i)}$ is updated at time $t$. Then

\[
g_i(\histshort^{t})\geq K_{(i)}^{t}-C-\alpha_{U}-\err{k\cdot c_{\max}}.
\]

This follows from the sensitivity of $g_i$ and the fact that $K_{(i)}$ was updated at time $t$.

\begin{align*}
&\ge g_i(s^t) - \errkcmax \tag*{(since $g_i$ has sensitivity $1$)} \\
&\ge \tilde{g_i}(s^{t})-\alpha_{U} - \errkcmax \\
&\ge K_{(i)}^{t}-C-\alpha_{U} - \errkcmax \tag*{(since $K_{(i)}$ is updated at time $t$)}
\end{align*}

as required.

It holds that $p_1 > 1$.

Note that variable $C$ in Algorithm <ref> is larger than $\alpha_{SV}+\alpha_{U}$.
Thus, if the condition in line <ref> is true for some $i$ at time $p_j$, then the condition in line <ref> is also true for the same $i$. Thus, whenever we close a segment, we also update at least one threshold, say the $i$th one. Using <ref> with $t = p_j$ gives us that

\[
g_i(h^{p_j}) \ge K_{(i)}^{p_j}-C-\alpha_{U} - \errkcmax
\]

Note that since $K>C+\err{k\cdot c_{\max}}+\alpha_{U}$,  this implies $g_i(\histshort^{p_1}) > 1$. As $g_i$ increases by at most $1$ per time step, it follows that $p_1>1$.

Next we show an upper bound on the true query values when a threshold is updated.

Let $i \in
Let $p_r$ be a timestep where threshold $K_{(i)}$ is updated. Then $g_i(\histshort^{p_r})<K_{(i)}^{p_r}+\err{k\cdot c_{\max}}+\alpha_{SV}+\alpha_U+1$.
Further, let $l$ and $r$ be integers such that $p_l$ and $p_r$ are two consecutive time steps where threshold $K_{(i)}$
is updated. Then  $p_r - p_l > 1$ and $|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|>1$.

We show the claim by induction over the number of updates of $K_{(i)}$.
As $p_r$ is a time step where $K_{(i)}$ is updated,  the condition in line <ref> is true, and, thus $r\leq k\cdot c_{\max}$.

Case 1: If $p_r$ is the first time that threshold $K_{(i)}$ is updated, then $p_r\geq p_1>1$ by Lemma <ref>. As the threshold was not updated before, it was not updated at time $p_r-1$. This fact and the fact that $r\leq k\cdot c_{\max}$ imply that either the condition in line <ref> was false or the condition in line <ref> was false for $i$ at time $p_r-1$.
Thus, either

and hence,
$$g_i(\histshort^{p_r-1})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot c_{\max}}.$$

As $g_i$ has sensitivity $1$ and $\histshort^{p_r}$ and $\histshort^{p_r-1}$ differ by at most 1 in each coordinate, it holds that $g_i(\histshort^{p_{r}})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot c_{\max}}+1$.

Case 2: If $p_r$ is not the first time threshold $K_{(i)}$ is updated, let $p_l$ be the last time at which threshold $K_{(i)}$ was updated before $p_r$. By induction, we have $g_i(\histshort^{p_{l}})<K_{(i)}^{p_l}+\alpha_{SV}+\alpha_U+\err{k\cdot c_{\max}}+1=K_{(i)}^{p_r}-K+\alpha_{SV}+\alpha_U+\err{k\cdot c_{\max}}+1$. Since the threshold $K_{(i)}$ is updated at time $p_r$, we have $g_i(\histshort^{p_{r}})\geq K_{(i)}^{p_r}-C-\alpha_U-\err{k\cdot c_{\max}}$ by <ref> for $t = p_r$. Thus,

\begin{align*}
|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|&>K_{(i)}^{p_j}-C-\alpha_{U}-\err{k\cdot c_{\max}}-(K_{(i)}^{p_r}-K+\err{k\cdot c_{\max}}+\alpha_{SV}+\alpha_U+1)\\
&=K-C-2\err{k\cdot c_{\max}}-\alpha_{SV}-2\alpha_{U}-1>1,
\end{align*}

since $K=3(C+\err{k\cdot c_{\max}})$ and $C>\alpha_{SV}+\alpha_U$. Thus, $p_r-p_l>1$, and as $g_i$ has sensitivity 1, the threshold $K_{(i)}$ was not updated at time $p_r-1$. Now by the same argument as before, $g_i(\histshort^{p_r-1})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot c_{\max}}$ and therefore $g_i(\histshort^{p_r})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot c_{\max}}+1$.

Let $t(i)$ be the last time in the whole input sequence that $K_{(i)}$ was updated,
let $p_l$ be the last time before $t$ that $K_{(i)}$ was updated, and let $p_r$ be the first time step at or after $t$  at which $K_{(i)}$ gets updated, i.e., $p_r \ge t$.

Case A:  $t \le t(i)$, i.e., there exists a time step $\ge t$ at which $K_{(i)}$ is updated.  First, we show by induction an upper bound on $g_i(\histshort^{p_r})$.

Now, by Lemma <ref> applied to $p_r$ and <ref> applied to $p_l$, we get

\begin{align*}
|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|&<K_{(i)}^{p_r}+\err{k\cdot c_{\max}}+\alpha_{SV}+\alpha_U+1-(K_{(i)}^{p_l}-K-C-\alpha_{U}-\err{k\cdot c_{\max}})\\
&=K+C+2\err{k\cdot c_{\max}}+\alpha_{SV}+2\alpha_{U}+1.
\numberthis\label{eq:etopkacc2}
\end{align*}

The error for outputting $g_i$ at any time step $t$ in an interval $[p_{j-1},p_j)\subseteq[p_{l},p_r)$ for any $j\leq k\cdot c_{\max}$ is now bounded by:

\begin{align}
\begin{split}
|g_i(\histshort^{t})-g_i(s^{p_{j-1}})| &\leq
&\leq |g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|+\err{k\cdot c_{\max}}\\
&\leq K+C+3\err{k\cdot c_{\max}}+\alpha_{SV}+2\alpha_{U}+1\\
&=O(\epsilon^{-1} \edinsideo +\err{k\cdot c_{\max}})\label{eq:etopkacc3}
\end{split}
\end{align}

Further, because of Lemma <ref>, every time we update $K_{(i)}$, $g_i(\histshort^{t})$ grows by at least $1$. Since all $g_i(\histshort^{t})$ are bounded by $c_{\max}$, and every time $j$ is updated at least one threshold is updated, this implies that $j<k\cdot c_{\max}$ is always true.

Case B:  $t > t(i)$.
Consider the last time step $T$. As $T \ge t > t(i)$, $K_{(i)}$ was not updated at time $T$. Since $j\leq k\cdot c_{\max}$, at time $T$ either the condition in line <ref> was false or the condition in line <ref> was false. Therefore $g_i(h^T)<K_{(i)}^{T}+\err{k\cdot c_{\max}}+\alpha_{U}+\alpha_{SV}$.
Then by <ref>, $ g_i(\histshort^{t(i)})\geq K_{(i)}^{T}-K-C-\alpha_{U}-\err{k\cdot c_{\max}} $. These two equations together give

\begin{equation}
\label{eq:ehThti}
g_i(\histshort^{T}) - g_i(\histshort^{t(i)}) \le K + C + 2 \alpha_{U} + \alpha_{SV} + \errkcmax
\le K + 3C + \errkcmax
\end{equation}

The error for outputting $g_i$ at any timestep $t$ in an interval $[p_{j-1},p_j)\subseteq[t(i),T]$ and at $t=T$ is now bounded by

\begin{align*}
&\leq |g_i(\histshort^{T})-g_i(\histshort^{t(i)})|+\err{k\cdot c_{\max}}\\
&\leq K + 3C + 2\err{k\cdot c_{\max}} \tag*{(by Equation~\ref{eq:ehThti})} \\
&=O(\epsilon^{-1}\edinsideo+\err{k\cdot c_{\max}})
\numberthis \label{eq:etopkoutputerror}
\end{align*}

Thus Equations <ref> and <ref> together give a bound on $|g_i(h^t) - g_i(s^{p_j-1})|$ in both cases.
For any time $t$ that belongs to interval $j$, the values of $g_i$ on the true histogram are $(g_1(h^{t}), g_2(h^t), \ldots, g_k(h^t))$, and the values output by Algorithm <ref> are $(g_1(s^{p_{j-1}}), g_2(s^{p_{j-1}}), \ldots, g_k(s^{p_{j-1}}))$. Thus the error of the algorithm is given by

\begin{align*}
\alpha
&= \max_{t \in T} \max_{i \in [k]} |g_i(h^t) - g_i(s^{p_{j-1}})| \tag*{(where $j$ is the interval that $t$ belongs to)} \\
&\le  \max_{t \in T} \max_{i \in [k]} O(\epsilon^{-1}\edinsideo+\err{k\cdot c_{\max}}) \tag*{(by Equations~\ref{eq:etopkacc3} and \ref{eq:etopkoutputerror})} \\
&\le O(\epsilon^{-1}\edinsideo +\err{k\cdot c_{\max}})
\end{align*}

This then gives us the following lemma.

Algorithm <ref> is $(\alpha, \beta)$-accurate, with $\alpha = O(\epsilon^{-1}\edinsideo+ \err{k\cdot c_{\max}})$.

§ DOUBLING MECHANISM FOR (EPSILON, DELTA)-DP

Doubling Mechanism for $\kquery$ with $(\epsilon, \delta)$-DP

Stream $x^1, x^2, \ldots, x^T \in \{0,1\}^d$.
End of each segment together with an estimate of the histogram at that time step.
$p_0 \leftarrow 0$, $j \leftarrow 1$

$s_i \leftarrow 0$ for all $i \in [d]$

$\T_j \leftarrow 1$, $\tilde{\T}_j \leftarrow \T_j + \Lap(4/\epsilon)$

$t \in [T]$
$s_i = s_i + x_i^t$ for all $i \in [d]$

$s \leftarrow (s_1, s_2, \ldots, s_d)$

$\max g_i(s) + \Lap(8/\epsilon) > \tilde{\T}_j$ and $j < \log T$
$\cross_j \leftarrow t$, $j \leftarrow j+1$

$s_i \leftarrow s_i + \doublingN$

$\T_j \leftarrow 2 \cdot \T_{j-1}$, $\tilde{\T}_j \leftarrow \T_j + \Lap(4/\epsilon)$

output $\left( t, s_1, s_2, \ldots, s_d \right) $

§.§ Privacy

We fix some notation. Let

* $\mu_t$ be the $\Lap(8/\epsilon)$ noise added to the maximum in <ref> of Algorithm <ref>,

* $\tau_j$ be the $\Lap(4/\epsilon)$ noise added to $\T_j$, and

* $\gamma_i^j$ be the $\doublingN$ noise added to $s_i$ at the end of segment $j$ in <ref>.

Since the histogram mechanism cumulatively adds Gaussian noise to each coordinate of every input, we get the following lemma.

The continuous histogram mechanism $H$ that cumulatively adds noise $\doublingN$ to each coordinate on every input is $(\epsilon, \delta/e^{\epsilon/2})$-adaptively differentially private.

Algorithm <ref> satisfies $(\epsilon, \delta)$-differential privacy.

From <ref>, the histogram mechanism $H$ which computes a running sum of all inputs and adds fresh normal noise scaled with $\doublingN$ to each coordinate for every new input is $(\epsilon/2, \delta/e^{\epsilon/2})$-adaptively differentially private under continual observation.
Now the lemma follows, since Algorithm <ref> can be seen as post-processing of Algorithm <ref> with $g=\max_i g_i$, $\Delta=\log T$, $K_j=2^{j-1}$, and $s_i=0$ for all $i\in [d]$.

§.§ Accuracy

Let $\ell$ be the total number of segments produced by the algorithm, which is a random variable that is upper bounded by $\log T$, and let $\Gamma_i^j = \sum_{k=1}^j \gamma_i^k$.

With probability $\ge 1 - \beta$, the following bounds hold simultaneously
for all $t \in [T]$, $j \in [\log T]$, and $i \in [d]$:

\begin{equation}
\label{eq:emu_conc}
|\mu_t| \le \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) =: \alpha_{\mu}
\end{equation}

\begin{equation}
\label{eq:etau_conc}
|\tau_j| \le \frac{4}{\epsilon} \cdot \log\left(\frac{3 \log T}{\beta}\right) =: \alpha_{\tau}
\end{equation}

\begin{equation}
\label{eq:ecross_conc}
|\Gamma_i^j| \le \agammaj
\end{equation}

In the algorithm, there are $T$ instances of $\mu_t \sim \Lap(8/\epsilon)$, and at most $\log T$ instances of $\tau_j \sim \Lap(4/\epsilon)$. Applying <ref> and <ref>, we obtain the first two bounds each with probability $\ge 1 - \beta/3$.

Sum of $j$ normal $N(0, \sigma^2)$ random variables is $N(0, j\sigma^2)$. Thus $\Gamma_i^j \sim \jdoublingN$. Using the concentration bound for normal random variables (<ref>) with $\beta_S = \beta/3d\log T$, we get the final guarantee with probability $\ge 1 - \beta/3$.
Union bound over all three guarantees gives the lemma.

* $\alpha_{\mu} = \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right)$,

* $\alpha_{\tau} = \frac{4}{\epsilon} \cdot \log\left(\frac{3 c_{\max}}{\beta}\right)$,

* $L = \Ldef$,

* $\alpha_{\Gamma} = \agammaL$,

* $\alpha_{DM} = \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} + L$.

Let $c_{\max} = \max_i g_i(h^T)$ be the maximum query value on the entire stream.
We first show an upper bound of $L$ which is roughly $\tO (\log c_{\max} + \log d)$ on the number $\ell$ of segments produced by the algorithm.

Assume that the random variables are bounded as in <ref>.
Then Algorithm <ref> creates at most $L = \Ldef $ segments.

We condition on the noises being bounded as stated in <ref>.
A trivial upper bound of $\log T$ on $\ell$ (and thus $L$) is obtained from the stopping condition of the algorithm in <ref>. At time $\cross_{\ell}$ when the last segment was closed[If the last segment was closed at $\cross_{\ell-1}$, then the following holds for $\ell - 1$, which gives the same asymptotic bounds on $\ell$.], we have that for $i = \argmax_k g_k(s^{\cross_{\ell}})$,

\begin{align*}
g_i(s^{\cross_{\ell}}) + \mu_{\cross_{\ell}}
&\ge 2^{\ell} + \tau_{\ell}.
\end{align*}

Let $h^t$ be the true histogram at time $t$. Taking $i^* = \argmax_k g_k(h^{\cross_{\ell}})$, we have that $g_i(h^{\cross_{\ell}}) \le g_{i^*}(h^{\cross_{\ell}})$.

\begin{align*}
&\le g_i(s^{\cross_{\ell}}) + \mu_{\cross_{\ell}} - \tau_{\ell} \\
&= g_i(h^{\cross_{\ell}}) + \Gamma_i^{\ell} + \mu_{\cross_{\ell}} - \tau_{\ell} \\
&\le g_{i^*}(h^{\cross_{\ell}}) + \Gamma_i^{\ell} + \mu_{\cross_{\ell}} - \tau_{\ell} \tag*{(by definition of $i^*$)}\\
&\le g_{i^*}(h^{\cross_{\ell}}) + \agammal  + \alpha_{\mu} + \alpha_{\tau}. \numberthis \label{eq:eoutput_error}
\end{align*}
We now get that

\begin{align*}
\ell
&\le \log \left[ c_{\max} + \agammal + \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) + \frac{4}{\epsilon} \cdot \log\left(\frac{3\log T}{\beta}\right) \right] \\
&\le \log \left[ c_{\max} + \agammal + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \right] \\
&\le \log \left[ c_{\max} + \agammalt + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \right] \numberthis\label{eq:eLbound} \\
&< \log c_{\max} + \log \frac{2}{\epsilon} + \frac{1}{2} \left(\log d + \log {\log T} + \log \ln \left(\frac{2e^{\epsilon/2}}{\delta}\right) + \log \log \frac{3d\log T}{\beta}\right) + \log \frac{12}{\epsilon} + \log \log\left(\frac{3T}{\beta}\right) \tag*{(upper bounding log of sum by sum of logs)} \\
&\le \Lval \\
\end{align*}

as required, where the third inequality follows from $\ell \le \log T$.

We use this to show that the $s_i$ values in Algorithm <ref> are at most
$\alpha_{\Gamma} = \agammaL$
away from the true column sums at all times.

Assume that the random variables are bounded as in <ref>. Let $t \in [T]$ and $i \in [d]$. Then
$| s_i^t - h_i^t | \le \alpha_{\Gamma} = O\left(\agammaLinO\right)$.

We condition on the noises being bounded as stated in <ref>. Thus we get an upper bound of $L$ on the number of segments from <ref>.
Let $j$ be the segment to which time $t$ belongs. Then

\begin{align*}
| s_i^t - h_i^t |
&= | h_i^t + \Gamma_i^j - h_i^t|\\
&\le \agammaj \\
&\le \alpha_{\Gamma}
\end{align*}

as required.

We finally bound the true maximum query value increase in a single segment.

Assume that the random variables are bounded as in <ref>. Then in Algorithm <ref>, the true maximum column sum for segment $j$ increases by at most
$2^{j-1} + 2\alpha_{DM}$, where $\alpha_{DM} = \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} + L = O \left( \frac{\agammaLoneline + \log (T/\beta)}{\epsilon} \right)$.

We condition on the noises being bounded as in <ref>. Recall that the time interval $(p_{j-1}, p_j]$ is the $j^{th}$ segment. First, assume that either $j <  \ell$, or $j=\ell$ and the condition in <ref> was true at time $p_j$. Let $M_t= \max_i g_i(h^t)$ be the true maximum query value at time $t$, and $\T_j$ be the $j^{th}$ threshold value. Then

\begin{align*}
|M_{p_j} - M_{p_{j-1}}|
&\le |\T_j - \T_{j-1}| + |M_{p_j} - \T_j| + |M_{p_{j-1}} - \T_{j-1}|
\end{align*}

The definition of $\T_j$ directly gives us that $|\T_j - \T_{j-1}| = 2^{j-1}$. Thus our task reduces to bounding $|M_{p_j} - \T_j|$ for all $j$.
We do this in two parts. Let $g_{max}(s^t) = \max_i g_i(s^t)$ be the maximum query value on the noisy histogram at time $t$. First, using <ref> and the fact that $\max_i g_i$ is a sensitivity $1$ function, we get that for all $t$,

\begin{equation}
\label{eq:eLog_Mt_bound}
|M_{t} - g_{max}(s^{t})|
\le \alpha_{\Gamma}
\end{equation}

and since at time $p_j$ the threshold was crossed, we have that

\begin{align*}
&> \T_j - \alpha_{\mu} - \alpha_{\tau}.
\end{align*}

Putting these two equations together, we get that

\begin{align*}
M_{p_j} - K_j
&> - \left( \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} \right).
\end{align*}

This gives us a lower bound. Now we show an upper bound.
Let $t < p_j$ be the last time step in which a segment was not closed. If a segment was closed at every time step until $p_j$ of the algorithm, then let $t= 0$.
Since at every time step between $t$ and $p_j$ a segment must have been closed and the total number of segments is at most $\ell$, we get that $t \ge p_j - \ell$. Let $k$ be the segment that $t$ belonged to. If $t=0$, we set $k = s_{max}^0 = K_0 = 0$ in the following equation. Then at time $t$,

\begin{align*}
&\le K_k + \alpha_{\mu} + \alpha_{\tau}
\end{align*}

Using Equation <ref> and the above equation, we get

\begin{equation}
\label{eq:eLogMK}
M_t \le K_k + \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma}
\end{equation}

Since $t \ge p_j - \ell$ and the $\max_i g_i$ is a sensitivity one function,

\begin{equation*}
M_t \ge M_{p_j} - \ell
\end{equation*}

Since the thresholds do not decrease with time, $K_{j} \ge K_k$. Note that $\ell \le L$ by <ref>. Using these two facts, and substituting the above equation into Equation <ref>, we get that

\begin{align*}
M_{p_j} - K_j
&\le \alpha_{\mu} + \alpha_{\tau} + \alpha_{\Gamma} + L
= \alpha_{DM}
\end{align*}

Thus putting it all together, we get that

\begin{align*}
|M_{p_j} - M_{p_{j-1}}|
&\le 2^{j-1} + 2 \cdot \alpha_{DM} \\
\end{align*}

as required.
Now, for $j=\ell$, if the condition in <ref> was false, we have two cases. First, assume $\ell=\log T$. Then at time $p_{l-1}$, we have

\begin{align*}
g_{max}(s^{p_{\ell-1}})+\mu_{p_{\ell-1}}> K_{\ell-1}+\tau_{\ell-1}=T/2+\tau_{\ell-1}
\end{align*}

and therefore

\begin{align*}
\end{align*}

Since $M_{p_{\ell}}\leq M_{T}\leq T$, we have

\begin{align*}
M_{p_{\ell}}-M_{p_{\ell-1}}\leq T/2+\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}=2^{\ell-1}+\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}.
\end{align*}

Second, assume $\ell< \log T$. Then

\begin{align*}
g_{max}(s^{p_j})\leq K_j+\alpha_{\mu}+\alpha_{\tau},
\end{align*}

and thus

\begin{align*}
M_{p_j}\leq K_j+\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}.
\end{align*}

Since the threshold was crossed at time $p_{j-1}$, we have

\begin{align*}
M_{p_{j-1}}\geq K_{j-1}-(\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma}).
\end{align*}

\begin{align*}
|M_{p_j}-M_{p_{j-1}}|=M_{p_j}-M_{p_{j-1}}&\leq (K_j-K_{j-1})+2(\alpha_{\mu}+\alpha_{\tau}+\alpha_{\Gamma})\\
&\le 2^{j-1} + 2 \alpha_{DM}
\end{align*}

which proves the claim.

With probability at least $1 - \beta$, we simultaneously have the following guarantees from Algorithm <ref>.

* the total number of segments produced by the algorithm is upper bounded by $L = \Ldef$,

* the difference between the noisy and the true histogram at all times stored by the algorithm is upper bounded by $\alpha_{\Gamma} =O\left(\agammaLinO\right)$, and

* the true maximum query value increase within segment $j$ is at most $2^{j-1} + 2\alpha_{DM}$, where $\alpha_{DM} = \eddm$.

Assume that the Laplace random variables in Algorithm <ref> are bounded as in <ref>. Then the three points of the theorem follow from Lemmas <ref>, <ref>, and <ref> respectively.

§ (EPSILON, DELTA)-DIFFERENTIALLY PRIVATE TWO-LEVEL MECHANISM FOR KQUERY

In this section, we combine the two mechanisms from the previous two sections to get an algorithm for . The first level of the mechanism is the same as Algorithm <ref>, which partitions the input stream into segments. For each such segment the second level algorithm is called, which is a modified version of Algorithm <ref> and is given in  Algorithm <ref>. The main difference  to Algorithm <ref> is that it does not start each column sum from 0, but instead it is given as input (1) a noisy histogram to initialize each column sum, (2) an upper bound on the amount of noise in the histogram, and (3) an upper bound on how much the maximum query value (with the given initial column sum values) can increase. The error of the input histogram has to be taken into account in the new partitioning algorithm, which results in a slightly more complicated algorithm than Algorithm <ref>. The full two-level algorithm is given in Algorithm <ref>.

$(\epsilon,\delta)$-dp Two-Level Mechanism for

Stream $x^1, x^2, \ldots, x^T \in \{0,1\}^d$.
Estimate of $g_i(\histshort(t))$ for all $i\in [k]$ and all $t\in[T]$
$L \leftarrow \Lval $

$\alpha_{\Gamma} \leftarrow \agammaL $

$\alpha_{DM} \leftarrow \frac{12}{\epsilon} \cdot \log \left( \frac{3T}{\beta} \right) + \alpha_{\Gamma} + L $

$p_0 \leftarrow 0$, $j \leftarrow 1$

$s_i \leftarrow 0$ for all $i \in [d]$

$\T_j \leftarrow 1$, $\tilde{K}_j \leftarrow \T_j + \Lap(4/\epsilon)$

Initialize Alg <ref> with parameters $(0, s_1, s_2, \ldots, s_d, \alpha_{\Gamma}, \strlen, T)$

$t \in [T]$
$s_i = s_i + x_i^t$ for all $i \in [d]$

$s \leftarrow (s_1, s_2, \ldots, s_d)$

$\max g_i(s) + \Lap(8/\epsilon) > \tilde{\T}_j$ and $j < \log T$
$p_j\leftarrow t$, $j \leftarrow j+1$

$s_i \leftarrow s_i + \edadd$

$\T_j \leftarrow 2 \cdot \T_{j-1}$, $\tilde{\T}_j \leftarrow \T_j + \Lap(4/\epsilon)$

Terminate current Alg <ref>

Initialize new Alg <ref> instance with parameters $(t, s_1, s_2, \ldots, s_d, \alpha_{\Gamma}, \strlen, T)$

output $(g_1(s), g_2(s), \ldots, g_k(s))$

feed $x^t$ to Alg <ref>

output returned value of Alg <ref>

Modified $(\epsilon, \delta)$-DP Mechanism for

Stream $x^{t_0+1}, x^{t_0+2}, \ldots, x^{t_{\infty}} \in \{0,1\}^d$, start time $t_0$, noisy estimates $s_i^{t_0}$ for $i \in [d]$ with error $\le \alpha_{\Gamma}$, error bound $\alpha_{\Gamma}$, max query value increase bound $\Delta$, stream length bound $T$, an adaptively $\edee$-DP continuous histogram mechanism $H$, additive error bound $\err{n}$ on all outputs of $H$ that holds with probability $\ge 1 - \beta/3$ when $H$ is run on a stream of length $n$
Estimate of the query values $g_i(\histshort(t))$ for all $i \in [k]$ at every time step $t \in [t_0, t_{\infty}]$.
Initialize an adaptively $\edee$-differentially private continuous histogram mechanism $H$ for stream length $k\Delta$

$p_0 \leftarrow 0$, $j \leftarrow 1$

$c_i = 0$, and $s_i = s_i^{t_0}$ for all $i \in [d]$$s_i$s are initialized with input noisy sums
$C\leftarrow \Cval $

$\T \leftarrow 3(C+\err{k\cdot\Delta}+\alpha_{\Gamma})$

$\tau\leftarrow \Lap(6/\epsilon)$

$\T_{(i)} \leftarrow g_i(s^{t_0}) + \T$, $\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau $ for all $i\in [k]$

$\textrm{out} \leftarrow \left( g_1(s^{t_0}), g_2(s^{t_0}), \ldots, g_k(s^{t_0}) \right) $

$t \in [t_0,T]$
$c_i \leftarrow c_i + x_i^t$, $s_i \leftarrow s_i + x_i^t$ for all $i \in [d]$

$\exists i\in[k]$: $g_i(s)+\mu>\tilde{\T}_{(i)}$ and $j\le k\Delta$
$p_j\leftarrow t$,
$j \leftarrow j+1$Close the current segment
insert $(c_1,\dots,c_d)$ into $H$, reset $c_i \leftarrow 0$ for all $i \in [d]$

$i\in [k]$
$\tilde{g_i}(s)\leftarrow g_i(s)+\edadd$

$\tilde{\T}_{(i)} \leftarrow \T_{(i)} + \tau$ for all $i \in [k]$

$(s_1,\dots,s_d) \leftarrow$ output$(H)$ + $(s_1^{t_0}, s_2^{t_0}, \ldots, s_d^{t_0})$ Current count from the histogram mechanism
$\textrm{out} \leftarrow (g_1(s),\dots,g_k(s))$

output out

In this section we will refer to Algorithm <ref> without the lines referring to Algorithm <ref> as the doubling mechanism, and to Algorithm <ref> as the modified BoundedMaxQuery mechanism.

§.§ Privacy

Algorithm <ref> satisfies $(2\epsilon, 2\delta)$-differential privacy.

We deal with the outputs of the calls to Alg <ref> separately from the outputs of Alg <ref> in <ref>.
Let $x$ and $y$ be two neighboring input streams.
First, note that since the instantiations of the modified BoundedMaxQuery mechanism do not affect the outputs on <ref>, we can use <ref> to prove that the doubling mechanism (since the outputs in <ref> of the two-level mechanism are exactly the same as run on the doubling mechanism) is $(\epsilon, \delta)$-differentially private. Now we condition on all the internal random variables (namely, the Laplace random variables in Lines <ref>, <ref>, <ref>, and <ref>)
of the two-level mechanism  being fixed such that both
$x$ and $y$ lead to the same sequence of segments, and argue about the privacy of the various modified BoundedMaxQuery mechanisms.

Since the segments produced by the doubling mechanism are fixed, all the modified BoundedMaxQuery mechanisms operate on disjoint parts of the stream. Each instantiation of the modified BoundedMaxQuery mechanism is $(\epsilon,\delta)$-dp by Lemma <ref>.

Since they operate on disjoint parts of the stream, by parallel composition, all instantiations of the modified BoundedMaxQuery mechanism together satisfy $(\epsilon, \delta)$-DP.
Naïve sequential composition now gives us the $(2\epsilon, 2\delta)$-DP guarantee.

§.§ Accuracy

§.§.§ Algorithm kKnownMod

We first analyze the accuracy of Algorithm <ref>, assuming that the input noisy column sums given to the algorithm are at most an additive error $\alpha_{\Gamma}$ away from the true column sums, and that the increase in the true maximum query value is bounded by $\Delta$. This property is shown to hold for the two-level algorithm with probability $\ge 1 - \beta$ in Lemmas <ref> and <ref>.

Let $t \in [T]$ be an arbitrary time step, let $s^{t}$ denote the value of $s$ at time $t$, and $\histshort^{t}$ be the value of the true histogram at time $t$.
In the following let $\alpha_{SV}:=\edsv$ and
$\alpha_U := \edu$.
We condition on the following  upper bounds on the additive error, which together hold with probability $ \ge 1-\beta$:

* The error of $H$ is bounded by $\err{k\cdot \Delta}$. By assumption, this holds with probability $1-\beta/3$.

* Adding the same random variable $\tau$ with $\Lap(6/\epsilon)$   distribution to all $K_{(i)}$  gives an additive error of at most  $\epsilon^{-1}6\ln(6k\cdot \Delta/\beta)$ with probability $1-\beta/6$ by Fact <ref> and the union bound, since  we sample for that variable at most $k\cdot \Delta$ times.

* The random variable $\mu$ with $\Lap(12/\epsilon)$ distribution drawn at every time steps gives an additive error of at most $\epsilon^{-1}12\ln(6T/\beta)$ by Fact <ref> and the union bound with probability $1-\beta/6$.

Together with the previous condition we have

* If the condition in line <ref> is true for $i$ at time $t$, then $g_i(s^t)>K_{(i)}-\alpha_{SV}$

* If the condition in line <ref> is false for $i$, then $g_i(s^t)<K_{(i)}+\alpha_{SV}$.

for $\alpha_{SV}=\edsv$

* We add $\edadd$ noise  to $g_i$ in line <ref> at most $k\cdot \Delta$ times for each $i\in[k]$. Thus, by Fact <ref> and the union bound, with probability $1-\beta/3$
at most an additive error of
$\edu=\alpha_{U}$ is added to $g_i$ for any $i$ and any time step.

We now proceed as follows:
Recall that $p_j$ denotes the end of the $j$th time interval and that $p_0 = t_0$.
To prove accuracy we will first show an auxiliary lemma that says that $p_1 > t_0 + 1$. Next fix any $i \in [k]$ and let $p_l$ and $p_r$ be any two time steps such that $K_{(i)}$ is updated at $p_l$ and $p_r$ but not between them. Then  we show that
$g_i$ must have increased by more than 1 between $p_l$ and $p_r$. The latter fact implies that $K_{(i)}$ was not updated at time $p_r-1$, which can be used to get an upper bound on $g_i(h^{p_r-1})$ and, by the 1-sensitivity of $g_i$, also on $g_i(h^{p_r})$.
As $K_{(i)}$ was updated at time $p_l$, we also have a lower bound on $g_i(h^{p_l})$. Combining the two gives
an upper bound on
$|g_i(h^{p_r}) - g_i(h^{p_l})|$ of $O(K + \alpha_{SV} + \alpha_U)$,
which is the crucial bound needed to upper bound $|g_i(h^{t}) - g_i(s^t)|$.

In the rest of the section let $K_{(i)}^t$ denote the value of $K_{(i)}$ at time $t$ when we reach Line <ref> of Algorithm <ref>. To show that $p_1 > t_0 + 1$, we first show that whenever the $i$th threshold is updated, the true value of $g_i$ is not much smaller than the threshold that was crossed.

Suppose the $i$th threshold $K_{(i)}$ is updated at time $t$. Then

\[
g_i(\histshort^{t})\geq K_{(i)}^{t}-C-\alpha_{U}-\err{k\cdot \Delta} - \alpha_{\Gamma}.
\]

This follows from the sensitivity of $g_i$ and the fact that $K_{(i)}$ was updated at time $t$.

\begin{align*}
&\ge g_i(s^t) - \errkcmax - \alpha_{\Gamma} \tag*{(since $g_i$ has sensitivity $1$)} \\
&\ge \tilde{g_i}(s^{t})-\alpha_{U} - \errkcmax - \alpha_{\Gamma} \\
&\ge K_{(i)}^{t}-C-\alpha_{U} - \errkcmax - \alpha_{\Gamma} \tag*{(since $K_{(i)}$ is updated at time $t$)}
\end{align*}

as required.

It holds that $p_1 > 1+t_0$.

Note that variable $C$ in Algorithm <ref> is larger than $\alpha_{SV}+\alpha_{U}$.
Thus, if the condition in line <ref> is true for some $i$ at time $p_j$, then the condition in line <ref> is also true for the same $i$. Thus, whenever we close a segment, we also update at least one threshold, say the $i$th one. Using <ref> with $t = p_j$ gives us that

\[
g_i(h^{p_j}) \ge K_{(i)}^{p_j}-C-\alpha_{U} - \errkcmax - \alpha_{\Gamma}
\]

Note that since $K>C+\err{k\cdot \Delta}+\alpha_{U} + \alpha_{\Gamma}$,  this implies $g_i(\histshort^{p_1}) > 1+t_0$. As $g_i$ increases by at most $1$ per time step, it follows that $p_1>1+t_0$.

Next we show an upper bound on the true query values when a threshold is updated.

Let $i \in
Let $p_r$ be a timestep where threshold $K_{(i)}$ is updated. Then $g_i(\histshort^{p_r})<K_{(i)}^{p_r}+\err{k\cdot \Delta}+\alpha_{SV}+\alpha_U + \alpha_{\Gamma}+1$.
Further, let $l$ and $r$ be integers such that $p_l$ and $p_r$ are two consecutive time steps where threshold $K_{(i)}$
is updated. Then  $p_r - p_l > 1$ and $|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|>1$.

We show the claim by induction over the number of updates of $K_{(i)}$.
As $p_r$ is a time step where $K_{(i)}$ is updated,  the condition in line <ref> is true, and, thus $r\leq k\cdot \Delta$.

Case 1: If $p_r$ is the first time that threshold $K_{(i)}$ is updated, then $p_r\geq p_1>1$ by Lemma <ref>. As the threshold was not updated before, it was not updated at time $p_r-1$. This fact and the fact that $r\leq k\cdot \Delta$ imply that either the condition in line <ref> was false or the condition in line <ref> was false for $i$ at time $p_r-1$.
Thus, either

and hence,
$$g_i(\histshort^{p_r-1})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\errkcmax + \alpha_{\Gamma}.$$

As $g_i$ has sensitivity $1$ and $\histshort^{p_r}$ and $\histshort^{p_r-1}$ differ by at most 1 in each coordinate, it holds that $g_i(\histshort^{p_{r}})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_{\Gamma}+1$.

Case 2: If $p_r$ is not the first time threshold $K_{(i)}$ is updated, let $p_l$ be the last time at which threshold $K_{(i)}$ was updated before $p_r$. By induction, we have $g_i(\histshort^{p_{l}})<K_{(i)}^{p_l}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_\Gamma+1=K_{(i)}^{p_r}-K+\alpha_{SV}+\alpha_U+\err{k\cdot\Delta}+\alpha_\Gamma+1$. Since the threshold $K_{(i)}$ is updated at time $p_r$, we have $g_i(\histshort^{p_{r}})\geq K_{(i)}^{p_r}-C-\alpha_U-\err{k\cdot \Delta}-\alpha_\Gamma$ by <ref> for $t = p_r$. Thus,

\begin{align*}
|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|&>K_{(i)}^{p_j}-C-\alpha_{U}-\err{k\cdot \Delta}-\alpha_\Gamma \\
&\ \ -(K_{(i)}^{p_r}-K+\err{k\cdot \Delta}+\alpha_{SV}+\alpha_U+\alpha_\Gamma+1)\\
&=K-C-2\err{k\cdot \Delta}-\alpha_{SV}-2\alpha_{U}-2\alpha_\Gamma-1>1,
\end{align*}

since $K=3(C+\err{k\cdot \Delta}+\alpha_\Gamma)$ and $C>\alpha_{SV}+\alpha_U$. Thus, $p_r-p_l>1$ and the threshold $K_{(i)}$ was not updated at time $p_r-1$. Now by the same argument as before, $g_i(\histshort^{p_r-1})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_\Gamma$ and therefore $g_i(\histshort^{p_r})<K_{(i)}^{p_r}+\alpha_{SV}+\alpha_U+\err{k\cdot \Delta}+\alpha_\Gamma+1$.

Let $t(i)$ be the last time in the whole input sequence that $K_{(i)}$ was updated,
let $p_l$ be the last time before $t$ that $K_{(i)}$ was updated, and let $p_r$ be the first time step at or after $t$  at which $K_{(i)}$ gets updated, i.e., $p_r \ge t$.

Case A:  $t \le t(i)$, i.e., there exists a time step $\ge t$ at which $K_{(i)}$ is updated.

Now, by Lemma <ref> applied to $p_r$ and <ref> applied to $p_l$, we get

\begin{align*}
|g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|&<K_{(i)}^{p_r}+\err{k\cdot \Delta}+\alpha_{SV}+\alpha_U+\alpha_\Gamma+1 \\
&\ \ -(K_{(i)}^{p_l}-K-C-\alpha_{U}-\err{k\cdot \Delta}-\alpha_\Gamma)\\
&=K+C+2\err{k\cdot \Delta}+\alpha_{SV}+2\alpha_{U}+2\alpha_\Gamma+1.
\numberthis\label{eq:xtopkacc2}
\end{align*}

The error for outputting $g_i$ at any time step $t$ in an interval $[p_{j-1},p_j)\subseteq[p_{l},p_r)$ for any $j\leq k\cdot \Delta$ is now bounded by:

\begin{align}
\begin{split}
&\leq |g_i(\histshort^{t})-g_i(\histshort^{p_{j-1}})|+|g_i(\histshort^{p_{j-1}})-g_i(s^{p_{j-1}})|\\
&\leq |g_i(\histshort^{p_r})-g_i(\histshort^{p_l})|+\err{k\cdot \Delta}+\alpha_\Gamma\\
&\leq K+C+3\err{k\cdot \Delta}+\alpha_{SV}+2\alpha_{U}+3\alpha_\Gamma+1\\
&=O(\epsilon^{-1}\edinsideo + \errkcmax + \alpha_\Gamma)\label{eq:xtopkacc3}
\end{split}
\end{align}

Further, because of Lemma <ref>, every time we update $K_{(i)}$, $g_i(\histshort^{t})$ grows by at least $1$. Since all $g_i(\histshort^{t})$ are bounded by $\Delta$, and every time $j$ is updated at least one threshold is updated, this implies that $j<k\cdot \Delta$ is always true.

Case B:  $t > t(i)$.
Consider the last time step $t_{\infty}$. As $t_{\infty} \ge t > t(i)$, $K_{(i)}$ was not updated at time $t_{\infty}$. Since $j\leq k\cdot \Delta$, at time $t_{\infty}$ either the condition in line <ref> was false or the condition in line <ref> was false. Therefore $g_i(h^T)<K_{(i)}^{T}+\err{k\cdot \Delta}+\alpha_{U}+\alpha_{SV}+\alpha_\Gamma$.
Then by <ref>, $ g_i(\histshort^{t(i)})\geq K_{(i)}^{T}-K-C-\alpha_{U}-\err{k\cdot \Delta} - \alpha_\Gamma $. These two equations together give

\begin{equation}
\label{eq:xhThti}
g_i(\histshort^{T}) - g_i(\histshort^{t(i)}) \le K + C + 2 \alpha_{U} + \alpha_{SV} + \errkcmax + 2 \alpha_\Gamma
\le K + 3C + \errkcmax + 2 \alpha_\Gamma
\end{equation}

The error for outputting $g_i$ at any timestep $t$ in an interval $[p_{j-1},p_j)\subseteq[t(i),T]$ and at $t=T$ is now bounded by

\begin{align*}
&\leq |g_i(\histshort^{T})-g_i(\histshort^{t(i)})|+\err{k\cdot \Delta}+\alpha_\Gamma\\
&\leq K + 3C + 2\err{k\cdot \Delta} + 3\alpha_\Gamma \tag*{(by Equation~\ref{eq:xhThti})} \\
&=O(\epsilon^{-1}\edinsideo+\err{k\cdot \Delta}+\alpha_\Gamma)
\numberthis \label{eq:xtopkoutputerror}
\end{align*}

Thus Equations <ref> and <ref> together give a bound on $|g_i(h^t) - g_i(s^{p_j-1})|$ in both cases.
For any time $t$ that belongs to interval $j$, the values of $g_i$ on the true histogram are $(g_1(h^{t}), g_2(h^t), \ldots, g_k(h^t))$, and the values output by Algorithm <ref> are $(g_1(s^{p_{j-1}}), g_2(s^{p_{j-1}}), \ldots, g_k(s^{p_{j-1}}))$. Thus the error of the algorithm is given by

\begin{align*}
\alpha
&= \max_{t \in T} \max_{i \in [k]} |g_i(h^t) - g_i(s^{p_{j-1}})| \tag*{(where $j$ is the interval that $t$ belongs to)} \\
&\le  \max_{t \in T} \max_{i \in [k]} O(\epsilon^{-1} \cdot \edinsideo + \errkcmax + \alpha_\Gamma) \tag*{(by Equation~\ref{eq:xtopkoutputerror})} \\
&\le  O(\epsilon^{-1} \cdot \tkinsideo)
\end{align*}

This then gives us the following lemma.

Algorithm <ref> is $(\alpha, \beta)$-accurate, with $\alpha = O(\epsilon^{-1} \cdot \tkinsideo)$.

§.§.§ Algorithm kTwo-Level

* $L = \Ldef$,

* $\alpha_{\Gamma} = \agammaL $,

* $\alpha_{DM} = \alpha_{\Gamma} + L + 8\epsilon^{-1} \log(3T/\beta)+ 4\epsilon^{-1} \log(3\log T/\beta)$,

In what follows, $\Oll$ hides $\log \log(d, k, T, 1/\epsilon, 1/\beta)$ terms.

Algorithm <ref> is $(\alpha, 2\beta)$-accurate for , with

$$ \alpha = \Oll\left( \epsilon^{-1} \cdot \left( \epsilon \cdot \erractdbl + \sqrt{d\log (d/\beta\delta)\log (dc_{\max}/\epsilon)} + \log(T/\beta) + \sqrt{k}\log(kdc_{\max}/\epsilon\beta\delta) \right)  \right)$$

We first argue about the doubling mechanism.
Using <ref>, we get that the following guarantees simultaneously hold with probability $\ge 1 - \beta$.

* the total number of segments produced by the doubling mechanism is upper bounded by $L$, where $L = \Ldef$,

* for every time step $t \in [T]$, the difference between the true histogram and the noisy histogram stored by the doubling mechanism is upper bounded by $\alpha_{\Gamma} = O \left( \agammaLinO \right)$, and

* the true maximum query value increase within segment $j$ is at most $2^{j-1} + 2\alpha_{DM}$, where $\alpha_{DM} = \eddm $

We condition on these guarantees.
We now argue about the accuracy when the modified BoundedMaxQuery mechanism returns an output.
For the $j^{th}$ instantiation of the modified BoundedMaxQuery mechanism, the max query value increase bound $\Delta$ is defined as $2^{j-1} + 2 \alpha_{DM}$.
Taking $\beta' = \beta/3L$ in <ref> gives us that the $j^{th}$ modified BoundedMaxSum mechanism has the following accuracy with probability $\ge 1 - \beta/L$

\begin{equation}
\label{ex:xModBMSL}
\begin{split}
\alpha =
O\left(\epsilon^{-1} \cdot \left(\sqrt{dL \log\left( Le^{\epsilon/2} d\log T/\beta\delta \right)} + \log(TL/\beta) + \log (Lk\Delta/\beta) + \right.\right.
\\ \left. \left. \sqrt{k\log(e^{\epsilon/3}Lk\Delta/\beta\delta)} \right) + \errdbl   \right)
\end{split}
\end{equation}

We first upper bound $\Delta$. Since $j \le L$,

\begin{align*}
\Delta
&= 2^{j-1} + 2 \alpha_{DM}
\le 2^{L} + 2 \alpha_{DM}
\end{align*}

We show that $\alpha_{DM} \le 2^{L+1}$, which lets us obtain an upper bound of $\Delta \le 2^{L+2}$. Recall that
$\alpha_{DM} = L + \alpha_{\Gamma} +\frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) + \frac{4}{\epsilon} \cdot \log\left(\frac{3\log T}{\beta}\right)$.
We bound $L$ trivially by $2^L$. We now bound the rest of the term by $2^L$. First, we bound $\alpha_{\Gamma}$

\begin{align*}
\alpha_{\Gamma}
&= \agammaL \\
&\le \frac{2}{\epsilon} \cdot \sqrt{ d \log T \ln\left(\frac{2e^{\epsilon/2}}{\delta}\right)\log\left(\frac{3d\log T}{\beta}\right)}\tag*{(since $L \le \log T$)}
\end{align*}

\begin{align*}
\alpha_{\Gamma} + \frac{8}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) + \frac{4}{\epsilon} \cdot \log\left(\frac{3\log T}{\beta}\right)
&\le \frac{2}{\epsilon} \cdot \sqrt{ d \log T \ln\left(\frac{2e^{\epsilon/2}}{\delta}\right)\log\left(\frac{3d\log T}{\beta}\right)} + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \\
&\le c_{\max} + \frac{2}{\epsilon} \cdot \sqrt{ d \log T \ln\left(\frac{2e^{\epsilon/2}}{\delta}\right)\log\left(\frac{3d\log T}{\beta}\right)} + \frac{12}{\epsilon} \cdot \log\left(\frac{3T}{\beta}\right) \\
&\le 2^L \tag*{(by definition of $L$ and (\ref{eq:eLbound}))}
\end{align*}

which gives $\alpha_{DM} \le 2^{L+1}$.
This gives us the required upper bound on $\Delta$ of $2^{L+2}$.
Next, we show that $\log L = \Oll(1)$. This follows, since

\begin{align*}
L &= \Lval
\end{align*}

and so

\begin{align*}
\log L &= \log\log \left( \Linside \right) = \Oll(1).
\end{align*}

Plugging in $\Delta \le 2^{L+2}$, $\log L = \Oll(1)$, and $\log \log T = \Oll(1)$ into Equation <ref>, we get

\begin{equation}
\label{eq:xHtobound}
\alpha = \Oll \left( \epsilon^{-1} \cdot \left( \sqrt{dL\log(d/\beta\delta}) + \epsilon \cdot \erractdbl + \log (T/\beta) + \sqrt{k\log(k 2^{L+2}/\beta\delta)} + \log (k2^{L+2}/\beta) \right) \right)
\end{equation}

For the last term in the summation,

\begin{align*}
\log 2^{L+2}
= L + 2
&= O(\Lval) \\
&= \Oll(\log (\epsilon^{-2} dc_{\max}))
\end{align*}

In the first term in Equation <ref>, we bound $\sqrt{L}$ as follows

\begin{align*}
\sqrt{L}
&\le \sqrt{\log (24\epsilon^{-2} dc_{\max})} + \sqrt{8\log \log(T/\beta)} + \sqrt{\log\ln(3d\log(T/\beta))}
\end{align*}

Since the final two terms are $\Oll(1)$, this reduces to

\begin{align*}
\sqrt{L} \le \Oll\left( \sqrt{\log (dc_{\max}/\epsilon)}\right)
\end{align*}

Plugging these bounds on $\sqrt{L}$ and $\log 2^{L+2}$ in Equation <ref>, we get

\begin{equation*}
\begin{split}
\alpha =
\Oll\left( \epsilon^{-1} \cdot \left( \sqrt{d\log (d/\beta\delta)\log (dc_{\max}/\epsilon)} +\epsilon \cdot \erractdbl + \log(T/\beta) \right. \right.
\\
+ \left. \left. \sqrt{k \log(kdc_{\max}/\epsilon\beta\delta}) + \log (kdc_{\max}/\epsilon\beta) \right) \right)
\end{split}
\end{equation*}

Since there are at most $L$ segments in the two-level mechanism, there are at most $L$ instantiations of Algorithm <ref>. Thus all the accuracy guarantees hold together with probability at least $1 - \beta$.

Combining the guarantees for the two-level mechanism and the modified BoundedMaxQuery mechanism, we get that Algorithm <ref> is $(\alpha, 2\beta)$-accurate for

\begin{align*}
\alpha
&= \Oll\left( \epsilon^{-1} \cdot \left( \epsilon \cdot \erractdbl + \sqrt{d\log (d/\beta\delta)\log (dc_{\max}/\epsilon)} + \log(T/\beta) + \sqrt{k}\log(kdc_{\max}/\epsilon\beta\delta) \right)  \right)
\end{align*}

which proves the claimed accuracy guarantee.

Algorithm <ref> instantiated with the histogram mechanism from Fact <ref> is $(\alpha, 2\beta)$-accurate for , with

$$\alpha = \Oll \left( \epsilon^{-1} \cdot \left( \sqrt{d}  \log (d/\beta\delta) \cdot \left( \log^{3/2} (dc_{\max}/\epsilon^2) + \log^{3/2} k \right) + \log(T/\beta) + \sqrt{k} \log(kdc_{\max}/\epsilon\beta\delta) \right) \right)$$

Using the histogram mechanism mentioned in Fact <ref>, we have
$$\erractdbl = O(\epsilon^{-1}\log(1/\delta)\log (k 2^{L+2}) \sqrt{d\ln(d k2^{L+2}/\beta)})$$

We start by bounding $\log^{3/2}(k2^L)$.

\begin{align*}
\log^{3/2} k2^L
&= \left(L+\log k\right)^{3/2} \\
&\le \left( \Lval + \log k \right)^{3/2} \\
&\le \Oll \left( \log^{3/2} (d c_{\max}/\epsilon^2) + \log^{3/2} k \right)
\end{align*}

\begin{align*}
\erractdbl
&\le \Oll \left( \epsilon^{-1} \cdot \sqrt{d} \cdot \log (d/\beta\delta) \cdot \left( \log^{3/2} (dc_{\max}/\epsilon^2) + \log^{3/2} k \right) \right)
\end{align*}

Plugging this into the accuracy guarantee in <ref>, the $\sqrt{d\log d \log dc_{\max}}$ term is dominated by $\erractdbl$.
This gives

\begin{align*}
\alpha
&= \Oll \left( \epsilon^{-1} \cdot \left( \sqrt{d}  \log (d/\beta\delta) \cdot \left( \log^{3/2} (dc_{\max}/\epsilon^2) + \log^{3/2} k \right) + \log(T/\beta) + \sqrt{k} \log(kdc_{\max}/\epsilon\beta\delta) \right) \right)
\end{align*}

as required.

[Cardoso and Rogers, 2022]
Adrian Rivera Cardoso and Ryan Rogers.
Differentially private histograms under continual observation:
Streaming selection into the unknown.
In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera,
editors, Proc. 25th AISTATS, pages 2397–2419, 2022.
URL <https://proceedings.mlr.press/v151/rivera-cardoso22a.html>.

[Carvalho et al., 2020]
Ricardo Silva Carvalho, Ke Wang, Lovedeep Gondara, and Chunyan Miao.
Differentially private top-k selection via stability on unknown
In Proc. 36th UAI, pages 1109–1118, 2020.

[Chan et al., 2011]
T.-H. Hubert Chan, Elaine Shi, and Dawn Song.
Private and continual release of statistics.
ACM Trans. Inf. Syst. Secur., 140 (3):0
26:1–26:24, 2011.

[Chan et al., 2012]
T.-H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu.
Differentially private continual monitoring of heavy hitters from
distributed streams.
In Proc. 12th PETS, pages 140–159, 2012.

[Cummings et al., 2018]
Rachel Cummings, Sara Krehbiel, Kevin A. Lai, and Uthaipon Tao Tantipongpipat.
Differential privacy for growing databases.
In Proc. 31st NeurIPS, pages 8878–8887, 2018.

[Denisov et al., 2022]
Sergey Denisov, H. Brendan McMahan, Keith Rush, Adam Smith, and Abhradeep
Improved differential privacy for sgd via optimal private linear
operators on adaptive streams.
In Proc. 36th NeurIPS, 2022.

[Durfee and Rogers, 2019]
David Durfee and Ryan M. Rogers.
Practical differentially private top-k selection with
pay-what-you-get composition.
In Proc. 33rd NeurIPS, pages 3527–3537, 2019.

[Dwork and Roth, 2014]
Cynthia Dwork and Aaron Roth.
The algorithmic foundations of differential privacy.
Found. Trends Theor. Comput. Sci., 90 (3-4):0
211–407, 2014.

[Dwork et al., 2006]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.
Calibrating noise to sensitivity in private data analysis.
In Shai Halevi and Tal Rabin, editors, Theory of Cryptography,
Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March
4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer
Science, pages 265–284. Springer, 2006.
URL <https://doi.org/10.1007/11681878_14>.

[Dwork et al., 2010]
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum.
Differential privacy under continual observation.
In Leonard J. Schulman, editor, Proceedings of the 42nd ACM
Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA,
5-8 June 2010, pages 715–724. ACM, 2010.
URL <https://doi.org/10.1145/1806689.1806787>.

[Dwork et al., 2015]
Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum.
Pure differential privacy for rectangle queries via private
In Proc. 21st ASIACRYPT, pages 735–751, 2015.
URL <https://doi.org/10.1007/978-3-662-48800-3_30>.

[Fichtenberger et al., 2021]
Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost.
Differentially private algorithms for graphs under continual
In Proc. 29th ESA, pages 42:1–42:16, 2021.

[Fichtenberger et al., 2022]
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay.
Constant matters: Fine-grained complexity of differentially private
continual observation using completely bounded norms.
CoRR, abs/2202.11205, 2022.
URL <https://arxiv.org/abs/2202.11205>.

[Gillenwater et al., 2021]
Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza.
Differentially private quantiles.
In Proc. 38th ICML, pages 3713–3722, 2021.

[Hardt and Talwar, 2010]
Moritz Hardt and Kunal Talwar.
On the geometry of differential privacy.
In Leonard J. Schulman, editor, Proceedings of the 42nd ACM
Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA,
5-8 June 2010, pages 705–714. ACM, 2010.
URL <https://doi.org/10.1145/1806689.1806786>.

[Huber, 1992]
Peter J. Huber.
Robust Estimation of a Location Parameter, pages 492–518.
Springer New York, New York, NY, 1992.

[Ilyas et al., 2008]
Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman.
A survey of top-k query processing techniques in relational
database systems.
ACM Comput. Surv., 400 (4):0 11:1–11:58,

[Jain et al., 2021]
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith.
The price of differential privacy under continual observation.
CoRR, abs/2112.00828, 2021.

[Kaplan et al., 2022]
Haim Kaplan, Shachar Schnapp, and Uri Stemmer.
Differentially private approximate quantiles.
In Proc. 39th ICML, pages 10751–10761, 2022.

[Kruskal and Wallis, 1952]
William H. Kruskal and W. Allen Wallis.
Use of ranks in one-criterion variance analysis.
J. Am. Stat. Assoc, 470 (260):0 583–621,

[Mir et al., 2011]
Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright.
Pan-private algorithms via statistics on sketches.
In Proc. 30th PODS, pages 37–48, 2011.

[Qiao et al., 2021]
Gang Qiao, Weijie J. Su, and Li Zhang.
Oneshot differentially private top-k selection.
In Proc. 38th ICML, pages 8672–8681, 2021.

[Qiu and Yi, 2022]
Yuan Qiu and Ke Yi.
Differential privacy on dynamic data, 2022.
URL <https://arxiv.org/abs/2209.01387>.

§ AN OMEGA(D LOGT) LOWER BOUND FOR INDEPENDENTLY DIFFERENTIALLY PRIVATE D-DIMENSIONAL BINARY COUNTING

So far, all solutions to  which were not polynomial in $T$ relied on running $d$ independent binary counting algorithms in parallel, and all achieved an error $\Omega(d\cdot \log T)$ for $\epsilon$-differential privacy. In this section we prove that using this strategy one cannot do better. For this, we formally define the following alternative version of differential privacy and neighboring for streams of elements from $\{0,1\}^d$:

Let $x$ be a stream of $T$ elements from $\{0,1\}^d$. We say $x$ and $y$ are independently neighboring if and only if for every $i\in [1,d]$ there exists a time step $t_i$ such that $x^t_i=y^t_i$ for all $t\neq t_i$. An algorithm $A$ is independently $\epsilon$-differentially private if it fulfills Definition <ref> for independently neighboring $x$ and $y$.

Note that this notion is a softer version of neighboring, i.e. all $x$ and $y$ which are neighboring are also independently neighboring, but not vice-versa. Thus, independent differential privacy is a stronger property then differential privacy.

We show the lower bound using a so-called packing argument [Hardt and Talwar, 2010], which relies on the group privacy property of differential privacy summarized in Fact <ref>.
We say $x$ and $y$ are $k$-neighboring if there exist $x=X_1, X_2, \dots, X_k=y$ such that $X_i$ and $X_{i+1}$ are neighboring for all $1\leq i <k$.
In the same way, we say $x$ and $y$ are independently $k$-neighboring if there exist $x=X_1, X_2, \dots, X_k=y$ such that $X_i$ and $X_{i+1}$ are independently neighboring for all $1\leq i <k$.
Let $A$ be an $\epsilon$-(independently) differentially private mechanism and $x$ and $y$ be (independently) $k$-neighboring. Then for all $S\in\mathrm{range}(A)$

\begin{align*}
P(A(x)\in S)\leq e^{k\epsilon}P(A(y) \in S)
\end{align*}

Note that computing all $d$ column sums by running independent binary counting algorithms fulfills independent $\epsilon$-differential privacy. Next we show that $\Omega(d\log T)$ noise is necessary for computing the noisy column sums in every time step while preserving independent $\epsilon$-differential privacy.

Assume $d\leq \sqrt{T}$. Then there is a $T'=T'(\epsilon)$ such that any independently $\epsilon$-differentially private algorithm for computing all $d$ column sums cannot be $(\alpha,\beta)$-accurate for constant $\beta$ and $\alpha\leq \frac{d\ln T}{16\epsilon}$ for streams of length $T\geq T'$.

Let $b=\frac{d\ln T}{8\epsilon}$.
We assume without loss of generality that $T$ is a multiple of $b$, otherwise we pad the stream with zero vectors. We start by dividing $[1,T]$ into $T/b$ blocks of length $b$, i.e. $B_1=[1,b]$, $B_2=[b+1,2b]$, …, $B_{T/b}=[T-b+1,T]$.
Now, for any vector $v\in [T/b]^d$ define the following stream $x(v)$ and output data set $S(v)$:

* $x(v)^t_i=1$ if and only if $t\in[(v_i-1)\cdot b +1, v_i \cdot b]$, else $x(v)^t_i=0$. That is, for every coordinate $d$ there is exactly one block which consists of only ones, and that block is the one specified by the $i$th coordinate in $v$.

* Denote $s_i^t$ the estimate for the $i$th column sum output by the algorithm in time $t$. $S(v)$ includes all outputs such that $s_i^t<b/2$ for all $t\leq (v_i-1)\cdot b$ and $s_i^t>b/2$ for all $t\geq v_i\cdot b$.

Now let $\beta=1/3$ and assume there is an algorithm $A$ which is $(\alpha,\beta)$ accurate for $\alpha=\frac{d\ln T}{16\epsilon}=b/2$.
Then $P(A(x(v))\in S(v))\geq \frac{2}{3}$.
Further, we have that for any $v,v'\in [T/b]^d$, $x(v)$ and $x(v')$ are independently $2b$-neighboring: for every coordinate $i$, $x(v')_i$ and $x(v)_i$ differ in at most $2b$ timesteps.
Therefore, by Fact <ref>, $P(A(x(v))\in S(v'))\geq \frac{2}{3}e^{-2b\epsilon}$.
Additionally, all $S(v)$ are disjoint for distinct $v$.

\begin{align*}
1&\geq \sum_{v\in [T/b]^d} \frac{2}{3}e^{-2b\epsilon}\\
&=\frac{2}{3}\left(\frac{8T\epsilon}{d\ln T}\right)^d e^{-\frac{d\ln T}{4}}\\
&\geq \frac{2}{3}\left(\frac{8\sqrt{T}\epsilon}{\ln T}\right)^d(1/\sqrt[4]{T})^d\\
&=\frac{2}{3}\left(\frac{8\sqrt[4]{T}\epsilon}{\ln T}\right)^d>1
\end{align*}

for large enough $T$, which is a contradiction.

§ THE BINARY TREE MECHANISM

$(\epsilon,\delta)$-differentially private partial sums

Stream $x^1, x^2, \ldots, x^T \in \mathbb{N}$, upper bound $T$ on the length of the stream, $\epsilon$, $\delta$
$p(I)$ estimating the partial sum $\sum_{t\in I}x^t$ for any $I\in \mathcal{I}=\{[(k-1)2^i+1,k2^i],~0\leq i \leq \lfloor \log T \rfloor,1\leq k\leq \lfloor \frac{T}{2^i}\rfloor\}$
$p(I)=0$ for all $I\in \mathcal{I}$

$p(I)=p(I)+N(0, \frac{2\ln (1.25/\delta)(\lfloor \log T\rfloor+1)}{\epsilon^2})$ for all $I\in \mathcal{I}$
$p(I)=p(I)+\Lap(\frac{\lfloor \log T\rfloor+1}{\epsilon})$ for all $I\in \mathcal{I}$
$t \in \mathbb{N}$
$p(I)=p(I)+x^t$ for all $I\in\mathcal{I}$ such that $t\in I$

$i\in [0,\lfloor\log T\rfloor]$
$t\mod 2^i=0$
output $p([t-2^i+1,t])$

Let $\mathcal{I}=\{[(k-1)2^i+1,k2^i],~0\leq i \leq \lfloor \log T \rfloor, 1\leq k\leq \lfloor \frac{T}{2^i}\rfloor\}$. For every $1\leq t\leq T$, there exists $D^t\subset \mathcal{I}$ such that

* all intervals in $D^t$ are disjoint,

* $[1,t]=\cup_{I\in D^t} I$,

* $|D^t|\leq \lceil \log T \rceil $.

Binary tree mechanism
Stream $x^1, x^2, \ldots, x^T \in \mathbb{N}$, upper bound $T$ on the length of the stream, $\epsilon$, $\delta$
Estimate $s^t$ of $\sum_{t'=1}^t x^{t'}$ at every time step $t$
Initialize Algorithm <ref>

$t \in \mathbb{N}$
get partial sums $p(I)$ from Algorithm <ref>

output $s_t=\sum_{I\in D^t} p(I)$, where $D^t$ is as in Fact <ref>

Define two streams $x=x^1,\dots, x^T\in{\mathbb{N}}$ and $y=y^1,\dots, y^T\in{\mathbb{N}}$ as neighboring if there is a time step $t^{*}$ such that $|x^{t^{*}}-y^{t^{*}}|=1$ and $x^t=y^t$ for all $t\neq t^{*}$. Under this notion of neighboring, Algorithm <ref> is $(\epsilon,\delta)$-differentially private.

Denote $q(x,I)=\sum_{t\in I} x^t$ be the true partial sums for $x$, and let $Q(x)=(q(x,I))_{I\in\mathcal{I}}$. Note that for any $0\leq i \leq \lfloor \log T\rfloor$, the intervals $[(k-1)2^i+1,k2^i]$ for all $k$ are pairwise disjoint. Thus, for $x$ and $y$ neighboring, there can be at most $\lfloor \log T\rfloor +1$ intervals $I\in \mathcal{I}$ where $q(x,I)$ and $q(y,I)$ differ, and they can differ by at most 1. It follows that $||Q(x)-Q(y)||_{1}\leq \lfloor \log T\rfloor +1$ and $||Q(x)-Q(y)||^2_{2}\leq \lfloor \log T\rfloor +1$. Now $(\epsilon,0)$- differential privacy follows from Theorem 3.6 in [Dwork and Roth, 2014] and $(\epsilon,\delta)$- differential privacy follows Theorem A.1, both in [Dwork and Roth, 2014].

Algorithm <ref> for $\delta=0$ is $(\alpha,\beta)$-accurate with $\alpha=\frac{4\log T\log(2T/\beta)}{\epsilon}$.

Follows from Lemma <ref>
with setting $b = \frac{\lfloor \log T\rfloor+1}{\epsilon}$, $k = \lceil \log T \rceil$, and
the probability bound $\beta_S$ to $\beta/T$. We upper bound $\max(\sqrt{k},\sqrt{\ln(2/\beta_S)})=\max(\sqrt{\lceil \log T \rceil},\sqrt{\ln(2T/\beta)})\leq \sqrt{\log(2T/\beta)}$.

A random variable of distribution $N(0,\sigma^2)$ follows the tail bound

\begin{align*}
P(X\geq t)\leq e^{\frac{-t^2}{2\sigma^2}}.
\end{align*}

Algorithm <ref> for $\delta>0$ is $(\alpha,\beta)$-accurate with $\alpha=\frac{2\sqrt{(\ln T+\ln(1/\beta))\ln(1.25/\delta)}\log T}{\epsilon}$.

The noise at every time step is the sum of $m\leq \lceil \log T\rceil$ random variables with their distribution $N(0, \frac{2\ln (1.25/\delta)(\lfloor \log T\rfloor+1)}{\epsilon^2})$, thus a random variable of distribution $N(0, \frac{2m\ln (1.25/\delta)(\lfloor \log T\rfloor+1)}{\epsilon^2})$.
Setting the right hand side in Fact <ref> equal to $\beta/T$ (we want the bound to hold at all time steps and apply a union bound), we get that the inequality holds for $t= \frac{4\sqrt{(\ln T+\ln(1/\beta))\ln(1/\delta)}\log T}{\epsilon}$.