erchiw/DPriv-Bench huggingface dataset:
Question: Suppose $\varepsilon(\lambda)$ is defined:
$$\varepsilon(\lambda) := 
\frac{1}{\lambda}
\log \left[
(1 - q) \cdot \mathbf{A}(q, \mu_2, \varepsilon_2)^{\lambda - 1}
+ q \cdot \mathbf{B}(q, \mu_1, \varepsilon_1)^{\lambda - 1}
\right],
$$
where $q = \min_{i^*\in [K]}\frac{1}{2}\sum_{i\neq i^*}\mathrm{erfc}\left(\frac{n_{i^*}-n_i}{2\sigma_2}\right)$, $\mu_2=\sigma_2\cdot \sqrt{\log(1/q)}$, $\mu_1=\mu_2+1$, $\varepsilon_1=\mu_1/\sigma_2^2$, $\varepsilon_2=\mu_2/\sigma_2^2$, $\mathbf{A}(q, \mu_2, \varepsilon_2)=(1-q)/\left(1-(qe^{\varepsilon_2})^{\frac{\mu2-1}{\mu_2}}\right)$ and $ \mathbf{B}(q, \mu_1, \varepsilon_1)=e^{\varepsilon_1}/q^{\frac{1}{\mu_1-1}}$.
When $q<1, \mu_1\geq \lambda, \mu_2>1$, and $q\leq e^{(\mu_2-1)\varepsilon_2}/\left(\frac{\mu_1}{\mu_1-1}\cdot \frac{\mu_2}{\mu_2-1}\right)^{\mu_2}$, does the following algorithm satisfy the data dependent $(\lambda, \lambda/\sigma_1^2+\varepsilon(\lambda))$-RDP?

\begin{algorithm}[H]
\caption{Confident-GNMax Aggregator}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input query $x$, threshold $T$, noise parameters $\sigma_1, \sigma_2$, $K$ classes}
Compute vote counts $n_j(x)$ for each class $j\in [K]$;

\If{$\max_{j\in [K]} n_j(x) + \mathcal{N}(0, \sigma_1^2) \ge T$}{
\textbf{return} $\arg\max_{j\in [K]} \{ n_j(x) + \mathcal{N}(0, \sigma_2^2) \}$
}
\Else{
\textbf{return} $\bot$
}
\end{algorithm}
Subject: DP-ML / PATE
Rationale: The algorithm is \citet[Algorithm~1]{papernot2018scalable}. The proof is by \citet[Proposition~8, Theorem~6]{papernot2018scalable} and sequential composition of R\'enyi DP \citep{mironov2017renyi}. The leading factor in $\varepsilon(\lambda)$ is changed from $\frac{1}{\lambda-1}$ to $\frac{1}{\lambda}$, thus the original privacy proof no longer applies and the stated privacy guarantee does not hold in general.
Question: Suppose $\varepsilon(\lambda)$ is defined:
$$\varepsilon(\lambda) := 
\frac{1}{\lambda-1}
\log \left[
(1 - q) \cdot \mathbf{A}(q, \mu_2, \varepsilon_2)^{\lambda - 1}
+ q \cdot \mathbf{B}(q, \mu_1, \varepsilon_1)^{\lambda - 1}
\right],
$$
where $q = \min_{i^*\in [K]}\frac{1}{2}\sum_{i\neq i^*}\mathrm{erfc}\left(\frac{n_{i^*}-n_i}{2\sigma_2}\right)$, $\mu_2=\sigma_2\cdot \sqrt{\log(1/q)}$, $\mu_1=\mu_2+1$, $\varepsilon_1=\mu_1/\sigma_2^2$, $\varepsilon_2=\mu_2/\sigma_2^2$, $\mathbf{A}(q, \mu_2, \varepsilon_2)=(1-q)/\left(1-(qe^{\varepsilon_2})^{\frac{\mu2-1}{\mu_2}}\right)$ and $ \mathbf{B}(q, \mu_1, \varepsilon_1)=e^{\varepsilon_1}/q^{\frac{1}{\mu_1-1}}$.
When $q\leq e^{(\mu_2-1)\varepsilon_2}/\left(\frac{\mu_1}{\mu_1-1}\cdot \frac{\mu_2}{\mu_2-1}\right)^{\mu_2}$, does the following algorithm satisfy the data dependent $(\lambda, \lambda/\sigma_1^2+\varepsilon(\lambda))$-RDP?

