erchiw/DPriv-Bench huggingface dataset:
Question: Let $\mathrm{TNB}_{\eta,\gamma}$ denote the truncated Negative Binomial distribution with parameters $\eta \in (-1,\infty)$ and $\gamma \in (0,1)$, supported on positive integers. For $\eta \neq 0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{\gamma^{-\eta}-1}\prod_{\ell=0}^{k-1}\frac{\ell+\eta}{\ell+1}$ and $\mathbb{E}[K] = \frac{\eta(1-\gamma)}{\gamma(1-\gamma^{\eta})}$. For $\eta=0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{k\log(1/\gamma)}$ and $\mathbb{E}[K] = \frac{1/\gamma - 1}{\log(1/\gamma)}$. If $\mathcal{D}=\mathrm{TNB}_{0,\gamma}$ and each $M_j$ satisfies $(\alpha,\varepsilon)$-RDP for all $\alpha>1$, the algorithm satisfies $(\alpha,\varepsilon')$-RDP with $\varepsilon' = (2-\tfrac{1}{\alpha})\varepsilon + \tfrac{\log(1/\gamma)}{\alpha} + \tfrac{\log(1-\gamma)-\log\gamma-\log(\log(1/\gamma))}{\alpha-1}$.

\begin{algorithm}[H]
\caption{Private Hyperparameter Tuning}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}


\Input{
  Dataset $D$;\,
  DP base training mechanisms $\{M_j\}_{j=1}^m$ (one per hyperparameter setting $j$);\,
  distribution for number of runs $\mathcal{D}$;\,
  validation metric $\mathrm{score}: \mathrm{model} \times \mathrm{dataset} \rightarrow \mathbb{R}_{+}$ 
}
\Output{
  Best model $\widehat{\theta}$ and chosen hyperparameter $j^\star$
}

\BlankLine
Draw $K \sim \mathcal{D}$ \\
\For{$k \leftarrow 1,2,\dots,K$}{
  Sample $j_k \sim \mathrm{Unif}(\{1,\dots,m\})$ \\
  $\theta_k \leftarrow M_{j_k}(D)$ \\
  $s_k \leftarrow \mathrm{score}(\theta_k, D)$ \\
}
$k^\star \leftarrow \arg\max_{k \in \{1,\dots,K\}} s_k$ \;
$j^\star \leftarrow j_{k^\star}$,\quad $\widehat{\theta} \leftarrow \theta_{k^\star}$ \;
\Return $(\widehat{\theta}, j^\star)$
\end{algorithm}
Subject: DP-ML / Hyperparameter-tuning
Rationale: The validation score is computed on the private dataset $D$, and the $\arg\max$ is taken directly afterward. Therefore, the algorithm is not differentially private.
Question: Let $\mathrm{TNB}_{\eta,\gamma}$ denote the truncated Negative Binomial distribution with parameters $\eta \in (-1,\infty)$ and $\gamma \in (0,1)$, supported on positive integers. For $\eta \neq 0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{\gamma^{-\eta}-1}\prod_{\ell=0}^{k-1}\frac{\ell+\eta}{\ell+1}$ and $\mathbb{E}[K] = \frac{\eta(1-\gamma)}{\gamma(1-\gamma^{\eta})}$. For $\eta=0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{k\log(1/\gamma)}$ and $\mathbb{E}[K] = \frac{1/\gamma - 1}{\log(1/\gamma)}$. If $\mathcal{D}=\mathrm{TNB}_{0,\gamma}$ and each $M_j$ satisfies $(\alpha,\varepsilon)$-RDP for all $\alpha>1$, the algorithm satisfies $(\alpha,\varepsilon')$-RDP with $\varepsilon' = (2-\tfrac{1}{\alpha})\varepsilon + \tfrac{\log(1/\gamma)}{\alpha} + \tfrac{\log(1-\gamma)-\log\gamma-\log(\log(1/\gamma))}{\alpha-1}$.


\begin{algorithm}[H]
\caption{Private Hyperparameter Tuning}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}


