erchiw/DPriv-Bench huggingface dataset:
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C\sqrt{T}}{\mu}\xi_t \right),\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: Since $n$ is private under the add/remove neighboring relation and the given algorithm does not privatize it, the algorithm therefore does not satisfy $\mu$-GDP.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?


\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \max\!\bigl(1,\, \tfrac{C}{\|g_i\|_2^2}\bigr)$\;
  }
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C\sqrt{T}}{\mu}\xi_t \right),\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: The gradient clipping is implemented incorrectly: the normalization term should be $\|g_i\|_2$, not $\|g_i\|_2^2$. Thus, the stated privacy guarantee doesn't hold in general.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship?


\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\bar g_t \leftarrow \frac{1}{n}\sum_{i=1}^n \hat g_i$\; 
  $\tilde g_t \leftarrow \bar g_t + \frac{2C\sqrt{T}}{(n-1)\mu}\xi_t ,\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: Assume $n>1$. Under add/remove neigbouring relation, the mean estimator has sensitivity at most $\frac{2C}{n-1}$, thus the noise added in line 6 ensures $\frac{\mu}{\sqrt{T}}$-GDP per iteration. Since the algorithm runs for a total of $T$ iterations, adaptive composition for Gaussian mechanisms implies that the overall algorithm satisfies $\mu$-GDP (\citet[Corollary~2]{dong2022gaussian}).
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\bar g_t \leftarrow \frac{1}{n}\sum_{i=1}^n \hat g_i$\; 
  $\tilde g_t \leftarrow \bar g_t + \frac{C\sqrt{T}}{(n+1)\mu}\xi_t ,\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: Under the add/remove neighboring relation, $\bar{g}_t$ can have sensitivity $\frac{2C}{n+1}$. For example, let $X=\{C\}_{i=1}^n$ and $X'=\{C\}_{i=1}^n \cup \{-C\}$. Then $\bigl|\mathrm{Avg}(X)-\mathrm{Avg}(X')\bigr|=\frac{2C}{n+1}$, so the noise scale used in line~6 may be insufficient.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine
\textbf{Setting noise distribution:} $\xi_0$ is sampled from $\mathcal{N}(0, I_d)$, as used in the noise multiplier for gaussian mechanism; \,

\For{$t=0,\dots,T-1$}{
  $\xi_t \sim \mathcal{N}(0, I_d)$\;
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  \uIf{$t\mod{2}==0$}{$\xi=\xi_{\lfloor t/2 \rfloor}$}
  \Else{$\xi=\xi_t$}
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C\sqrt{T}}{\mu}\xi \right)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: Line 7-10 reuses noise every two iterations, and therefore does not satisfy the stated privacy guarantee.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
data batches $\mathcal{B}=\{B_1,...,B_k\}$, i.e. a partition of $D$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,k$}{
    $g_i = \frac{1}{|B_i|}\sum_{k \in B_i}\nabla_{\theta}\ell(\theta_t;z_i)$\;
    $\tilde g_i = g_i + \frac{C\sqrt{T}}{\mu}\xi_i, \quad \xi_i \sim \mathcal{N}(0, I_d)$\;
    $\tilde g_i \leftarrow  \tilde g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|\tilde g_i\|_2}\bigr)$\;
  }
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \sum_{i=1}^{k}\tilde g_i$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: The algorithm doesn't satisfy $\mu$-GDP because it swaps the order of clipping and noise addition.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  $C = \mathrm{Median}(\nabla_\theta \ell(\theta_t; z_1),...,\nabla_\theta \ell(\theta_t; z_n))$\;
  
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
   
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C\sqrt{T}}{\mu}\xi_t \right),\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: The clipping threshold $C$ is data-dependent and has not been privatized. Therefore, the algorithm does not satisfy the stated privacy guarantee.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?


\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
clipping norm $C>0$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  $C^\prime = \mathrm{Median}(\nabla_\theta \ell(\theta_t; z_1),...,\nabla_\theta \ell(\theta_t; z_n))+ \mathcal{N}(0, \frac{4C^2 T}{\mu^2})$\;
  
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C^\prime}{\|g_i\|_2}\bigr)$\;
  }
   
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C^{\prime}\sqrt{T}}{\mu/2}\xi_t \right),\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: The additive noise in line 2 is not calibrated to the sensitivity of the median of the gradients. Therefore, the algorithm does not satisfy the stated privacy guarantee.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$;\,
Stopping threshold $\tau$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C\sqrt{T}}{\mu}\xi_t \right),\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
  \tcp{post-processing}
  \If{$\sum_{i=1}^{n}\ell(\theta_{t+1};z_i) \geq \tau$}{
        \textbf{break} 
  }
  
}

\Return{$\theta_{t+1}$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: The stopping condition is data-dependent and hasn't been privatized. Therefore, the algorithm does not satisfy the stated privacy guarantee.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$;\,
Stopping threshold $\tau$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C\sqrt{2T}}{\mu}\xi_t \right),\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
  \tcp{running above-threshold}
  \If{$\sum_{i=1}^{n}\ell(\theta_{t+1};z_i) + \frac{C\sqrt{2T}}{\mu}\xi_t \geq \tau$}{
        \textbf{break} 
  }
  
}