\begin{algorithm}[H]
\caption{Confident-GNMax Aggregator}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input query $x$, threshold $T$, noise parameters $\sigma_1, \sigma_2$, $K$ classes}
Compute vote counts $n_j(x)$ for each class $j\in [K]$;

\If{$\max_{j\in [K]} n_j(x) + \mathcal{N}(0, \sigma_1^2) \ge T$}{
\textbf{return} $\arg\max_{j\in [K]} \{ n_j(x) + \mathcal{N}(0, \sigma_2^2) \}$
}
\Else{
\textbf{return} $\bot$
}
\end{algorithm}
Subject: DP-ML / PATE
Rationale: The algorithm is \citet[Algorithm~1]{papernot2018scalable}. Since we drop the assumptions $q<1$, $\mu_1 \ge \lambda$, and $\mu_2>1$, the original privacy proof no longer applies and the stated privacy guarantee does not hold in general.
Question: Given dataset $X \in \mathcal{X}^*$, and query $f:\mathcal{X}^* \rightarrow \mathbb{R}$, we define a proxy: 
\[D_{\beta}^{f}(X)= \min_{X''} \left\{ \mathrm{Hamming}(X, X'') : \max\limits_{X \text{ and } X' \text{neighbours}}\|f(X) - f(X')\|_1 > \beta \right\}\]. 

Does the following algorithm satisfy $(\varepsilon,\delta)$-DP?

\begin{algorithm}[H]
\caption{Propose-Test-Release}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\Input{Dataset $X$; privacy parameters $\varepsilon, \delta$; proposed bound $\beta$; query function $f : \mathcal{X} \to \mathbb{R}$.}
\eIf{$D_{\beta}^{f}(X) + \mathrm{Lap}\left(\frac{2}{\varepsilon}\right)
\le \frac{2\log(1/\delta)}{\varepsilon}$}{
    \textbf{output} $\bot$\;
}{
    \textbf{release} $f(X) + \mathrm{Lap}\!\left(\tfrac{2\beta}{\varepsilon}\right)$\;
}
\end{algorithm}
Subject: Data-Adaptive / PTR
Rationale: The algorithm is propose-test-release from \citet{dwork2009differential}. The privacy guarantee follows \citet[Proposition~7.3.2]{vadhan2017complexity}
Question: Given dataset $X \in \mathcal{X}^*$, and query $f:\mathcal{X}^* \rightarrow \mathbb{R}$, we define a proxy: 
\[D_{\beta}^{f}(X)= \min_{X''} \left\{ \mathrm{Hamming}(X, X'') : \max\limits_{X \text{ and } X' \text{neighbours}}\|f(X) - f(X')\|_1 > \beta \right\}\]. 

Does the following algorithm satisfy $(\varepsilon,\delta)$-DP?

