erchiw/DPriv-Bench huggingface dataset:
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon$-DP? (assume $c>1$)

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.} A database $\mathcal{D}$, a query sequence $\{q_i\}_{i=1}^\infty$ each with sensitivity at most $\Delta$, a set of thresholds $\{T_i\}_{i=1}^{\infty}$, privacy budget $\varepsilon$, and an answer cap $c \in \mathbb{N}$.

\textbf{Procedure.}
\begin{enumerate}
    \item Split privacy budget: $\varepsilon_1 = \varepsilon_2 = \varepsilon/2$.
    \item Sample a noisy reference threshold $\theta \sim \mathrm{Lap}(\Delta / \varepsilon_1)$.
    \item Initialize counter $r \leftarrow 0$.
    \item For each query $q_i$:
    \begin{enumerate}
        \item Draw $\eta_i \sim \mathrm{Lap}(2c\Delta / \varepsilon_2)$.
        \item If $q_i(\mathcal{D}) + \eta_i \ge T_i + \theta$, output $\top$ and increment $r$.
        \item Stop if $r \ge c$; otherwise continue.
        \item If the condition fails, output $\perp$.
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: \citet[Algorithm~1]{lyu2017understanding}
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon$-DP? (assume $c>1$)

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.} A database $\mathcal{D}$, a query sequence $\{q_i\}_{i=1}^\infty$ each with sensitivity at most $\Delta$, a thresholds $T$, privacy budget $\varepsilon$, and an answer cap $c \in \mathbb{N}$.

\textbf{Procedure.}
\begin{enumerate}
    \item Allocate $\varepsilon_1 = \varepsilon_2 = \varepsilon/2$.
    \item Sample threshold noise $\theta \sim \mathrm{Lap}(c\Delta / \varepsilon_1)$.
    \item Initialize $r \leftarrow 0$.
    \item For each $q_i$:
    \begin{enumerate}
        \item Draw $\eta_i \sim \mathrm{Lap}(2c\Delta / \varepsilon_1)$.
        \item If $q_i(\mathcal{D}) + \eta_i \ge T + \theta$, report $\top$.
        \item Resample $\theta' \sim \mathrm{Lap}(c\Delta / \varepsilon_2)$ for the next iteration.
        \item Increment $r$, and stop once $r \ge c$.
        \item Otherwise output $\perp$.
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: \citet[Algorithm~2]{lyu2017understanding}
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon$-DP? (assume $c>1$)

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.}  A database $\mathcal{D}$, a query sequence $\{q_i\}_{i=1}^\infty$ each with sensitivity at most $\Delta$, a thresholds $T$, privacy budget $\varepsilon$, and an answer cap $c \in \mathbb{N}$.


\textbf{Procedure.}
\begin{enumerate}
    \item Split $\varepsilon$ as $\varepsilon_1 = \varepsilon/2$, $\varepsilon_2 = \varepsilon - \varepsilon_1$.
    \item Sample threshold offset $\theta \sim \mathrm{Lap}(\Delta / \varepsilon_1)$.
    \item Initialize $r \leftarrow 0$.
    \item For each $q_i$:
    \begin{enumerate}
        \item Draw $\eta_i \sim \mathrm{Lap}(c\Delta / \varepsilon_2)$.
        \item If $q_i(\mathcal{D}) + \eta_i \ge T + \theta$, release the noisy score $q_i(\mathcal{D}) + \eta_i$.
        \item Increment $r$ and stop if $r \ge c$.
        \item Otherwise, return $\bot$.
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: \citet[Algorithm~3]{lyu2017understanding}
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon$-DP? (assume $c>1$)

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.} A database $\mathcal{D}$, a query sequence $\{q_i\}_{i=1}^\infty$ each with sensitivity at most $\Delta$, a thresholds $T$, privacy budget $\varepsilon$, and an answer cap $c \in \mathbb{N}$.


\textbf{Procedure.}
\begin{enumerate}
    \item Allocate $\varepsilon_1 = \varepsilon / 4$ to threshold noise; $\varepsilon_2 = \varepsilon - \varepsilon_1$.
    \item Draw $\theta \sim \mathrm{Lap}(\Delta / \varepsilon_1)$ and set $r \leftarrow 0$.
    \item For each $q_i$:
    \begin{enumerate}
        \item Sample $\eta_i \sim \mathrm{Lap}(\Delta / \varepsilon_2)$.
        \item If $q_i(\mathcal{D}) + \eta_i \ge T + \theta$, emit $\top$ and increment $r$.
        \item Otherwise output $\perp$; stop when $r \ge c$; 
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: \citet[Algorithm~4]{lyu2017understanding}
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon$-DP?

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.} Database $\mathcal{D}$, queries $Q$, sensitivity $\Delta$, global threshold $T$, privacy budget $\varepsilon$.