\Return{$\theta_{t+1}$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: The noise added to the threshold is not properly calibrated to its sensitivity.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?


\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$;\,
Stopping threshold $\tau$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\tilde g_t \leftarrow \frac{1}{n}\left(\sum_{i=1}^n \hat g_i + \frac{C\sqrt{2T}}{\mu}\xi_t \right),\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
  \tcp{running above-threshold}
  $\xi_t^\prime \sim \mathcal{N}(0, I_d)$\;
  \If{$\sum_{i=1}^{n}\ell(\theta_{t+1};z_i) + \frac{C\sqrt{2T}}{\mu}\xi_t^\prime \geq \tau$}{
        \textbf{break} 
  }
  
}

\Return{$\theta_{t+1}$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: The noise added to the threshold is not properly calibrated to its sensitivity.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu$-Gaussian differential privacy under the replace-one neighboring relationship?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\bar g_t \leftarrow \frac{1}{n}\sum_{i=1}^n \hat g_i$\; 
  $\tilde g_t \leftarrow \bar g_t + \frac{C\sqrt{T}}{n\mu}\xi_t ,\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: Since number of sample $n$ is private under the add/remove neighboring relation and the given algorithm does not add enough noise to privatize it, the algorithm therefore does not satisfy $\mu$-GDP.
Question: The following is an implementation of differentially private gradient descent (DP-GD). Does this implementation satisfy $\mu/2$-Gaussian differential privacy under the add/remove neighboring relationship (assume number of samples $n$ is public information)?

\begin{algorithm}[H]
\caption{DP-GD with Gaussian Noise }
 
\DontPrintSemicolon
\SetNoFillComment
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{
Dataset $D=\{z_i\}_{i=1}^n$;\,
loss $\ell(\theta;z)$;\,
initial parameter $\theta_0\in\mathbb{R}^d$;\,
iterations $T$;\,
step sizes $\{\eta_t\}_{t=0}^{T-1}$;\,
clipping norm $C>0$;\,
target gaussian DP $\mu$
}
\Output{Final parameter $\theta_T$  }
\BlankLine

\For{$t=0,\dots,T-1$}{
  \For{$i=1,\dots,n$}{
    $g_i \leftarrow \nabla_\theta \ell(\theta_t; z_i)$\;
    $\hat g_i \leftarrow  g_i \cdot \min\!\bigl(1,\, \tfrac{C}{\|g_i\|_2}\bigr)$\;
  }
  $\bar g_t \leftarrow \frac{1}{n}\sum_{i=1}^n \hat g_i$\; 
  $\tilde g_t \leftarrow \bar g_t + \frac{C\sqrt{T}}{n\mu}\xi_t ,\quad \xi_t \sim \mathcal{N}(0, I_d)$\; 
  $\theta_{t+1} \leftarrow \theta_t \;-\; \eta_t \,\tilde g_t$\;
}

\Return{$\theta_T$}
\end{algorithm}
Subject: DP-ML / DP-GD
Rationale: Using the adaptive composition property of Gaussian differential privacy (GDP), the algorithm satisfies $\mu$-GDP, not $\mu/2$-GDP.
Question: Is the following algorithm $(\varepsilon, \delta)$-differentially private?


\begin{algorithm}[H]
\caption{Outputting a private Johnson--Lindenstrauss projection of a matrix.}
\KwIn{A matrix $A \in \mathbb{R}^{n \times d}$ and a bound $B > 0$ on the $\ell_2$-norm of any row in $A$; Privacy parameters: $\varepsilon, \delta > 0$; Parameter $r$ indicating the number of rows in the resulting matrix.}

\BlankLine
Set $w$ such that 
\[
w^2 = \frac{8B^2}{\varepsilon} \left( \sqrt{2r \ln(8/\delta)} + 2\ln(8/\delta) \right).
\]
Sample $Z \sim \mathrm{Lap}(4B^2 / \varepsilon)$ and let $\sigma_{\min}(A)$ denote the smallest singular value of $A$.

\BlankLine
\If{$\sigma_{\min}(A)^2 > w^2 + Z + \frac{4B^2 \ln(1/\delta)}{\varepsilon}$}{
    Sample a $(r \times n)$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA$ and ``matrix unaltered''}\;
}
\Else{
    Let $A'$ denote the result of appending $A$ with the $d \times d$-matrix $wI_{d \times d}$.\;
    Sample a $(r \times (n + d))$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA'$ and ``matrix altered''}\;
}
\end{algorithm}
Subject: DP-ML / DP-OLS
Rationale: The given algorithm is \citet[Algorithm~1]{sheffet2017differentially}. The privacy guarantee follows \citet[Theorem~A.1]{sheffet2017differentially}.
Question: Is the following algorithm $(\varepsilon, \delta)$-differentially private?

