erchiw/DPriv-Bench huggingface dataset:
Question: Suppose that for all $z\in \mathcal{Z}$, $\ell(\cdot, z)$ is twice-differentiable, and the rank of its Hessian $\nabla^2\ell(\mathbf{w}, z)$ at any $\mathbf{w}\in \mathcal{W}$ is at most 1. Also assume that  the smoothness parameter satisfies $\beta \leq \varepsilon n\lambda$. Is the following algorithm$(\varepsilon, \delta)$-differentially private?

\begin{algorithm}[H]
\caption{$\mathcal{A}_{\text{ObjP}}$: Objective Perturbation}
\KwIn{Private dataset $S = (z_1, \ldots, z_n) \in \mathcal{Z}^n$, 
$L$-Lipschitz, $\beta$-smooth, loss function $\ell$, privacy parameters 
$\varepsilon \le 1$, $\delta \le 1/n^2$, regularization parameter $\lambda$.}

\BlankLine
\textbf{1:} Sample $\mathbf{G} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \mathbf{I}_d)$, 
where $\sigma^2 = \dfrac{10 L^2 \log(1/\delta)}{\varepsilon^2}$\;

\textbf{2:} \textbf{return} 
$\hat{\mathbf{w}} = 
\arg\min_{\mathbf{w} \in \mathcal{W}} 
\hat{\mathcal{L}}(\mathbf{w}; S) 
+ \dfrac{\langle \mathbf{G}, \mathbf{w} \rangle}{n} 
+ \lambda \|\mathbf{w}\|^2$, 
where $\hat{\mathcal{L}}(\mathbf{w}; S) 
\triangleq \dfrac{1}{n} \sum_{i=1}^{n} \ell(\mathbf{w}, z_i)$\;

\end{algorithm}
Subject: DP-ML / objective perturbation
Rationale: The given algorithm is modified from \citet[Algorithm~2]{bassily2019private}, removing the convexity assumption on loss function $\ell$, thus doesn't satisfy DP in general.
Question: Suppose that for all $z\in \mathcal{Z}$, $\ell(\cdot, z)$ is twice-differentiable, and the rank of its Hessian $\nabla^2\ell(\mathbf{w}, z)$ at any $\mathbf{w}\in \mathcal{W}$ is at most 1. Also assume that  the smoothness parameter satisfies $\beta \leq \varepsilon n\lambda$. Is the following algorithm$(\varepsilon, \delta)$-differentially private?

\begin{algorithm}[H]
\caption{$\mathcal{A}_{\text{ObjP}}$: Objective Perturbation}
\KwIn{Private dataset $S = (z_1, \ldots, z_n) \in \mathcal{Z}^n$, 
$L$-Lipschitz, $\beta$-smooth, convex loss function $\ell$, convex set 
$\mathcal{W} \subseteq \mathbb{R}^d$, privacy parameters 
$\varepsilon \le 1$, $\delta \le 1/n^2$, regularization parameter $\lambda$, gradient solver $\mathcal{O}$}

\BlankLine
\textbf{1:} Sample $\mathbf{G} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \mathbf{I}_d)$, 
where $\sigma^2 = \dfrac{10 L^2 \log(1/\delta)}{\varepsilon^2}$\;

\textbf{2:} Define
$f(\mathbf{w}) = \hat{\mathcal{L}}(\mathbf{w}; S) 
+ \dfrac{\langle \mathbf{G}, \mathbf{w} \rangle}{n} 
+ \lambda \|\mathbf{w}\|^2$, 
where $\hat{\mathcal{L}}(\mathbf{w}; S) 
\triangleq \dfrac{1}{n} \sum_{i=1}^{n} \ell(\mathbf{w}, z_i)$\;


\textbf{3:} Specify the number of iterations \(T\) and the feasible region \(\mathcal{W}\). Apply gradient solver $\mathcal O$ to \(f(\mathbf{w})\) (constrained to \(\mathcal{W}\)) and output the solution path \(\{\hat{\mathbf{w}}_{t}\}_{t=1}^{T}\).\\