\begin{algorithm}[H]
\caption{Propose-Test-Release}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}
\Input{Dataset $X$; privacy parameters $\varepsilon, \delta$; proposed bound $\beta$; query function $f : \mathcal{X} \to \mathbb{R}$.}
\eIf{$D_{\beta}^{f}(X) + \mathrm{Lap}\left(\frac{2}{\varepsilon}\right)
\le \frac{2\log(1/\delta)}{\varepsilon}$}{
    \textbf{output} $\bot$\;
}{
    \textbf{release} $f(X) + \mathrm{Lap}\!\left(\tfrac{\beta}{\varepsilon}\right)$\;
}
\end{algorithm}
Subject: Data-Adaptive / PTR
Rationale: The algorithm is modified from propose-test-release from \citet{dwork2009differential}. The release step follows $\varepsilon$-DP when the local sensitivity is upper bounded by $\beta$. Thus, following the composition style analysis (\citet[Proposition~7.3.2]{vadhan2017complexity}), the privacy guarantee is $(\frac{3\varepsilon}{2},\delta)$-DP, which is weaker than $(\varepsilon,\delta)$-DP.
Question: Given a dataset $X \in \mathcal{X}^*$, a proposed noise scale $\Delta > 0$, and a query function
$f : \mathcal{X} \to \mathbb{R}$, define the local sensitivity of $f$ at $X$ as $\Delta_{\mathrm{LS}}(X):=
\max_{X'} \Bigl\{ \lVert f(X) - f(X') \rVert_1 \;\big|\; X' \text{ is a neighbor of } X \Bigr\}$. Suppose we have an oracle $\mathcal{T} : \mathcal{X} \to \{0,1\}$ such that: (1) $\mathcal{T}$ satisfies $(\varepsilon,\delta)$-differential privacy; (2) whenever $\Delta_{\mathrm{LS}}(X) \ge \Delta / \varepsilon$, it holds that $\Pr\bigl[ \mathcal{T}(X) = 1 \bigr] \le \delta$. Does the following algorithm satisfy $(2\varepsilon, 2\delta)$-differential privacy?

\begin{algorithm}[H]
\caption{Propose-test-release-variant}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}

\Input{Dataset $X$; budget $\varepsilon$; $(\varepsilon, \delta)$-DP oracle $\mathcal{T}$ with false positive rate $\le \delta$} 

\If{\textbf{not} $\mathcal{T}(X)$}{
    \textbf{output} $\bot$\;
}
\Else{
    \textbf{release} $\theta = f(X) + \mathrm{Laplace}(\Delta)$\;
}
\end{algorithm}
Subject: Data-Adaptive / PTR
Rationale: The proof follows by \citet[Theorem~4.3]{redberg2023generalized}
Question: Given a dataset $X \in \mathcal{X}^*$, a proposed noise scale $\Delta > 0$, and a query function
$f : \mathcal{X} \to \mathbb{R}$, define the local sensitivity of $f$ at $X$ as $\Delta_{\mathrm{LS}}(X):=
\max_{X'} \Bigl\{ \lVert f(X) - f(X') \rVert_1 \;\big|\; X' \text{ is a neighbor of } X \Bigr\}$. Suppose we have an oracle $\mathcal{T} : \mathcal{X} \to \{0,1\}$ such that: (1) $\mathcal{T}$ satisfies $(\varepsilon,\delta)$-differential privacy; (2) whenever $\Delta_{\mathrm{LS}}(X) \ge \Delta / \varepsilon$, it holds that $\Pr\bigl[ \mathcal{T}(X) = 1 \bigr] \le \delta$. Does the following algorithm satisfy $(2\varepsilon, 2\delta)$-differential privacy?

\begin{algorithm}[H]
\caption{Propose-test-release-variant}
\DontPrintSemicolon
\SetKwInOut{Input}{Input}

\Input{Dataset $X$; budget $\varepsilon$; $(\varepsilon, \delta)$-DP oracle $\mathcal{T}$ with false positive rate $\le \delta$} 

\If{\textbf{not} $\mathcal{T}(X)$}{
    \textbf{output} $\bot$\;
}
\Else{
    \textbf{release} $\theta = f(X) + \mathrm{Laplace}(\frac{\Delta_{\mathrm{LS}}}{\varepsilon})$\;
}
\end{algorithm}
Subject: Data-Adaptive / PTR
Rationale: This is modified from \citet[Algorithm~2]{redberg2023generalized}. The "release" step is not $\varepsilon$-DP as it add noise calibrated to the local sensitivity, rather than the propose noise scale $\Delta$. Thus the whole procedure is not $(2\varepsilon,2\delta)$-DP in general.
Question: Does the quantile estimation mechanism described below satisfy $\varepsilon$-differential privacy?

\begin{algorithm}[H]
\caption{DP Single Quantile Estimation via Exponential Mechanism}
\KwIn{Quantile level $q\in[0,1]$, dataset $X = (x_1,\ldots,x_n) \subset (a,b)^n$, privacy budget $\varepsilon$.}
\KwOut{Quantile estimate $v \in (a,b)$.}