\Input{
  Dataset $D$;\,
  DP base training mechanisms $\{M_j\}_{j=1}^m$ (one per hyperparameter setting $j$);\,
  distribution for number of runs $\mathcal{D}$;\,
  validation metric $\mathrm{score}(\cdot)$ computed on a public holdout set
}
\Output{
  Best model $\widehat{\theta}$ and chosen hyperparameter $j^\star$
}

\BlankLine
Draw $K \sim \mathcal{D}$ \\
$\mathcal{M}\leftarrow\mathrm{Shuffle}(\{1,2,3,\ldots,m\})$\\
\For{$k \leftarrow 1,2,\dots,K$}{
  $\mathrm{index}_k = k\mod{m}$ \\
  $j_k = \mathcal{M}[\mathrm{index}]$ \\
  $\theta_k \leftarrow M_{j_k}(D)$ \\
  $s_k \leftarrow \mathrm{score}(\theta_k, D)$ \\
}
$k^\star \leftarrow \arg\max_{k \in \{1,\dots,K\}} s_k$ \;
$j^\star \leftarrow j_{k^\star}$,\quad $\widehat{\theta} \leftarrow \theta_{k^\star}$ \;
\Return $(\widehat{\theta}, j^\star)$
\end{algorithm}
Subject: DP-ML / Hyperparameter-tuning
Rationale: The $\arg\max$ is taken over all candidates without random stopping. Therefore, the algorithm does not satisfy the stated privacy guarantee.
Question: Let $\mathrm{TNB}_{\eta,\gamma}$ denote the truncated Negative Binomial distribution with parameters $\eta \in (-1,\infty)$ and $\gamma \in (0,1)$, supported on positive integers. For $\eta \neq 0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{\gamma^{-\eta}-1}\prod_{\ell=0}^{k-1}\frac{\ell+\eta}{\ell+1}$ and $\mathbb{E}[K] = \frac{\eta(1-\gamma)}{\gamma(1-\gamma^{\eta})}$. For $\eta=0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{k\log(1/\gamma)}$ and $\mathbb{E}[K] = \frac{1/\gamma - 1}{\log(1/\gamma)}$. If $\mathcal{D}=\mathrm{TNB}_{0,\gamma}$ and each $M_j$ satisfies $(\alpha,\varepsilon^2 )$-RDP with $\varepsilon>1$ for all $\alpha>1$, the algorithm satisfies $(\alpha,\varepsilon')$-RDP with $\varepsilon' = (2-\tfrac{1}{\alpha})\varepsilon + \tfrac{\log(1/\gamma)}{\alpha} + \tfrac{\log(1-\gamma)-\log\gamma-\log(\log(1/\gamma))}{\alpha-1}$.

\begin{algorithm}[H]
\caption{Private Hyperparameter Tuning}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{
  Dataset $D$;\,
  DP base training mechanisms $\{M_j\}_{j=1}^m$ (one per hyperparameter setting $j$);\,
  distribution for number of runs $\mathcal{D}$;\,
  validation metric $\mathrm{score}(\cdot)$ computed on a public holdout set
}
\Output{
  Best model $\widehat{\theta}$ and chosen hyperparameter $j^\star$
}

\BlankLine
Draw $K \sim \mathcal{D}$ \\
\For{$k \leftarrow 1,2,\dots,K$}{
  Sample $j_k \sim \mathrm{Unif}(\{1,\dots,m\})$ \\
  $\theta_k \leftarrow M_{j_k}(D)$ \\
  $s_k \leftarrow \mathrm{score}(\theta_k)$ \\
}
$k^\star \leftarrow \arg\max_{k \in \{1,\dots,K\}} s_k$ \;
$j^\star \leftarrow j_{k^\star}$,\quad $\widehat{\theta} \leftarrow \theta_{k^\star}$ \;
\Return $(\widehat{\theta}, j^\star)$
\end{algorithm}
Subject: DP-ML / Hyperparameter-tuning
Rationale: Consider the following counterexample. Let $\varepsilon = 4$ and suppose each $M_j$ is a $16$-DP mechanism. Taking $\alpha \to \infty$ yields $\varepsilon' = 8$, which would imply that the overall hyperparameter selection algorithm is $8$-DP—i.e., it would provide a stronger privacy guarantee than the underlying mechanisms. This cannot be true.
Question: Let $\mathrm{TNB}_{\eta,\gamma}$ denote the truncated Negative Binomial distribution: with parameters $\eta \in (-1,\infty)$ and $\gamma > 0$, supported on positive integers. For $\eta \neq 0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{\gamma^{-\eta}-1}\prod_{\ell=0}^{k-1}\frac{\ell+\eta}{\ell+1}$ and $\mathbb{E}[K] = \frac{\eta(1-\gamma)}{\gamma(1-\gamma^{\eta})}$. For $\eta=0$, $\Pr[K=k] = \frac{(1-\gamma)^k}{k\log(1/\gamma)}$ and $\mathbb{E}[K] = \frac{1/\gamma - 1}{\log(1/\gamma)}$. If $\mathcal{D}=\mathrm{TNB}_{\gamma,3}$ with $\gamma=3$ and each $M_j$ satisfies $(\alpha,\varepsilon )$-RDP with $\varepsilon>1$ for all $\alpha>1$, does the algorithm satisfy $(\alpha,\varepsilon')$-RDP with $\varepsilon' = (2-\tfrac{1}{\alpha})\varepsilon + \tfrac{\log(1/\gamma)}{\alpha} + \tfrac{\log(5-\gamma)-\log\gamma-\log(\log(1/\gamma))}{\alpha-1}$?

\begin{algorithm}[H]
\caption{Private Hyperparameter Tuning}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{
  Dataset $D$;\,
  DP base training mechanisms $\{M_j\}_{j=1}^m$ (one per hyperparameter setting $j$);\,
  distribution for number of runs $\mathcal{D}$;\,
  validation metric $\mathrm{score}(\cdot)$ computed on a public holdout set
}
\Output{
  Best model $\widehat{\theta}$ and chosen hyperparameter $j^\star$
}

\BlankLine
Draw $K \sim \mathcal{D}$ \\
\For{$k \leftarrow 1,2,\dots,K$}{
  Sample $j_k \sim \mathrm{Unif}(\{1,\dots,m\})$ \\
  $\theta_k \leftarrow M_{j_k}(D)$ \\
  $s_k \leftarrow \mathrm{score}(\theta_k)$ \\
}
$k^\star \leftarrow \arg\max_{k \in \{1,\dots,K\}} s_k$ \;
$j^\star \leftarrow j_{k^\star}$,\quad $\widehat{\theta} \leftarrow \theta_{k^\star}$ \;
\Return $(\widehat{\theta}, j^\star)$
\end{algorithm}
Subject: DP-ML / Hyperparameter-tuning
Rationale: To define a valid probability distribution, $\gamma$ must lie in $[0,1]$; otherwise the resulting density can take negative values. Therefore, the statement is false.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship?

\begin{algorithm}[H]
\caption{Mean estimation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping thresld $C$}
Sample $\xi_1 \sim \mathrm{Lap}(2C/\varepsilon)$ \\
Sample $\xi_2 \sim \mathrm{Lap}(2/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\} + \xi_1}{n + \xi_2}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Under the add/remove neighboring relation, the numerator has sensitivity $C$ and the denominator has sensitivity $1$. By (sequential) composition, the resulting released estimator is $\varepsilon$-DP.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship?

\begin{algorithm}[H]
\caption{Mean estimation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi \sim \mathrm{Lap}(C/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\}}{n} + \xi$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Assuming $0/0=0$, under the add/remove neighboring relation, the sensitivity of $\frac{\sum_{i=1}^n x_i}{n}$ is upper bounded by $\max\left\{\frac{2C}{n+1},\,\frac{2C}{n-1}\right\}$. The first term is at most $C$, while the second term is maximized at $n=2$. When $n=2$, however, the sensitivity under the remove-one relation admits the tighter bound $C$. Therefore, it suffices to add Laplace noise calibrated to $C$.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? (assume $2<n<10$)

\begin{algorithm}[H]
\caption{Mean estimation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi \sim \mathrm{Lap}(C/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\} + 10\xi}{n}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: The sensitivity is upper boudned by $\max\left\{\frac{2C}{n+1},\,\frac{2C}{n-1}\right\}$. Hence it suffices to check the cases $n=3$ and $n=9$, which clearly satisfy $\varepsilon$-DP since the mechanism adds more noise than required.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi_1 \sim \mathrm{Lap}(2C/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\} + \xi_1}{n}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Under the add/remove neighboring relation, the sample size $n$ is private, and the proposed estimator does not add enough noise to privatize $n$.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
 
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi_1 \sim \mathrm{Lap}(2C/\varepsilon)$ \\
Sample $\xi_2 \sim \mathrm{Lap}(2/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^{n-1} \min\{\max\{-C, x_i\},C\} + \xi_1}{n + \xi_2}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Because the sum ranges from $1$ to $n-1$, it can induce sensitivity larger than $C$ under the add/remove neighboring relation. For instance, consider the neighboring datasets $\{C,\,-C,\,C\}$ and $\{C,\,-C,\,-C,\,C\}$.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
 
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi_1 \sim \mathrm{Lap}(2C/\varepsilon)$ \\
Sample $\xi_2 \sim \mathrm{Lap}(1/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\} + \xi_1}{n + \xi_2}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Under the add/remove neighboring relation, the numerator has sensitivity $C$ and the denominator has sensitivity $1$. By (sequential) composition, the resulting released estimator is $\frac{3\varepsilon}{2}$-DP.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{Dataset $\mathcal{D} \subset [l, u]$, privacy budget $\varepsilon > 0$.}
\Output{Noisy mean estimate $\tilde{m}$.}