\begin{algorithm}[H]
\caption{Outputting a private Johnson--Lindenstrauss projection of a matrix.}
\KwIn{A matrix $A \in \mathbb{R}^{n \times d}$ and a bound $B > 0$ on the $\ell_{\infty}$-norm of any row in $A$; Privacy parameters: $\varepsilon, \delta > 0$; Parameter $r$ indicating the number of rows in the resulting matrix.}

\BlankLine
Set $w$ such that 
\[
w^2 = \frac{8B^2}{\varepsilon} \left( \sqrt{2r \ln(8/\delta)} + 2\ln(8/\delta) \right).
\]
Sample $Z \sim \mathrm{Lap}(4B^2 / \varepsilon)$ and let $\sigma_{\min}(A)$ denote the smallest singular value of $A$.

\BlankLine
\If{$\sigma_{\min}(A)^2 > w^2 + Z + \frac{4B^2 \ln(1/\delta)}{\varepsilon}$}{
    Sample a $(r \times n)$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA$ and ``matrix unaltered''}\;
}
\Else{
    Let $A'$ denote the result of appending $A$ with the $d \times d$-matrix $wI_{d \times d}$.\;
    Sample a $(r \times (n + d))$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA'$ and ``matrix altered''}\;
}
\end{algorithm}
Subject: DP-ML / DP-OLS
Rationale: The given algorithm is modified from \citet[Algorithm~1]{sheffet2017differentially}. The bound $B$, originally stated as upper bound for $\ell_2$ norm, is changed to bound on $\ell_\infty$ norm. Since $\ell_2$ norm is larger than $\ell_\infty$ norm, the added noise according to $B$ is not enough.
Question: Is the following algorithm $(\varepsilon, \delta)$-differentially private?

\begin{algorithm}[H]
\caption{Outputting a private Johnson--Lindenstrauss projection of a matrix.}
\KwIn{A matrix $A \in \mathbb{R}^{n \times d}$ and a bound $B > 0$ on the $\ell_2$-norm of any row in $A$; Privacy parameters: $\varepsilon, \delta > 0$; Parameter $r$ indicating the number of rows in the resulting matrix.}

\BlankLine
Set $w$ such that 
\[
w^2 = \frac{8B^2}{\varepsilon} \left( \sqrt{2r \ln(8/\delta)} + 2\ln(8/\delta) \right).
\]
Let $\sigma_{\min}(A)$ denote the smallest singular value of $A$.

\BlankLine
\If{$\sigma_{\min}(A)^2 > w^2 + \frac{4B^2 \ln(1/\delta)}{\varepsilon}$}{
    Sample a $(r \times n)$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA$ and ``matrix unaltered''}\;
}
\Else{
    Let $A'$ denote the result of appending $A$ with the $d \times d$-matrix $wI_{d \times d}$.\;
    Sample a $(r \times (n + d))$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA'$ and ``matrix altered''}\;
}
\end{algorithm}
Subject: DP-ML / DP-OLS
Rationale: The given algorithm is adapted from \citet[Algorithm~1]{sheffet2017differentially}. In the PTR test step (line 2), the Laplace noise has been removed. Because this data-dependent step is not privatized, the resulting algorithm is not differentially private.
Question: Is the following algorithm $(\varepsilon, \delta)$-differentially private?

\begin{algorithm}[H]
\caption{Outputting a private Johnson--Lindenstrauss projection of a matrix.}
\KwIn{A matrix $A \in \mathbb{R}^{n \times d}$ and a bound $B > 0$ on the $\ell_2$-norm of any row in $A$; Privacy parameters: $\varepsilon, \delta > 0$; Parameter $r$ indicating the number of rows in the resulting matrix.}

\BlankLine
Set $w$ such that 
\[
w^2 = \frac{8B^2}{\varepsilon} \left( \sqrt{2r \ln(8/\delta)} + 2\ln(8/\delta) \right).
\]
Sample $Z \sim \mathrm{Lap}(B^2 / \varepsilon)$ and let $\sigma_{\min}(A)$ denote the smallest singular value of $A$.

\BlankLine
\If{$\sigma_{\min}(A)^2 > w^2 + Z + \frac{4B^2 \ln(1/\delta)}{\varepsilon}$}{
    Sample a $(r \times n)$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA$ and ``matrix unaltered''}\;
}
\Else{
    Let $A'$ denote the result of appending $A$ with the $d \times d$-matrix $wI_{d \times d}$.\;
    Sample a $(r \times (n + d))$-matrix $R$ whose entries are i.i.d.\ samples from a normal Gaussian.\;
    \Return{$RA'$ and ``matrix altered''}\;
}
\end{algorithm}
Subject: DP-ML / DP-OLS
Rationale: The given algorithm is adapted from \citet[Algorithm~1]{sheffet2017differentially}. In the PTR test step (line 2), the Laplace noise $Z$'s scale has been reduced by a factor of $4$, and therefore the stated privacy guarantee no longer holds.