Define: $u(X,w) = -\bigl|\#\{x \in X \mid x<w\} - \lfloor qn \rfloor \bigl|$ \\
Partition $(a,b)$ into intervals $I_k=[x_{k-1},x_k]$, $k=1,\ldots,n+1$ where $x_0=a$, $x_{n+1}=b$ \\
Sample $I_k$ with probability 
\[
\Pr[\mathcal{A}(X)=I_k] \propto \exp\!\Bigl(\tfrac{\varepsilon u(X,I_k)}{2}\Bigr)(x_k-x_{k-1}).
\]\\
Output $v \sim \mathrm{Unif}(I_k)$.
\end{algorithm}
Subject: DP-statistics / quantile
Rationale: The algorithm is the DP single-quantile mechanism defined in \citet[Appendix~A]{kaplan2022differentially}. It satisfies $\varepsilon$-DP by \citet[Lemma~A.1]{kaplan2022differentially}.
Question: Does the quantile estimation mechanism described below satisfy $\varepsilon/2$-differential privacy?

\begin{algorithm}[H]
\caption{DP Single Quantile Estimation via Exponential Mechanism}
\KwIn{Quantile level $q\in[0,1]$, dataset $X = (x_1,\ldots,x_n) \subset (a,b)^n$, privacy budget $\varepsilon$.}
\KwOut{Quantile estimate $v \in (a,b)$.}

Define: $u(X,w) = -\bigl|\#\{x \in X \mid x<w\} - \lfloor qn \rfloor \bigl|$ \\
Partition $(a,b)$ into intervals $I_k=[x_{k-1},x_k]$, $k=1,\ldots,n+1$ where $x_0=a$, $x_{n+1}=b$ \\
Sample $I_k$ with probability 
\[
\Pr[\mathcal{A}(X)=I_k] \propto \exp\!\Bigl(\tfrac{\varepsilon u(X,I_k)}{2}\Bigr)(x_k-x_{k-1}).
\]\\
Output $v \sim \mathrm{Unif}(I_k)$.
\end{algorithm}
Subject: DP-statistics / quantile
Rationale: The algorithm is the DP single-quantile mechanism defined in \citet[Appendix~A]{kaplan2022differentially}. It satisfies $\varepsilon$-DP by \citet[Lemma~A.1]{kaplan2022differentially}.
Question: Does the quantile estimation mechanism described below satisfy $\varepsilon$-differential privacy under add/remove neighbouring relation?

\begin{algorithm}[H]
\caption{DP Single Quantile Estimation via Exponential Mechanism}
\KwIn{Quantile level $q\in[0,1]$, dataset $X = (x_1,\ldots,x_n) \subset (a,b)^n$, privacy budget $\varepsilon$.}
\KwOut{Quantile estimate $v \in (a,b)$.}

Define: $u(X,w) = -\bigl|\#\{x \in X \mid x<w\} - \lfloor qn \rfloor \bigl|$ \\
Partition $(a,b)$ into intervals $I_k=[x_{k-1},x_k]$, $k=1,\ldots,n+1$ where $x_0=a$, $x_{n+1}=b$ \\
Sample $I_k$ with probability 
\[
\Pr[\mathcal{A}(X)=I_k] \propto \exp\!\Bigl(\tfrac{\varepsilon u(X,I_k)}{2}\Bigr)(x_k-x_{k-1}).
\]\\
Output $v \sim \mathrm{Unif}(I_k)$.
\end{algorithm}
Subject: DP-statistics / quantile
Rationale: The algorithm is the DP single-quantile mechanism defined in \citet[Appendix~A]{kaplan2022differentially}. It satisfies $\varepsilon$-DP by \citet[Lemma~A.1]{kaplan2022differentially}.
Question: Does the quantile-estimation mechanism described below satisfy $\varepsilon$-differential privacy?

\begin{algorithm}[H]
\caption{DP Single Quantile Estimation via Exponential Mechanism}
\KwIn{Quantile level $q\in[0,1]$, dataset $X = (x_1,\ldots,x_n) \subset (a,b)^n$, privacy budget $\varepsilon$.}
\KwOut{Quantile estimate $v \in (a,b)$.}