\BlankLine
Set $\Delta \gets u - l$. \;
Let $\mathcal{X} \gets \{ (x - l)/\Delta : x \in \mathcal{D} \}$. \;
$a \gets \sum_{x \in \mathcal{X}} x$, \quad
$b \gets \sum_{x \in \mathcal{X}} (1 - x)$. \;
Draw $(\eta_1, \eta_2) \sim \xi_1 \times \xi_2$, $\xi_1$ and $\xi_2$ are i.i.d. $\mathrm{Lap}(1/\varepsilon)$ \;
$\hat{a} \gets a + \eta_1$, \quad
$\hat{b} \gets b + \eta_2$. \;
$\rho \gets \min\{ \max \{ \dfrac{\hat{a}}{\hat{a} + \hat{b}}, 0 \}, 1\}$. \;
$\tilde{m} \gets l + \Delta \cdot \rho$. \;
\Return $\tilde{m}$. \;
\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: The algorithm is given in \citet[Algorithm~3]{kulesza2024mean}, and its privacy guarantee is proved in \citet[Theorem~1]{kulesza2024mean}.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{Dataset $\mathcal{D} \subset [l, u]$, privacy budget $\varepsilon > 0$.}
\Output{Noisy mean estimate $\tilde{m}$.}

\BlankLine
Set $\Delta \gets u - l$. \;
Let $\mathcal{X} \gets \{ x/\Delta : x \in \mathcal{D} \}$. \;
$a \gets \sum_{x \in \mathcal{X}} x$, \quad
$b \gets \sum_{x \in \mathcal{X}} (1 - x)$. \;
Draw $(\eta_1, \eta_2) \sim \xi_1 \times \xi_2$, $\xi_1$ and $\xi_2$ are i.i.d. $\mathrm{Lap}(1/\varepsilon)$ \;
$\hat{a} \gets a + \eta_1$, \quad
$\hat{b} \gets b + \eta_2$. \;
$\rho \gets \min\{ \max \{ \dfrac{\hat{a}}{\hat{a} + \hat{b}}, 0 \}, 1\}$. \;
$\tilde{m} \gets l + \Delta \cdot \rho$. \;
\Return $\tilde{m}$. \;
\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: The algorithm is modified from \citet[Algorithm~3]{kulesza2024mean}. However, it is not $\varepsilon$-DP because $\lvert a(X)-a(X^\prime)\rvert = \lvert x/\Delta\rvert$ need not be bounded by $1$, so the noise scale of $\eta_1$ may be insufficient.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{Dataset $\mathcal{D} \subset [l, u]$, privacy budget $\varepsilon > 0$.}
\Output{Noisy mean estimate $\tilde{m}$.}