\KwRet{$\{\hat{\mathbf{w}}_{t}\}_{t=1}^{T}$}
\end{algorithm}
Subject: DP-ML / objective perturbation
Rationale: Objective perturbation guarantees DP only for the released minimizer. It does not, in general, provide DP for the entire released optimization trajectory.
Question: Suppose that for all $z\in \mathcal{Z}$, $\ell(\cdot, z)$ is twice-differentiable, and the rank of its Hessian $\nabla^2\ell(\mathbf{w}, z)$ at any $\mathbf{w}\in \mathcal{W}$ is at most 1. Also assume that  the smoothness parameter satisfies $\beta \leq \varepsilon n\lambda$. Is the following algorithm$(\varepsilon/2, \delta)$-differentially private?

\begin{algorithm}[H]
\caption{$\mathcal{A}_{\text{ObjP}}$: Objective Perturbation}
\KwIn{Private dataset $S = (z_1, \ldots, z_n) \in \mathcal{Z}^n$, 
$L$-Lipschitz, $\beta$-smooth, convex loss function $\ell$, convex set 
$\mathcal{W} \subseteq \mathbb{R}^d$, privacy parameters 
$\varepsilon \le 1$, $\delta \le 1/n^2$, regularization parameter $\lambda$.}

\BlankLine
\textbf{1:} Sample $\mathbf{G} \sim \mathcal{N}(\mathbf{0}, \sigma^2 \mathbf{I}_d)$, 
where $\sigma^2 = \dfrac{10 L^2 \log(1/\delta)}{\varepsilon^2}$\;

\textbf{2:} \textbf{return} 
$\hat{\mathbf{w}} = 
\arg\min_{\mathbf{w} \in \mathcal{W}} 
\hat{\mathcal{L}}(\mathbf{w}; S) 
+ \dfrac{\langle \mathbf{G}, \mathbf{w} \rangle}{n} 
+ \lambda \|\mathbf{w}\|^2$, 
where $\hat{\mathcal{L}}(\mathbf{w}; S) 
\triangleq \dfrac{1}{n} \sum_{i=1}^{n} \ell(\mathbf{w}, z_i)$\;