Define: $u(X,w) = -\bigl|\#\{x \in X \mid x<w\} - \lfloor qn \rfloor \bigl|$ \\
Let $I_k=[x_{k-1},x_k]$, $k=1,\ldots,n+1$ where $x_0=a$, $x_{n+1}=b$ \\
Sample $I_k$ with probability 
\[
\Pr[\mathcal{A}(X)=I_k] \propto \exp\!\Bigl(\varepsilon u(X,I_k)\Bigr)(x_k-x_{k-1}).
\]\\
Output $v \sim \mathrm{Unif}(I_k)$.
\end{algorithm}
Subject: DP-statistics / quantile
Rationale: The algorithm is modified from the DP single-quantile mechanism defined in \citet[Appendix~A]{kaplan2022differentially}. However, the exponential mechanism is missing a factor of $1/2$ in the exponent of its density and therefore does not satisfy $\varepsilon$-DP.
Question: Does the quantile-estimation mechanism described below satisfy $\varepsilon$-differential privacy?

\begin{algorithm}[H]
\caption{DP Single Quantile Estimation via Exponential Mechanism}
\KwIn{Quantile level $q\in[0,1]$, dataset $X = (x_1,\ldots,x_n) \subset (a,b)^n$, privacy budget $\varepsilon$.}
\KwOut{Quantile estimate $v \in (a,b)$.}