\textbf{Procedure.}
\begin{enumerate}
    \item Use $\varepsilon_1 = \varepsilon/2$, $\varepsilon_2 = \varepsilon - \varepsilon_1$.
    \item Perturb threshold once: $\theta \sim \mathrm{Lap}(\Delta / \varepsilon_1)$.
    \item Set $r \leftarrow 0$.
    \item For each $q_i$:
    \begin{enumerate}
        \item Output $\top$ if $q_i(\mathcal{D}) \ge T + \theta$, otherwise $\perp$.
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: \citet[Algorithm~5]{lyu2017understanding}
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon$-DP?

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.} Dataset $\mathcal{D}$, sensitivity $\Delta$, per-query thresholds $\{T_i\}$, and total privacy budget $\varepsilon$.

\textbf{Procedure.}
\begin{enumerate}
    \item Divide budget: $\varepsilon_1 = \varepsilon/2$, $\varepsilon_2 = \varepsilon - \varepsilon_1$.
    \item Sample $\theta \sim \mathrm{Lap}(\Delta / \varepsilon_1)$.
    \item For each $q_i$:
    \begin{enumerate}
        \item Draw $\eta_i \sim \mathrm{Lap}(\Delta / \varepsilon_2)$.
        \item If $q_i(\mathcal{D}) + \eta_i \ge T_i + \theta$, output $\top$; else $\perp$.
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: \citet[Algorithm~6]{lyu2017understanding}
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon/2$-DP? (assume $c>1$)

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.} A database $\mathcal{D}$, a query sequence $\{q_i\}_{i=1}^\infty$ each with sensitivity at most $\Delta$, a set of thresholds $\{T_i\}_{i=1}^{\infty}$, privacy budget $\varepsilon$, and an answer cap $c \in \mathbb{N}$.

\textbf{Procedure.}
\begin{enumerate}
    \item Split privacy budget: $\varepsilon_1 = \varepsilon_2 = \varepsilon/2$.
    \item Sample a noisy reference threshold $\theta \sim \mathrm{Lap}(\Delta / \varepsilon_1)$.
    \item Initialize counter $r \leftarrow 0$.
    \item For each query $q_i$:
    \begin{enumerate}
        \item Draw $\eta_i \sim \mathrm{Lap}(2c\Delta / \varepsilon_2)$.
        \item If $q_i(\mathcal{D}) + \eta_i \ge T_i + \theta$, output $\top$ and increment $r$.
        \item Stop if $r \ge c$; otherwise continue.
        \item If the condition fails, output $\perp$.
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: The privacy guarantee comes from \citet[Algorithm~1]{lyu2017understanding}, should be $\varepsilon$-DP by adaptive composition.
Question: Does the following implementation of the sparse vector technique (SVT) satisfy $\varepsilon$-DP, under the add/remove neighbouring relation? (assume $c>1$)

\begin{algorithm}[H]
\caption{SVT}
\textbf{Input.} A database $\mathcal{D}$ with each datum $x \in \mathbb{R}$, a query sequence $\{q_i\}_{i=1}^\infty$ with $q_i = \sum_{x \in D} \mathbf{1}\{x \geq i\}$, privacy budget $\varepsilon$, and an answer cap $c \in \mathbb{N}$.

\textbf{Procedure.}
\begin{enumerate}
    \item Split privacy budget: $\varepsilon_1 = \varepsilon_2 = \varepsilon/2$.
    \item Sample a noisy reference threshold $\theta \sim \mathrm{Lap}(\Delta / \varepsilon_1)$.
    \item Initialize counter $r \leftarrow 0$.
    \item For each query $q_i$:
    \begin{enumerate}
        \item Draw $\eta_i \sim \mathrm{Lap}(c\Delta / \varepsilon_2)$.
        \item If $q_i(\mathcal{D}) + \eta_i \ge i + \theta$, output $\top$ and increment $r$.
        \item Stop if $r \ge c$; otherwise continue.
        \item If the condition fails, output $\perp$.
    \end{enumerate}
\end{enumerate}
\end{algorithm}
Subject: Accounting and Composition / SVT
Rationale: Algorithm~1 in \citet{lyu2017understanding}. Moreover, by the monotone query property, the noise in line~4(a) only needs to be $\mathrm{Lap}(c\Delta/\varepsilon_2)$ (rather than $\mathrm{Lap}(2c\Delta/\varepsilon_2)$).