\BlankLine
Set $\Delta \gets u - l$. \;
Let $\mathcal{X} \gets \{ (x - u)/\Delta : x \in \mathcal{D} \}$. \;
$a \gets \sum_{x \in \mathcal{X}} x$, \quad
$b \gets \sum_{x \in \mathcal{X}} (1 - x)$. \;
Draw $(\eta_1, \eta_2) \sim \xi_1 \times \xi_2$, $\xi_1$ and $\xi_2$ are i.i.d. $\mathrm{Lap}(1/\varepsilon)$ \;
$\hat{a} \gets a + \eta_1$, \quad
$\hat{b} \gets b + \eta_2$. \;
$\rho \gets \min\{ \max \{ \dfrac{\hat{a}}{\hat{a} + \hat{b}}, 0 \}, 1\}$. \;
\Return $\tilde{m}$. \;
\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: The algorithm is modified from \citet[Algorithm~3]{kulesza2024mean}. However, it is not $\varepsilon$-DP since $\lvert b(X)-b(X^\prime)\rvert=\left\lvert 1+\frac{u-x}{u-l}\right\rvert \ge 1$, so the noise scale of $\eta_1$ may be insufficient.
Question: Does the following algorithm satisfy $\varepsilon/2$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
 
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi_1 \sim \mathrm{Lap}(2C/\varepsilon)$ \\
Sample $\xi_2 \sim \mathrm{Lap}(2/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\} + \xi_1}{n + \xi_2}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Under the add/remove neighboring relation, the numerator has sensitivity $C$ and the denominator has sensitivity $1$. By (sequential) composition, the resulting released estimator is $\varepsilon$-DP.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
 
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi_1 \sim \mathrm{Lap}((C+1)/\varepsilon)$ \\
Sample $\xi_2 \sim \mathrm{Lap}((C+1)/\varepsilon)$ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\} + \xi_1}{n + \xi_2}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Under the add/remove neighboring relation, the $L_1$ sensitivity of releasing the vector $\Bigl(\sum_{i=1}^n \mathrm{Clip}(x_i),\, n\Bigr)$ is $C+1$. Hence, adding two-dimensional Laplace noise with per-coordinate scale $(C+1)/\varepsilon$ achieves $\varepsilon$-DP.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the add/remove neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
 
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Input scalar dataset $D:=\{x_1,\ldots,x_n\} $, privacy budget $\varepsilon$, clipping threshold $C$}
Sample $\xi_1 \sim \mathrm{Lap}((C+1)/\varepsilon)$ \\
Let $\xi_2 \leftarrow \xi_1 $ \\
Let $\hat \theta \leftarrow \frac{\sum_{i=1}^n \min\{\max\{-C, x_i\},C\} + \xi_1}{n + \xi_2}$