Define: $u(X,w) = -\bigl|\#\{x \in X \mid x<w\} - \lfloor qn \rfloor \bigl|$ \\
Let $I_k=[x_{k-1},x_k]$, $k=1,\ldots,n+1$ where $x_0=a$, $x_{n+1}=b$ \\
Sample $I_k$ using exponential mechanism
\[
\Pr[\mathcal{A}(X)=I_k] \propto \exp\!\Bigl(\tfrac{\varepsilon u(X,I_k)}{2}\Bigr).
\]\\
Output $v \sim \mathrm{Unif}(I_k)$.
\end{algorithm}
Subject: DP-statistics / quantile
Rationale: The algorithm is modified from the DP single-quantile mechanism defined in \citet[Appendix~A]{kaplan2022differentially}. However, the exponential mechanism is missing the interval-length multiplier in its density and therefore does not satisfy $\varepsilon$-DP.
Question: Let $\{\mathcal{M}_i\}_{i=1}^{n}$ be mechanisms, each satisfying $\varepsilon$-DP under the same neighboring relation. Consider their sequential (possibly adaptive) composition on the same dataset. For any order $\alpha>1$, does the composed mechanism $\mathcal{M}$ satisfy $(\alpha, n\varepsilon^{2}/2)$-RDP?
Subject: Accounting and Composition / Sequential or Adaptive Composition
Rationale: Consider the following counterexample. Let $\mathcal{M}$ be randomized response on a single bit, which outputs the true bit with probability $p=\frac{e^{0.5}}{1+e^{0.5}}$. Then $\mathcal{M}$ is $0.5$-DP. However, the statement in question would imply that $\mathcal{M}$ satisfies $(\infty,0.125)$-RDP. Since $(\infty,\delta)$-RDP is equivalent to $\delta$-DP (because $D_\infty(P\|Q)=\log \sup_y \frac{P(y)}{Q(y)}$), this would further imply that $\mathcal{M}$ is $0.125$-DP, contradicting the fact that the privacy loss of randomized response here is exactly $0.5$.
Question: Let $\{\mathcal{M}_i\}_{i=1}^{n}$ be mechanisms, each satisfying $\varepsilon$-DP under the same neighboring relation. Consider their sequential (possibly adaptive) composition on the same dataset. Does the composed mechanism $\mathcal{M}$ satisfy $(\alpha, \sqrt{n}\varepsilon^{2})$-RDP
Subject: Accounting and Composition / Sequential or Adaptive Composition
Rationale: Consider the following counterexample. Let $\mathcal{M}$ be randomized response on a single bit, which outputs the true bit with probability $p=\frac{e^{0.5}}{1+e^{0.5}}$. Then $\mathcal{M}$ is $0.5$-DP. However, the statement in question would imply that $\mathcal{M}$ satisfies $(\infty,0.125)$-RDP. Since $(\infty,\varepsilon)$-RDP is equivalent to $\varepsilon$-DP, this would further imply that $\mathcal{M}$ is $0.125$-DP, contradicting the fact that the privacy loss of randomized response here is exactly $0.5$.
Question: Let $\{\mathcal{M}_i\}_{i=1}^{n}$ be mechanisms, each satisfying $\varepsilon$-DP under the same neighboring relation. Consider their sequential (possibly adaptive) composition on the same dataset. Does the composed mechanism $\mathcal{M}$ satisfy $(n\varepsilon^{2}/2)$-zCDP
Subject: Accounting and Composition / Sequential or Adaptive Composition
Rationale: Since each mechanism $\mathcal{M}_i$ satisfies $\varepsilon$-DP, it also satisfies $\frac{\varepsilon^2}{2}$-zCDP. By the (adaptive) composition property of zCDP, the sequential composition $\mathcal{M}$ therefore satisfies $\frac{n\varepsilon^2}{2}$-zCDP.
Question: Let $\{\mathcal{M}_i\}_{i=1}^{n}$ be mechanisms, each satisfying $\varepsilon$-DP under the same neighboring relation. Consider their sequential (possibly adaptive) composition on the same dataset. Does the composed mechanism $\mathcal{M}$ satisfy $(\sqrt{n}\varepsilon^{2}/2)$-zCDP
Subject: Accounting and Composition / Sequential or Adaptive Composition
Rationale: Let the dataset be a single bit $x\in\{0,1\}$ with neighboring relation $0\sim 1$. Fix $\varepsilon>0$, and let each $\mathcal{M}_i$ be randomized response: on input $x$, output $x$ with probability $p=\frac{e^\varepsilon}{1+e^\varepsilon}$ and output $1-x$ otherwise. Then each $\mathcal{M}_i$ is $\varepsilon$-DP, and the sequential composition $\mathcal{M}$ outputs the vector of $n$ independent randomized-response outputs. Let $P=\mathcal{M}(0)$ and $Q=\mathcal{M}(1)$. For a single draw $i \in [n]$, when $\alpha>1$, the order-$\alpha$ R\'enyi divergence is $D_\alpha(P_i \|Q_i )=\frac{1}{\alpha-1}\log\!\left(\frac{e^{\varepsilon \alpha}+e^{\varepsilon(1-\alpha)}}{1+e^\varepsilon}\right) = \varepsilon - \frac{1}{\alpha-1}\log\left(\frac{1+\exp(-\varepsilon)}{1+\exp((1-2\alpha)\varepsilon)}\right) \geq \varepsilon - \frac{\log(1+\exp(-\varepsilon))}{\alpha-1}$. By additivity under composition, $D_\alpha(P\|Q)=\sum_{i=1}^n D_\alpha(P_i\|Q_i)\ge n\left(\varepsilon-\frac{\log(1+e^\varepsilon)}{\alpha-1}\right)$. Choosing $\alpha \ge 1+\frac{4\log(1+e^\varepsilon)}{\varepsilon}$ gives $D_\alpha(P\|Q)\ge \frac{3}{4}n\varepsilon$. If, towards a contradiction, $\mathcal{M}$ satisfied $\rho$-zCDP with $\rho=\frac{\sqrt{n}\varepsilon^2}{2}$, then it would satisfy $(\alpha,\alpha\rho)$-RDP for every $\alpha>1$, hence $D_\alpha(P\|Q)\le \alpha\rho=\alpha\cdot\frac{\sqrt{n}\varepsilon^2}{2}$. Setting $\alpha=\frac{\sqrt{n}}{\varepsilon}$ (and taking $n$ large enough so that this $\alpha$ also meets the earlier condition) yields the upper bound $\alpha\rho=\frac{n\varepsilon}{2}$, contradicting $D_\alpha(P\|Q)\ge \frac{3}{4}n\varepsilon$. Therefore,in general, the sequential composition of $n$ $\varepsilon$-DP mechanisms does not satisfy $\big(\frac{\sqrt{n}\varepsilon^2}{2}\big)$-zCDP.
Question: Let $\{\mathcal{M}_i\}_{i=1}^{n}$ be mechanisms, each satisfying $\varepsilon/n$-DP under the same neighboring relation (assume $\varepsilon<1$). Consider their sequential (possibly adaptive) composition on the same dataset. Does the composed mechanism $\mathcal{M}$ satisfy $(\frac{\varepsilon}{10}, \exp(\frac{\varepsilon^2}{n}-\frac{\varepsilon}{10}-1))$-DP?
Subject: Accounting and Composition / Sequential or Adaptive Composition
Rationale: Since each mechanism $\mathcal{M}_i$ satisfies $\varepsilon/n$-DP, it also satisfies $\frac{\varepsilon^2}{2n^2}$-zCDP. By the (adaptive) composition property of zCDP, the sequential composition $\mathcal{M}$ therefore satisfies $\frac{\varepsilon^2}{2n}$-zCDP. Using \citet[Proposition~12]{canonne2020discrete} with $\alpha=2$ and $\tau=\frac{\varepsilon^2}{n}$, it satisfies $(\frac{\varepsilon}{10}, \delta)$-DP with $\delta=\exp(\frac{\varepsilon^2}{n}-\frac{\varepsilon}{10}-1)$
Question: Let $\{\mathcal{M}_i\}_{i=1}^{n}$ be exponential mechanisms, each satisfying $\varepsilon/n$-DP under the same neighboring relation. Consider their sequential (possibly adaptive) composition on the same dataset. Does the composed mechanism $\mathcal{M}$ satisfy $(\frac{\varepsilon}{16}, \exp(\frac{\varepsilon^2}{4n}-\frac{\varepsilon}{16}-1))$-DP?
Subject: Accounting and Composition / Sequential or Adaptive Composition
Rationale: Since each mechanism $\mathcal{M}_i$ satisfies $\varepsilon/n$-DP, by the bounded range property of exponential nechanism, it also satisfies $\frac{\varepsilon^2}{8n^2}$-zCDP. By the (adaptive) composition property of zCDP, the sequential composition $\mathcal{M}$ therefore satisfies $\frac{\varepsilon^2}{8n}$-zCDP. Using \citet[Proposition~12]{canonne2020discrete} with $\alpha=2$ and $\tau=\frac{\varepsilon^2}{n}$, it satisfies $(\frac{\varepsilon}{16}, \delta)$-DP with $\delta=\exp(\frac{\varepsilon^2}{4n}-\frac{\varepsilon}{16}-1)$
Question: Let $\{\mathcal{M}_i\}_{i=1}^{n}$ be report noisy max mechanisms with gaussian noise, each satisfying $(\varepsilon/n,\delta)$-DP under the same neighboring relation. Consider their sequential (possibly adaptive) composition on the same dataset. Does the composed mechanism $\mathcal{M}$ satisfy $(\varepsilon, \exp(\frac{\varepsilon^2}{8n}-\varepsilon-1))$-DP?
Subject: Accounting and Composition / Sequential or Adaptive Composition
Rationale: Take $n=1$ and set $\varepsilon=1$, so $\delta'=\exp(1/8-1-1)=\exp(-1.875)\approx 0.153$. Choose $\delta=0.2>\delta'$, and let $\mathcal{M}$ be a Gaussian report-noisy-max mechanism that satisfies $(1,0.2)$-DP. Since $(\varepsilon,\delta)$-DP does not imply $(\varepsilon,\delta')$-DP for any $\delta'<\delta$, it follows that $\mathcal{M}$ need not satisfy $(1,0.153)$-DP.
Question: Does the following algorithm satisfy $8$-zCDP under the replace-one neighbouring relation?  

\begin{algorithm}[H]
\caption{Trimmed Mean estimation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} \in [0,1]^n$, integer $m \in [0,n/2)$}
Denote the $i$-th order statistics of $D$ by $x_{(i)}$, where $x_{(1)} \leq \ldots x_{(n)}$ \\
Let $T = \Pi_{[0,1]} \left(\frac{\sum_{i=m+1}^{n-m}x_{(i)}}{n-2m}\right)$, where $\Pi$ denotes projection operator \\
Sample $a \sim \mathcal{N}(0,1)$ \\
Calculate $b = \frac{e^{a} - e^{-a}}{2}$ \\
Get scale $c = \max\{\frac{x_{(n)} - x_{(m)}}{n-2m}, \exp(-m)\}$\\
\textbf{return} $T + cb$
\end{algorithm}
Subject: Data-Adaptive / Smooth_sensitivity
Rationale: The proof follows directly from \citet[Propositions~5 and Lemma~50]{bun2019average} with $t=s=1$.
Question: Does the following algorithm satisfy $8$-zCDP under the replace-one neighbouring relation?  