\end{algorithm}
Subject: DP-ML / objective perturbation
Rationale: Take $d=1$ and $\mathcal W=[-1,1]$. Let the loss be $\ell(w,z)=zw$ with $z\in\{-1,+1\}$. Then $\ell(\cdot,z)$ is convex and twice differentiable, $L=1$-Lipschitz since $|\partial_w\ell(w,z)|=|z|\le 1$, $\beta=0$-smooth, and $\nabla^2\ell(w,z)=0$ so $\mathrm{rank}(\nabla^2\ell(w,z))=0\le 1$; hence $\beta\le \varepsilon n\lambda$ holds for any $\varepsilon,n,\lambda$. Fix $n=100$, $\varepsilon=1$, $\delta=1/n^2=10^{-4}$, $\lambda=1$, $L=1$. Consider replace-one neighboring datasets $S$ and $S'$ where $S$ has all $z_i=+1$ and $S'$ differs in one example with $z_1=-1$. Then $\hat{\mathcal L}(w;S)=w$ and $\hat{\mathcal L}(w;S')=0.98\,w$. The algorithm outputs $\hat w(S)=\arg\min_{w\in[-1,1]}\big(w+\tfrac{G}{n}w+\lambda w^2\big)=-\tfrac{1+G/n}{2\lambda}$ and $\hat w(S')=\arg\min_{w\in[-1,1]}\big(0.98\,w+\tfrac{G}{n}w+\lambda w^2\big)=-\tfrac{0.98+G/n}{2\lambda}$, where $G\sim\mathcal N(0,\sigma^2)$ with $\sigma^2=\tfrac{10L^2\log(1/\delta)}{\varepsilon^2}$. Thus $\hat w(S)$ and $\hat w(S')$ are Gaussians with common standard deviation $s=\tfrac{\sigma}{2\lambda n}$ and mean shift $\Delta=\mathbb E[\hat w(S')]-\mathbb E[\hat w(S)]=\tfrac{1-0.98}{2\lambda}=0.01$. With $\delta=10^{-4}$ and $\varepsilon=1$, $\sigma=\sqrt{10\log(10^4)}\approx 9.597$, hence $s=\tfrac{9.597}{2\cdot 1\cdot 100}\approx 0.047985$. For two Gaussians with equal variance, the tight $\delta$ at privacy level $\varepsilon_0$ is $\delta(\varepsilon_0)=\Phi\!\big(\tfrac{\Delta}{2s}-\varepsilon_0\tfrac{s}{\Delta}\big)-e^{\varepsilon_0}\Phi\!\big(-\tfrac{\Delta}{2s}-\varepsilon_0\tfrac{s}{\Delta}\big)$, where $\Phi$ is the standard normal CDF. Plugging $\Delta=0.01$, $s\approx 0.047985$, and $\varepsilon_0=\varepsilon/2=0.5$ yields $\delta(0.5)\approx 7.26\times 10^{-4}>10^{-4}$. Therefore the algorithm is not $(\varepsilon/2,\delta)$-DP in general.
Question: Let $\varepsilon > 0$, $\delta \in [0, \frac{1}{2})$. Let $F : \mathbb{R}^d \times \mathcal{X}^n \to \mathbb{R}$ be a function with $L_2$ sensitivity $\Delta_F$ and unique minimizer $w^*(X) = \arg\min_{w \in \mathbb{R}^d} F(w, X)$ for all $X \in \mathcal{X}^n$. The (conceptual) output perturbation algorithms $\mathcal{A}(X) = w_{\mathcal{A}}(X) := w^*(X) + z$ with noise given by density
$$
p_z(t) \propto 
\begin{cases}
\exp\!\left(-\dfrac{\varepsilon \|t\|_2}{\Delta_F}\right), & \text{if } \delta = 0,\\[1em]
\exp\!\left(-\dfrac{\varepsilon^2 \|t\|_2^2}{\Delta_F^2 (c_\delta + \sqrt{c_\delta^2 + \varepsilon})^2}\right), & \text{if } \delta \in (0, \tfrac{1}{2})
\end{cases}
$$
where $c_\delta := \sqrt{\log\!\left(\dfrac{2}{\sqrt{16\delta^2 + 1} - 1}\right)}$. Is $\mathcal{A}(X)$ $(\varepsilon, \delta)$-differentially private?
Subject: DP-ML / output perturbation
Rationale: Not necessarily. Adding Laplace/Gaussian noise to $w^*(X)$ is $(\varepsilon,\delta)$-DP only if the noise is calibrated to the $L_2$-sensitivity of $w^*(X)$, which does not follow from assuming $F$ has sensitivity $\Delta_F$ without additional conditions.
Question: Let $\varepsilon > 0$, $\delta \in [0, \frac{1}{2})$. Let $F : \mathbb{R}^d \times \mathcal{X}^n \to \mathbb{R}$ be a function with $L_2$ sensitivity $\Delta_F$ and unique minimizer $w^*(X) = \arg\min_{w \in \mathbb{R}^d} F(w, X)$ for all $X \in \mathcal{X}^n$. The (conceptual) output perturbation algorithms $\mathcal{A}(X) = w_{\mathcal{A}}(X) := w^*(X) + z$ with noise given by density
$$
p_z(t) \propto 
\begin{cases}
\exp\!\left(-\dfrac{\varepsilon \|t\|_2}{\Delta_F}\right), & \text{if } \delta = 0,\\[1em]
\exp\!\left(-\dfrac{\varepsilon \|t\|_2}{\Delta_F (c_\delta + \sqrt{c_\delta^2 + \varepsilon})}\right), & \text{if } \delta \in (0, \tfrac{1}{2})
\end{cases}
$$
where $c_\delta := \sqrt{\log\!\left(\dfrac{2}{\sqrt{16\delta^2 + 1} - 1}\right)}$. Is $\mathcal{A}(X)$ $(\varepsilon, \delta)$-differentially private?
Subject: DP-ML / output perturbation
Rationale: (1) Not necessarily: adding Laplace/Gaussian noise to $w^*(X)$ is $(\varepsilon,\delta)$-DP only if the noise is calibrated to the $L_2$-sensitivity of $w^*(X)$, which does not follow from assuming $F$ has sensitivity $\Delta_F$ without additional stability/regularity conditions; (2) the density for $\delta \in (0,1/2)$ is not correct.
Question: Let $\varepsilon > 0$, $\delta \in [0, \frac{1}{2})$. Let $F : \mathbb{R}^d \times \mathcal{X}^n \to \mathbb{R}$ be a function and assume it has unique minimizer $w^*(X) = \arg\min_{w \in \mathbb{R}^d} F(w, X)$ for all $X \in \mathcal{X}^n$. We define with $L_2$ sensitivity $\Delta_F := \sup_{X,X' \in \mathcal{X}^n,\; |X \triangle X'|\le 2} \left\| w^*(X) - w^*(X') \right\|_2$. The (conceptual) output perturbation algorithms $\mathcal{A}(X) = w_{\mathcal{A}}(X) := w^*(X) + z$ with noise given by density
$$
p_z(t) \propto 
\begin{cases}
\exp\!\left(-\dfrac{\varepsilon \|t\|_2}{\Delta_F}\right), & \text{if } \delta = 0,\\[1em]
\exp\!\left(-\dfrac{\varepsilon^2 \|t\|_2^2}{\Delta_F^2 (c_\delta + \sqrt{c_\delta^2 + \varepsilon})^2}\right), & \text{if } \delta \in (0, \tfrac{1}{2})
\end{cases}
$$
where $c_\delta := \sqrt{\log\!\left(\dfrac{2}{\sqrt{16\delta^2 + 1} - 1}\right)}$. Is $\mathcal{A}(X)$ $(\varepsilon, \delta)$-differentially private? 
Subject: DP-ML / output perturbation
Rationale: This is \citet[proposition~2.1]{lowy2021output}. The proof is in \citet[Appendix~B.1.1]{lowy2021output}.
Question: We aim to release a histogram whose bins are $n$ disjoint, data-independent intervals. 
If we add independent noise drawn from $\mathrm{Lap}(2/\varepsilon)$ to each bin, 
does the resulting mechanism satisfy $\varepsilon$-differential privacy under the replace-one neighboring relationship?
Subject: Accounting and Composition / Parallel Composition
Rationale: The sensitivity for releasing the histogram under the replace-one neighboring relation is 2. Therefore, adding independent Laplace noise with scale $\varepsilon/2$ to each histogram bin guarantees $\varepsilon$-differential privacy.
Question: We aim to release a histogram whose bins are $n$ data-independent but potentially non-disjoint intervals. 
If we add independent noise drawn from $\mathrm{Lap}(2/\varepsilon)$ to each bin, 
does the resulting mechanism satisfy $\varepsilon$-differential privacy under the replace-one neighboring relationship?
Subject: Accounting and Composition / Parallel Composition
Rationale: Since the histogram bins may be non-disjoint, replacing a single data point can affect the counts of more than two bins. Consequently, adding Laplace noise with scale \(2/\varepsilon\) may not be sufficient to guarantee \(\varepsilon\)-differential privacy.
Question: We aim to release a histogram whose bins are $n$ disjoint, data-independent intervals. 
If we add independent noise drawn from $\mathrm{Lap}(1/\varepsilon)$ to each bin, 
does the resulting mechanism satisfy $\varepsilon$-differential privacy under the replace-one neighboring relationship?
Subject: Accounting and Composition / Parallel Composition
Rationale: The sensitivity for releasing the histogram under the replace-one neighboring relation is 2. Therefore, adding independent Laplace noise with scale $\varepsilon$ to each histogram bin only guarantees $2\varepsilon$-differential privacy.
Question: We aim to release a histogram whose bins are $n$ disjoint, data-independent intervals. 
If we add independent noise drawn from $\mathrm{Lap}(1/\varepsilon)$ to each bin, 
does the resulting mechanism satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship?
Subject: Accounting and Composition / Parallel Composition
Rationale: The sensitivity for releasing the histogram under the add/remove neighboring relation is 1. Therefore, adding independent Laplace noise with scale $\varepsilon$ to each histogram bin guarantees $\varepsilon$-differential privacy.
Question: We aim to release a histogram whose bins are $n$ disjoint, data-dependent intervals. 
If we add independent noise drawn from $\mathrm{Lap}(1/\varepsilon)$ to each bin, 
does the resulting mechanism satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship?
Subject: Accounting and Composition / Parallel Composition
Rationale: Since the histogram bins are data-dependent, add/remove a single data point can potentially affect the counts of more than one bins. Consequently, adding Laplace noise with scale \(\varepsilon\) may not be sufficient to guarantee \(\varepsilon\)-differential privacy.
Question: Consider the following mechanism: $\mathcal{M}(X) := \{\mathcal{M}_i(X_i)\}_{i=1}^n$, where each subset $X_i$ is disjoint from the others, i.e., $X_i \cap X_j = \emptyset$ for all $i \neq j$, and their union covers the entire dataset, i.e., $\bigcup_{i=1}^n X_i = X$. Furthermore, the partition is data-independent. 
Suppose each mechanism $\mathcal{M}_i$ satisfies $(\varepsilon_i, \delta_i)$-differential privacy.  
Does the combined mechanism $\mathcal{M}$ satisfy $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy?
Subject: Accounting and Composition / Parallel Composition
Rationale: Since the histogram bins are data-dependent, add/remove a single data point can potentially affect the counts of more than one bins. Consequently, adding Laplace noise with scale \(\varepsilon\) may not be sufficient to guarantee \(\varepsilon\)-differential privacy.
Question: Consider the following mechanism: $\mathcal{M}(X) := \{\mathcal{M}_i(X_{n-i+1})\}_{i=1}^n$, where each subset $X_i$ is disjoint from the others, i.e., $X_i \cap X_j = \emptyset$ for all $i \neq j$, and their union covers the entire dataset, i.e., $\bigcup_{i=1}^n X_i = X$. Furthermore, the partition is data-independent. 
Suppose each mechanism $\mathcal{M}_i$ satisfies $(\varepsilon_i, \delta_i)$-differential privacy.  
Does the combined mechanism $\mathcal{M}$ satisfy $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy?
Subject: Accounting and Composition / Parallel Composition
Rationale: Under the assumptions that subsets are disjoint and the partition is data-independent, the combined mechanism satisfies parallel composition, thus $\mathcal{M}$ satisfies $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy.
Question: Consider the procedure that releases $\mathcal{M}:=\{a_i\}_{i=1}^n$. The outputs are defined recursively by $a_1=\mathcal{M}_1(X_1)$, $a_2=(a_1,\ \mathcal{M}_2(a_1,X_2))$, $a_3=(a_1,a_2,\ \mathcal{M}_3(a_1,a_2,X_3))$, and in general $a_n=(a_1,\ldots,a_{n-1},\ \mathcal{M}_n(a_1,\ldots,a_{n-1},X_n))$. Assume the datasets are disjoint and cover the whole data, i.e., $X_i\cap X_j=\emptyset$ for all $i\neq j$ and $\bigcup_{i=1}^n X_i=X$. Suppose each mechanism $\mathcal{M}_i$ is $(\varepsilon_i,\delta_i)$-DP with respect to its own subset $X_i$. Furthermore, the partition is data-independent. Does the overall release $\mathcal{M}$ satisfy $(\max_{i\in[n]}\varepsilon_i,\ \max_{i\in[n]}\delta_i)$-DP?
Subject: Accounting and Composition / Parallel Composition
Rationale: Under the assumptions that the subsets are disjoint and the partition is data-independent, the combined mechanism follows the parallel composition and post-processing property of differential privacy, this implies that $\mathcal{M}$ satisfies $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy.
Question: Consider releasing $\mathcal{M}:=\{a_i\}_{i=1}^n$, where $a_1=\mathcal{M}_1(X_1)$, $a_2=\mathcal{M}_2(a_1,X_2)$, $a_3=\mathcal{M}_3(a_1,a_2,X_3)$, and in general $a_i=\mathcal{M}_i(a_1,\ldots,a_{i-1},X_i)$ for $i\ge 2$. Assume the data partitions are disjoint and cover the full dataset, i.e., $X_i\cap X_j=\varnothing$ for all $i\ne j$ and $\bigcup_{i=1}^n X_i=X$. Furthermore, the partition is data-independent. Suppose each mechanism $\mathcal{M}_i$ is $(\varepsilon_i,\delta_i)$-DP with respect to its own subset $X_i$. Does the overall release $\mathcal{M}$ satisfy $(\max_{i\in[n]}\varepsilon_i,\ \max_{i\in[n]}\delta_i)$-DP?
Subject: Accounting and Composition / Parallel Composition
Rationale: Under the assumptions that the subsets are disjoint and the partition is data-independent, the combined mechanism follows the parallel composition and post-processing property of differential privacy, this implies that $\mathcal{M}$ satisfies $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy.
Question: Consider this procedure: release $\mathcal{M}:=\{a_i\}_{i=1}^n$ with $a_1 = \mathcal{M}_{1}(X_1)$, $a_2=(\mathcal{M}_{1}(X_1), \mathcal{M}_{2}(\mathcal{M}_{1}(X_1), X_2))$, $a_3=(\mathcal{M}_{1}(X_1), \mathcal{M}_{2}(\mathcal{M}_{1}(X_1), X_2), \mathcal{M}_{3}(\mathcal{M}_{1}(X_1), \mathcal{M}_{2}(\mathcal{M}_{1}(X_1), X_2), X_3))$ and all other $a_i$'s are defined similarly. Here $\mathcal{M}_i (X_j)$ means apply the mechanism $\mathcal{M}_i$ on subset $X_j$. Suppose $X_i \cap X_j = \phi$ for any $i \neq j$ and $\cup_{i=1}^n X_i = X$. Furthermore, the partition is data-independent. Suppose each mechanism $\mathcal{M}_i$ satisfies $(\varepsilon_i, \delta_i)$-DP. Does $\mathcal{M}$ satisfy $(\max_{i \in [n]} \varepsilon_i, \max_{i \in [n]} \delta_i )$-DP?
Subject: Accounting and Composition / Parallel Composition
Rationale: Under the assumptions that the subsets are disjoint and the partition is data-independent, the combined mechanism follows the parallel composition and post-processing property of differential privacy, this implies that $\mathcal{M}$ satisfies $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy.
Question: Consider the following procedure: $\mathcal{M} := \{\mathcal{M}_i(X_i)\}_{i=1}^n$, where each subset $X_i$ is disjoint from the others, i.e., $X_i \cap X_j = \emptyset$ for all $i \neq j$, and their union covers the entire dataset, i.e., $\bigcup_{i=1}^n X_i = X$. Furthermore, the partition is data-independent.  
Suppose each mechanism $\mathcal{M}_i$ satisfies $(\varepsilon_i, \delta_i)$-differential privacy.  
Does the combined mechanism $\mathcal{M}$ satisfy $(\varepsilon_i,\  \delta_i)$-differential privacy?
Subject: Accounting and Composition / Parallel Composition
Rationale: Under the assumptions that the subsets are disjoint and the partition is data-independent, the combined mechanism follows the parallel composition and post-processing property of differential privacy, this implies that $\mathcal{M}$ satisfies $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy, rather than the stronger $(\varepsilon_i, \delta_i)$-DP guarantee stated.
Question: Consider the following mechanism: $\mathcal{M}(X) := \{\mathcal{M}_i(X_{i\mod{2}})\}_{i=1}^n$, where each subset $X_i$ is disjoint from the others, i.e., $X_i \cap X_j = \emptyset$ for all $i \neq j$, and their union covers the entire dataset, i.e., $\bigcup_{i=1}^n X_i = X$. Furthermore, the partition is data-independent. 
Suppose each mechanism $\mathcal{M}_i$ satisfies $(\varepsilon_i, \delta_i)$-differential privacy.  
Does the combined mechanism $\mathcal{M}$ satisfy $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy?
Subject: Accounting and Composition / Parallel Composition
Rationale: The overall mechanism can be written as $\mathcal{M}:=\Big\{\{\mathcal{M}_i(X_0)\}_{i\in A},\ \{\mathcal{M}_i(X_1)\}_{i\in B}\Big\}$, where \(A:=\{i\in[n]: i \text{ is even}\}\) and \(B:=\{i\in[n]: i \text{ is odd}\}\). Consequently, \(\mathcal{M}\) satisfies $\Big(\max\Big\{\sum_{i\in A}\varepsilon_i,\ \sum_{i\in B}\varepsilon_i\Big\},\ \max\Big\{\sum_{i\in A}\delta_i,\ \sum_{i\in B}\delta_i\Big\}\Big)$-DP
Question: Consider the following procedure: $\mathcal{M} := \{\mathcal{M}_i(X_i)\}_{i=1}^n$, where $X_i \cap X_{i+1} = \emptyset$ for all $i\in\{1,\ldots,n-1\}$, and their union covers the entire dataset, i.e., $\bigcup_{i=1}^n X_i = X$. Furthermore, the partition is data-independent. 
Suppose each mechanism $\mathcal{M}_i$ satisfies $(\varepsilon_i, \delta_i)$-differential privacy.  
Does the combined mechanism $\mathcal{M}$ satisfy $(\max_{i \in [n]}\varepsilon_i,\max_{i \in [n]} \delta_i)$-differential privacy?
Subject: Accounting and Composition / Parallel Composition
Rationale: Consider the following counter example: let $X_i = X$ when $i$ is odd and $X_i = \emptyset$ when $i$ is even, then $\mathcal{M}$ satisfies \(\mathcal{M}\) satisfies $\Big(\sum\limits_{i \in [n]\text{ and i is odd}}\varepsilon_i, \sum\limits_{i \in [n]\text{ and i is odd}}\delta_i\Big)$-DP
Question: Given dataset $X=\{x_1,\ldots,x_n\} \subset \mathbb{R}$, define empirical cumulative distribution function $F_n(x) = \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}_{\{x_{i} \leq x\}} = \frac{\# \{i \mid x_{i} \leq x \}}{n}$ and its inverse: $F_n^{-1}(p) = \inf \left\{ x \in \mathbb{R} \mid F_n(x) \geq p \right\}, \quad \text{for } p \in [0,1]$. Define subset of $X$ as $X_i:=\{x \in X \mid F_n^{-1}(\frac{i-1}{n}) < x \leq F_n^{-1}(\frac{i}{n})\}$, for $i\in\{1,\ldots,n\}$. Clearly each subset is disjoint from the others, i.e., $X_i \cap X_j = \emptyset$ for all $i \neq j$, and their union covers the entire dataset, i.e., $\bigcup_{i=1}^n X_i = X$. Suppose each mechanism $\mathcal{M}_i$ satisfies $(\varepsilon_i, \delta_i)$-differential privacy.  
Does the combined mechanism $\mathcal{M}$ satisfy $(\max_{i \in [n]} \varepsilon_i,\ \max_{i \in [n]} \delta_i)$-differential privacy under replace-one neighbouring relation?
Subject: Accounting and Composition / Parallel Composition
Rationale: An counter example: Suppose $x_1 < x_2 < \ldots < x_n$, then $\mathcal{M}(X)=\{\mathcal{M}_1 (x_1),\ldots,\mathcal{M}_n (x_n)\}$. Let the neighbouring dataset $X^\prime=\{x_1,x_2^\prime,x_2,\ldots,x_{n-1}\}$ and $x_1 <x_2^\prime <x_2$. Then $\mathcal{M}(X^\prime)=\{\mathcal{M}_1 (x_1),\mathcal{M}_2 (x_2^\prime ), \mathcal{M}_3 (x_2 ),\ldots,\mathcal{M}_n (x_{n-1})\}$. By sequential composition, the resulting mechanism satisfies $(\sum_{i-1}^n\varepsilon_i, \sum_{i-1}^n\delta_i)$-DP.
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<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 proof is by \citet[Proposition~8, Theorem~6]{papernot2018scalable} and sequential composition of R\'enyi DP \citep{mironov2017renyi}