\textbf{return} $\hat \theta$

\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: The added Laplace noises $\xi_1$ and $\xi_2$ are identical and not independent, thus not guarantee $\varepsilon$-DP.
Question: Does the following algorithm satisfy $\varepsilon$-differential privacy under the replace-one neighboring relationship? 

\begin{algorithm}[H]
\caption{Mean estimation}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{Dataset $\mathcal{D} \subset [l, u]$, privacy budget $\varepsilon > 0$.}
\Output{Noisy mean estimate $\tilde{m}$.}

\BlankLine
Set $\Delta \gets u - l$. \;
Let $\mathcal{X} \gets \{ (x - l)/\Delta : x \in \mathcal{D} \}$. \;
$a \gets \sum_{x \in \mathcal{X}} x$, \quad
$b \gets \sum_{x \in \mathcal{X}} (1 - x)$. \;
Draw $(\eta_1, \eta_2) \sim \xi_1 \times \xi_2$, $\xi_1$ and $\xi_2$ are i.i.d. $\mathrm{Lap}(1/\varepsilon)$ \;
$\hat{a} \gets a + \eta_1$, \quad
$\hat{b} \gets b + \eta_2$. \;
$\rho \gets \min\{ \max \{ \dfrac{\hat{a}}{\hat{a} + \hat{b}}, 0 \}, 1\}$. \;
$\tilde{m} \gets l + \Delta \cdot \rho$. \;
\Return $\tilde{m}$. \;
\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: The algorithm appears as \citet[Algorithm~3]{kulesza2024mean}, and its privacy guarantee is proved in \citet[Theorem~1]{kulesza2024mean} under the add/remove neighboring relation. Since the statement here asks for a guarantee under the replace-one neighboring relation, the noise scale should be doubled.
Question: Does the following algorithm satisfy $(\alpha, 0.8\varepsilon)$-RDP under the add/remove neighboring relationship, for any $\alpha>1$? 