\begin{algorithm}[H]
\caption{Trimmed Mean estimation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} \in [0,1]^n$, integer $m \in [0,n/2)$}
Denote the $i$-th order statistics of $D$ by $x_{(i)}$, where $x_{(1)} \leq \ldots x_{(n)}$ \\
Let $T = \Pi_{[0,1]} \left(\frac{\sum_{i=m+1}^{n-m}x_{(i)}}{n-2m}\right)$, where $\Pi$ denotes projection operator \\
Sample $a \sim \mathcal{N}(0,1)$ \\
Get scale $c = \max\{\frac{x_{(n)} - x_{(m)}}{n-2m}, \exp(-m)\}$\\
\textbf{return} $T + ca$
\end{algorithm}
Subject: Data-Adaptive / Smooth_sensitivity
Rationale: Take \(n=3\) and \(m=1\). Then \(T=x_{(2)}\) and \(c=\max\{x_{(3)}-x_{(1)},e^{-1}\}\). Consider replace-one neighbors \(D=(0,0,1)\) and \(D'=(0,0,0)\). For \(D\), \(T=0\) and \(c=1\), hence \(\mathcal{M}(D)\sim\mathcal{N}(0,1)\). For \(D'\), \(T=0\) and \(c=e^{-1}\), hence \(\mathcal{M}(D')\sim\mathcal{N}(0,e^{-2})\). For \(P=\mathcal{N}(0,\sigma_1^2)\) and \(Q=\mathcal{N}(0,\sigma_2^2)\) with \(\sigma_1^2>\sigma_2^2\), one has \(D_\alpha(P\|Q)<\infty\) iff \(\alpha<\sigma_1^2/(\sigma_1^2-\sigma_2^2)\). Plugging in \(\sigma_1^2=1\) and \(\sigma_2^2=e^{-2}\) yields the threshold \(\alpha \geq 1/(1-e^{-2})\approx 1.157\), so in particular \(D_2(\mathcal{M}(D)\,\|\,\mathcal{M}(D'))=\infty\). Therefore the mechanism is not \(\rho\)-zCDP for any finite \(\rho\) (hence not \(8\)-zCDP).
Question: Does the following algorithm satisfy $2$-zCDP under the replace-one neighbouring relation?  

\begin{algorithm}[H]
\caption{Trimmed Mean estimation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} \in [0,1]^n$, integer $m \in [0,n/2)$}
Denote the $i$-th order statistics of $D$ by $x_{(i)}$, where $x_{(1)} \leq \ldots x_{(n)}$ \\
Let $T = \Pi_{[0,1]} \left(\frac{\sum_{i=m+1}^{n-m}x_{(i)}}{n-2m}\right)$, where $\Pi$ denotes projection operator \\
Sample $a \sim \mathrm{Laplace}(0,1)$ \\
Sample $b \sim \mathcal{N}(0,1)$ \\
Get scale $c = \max\{\frac{x_{(n)} - x_{(m)}}{n-2m}, \exp(-m)\}$\\
\textbf{return} $T + e^{1.5+b}ac$
\end{algorithm}
Subject: Data-Adaptive / Smooth_sensitivity
Rationale: The proof follows directly from \citet[Propositions~3 and Lemma~50]{bun2019average} with $t=\sigma=1$, $s=\exp(-3/2)$.