\begin{algorithm}[H]
\caption{Mean estimation}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{Dataset $\mathcal{D} \subset [l, u]$, privacy budget $\varepsilon > 0$.}
\Output{Noisy mean estimate $\tilde{m}$.}

\BlankLine
Set $\Delta \gets u - l$. \;
Let $\mathcal{X} \gets \{ (x - l)/\Delta : x \in \mathcal{D} \}$. \;
$a \gets \sum_{x \in \mathcal{X}} x$, \quad
$b \gets \sum_{x \in \mathcal{X}} (1 - x)$. \;
Draw $(\eta_1, \eta_2) \sim \xi_1 \times \xi_2$, $\xi_1$ and $\xi_2$ are i.i.d. $\mathrm{Lap}(1/\varepsilon)$ \;
$\hat{a} \gets a + \eta_1$, \quad
$\hat{b} \gets b + \eta_2$. \;
$\rho \gets \min\{ \max \{ \dfrac{\hat{a}}{\hat{a} + \hat{b}}, 0 \}, 1\}$. \;
$\tilde{m} \gets l + \Delta \cdot \rho$. \;
\Return $\tilde{m}$. \;
\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Taking $\alpha=\infty$, the statement reduces to checking whether the algorithm satisfies $0.8\varepsilon$-DP. Under the add/remove neighboring relation, \citet[Theorem~1]{kulesza2024mean} proves that the algorithm is $\varepsilon$-DP. Thus, the statement is not true.
Question: Does the following algorithm satisfy $(\alpha, \frac{(3\alpha^2 + 11\alpha + 8)\varepsilon}{5\alpha^2 + 6\alpha})$-RDP under the add/remove neighboring relationship, for any $\alpha>1$? 

\begin{algorithm}[H]
\caption{Mean estimation}
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}

\Input{Dataset $\mathcal{D} \subset [l, u]$, privacy budget $\varepsilon > 0$.}
\Output{Noisy mean estimate $\tilde{m}$.}

\BlankLine
Set $\Delta \gets u - l$. \;
Let $\mathcal{X} \gets \{ (x - l)/\Delta : x \in \mathcal{D} \}$. \;
$a \gets \sum_{x \in \mathcal{X}} x$, \quad
$b \gets \sum_{x \in \mathcal{X}} (1 - x)$. \;
Draw $(\eta_1, \eta_2) \sim \xi_1 \times \xi_2$, $\xi_1$ and $\xi_2$ are i.i.d. $\mathrm{Lap}(1/\varepsilon)$ \;
$\hat{a} \gets a + \eta_1$, \quad
$\hat{b} \gets b + \eta_2$. \;
$\rho \gets \min\{ \max \{ \dfrac{\hat{a}}{\hat{a} + \hat{b}}, 0 \}, 1\}$. \;
$\tilde{m} \gets l + \Delta \cdot \rho$. \;
\Return $\tilde{m}$. \;
\end{algorithm}
Subject: DP-statistics / mean estimation
Rationale: Taking $\alpha=\infty$, the statement reduces to checking whether the algorithm satisfies $0.8\varepsilon$-DP. Under the add/remove neighboring relation, \citet[Theorem~1]{kulesza2024mean} proves that the algorithm is $\varepsilon$-DP. Thus, the statement is not true.
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$.}

\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 from \citet[Algorithm~2]{bassily2019private}. The privacy guarantee follows \citet[Theorem~5.2]{bassily2019private}.