Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness

## Abstract

Abstract We study the Differential Privacy (DP) guarantee of hidden-state Noisy-SGD algorithms over a bounded domain. Standard privacy analysis for Noisy-SGD assumes all internal states are revealed, which leads to a divergent Rényi DP bound with respect to the number of iterations. Ye & Shokri ( 2022 ) and Altschuler & Talwar ( 2022 ) proved convergent bounds for smooth (strongly) convex losses, and raise open questions about whether these assumptions can be relaxed. We provide positive answers by proving convergent Rényi DP bound for non-convex non-smooth losses, where we show that requiring losses to have Hölder continuous gradient is sufficient. We also provide a strictly better privacy bound compared to state-of-the-art results for smooth strongly convex losses. Our analysis relies on the improvement of shifted divergence analysis in multiple aspects, including forward Wasserstein distance tracking, identifying the optimal shifts allocation, and the Hölder reduction lemma. Our results further elucidate the benefit of hidden-state analysis for DP and its applicability.

## 1 Introduction

Noisy Stochastic Gradient Descent (Noisy-SGD), also known as DP-SGD (Abadi et al., ), is now the fundamental workhorse for privatizing machine learning models with the guarantee of differential privacy (DP) Dwork et al. (). The popularity of DP-SGD is due to its effectiveness and simplicity — it is nothing but SGD with per-sample gradient projected to a $\ell_{2}$ ball (also known as gradient clipping) and additive Gaussian noise. Despite the simplicity and ubiquity of the DP-SGD algorithm, we still do not have a holistic understanding regarding its privacy loss(^1^11We refer privacy loss to the DP parameters for the last iterate of Noisy-SGD.). One such evidence is that standard privacy analysis based on composition theorem (Kairouz et al., ; Mironov, ) gives a divergent privacy loss with respect to the number of iterations. On the other hand, a naive but convergent privacy loss can be obtained by output perturbation when the domain is bounded. It shows that neither of these analyses provides a tight privacy bound, which worsens the privacy-utility trade-off by overestimating the amount of noise required for training with DP-SGD.

A natural question is open: Is there a privacy loss bound that outperforms the Pareto frontier of standard composition and output perturbation? Two recent seminal works (Altschuler & Talwar, ; Ye & Shokri, ) partially answer this question under various assumptions on the loss. They show that for smooth (strongly) convex losses over a bounded domain, the privacy loss of Noisy-SGD is convergent and lower than the output perturbation bound. Unfortunately, both works require losses to be smooth and (strongly) convex, which precludes the applicability of their results to more general problems beyond convexity and smoothness. Whether these restrictive assumptions can be relaxed is stated as an important open question in Ye & Shokri (); Altschuler & Talwar (). Specifically: Can these restrictive assumptions be removed while still having a privacy loss bound that outperforms the Pareto frontier of standard composition and output perturbation?

Figure: Figure 1: (a) Our RDP guarantees for smooth losses over the bounded domain, where the noise variance is the same for all lines. Orange and green lines indicate the cases where the loss is further assumed to be (strongly) convex. The output perturbation directly utilizes the Gaussian mechanism with sensitivity chosen to be the diameter of the bounded domain. (b) The detailed comparison of our privacy bound with Altschuler & Talwar (); Ye & Shokri () for smooth strongly convex losses. The setting is the same as (a). We relegate the detail setting to Appendix A.13.
Refer to caption: x1.png

**Table 1: Summary of the required assumptions of existing analysis. $\checkmark$ indicates the assumption is necessary and ☺ indicates one can optionally incorporate that assumption for a better privacy bound. ^†If we do not assume smoothness, we must have Hölder continuous gradient instead. ^⋆If we assume strong convexity, the bounded domain assumption can be dropped.**
|  | Strongly convex | Convex | Smooth | Bounded domain |
| --- | --- | --- | --- | --- |
| Ye & Shokri () | ✓ | ✓ | ✓ |  |
| Altschuler & Talwar () | ☺ | ✓ | ✓ | ☺^⋆ |
| Ours | ☺ | ☺ | ☺^† | ☺^⋆ |

Figure: Figure 2: (a) Our RDP bound for non-smooth loss with $(L,\lambda)$-Hölder continuous gradient, where we empirically estimate the Hölder continuous constant $L$ of a 2 layer Multi-Layer Perceptron (MLP) for each $\lambda$. See Appendix A.13 for the detailed setting. (b) The illustration of the overall analysis. The decomposition of (A) + (B) parts is developed by Altschuler & Talwar (). It done by constructing a coupling $(G_{t},G_{t}^{\prime})$, resulting a coupled process $\tilde{W_{t}}$. Part (A) is handled via standard composition or privacy amplification by subsampling in the mini-batch setting. Part (B) is handled by the shifted divergence analysis for smooth convex losses, which is also known as privacy amplification by iteration and will depend on the infinite Wasserstein distance $W_{\infty}(W_{\tau},W_{\tau}^{\prime})$. Altschuler & Talwar () use the domain diameter $D$ as an upper bound. In contrast, we perform a careful forward $W_{\infty}$ distance tracking analysis (part (C)) to give a better bound, which provides a strict improvement to the final privacy loss bound. We further modify the analysis of part (B) so that it becomes applicable to even non-convex non-smooth losses with Hölder continuous gradients.
Refer to caption: x2.png

### 1.1 Our Contributions and Analysis Overview

Contributions. We give a positive answer to the aforementioned open questions in this work. We show that the privacy loss of the Noisy-SGD algorithm is indeed convergent to a non-trivial value over a bounded domain even without convexity or smoothness assumptions. The least restrictive assumption we need is Hölder continuous (see Definition 2.5) gradients of order $\lambda\in(0,1]$, which is a more general assumption compared to the loss being smooth. We say a function $f$ has Hölder continuous gradient with constant $L$ and order $\lambda$ if it satisfies $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|^{\lambda}$ for any $x,y$ in the domain. Specifically, when $\lambda=1$ we recover the standard smoothness assumption. Note that there are non-smooth functions that still have Hölder continuous gradient. An iconic example is $f(x)=\text{sign}(x)\frac{3}{4}|x|^{4/3}$, where $f^{\prime}(x)=|x|^{1/3}$. One can show that $f$ has Hölder continuous derivative of order $1/3$ with constant $2^{2/3}$ but not smooth (Appendix A.14). Even for a smooth function, the corresponding Hölder constant may be significantly smaller than the smooth constant for a smaller Hölder order $\lambda$, which potentially leads to a better privacy bound. See Figure 2 (a) for a neural network example. Interestingly, our analysis also gives a strict improvement over existing privacy bounds (Altschuler & Talwar, ; Ye & Shokri, ) under the same set of assumptions with smoothness and strong convexity (Figure 1 (b)).

Analysis. We study the projected Noisy-SGD algorithm with per-sample gradient clipping, which is the projected version of the popular DP-SGD (Abadi et al., ). We defer all missing definitions in the preliminaries section 2. Let $\mathcal{D}=\{d_{i}\}_{i=1}^{n}\in\mathcal{X}^{n}$ be a training datasets of $n$ data points, where each data point $d_{i}$ associate with a loss function $\ell(\cdot;d_{i})$ on a convex set $\mathcal{K}$ of diameter $D$. For any step size $\eta$, batch size $b$ and initialization $W_{0}\in\mathcal{K}$, we iterate $T$ times the Noisy-SGD update

$$ $\displaystyle W_{t+1}=\Pi_{\mathcal{K}}\left[W_{t}-\eta\frac{1}{b}\sum_{i\in \mathcal{B}_{t}}\Pi_{B_{K}}\left[\nabla\ell_{i}(W_{t})\right]+G_{t}\right],$ (1) $$

where $\Pi_{\mathcal{K}}$ is the Euclidean projection to the closed convex set $\mathcal{K}$, $\Pi_{B_{K}}$ is the projection to the $\ell_{2}$ ball of radius $K$ (also known as gradient clipping), $G_{t}\sim N(0,\sigma^{2}I)$ and $\mathcal{B}_{t}$ is the mini-batch of indices at time $t$. Our goal is to establish a worst-case upper bound of the Rényi divergence between distributions of the last iterate $W_{T}$ and $W_{T}^{\prime}$ that are trained on any two adjacent datasets differing with one point. Prior work (Altschuler & Talwar, ) has shown that such Rényi divergence can be decomposed via coupling argument into two parts, see Figure 2 (b) for the illustration. Part (A) is the Rényi divergence between two processes with different gradient updates but the same start $W_{\tau}^{\prime}$ for some intermediate time step $\tau$. This part can be handled via standard composition theorem and privacy amplification by subsampling. Part (B) is the Rényi divergence between two processes with the same gradient updates but different start $W_{\tau},W_{\tau}^{\prime}$. This part is handled by the shifted divergence analysis, which is originally known as privacy amplification by iteration (Feldman et al., ) and requires smoothness and convexity. Our main technical contributions are to improve the analysis of part (B), which allows us to not only relax the convexity and smoothness assumptions but also have a strictly tighter analysis for smooth strongly convex losses.

We first perform a careful forward Wasserstein distance tracking analysis (Lemma 3.5) until time step $\tau$ (part (C)). Compared to Altschuler & Talwar () that utilize the domain diameter $D$ directly, our approach leads to a tighter bound for part (B) when further combined with the shifted divergence analysis. One design choice in the shifted divergence analysis is how we allocate the “shifts” for time step $t\in[\tau,T-1]$. We identify the optimal shift allocations that not only lead to a superior privacy bound compared to the Pareto frontier of standard composition and output perturbation for smooth non-convex losses but also a strictly tighter privacy bound for smooth strongly convex losses. Our key intuition is that shifted divergence analysis provides us with a way to distribute the maximum discrepancy $W_{\infty}(W_{\tau},W_{\tau}^{\prime})$ to shifts in each time step $t\in[\tau,T-1]$. This phenomenon does not rely on the convexity of losses, where the convexity only plays a role in the constraints that these shifts have to obey. To relax the smoothness assumption, the main challenge is that shifted divergence analysis strongly relies on the Lipschitz property of the gradient update (i.e., the Lipschitz reduction lemma 3.3) for establishing the proper constraints of shifts in each time step. We alleviate this issue by proving the Hölder reduction lemma (Lemma 3.7) which allows us to work with the general Hölder continuous gradient condition.

## 2 Preliminaries

Notations. We consider the empirical risk minimization problem, where the loss for weight $w$ on dataset $\mathcal{D}$ is $L(w;\mathcal{D})=\frac{1}{n}\sum_{i=1}^{n}\ell(w;d_{i})$. We denote $[n]:=\{1,2,\cdots,n\}$. We denote $f\sharp\mu$ the pushforward of a distribution $\mu$ under a function $f$. We denote $X_{i:j}$ as shorthand for the vector concatenating $X_{i},\cdots,X_{j}$.

(Rényi) differential privacy. In this work we focus on replacement DP for simplicity, while extensions to notions of dataset adjacency are possible. We say two datasets $\mathcal{D},\mathcal{D}^{\prime}$ are adjacent (denoted as $\mathcal{D}\simeq\mathcal{D}^{\prime}$) if one can be obtained from the other by replacing one data point arbitrarily. One may adopt the zero-out adjacency definition (Kairouz et al., ) for a smaller privacy loss as well. A popular way of deriving DP guarantees is to work with Rényi Differential Privacy (RDP) (Mironov, ), which relates to the Rényi divergence defined below.

###### Definition 2.1 (Rényi divergence) .

For any $\alpha>1$, the $\alpha$-Rényi divergence between two probability measures $\mu$ and $\nu$ is $D_{\alpha}(\mu||\nu)=\frac{1}{\alpha-1}\log\left(\int(\mu(x)/\nu(x))^{\alpha}
\nu(x)dx\right)$ if $\mu\ll\nu$, and $\infty$ otherwise.

###### Definition 2.2 (Rényi differential Privacy) .

A randomized algorithm $A$ satisfies $(\alpha,\varepsilon)$-RDP if $D_{\alpha}(\mathcal{A}(\mathcal{D})||\mathcal{A}(\mathcal{D}^{\prime}))\leq\varepsilon$ for all possible $\mathcal{D}\simeq\mathcal{D}^{\prime}$.

With a slight abuse of notation, for random variables $X\sim\mu$ and $Y\sim\nu$ we define $D_{\alpha}(X||Y)=D_{\alpha}(\mu||\nu)$. Rényi divergence has various nice properties, where we introduce the post-processing property and strong composition property as follows.

###### Lemma 2.3 (Post-processing property) .

For any $\alpha>1$, any function $f$, and any probability distribution $\mu,\nu$, $D_{\alpha}(h\sharp\mu||h\sharp\nu)\leq D_{\alpha}(\mu||\nu).$

###### Lemma 2.4 (Strong composition for Rényi divergence) .

For any $\alpha>1$ and any two sequences of random variables $X_{1},\cdots,X_{k}$ and $Y_{1},\cdots,Y_{k}$, $D_{\alpha}(X_{1:k}||Y_{1:k})\leq\sum_{i=1}^{k}\sup_{x_{1:i-1}}D_{\alpha}(X_{i}
|_{X_{1:i-1}=x_{1:i-1}}||Y_{i}|_{Y_{1:i-1}=x_{1:i-1}}).$

Both of the above lemma are known to the literature and we refer interested readers to Altschuler & Talwar () for a more thorough discussion.

Potential assumptions on the loss $\ell$. Throughout, the loss function corresponding to a data point $d_{i}$ or $d_{i}^{\prime}$ is denoted by $\ell_{i}(\cdot)=\ell(\cdot;d_{i})$ and $\ell_{i}^{\prime}(\cdot)=\ell(\cdot;d_{i}^{\prime})$ respectively. Let $\mathcal{K}\subset\mathbb{R}^{d}$ be an arbitrary closed convex set in which our model parameters $w$ lie.

###### Definition 2.5 (Hölder continuity) .

For a function $f:\mathcal{K}\mapsto\mathbb{R}^{d}$, we say $f$ is $(L,\lambda)$-Hölder continuous if for all $w,w^{\prime}\in\mathcal{K}$, $\|f(w)-f(w^{\prime})\|\leq L\|w-w^{\prime}\|^{\lambda},$
where $L\geq 0$ and $\lambda\in(0,1]$.

Note that $(L,1)$-Hölder continuous is equivalent to $L$-Lipschitz continuous. Thus a function has $(L,1)$-Hölder continuous gradient is equivalent to $L$-smoothness when gradient exists. Hence, the $(L,\lambda)$-Hölder continuous gradient assumption is indeed more general. The other standard definitions such as Lipschitz, convexity, and smoothness are deferred to Appendix A.1.

Shifted Rényi divergence analysis. Our analysis generalizes the shifted Rényi divergence analysis developed by Feldman et al. (); Altschuler & Talwar (), where we merely need the Hölder continuous gradient instead of requiring the loss to be convex, smooth, and Lipschitz continuous. Below we introduce the definitions of infinite Wasserstein distance and shifted Rényi divergence which will play a central role in our proof.

###### Definition 2.6 ( $W_{\infty}$ distance) .

Let $\mu,\nu$ be probability distributions over $\mathbb{R}^{d}$. The infinite Wasserstein distance between $\mu,\nu$ is defined as $W_{\infty}(\mu,\nu)=\inf_{\gamma\in\Gamma(\mu,\nu)}\operatorname*{ess\,sup}_{(
X,Y)\sim\gamma}\|X-Y\|,$
where $\Gamma(\mu,\nu)$ is the set of all possible coupling of $\mu,\nu$.

###### Definition 2.7 (Shifted Rényi divergence) .

Let $\mu,\nu$ be probability distributions over $\mathbb{R}^{d}$. For any $z\geq 0$ and $\alpha>1$, the shifted Rényi divergence is defined as $D_{\alpha}^{(z)}(\mu||\nu)=\inf_{\mu^{\prime}:W_{\infty}(\mu,\mu^{\prime})\leq
z
}D_{\alpha}(\mu^{\prime}||\nu).$

###### Definition 2.1 (Rényi divergence) .

###### Definition 2.2 (Rényi differential Privacy) .

###### Lemma 2.3 (Post-processing property) .

###### Lemma 2.4 (Strong composition for Rényi divergence) .

###### Definition 2.5 (Hölder continuity) .

###### Definition 2.6 ( W ∞ subscript 𝑊 W_{\infty} italic_W start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT distance) .

###### Definition 2.7 (Shifted Rényi divergence) .

## 3 Our hidden state DP-SGD privacy loss analysis

Our goal is to show that the last iterate of the DP-SGD update (1) $W_{T}$ is $(\alpha,\varepsilon(\alpha))$-RDP and characterize the bound $\varepsilon(\alpha)$ under our weak assumptions. This is equivalent to bound the Rényi divergence of any two adjacent processes $W_{T},W_{T}^{\prime}$ defined by $\mathcal{D}\simeq\mathcal{D}^{\prime}$ respectively in the worst case. The adjacent process of (1) with respect to the dataset $\mathcal{D}^{\prime}$ is defined as follows

$$ $\displaystyle W_{t+1}^{\prime}=\Pi_{\mathcal{K}}\left[W_{t}^{\prime}-\eta\frac {1}{b}\sum_{i\in\mathcal{B}_{t}^{\prime}}\Pi_{B_{K}}\left[\nabla\ell_{i}^{ \prime}(W_{t}^{\prime})\right]+G_{t}^{\prime}\right],$ (2) $$

where the initializations are identical almost surely $W_{0}=W_{0}^{\prime}$.

Note that there are different possible mini-batch strategies adopted in practice such as without replacement subsampling, shuffled cyclic mini-batch, and full-batch cases. All of these are compatible with our analysis and we will study them separately. For simplicity, we start with the full batch setting $\mathcal{B}_{t}=[n]$ to demonstrate the key insight of our analysis.

### 3.1 Full batch case with smooth losses

We start with introducing our first theorem, which gives a state-of-the-art privacy bound for smooth losses. Our theorem gives a lower privacy loss when more structural assumptions are presented, where we cover the case from strongly convex to non-convex losses in a unified manner.

###### Theorem 3.1 (Privacy loss of Noisy-GD with smooth loss) .

Assume $\ell$ is $L$-smooth. Then the Noisy-SGD update (1) with full batch setting is $(\alpha,\varepsilon(\alpha))$-RDP for $\alpha>1$, where

$$ $\displaystyle\varepsilon(\alpha)\leq\min_{\tau,\beta}\frac{\alpha}{2\sigma^{2} }\left(\sum_{t=\tau}^{T-1}\frac{(\frac{2K\eta}{n})^{2}}{\beta_{t}}+\frac{\min( \frac{2\eta K}{n}\sum_{t=0}^{\tau-1}c^{t},2\eta K\tau,D)^{2}}{\sum_{t=\tau}^{T -1}(1-\beta_{t})c^{-2(t-\tau+1)}}\right),$ (3) $\displaystyle s.t.\;\tau\in\{0,1\cdots,T-1\},\;\beta_{t}\in[0,1],\;\forall t \geq\tau,\;c=1+\eta L.$ (4) $$

If $\ell$ is also convex, $K$-Lipschitz and choose $\eta\leq 2/L$, we have $c=1$. If $\ell$ is also $m$-strongly convex, $K$-Lipschitz and choose $\eta\leq 1/L$, we have $c=1-\eta m$.

Theorem 3.1 indicates that after a burn-in period of iterations, there is no further privacy loss for both convex and non-convex cases as shown in Figure 1 (a). Our result degenerated to the results of Altschuler & Talwar () for the convex case, and we show that a similar phenomenon also holds without convexity but requires a longer burn-in period of iterations with a larger final privacy loss. When the loss is $m$-strongly convex, our Theorem 3.1 provides a strict improvement over the result of Altschuler & Talwar (); Ye & Shokri ()(^2^22In recent work concurrent to this paper, Altschuler et al. () also proposed the improved analysis for strongly convex case that does not require a bounded domain and match our results asymptotically. Still, our analysis provides a strict improvement in the non-asymptotic regime.). See Figure 1 (b) for the illustration.

Below we provide a sketch of proof for Theorem 3.1 and the missing part can be found in Appendix A.4. The analysis presented in this section is the foundation of more general cases, such as non-smooth losses with Hölder continuous gradient and mini-batch settings. We start with introducing several technical lemmas that are crucial for our proof. The first two are the shift and Lipschitz reduction lemma, which establishes the relation of how an additive Gaussian noise and Lipschitz map affect the shifted Rényi divergence. They are the core of the shifted divergence analysis.

###### Lemma 3.2 (Shift reduction lemma (Altschuler & Talwar, 2022 ; Feldman et al., 2018 ) ) .

For any probability distribution $\mu,\nu$ on $\mathbb{R}^{d}$, $\alpha>1$ and $a,z\geq 0$, we have

$$ $\displaystyle D_{\alpha}^{(z)}(\mu\ast N(0,\sigma^{2}I)||\nu\ast N(0,\sigma^{2 }I))\leq D_{\alpha}^{(z+a)}(\mu||\nu)+\frac{\alpha a^{2}}{2\sigma^{2}}.$ (5) $$

###### Lemma 3.3 (Lipschitz reduction lemma Altschuler & Talwar ( 2022 ) ) .

Assume the mapping $\phi$ is $c$-Lipschitz for $c\geq 0$. Then for any probability distribution $\mu,\nu$ on $\mathbb{R}^{d}$, $\alpha>1$ and $z\geq 0$, we have

$$ $\displaystyle D_{\alpha}^{(cz)}(\phi\sharp\mu||\phi\sharp\nu)\leq D_{\alpha}^{ (z)}(\mu||\nu).$ (6) $$

On the other hand, one can show that the gradient update $x\leftarrow x-\eta\Pi_{B_{K}}\left[\nabla f(x)\right]$ is Lipschitz if the loss $f$ is at least smooth (Hardt et al., ; Altschuler & Talwar, ).

###### Lemma 3.4 (Lipschitz constant of the gradient update map) .

Let $\psi(x)=x-\eta\Pi_{B_{K}}\left[\nabla f(x)\right]$ be the gradient update map with loss $f$ and step size $\eta>0$. If $f$ is $L$-smooth, $\psi$ is $1+\eta L$ Lipschitz. If $f$ is further convex, $K$-Lipschitz and $\eta\leq 2/L$, $\psi$ is $1$ Lipschitz. If $f$ is further $m$-strongly convex, $K$-Lipschitz and $\eta\leq 1/L$, $\psi$ is $1-\eta m$ Lipschitz.

Finally, we introduce our forward Wasserstein distance tracking lemma, which is crucial to obtain strict improvement over the prior bounds for all number of iterations for smooth strongly convex losses. Notably, Chien et al. (); Wei et al. () have also adopted the similar idea of Wasserstein distance tracking analysis, but their analysis is for machine unlearning and DP-PageRank respectively, which are different from ours.

###### Lemma 3.5 (Forward Wasserstein distance tracking for Lipschitz gradient update) .

Consider the adjacent processes $W_{t}$, $W_{t}^{\prime}$ defined in (1) and (2) respectively. Assume the gradient update map $\psi_{t}(x)=x-\frac{\eta}{n}\sum_{i\in[n]}\Pi_{B_{K}}[\nabla\ell_{i}(x)]$, $\psi_{t}^{\prime}(x)=x-\frac{\eta}{n}\sum_{i\in[n]}\Pi_{B_{K}}[\nabla\ell_{i}^
{\prime}(x)]$ are $c$-Lipschitz for the full batch setting $\mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}=[n]$. Then we have

$$ $\displaystyle W_{\infty}(W_{t},W_{t}^{\prime})\leq\min(D_{t},D),\;D_{t}=\min( cD_{t-1}+2\eta K/n,D_{t-1}+2\eta K),\;D_{0}=0.$ (7) $$

Now we are ready to state the proof of sketch for Theorem 3.1.

###### Proof.

We start with the argument of Altschuler & Talwar (), which constructs a specific coupling between the adjacent Noisy-SGD processes (1) and (2). To ease the notation, we denote $\psi_{t},\psi_{t}^{\prime}$ to be the gradient update map in (1) and (2) respectively and $\stackrel{{\scriptstyle d}}{{=}}$ for equivalent in distribution.

$$ $\displaystyle W_{t+1}\stackrel{{\scriptstyle d}}{{=}}\Pi_{\mathcal{K}}[\psi_{t }(W_{t})+Y_{t}+Z_{t}],\;W_{t+1}^{\prime}\stackrel{{\scriptstyle d}}{{=}}\Pi_{ \mathcal{K}}[\psi_{t}(W_{t}^{\prime})+Y_{t}+Z_{t}^{\prime}],$ (8) $$

where $Y_{t}\sim N(0,(1-\beta_{t})\sigma^{2}I)$, $Z_{t}\sim N(0,\beta_{t}\sigma^{2}I)$ and $Z_{t}^{\prime}\sim N(\psi_{t}^{\prime}(W_{t}^{\prime})-\psi_{t}(W_{t}^{\prime}
),\beta_{t}\sigma^{2}I)$ for $\beta_{t}\in[0,1]$. Notice that condition on $Z_{t}=Z_{t}^{\prime}$, the two processes exhibit the same gradient update and additive noise. For any time step $0\leq\tau\leq T-1$ to be chosen later, we adopt this coupling for all $t\geq\tau$. Then by Lemma 2.4, we have the following decomposition of the privacy loss

$$ $\displaystyle D_{\alpha}(W_{T}||W_{T}^{\prime})\leq D_{\alpha}((W_{T},Z_{\tau: T-1})||(W_{T}^{\prime},Z_{\tau:T-1}^{\prime}))$ (9) $\displaystyle\leq D_{\alpha}(Z_{\tau:T-1}||Z_{\tau:T-1}^{\prime})+\sup_{z_{ \tau:T-1}}D_{\alpha}(W_{T}|_{Z_{\tau:T-1}=z_{\tau:T-1}}||W_{T}^{\prime}|_{Z_{ \tau:T-1}^{\prime}=z_{\tau:T-1}}).$ (10) $$

The first part can be handled by further applying the standard composition theorem (Lemma 2.4 for each time step), which leads to a bound $\sum_{t=\tau}^{T-1}\frac{\alpha}{2\beta_{t}\sigma^{2}}(\frac{2\eta K}{n})^{2}$ and correspond to part (A) in Figure 2 (b). For the second term, we may iteratively apply Lemma 3.2, 3.3 to upper bound it with a shifted Rényi divergence term and additive Gaussian mechanism terms. Let us denote the shift for time step $t$ as $a_{t}\geq 0$, which will be determined later. With slight abuse of notation, we neglect the conditioning of $Z,Z^{\prime}$ but keep in mind that the analysis below is under such conditioning.

$$ $\displaystyle D_{\alpha}(W_{T}||W_{T}^{\prime})=D_{\alpha}^{(0)}(\Pi_{\mathcal {K}}[\psi_{T-1}(W_{T-1})+Y_{T-1}+z_{T-1}]||\Pi_{\mathcal{K}}[\psi_{T-1}(W_{T-1 }^{\prime})+Y_{T-1}+z_{T-1}])$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}D_{\alpha}^{(0)}(\psi_{T-1}(W _{T-1})+Y_{T-1}]||\psi_{T-1}(W_{T-1}^{\prime})+Y_{T-1})$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}D_{\alpha}^{(c^{-1}a_{T-1})}( W_{T-1}||W_{T-1}^{\prime})+\frac{\alpha a_{T-1}^{2}}{2(1-\beta_{T-1})\sigma^{2}}$ $\displaystyle\leq D_{\alpha}^{(\sum_{t=\tau}^{T-1}c^{-(t-\tau+1)}a_{t})}(W_{ \tau}||W_{\tau}^{\prime})+\sum_{t=\tau}^{T-1}\frac{\alpha a_{t}^{2}}{2(1-\beta _{t})\sigma^{2}}.$ $$

where $(a)$ is due the projection and constant shift are $1$-Lipshitz maps and thus by Lemma 3.3, $(b)$ is due to Lemma 3.2 and 3.3, where the Lipschitz constant $c$ can be obtained from Lemma 3.4 based on different assumptions on the losses. The last inequality is by applying the argument iteratively until time step $\tau$. Note that while the shifted divergence term is in general non-tractable, it is 0 0 when $W_{\infty}(W_{\tau}||W_{\tau}^{\prime})$ is less then the accumulated shifts according to its definition 2.7. By enforcing this constraint, we obtain a closed-form privacy loss bound to be optimized with respect to $\tau,\beta_{t},a_{t}$, where the constraint can be characterized by forward Wasserstein distance tracking lemma 3.5.

$$ $\displaystyle\min_{\tau,\beta,a}\frac{\alpha}{2\sigma^{2}}\sum_{t=\tau}^{T-1} \frac{1}{\beta_{t}}(\frac{2\eta K}{n})^{2}+\frac{\alpha a_{t}^{2}}{(1-\beta_{t })},\;s.t.\;\sum_{t=\tau}^{T-1}c^{-(t-\tau+1)}a_{t}\geq\min(D_{\tau},D),$ (11) $$

where $\tau\in[0,T-1],\beta_{t}\in(0,1),a_{t}\geq 0$ and $D_{t}$ is defined in Lemma 3.5. Finally, observing this constrained optimization can be further simplified by characterizing the optimum solution as follows. By Cauchy-Schwartz inequality, we have

$$ $\displaystyle\left[\sum_{t=\tau}^{T-1}\frac{a_{t}^{2}}{(1-\beta_{t})}\right] \cdot\left[\sum_{t=\tau}^{T-1}(1-\beta_{t})(c^{-2(t-\tau+1)})\right]\geq(\sum_ {t=\tau}^{T-1}a_{t}c^{-(t-\tau+1)})^{2},$ (12) $$

where the equality holds if the ratio $\frac{a_{t}}{(1-\beta_{t})c^{-(t-\tau+1)}}$ is the same for all $\tau\leq t\leq T-1$. Apparently, this is attainable by choosing $a_{t}$ properly according to $\beta_{t},c^{-(t-\tau+1)}$. Note that $(1-\beta_{t})$ and $c^{-(t-\tau+1)}$ are all non-negative so that this characterization of $a_{t}$ still matches its non-negative constraint. As a result, the optimization problem above can be further simplified as stated in Theorem 3.1, where we complete the proof.
∎

It is worth noting the interpretation of Theorem 3.1, which is the root of our key intuition stated in Section 1.1. Under the optimum choice of $a_{t}$ determined by (12), we know that $a_{t}\propto(1-\beta_{t})c^{-(t-\tau+1)}$ where the left-hand side is closely related to the denominator of the second term $(1-\beta_{t})c^{-2(t-\tau+1)}$ in the privacy bound of Theorem 3.1. As a result, the second term in the privacy bound of Theorem 3.1 can be interpreted as how we distribute the maximum discrepancy $\min(\frac{2\eta K}{n}\sum_{t=0}^{\tau-1}c^{t},2\eta K\tau,D)$ to the shifts $a_{t}$ each time step $t\in[\tau,T-1]$ along with weights $c^{-(t-\tau+1)}$. Even if the losses are non-convex so that $c>1$, it is still possible to distribute the maximum discrepancy to more than one shift and thus a bound better than output perturbation is possible. We emphasize the discussion so far still relies on the smoothness assumption. Relaxing the smoothness assumption requires further non-trivial analysis as presented in the following section.

###### Theorem 3.1 (Privacy loss of Noisy-GD with smooth loss) .

###### Lemma 3.2 (Shift reduction lemma (Altschuler & Talwar, 2022 ; Feldman et al., 2018 ) ) .

###### Lemma 3.3 (Lipschitz reduction lemma Altschuler & Talwar ( 2022 ) ) .

###### Lemma 3.4 (Lipschitz constant of the gradient update map) .

###### Lemma 3.5 (Forward Wasserstein distance tracking for Lipschitz gradient update) .

###### Proof.

### 3.2 Non-smooth losses with Hölder continuous gradient

Prior hidden-state Noisy-SGD privacy analysis requires the loss to be smooth (Altschuler & Talwar, ; Ye & Shokri, ), which restricts their application to non-smooth problems. Our Theorem 3.6 shows that Hölder continuous gradient is sufficient to enable the similar phenomenon of convergent privacy loss after a burn-in period. See Figure 2 (a) for an illustration.

###### Theorem 3.6 (Privacy loss of Noisy-GD with Hölder continuous gradient) .

Assume $\nabla\ell$ are $(L,\lambda)$-Hölder continuous with $\lambda\in(0,1]$. Let $g(x)=x+\eta Lx^{\lambda}$ with domain and range being $\mathbb{R}_{\geq 0}$ and $h=g^{-1}$.Then the Noisy-SGD update (1) with full batch setting is $(\alpha,\varepsilon(\alpha))$-RDP for $\alpha>1$, where

$$ $\displaystyle\varepsilon(\alpha)\leq\min_{\tau,\beta,a}\frac{\alpha}{2\sigma^{ 2}}\sum_{t=\tau}^{T-1}\frac{1}{\beta_{t}}(\frac{2\eta K}{n})^{2}+\frac{a_{t}^{ 2}}{1-\beta_{t}},$ (13) $\displaystyle s.t.\;\tau\in\{0,1\cdots,T-1\},\;\beta_{t}\in[0,1],\;a_{t}\geq 0 \;\forall t\geq\tau,\;A_{\tau}\geq D_{\tau},$ (14) $\displaystyle A_{T}=D_{0}=0,\;A_{t-1}=h(A_{t}+a_{t-1}),\;D_{t}=\min(g(D_{t-1}) +2\eta K/n,D_{t-1}+2\eta K,D).$ (15) $$

Below we provide the key lemmas that enable the analysis in Section 3.1 to be generalized to non-smooth losses with Hölder continuous gradient. Note that when the loss is non-smooth, the gradient update map $\psi$ can no longer be guaranteed to be Lipschitz, and thus Lemma 3.3 cannot be utilized. We prove the following key lemma which allows us to work without smoothness assumption.

###### Lemma 3.7 (Hölder reduction lemma) .

Assume the map $\phi$ is $(L,\lambda)$-Hölder continuous for $L\geq 0$ and $\lambda\in(0,1]$. Then for any probability distribution $\mu,\nu$ over $\mathbb{R}^{d}$, $\alpha>1$ and $z\geq 0$,

$$ $\displaystyle D_{\alpha}^{(z)}((I+\phi)\sharp\mu||(I+\phi)\sharp\nu)\leq D_{ \alpha}^{(h(z))}(\mu||\nu),$ (16) $$

where $h(z)$ is the solution map of the equation $x+Lx^{\lambda}=z$ for $x\geq 0$ and $I$ is the identity map.

Note that the gradient update map $\psi$ can indeed be written as $I+\phi$, where $I$ is the identity map and $\phi$ is the gradient term. We further prove that the map $h$ is “well-behaved”.

###### Lemma 3.8 (Properties of $h$ ) .

For any $z\geq 0$, let $h(z)$ be the solution map of the equation $x+Lx^{\lambda}=z$ for $x\geq 0$. For any $L\geq 0$ and $\lambda\in(0,1]$, we have 1) $h:\mathbb{R}_{\geq 0}\mapsto\mathbb{R}_{\geq 0}$, 2) $h$ is strictly monotonic increasing and continuous, 3) $h$ is bijective, 4) when $\lambda=1/2$, we have the close-form characterization $h(z)=\left(\frac{-L+\sqrt{L^{2}+4z}}{2}\right)^{2}.$

Finally, we perform the forward $W_{\infty}$ distance tracking in this case.

###### Lemma 3.9 (Forward Wasserstein distance tracking) .

Consider the adjacent processes $W_{t},W_{t}^{\prime}$ defined in (1) and (2) respectively. Assume that $\nabla\ell_{i}(x),\nabla\ell_{i}^{\prime}(x)$ are $(L,\lambda)$-Hölder continuous for all $i\in[n]$. Denote $g(x;L)=x+Lx^{\lambda}$, then we have

$$ $\displaystyle W_{\infty}(W_{t},W_{t}^{\prime})\leq\min(D_{t},D),\;D_{t}=\min(g (D_{t-1};\eta L)+2\eta K/n,D_{t-1}+2\eta K),\;D_{0}=0.$ (17) $$

The proof of Theorem 3.6 follows by a similar analysis in Section 3.1, but replacing the Lipschitz reduction lemma with Lemma 3.7 and Lemma 3.5 with Lemma 3.9. The full proof can be found in Appendix A.2 by specializing the minibatch results to full batch $[n]$ setting.

###### Theorem 3.6 (Privacy loss of Noisy-GD with Hölder continuous gradient) .

###### Lemma 3.7 (Hölder reduction lemma) .

###### Lemma 3.8 (Properties of h ℎ h italic_h ) .

###### Lemma 3.9 (Forward Wasserstein distance tracking) .

### 3.3 Mini-batch cases

Our analysis naturally supports two different popular mini-batch settings: subsampling without replacement and shuffled cyclic mini-batch. While the privacy analysis for subsampling without replacement is more elegant, shuffled cyclic mini-batch can be implemented more efficiently and is closer to the standard mini-batch construction. We recommend interested readers to the recent excellent study on their pros and cons when deploying them in practice (Chua et al., ).

Subsampling without replacement. To express the result, we first introduce the Sampled Gaussian Mechanism (Mironov et al., ).

###### Definition 3.10 (Rényi divergence of Sampled Gaussian Mechanism) .

For any $\alpha>1$, mixing probability $q\in(0,1)$ and noise parameter $\sigma>0$, define

$$ $\displaystyle S_{\alpha}(q,\sigma)=D_{\alpha}(N(0,\sigma^{2})||(1-q)N(0,\sigma ^{2})+qN(1,\sigma^{2})).$ (18) $$

Note that $S_{\alpha}$ can be computed in practice with a numerically stable procedure for precise computation Mironov (). Now we are ready to state the result for subsampling without replacement.

###### Theorem 3.11 .

Assume $\nabla\ell_{i},\nabla\ell_{i}^{\prime}$ are $(L,\lambda)$-Hölder continuous for $L\geq 0$ and $\lambda\in(0,1]$. Let $h$ be the solution map defined in Lemma 3.7 with constant $\eta L,\lambda$. Then the DP-SGD update (1) under without replacement sampling mini-batches of size $b$ is $(\alpha,\varepsilon(\alpha))$-RDP for $\alpha>1$, where

$$ $\displaystyle\varepsilon(\alpha,\mathcal{B})=\min_{\tau,\beta,a}\sum_{t=\tau}^ {T-1}S_{\alpha}(\frac{b}{n},\frac{\beta_{t}\sigma b}{2\eta K})+\frac{\alpha a_ {t}^{2}}{2\sigma^{2}(1-\beta_{t})},$ (19) $\displaystyle s.t.\;\tau\in\{0,1\cdots,T-1\},\;\beta_{t}\in[0,1],\;a_{t}\geq 0 \;\forall t\geq\tau,\;A_{\tau}\geq D_{\tau},\;A_{T}=D_{0}=0,$ (20) $\displaystyle A_{t-1}=h(A_{t}+a_{t-1}),\;D_{t}=\min(g(D_{t-1};\eta L(b-1)/b)+2 \eta K/b,D_{t-1}+2\eta K,D),$ (21) $$

where $g(x;L)=x+Lx^{\lambda}$ and $S_{\alpha}(q,\sigma)$ is defined in Definition 3.10.

The proof is similar to the proof of Theorem 3.6, except that we adopt the Sampled Gaussian Mechanism $S_{\alpha}$ to bound the first term (i.e., part (A) in Figure 2 (b)), which can be found at Appendix A.3. One can further specialize Theorem 3.11 if more structure assumptions are given, which leads to the subsampling without replacement version of Theorem 3.1. We leave it as an exercise for readers.

Shuffled cyclic mini-batch. The analysis for shuffled cyclic mini-batch is more tedious, but the main idea still follows Section 3.1. Due to the space limit, we defer the results to Appendix A.2.

###### Definition 3.10 (Rényi divergence of Sampled Gaussian Mechanism) .

###### Theorem 3.11 .

## 4 Related Works

There are three types of privacy analysis for hidden-state Noisy-SGD, which are related to either Langevin dynamic, contraction of hockey-stick divergence, and shifted divergence. Chourasia et al. () is the first that leverages Langevin dynamic analysis for deriving convergent privacy bound in the full batch setting. Ye & Shokri () extend and refine their analysis to the mini-batch setting, yet both of which require smooth strongly convex losses. Chien et al. () also leverage the Langevin dynamic analysis but for machine unlearning problem. In the meanwhile, Asoodeh & Diaz () utilize the bounded domain property with the contraction analysis of the hockey-stick divergence. Unfortunately, their bound heavily relies on the privacy amplification by subsampling effect, where their result degenerates to output perturbation in the full batch setting and is different from our approach. Finally, Altschuler & Talwar () developed the analysis that combines privacy amplification by subsampling and iteration (Feldman et al., ) in a clever way, which leads to the state-of-the-art privacy bound for Noisy-SGD under smoothness and convexity assumption. Altschuler & Talwar (); Chien et al. () adopted a similar analysis for studying the mixing time of Noisy-SGD and its unlearning guarantee respectively. We improve their results with not only a generalization to non-smooth non-convex losses with Hölder continuous gradients, but also a tighter bound for the smooth strongly convex losses.

## 5 Conclusions and Open problems

We provide an affirmative answer to the open question raised in Altschuler & Talwar (); Ye & Shokri (): hidden-state Noisy-SGD indeed has non-trivial convergent privacy loss over the bounded domain even when the convexity and smoothness assumptions are relaxed. Our analysis shows that requiring losses to have Hölder continuous gradient is sufficient for convergent privacy loss that is better than the Pareto frontier of standard composition analysis and output perturbation. To the best of our knowledge, this is the least restrictive assumption in the literature. We further provide the superior privacy bound for smooth strongly convex losses compared to prior works.

While our results make a step forward toward the ultimate goal of providing a better privacy-utility trade-off of Noisy-SGD (or equivalently, DP-SGD) for training deep neural networks, several gaps remain. We discuss some future directions that can further progress in this direction.

Gradient clipping. While our Theorem 3.6 and 3.1 directly rely on gradient clipping in non-convex cases, it additionally requires losses to have bounded gradient norm “continuously”. For simplicity, we directly require losses to be Lipschitz to satisfy this condition. While the gradient clipping operation can also ensure the bounded gradient norm, it inevitably induces discontinuous derivative of gradients on a set with negligible measure. The same open question is raised in Altschuler & Talwar (). The key question is whether we can prove the gradient update map $\psi(x)=x-\eta\Pi_{B_{K}}[\nabla f(x)]$ to be $c\leq 1$ Lipschitz when the loss $f$ is known to be (strongly) convex and smooth. We conjecture this analysis can be done but potentially require additional assumptions on $f$.

Better practical privacy accounting. For ease of analysis, current hidden-state Noisy-SGD literature treats the model weight as a whole real vector as well as the assumptions of loss corresponding to it. This inevitably makes the corresponding Lipshitz, smooth, or Hölder constants large for neural networks even if they are naturally or modified to satisfy these assumptions. A recent interesting work (Béthune et al., ) proposes to directly enforce layer-wise Lipschitzness of neural networks, so that gradient clipping can be dropped to reduce the time and space complexity of DP-SGD. They show that a per-layer analysis provides a better privacy-utility trade-off compared to requiring the Lipschitzness of the neural network as a whole. We conjecture a similar idea is necessary to improve the practicality of hidden-state Noisy-SGD analysis.

Non-uniform Hölder continuous gradient. Another aspect of improving the practicality of our work is to consider the non-uniform Hölder continuous gradient. Indeed, whenever the parameter difference $\|x-y\|\leq 1$, a smaller Hölder constant can be obtained for $\lambda<1$. One interesting idea is to introduce the non-uniform (local) Hölder continuous gradient assumption for neural networks depending on the parameter difference. We conjecture that this is closer to the actual behavior of neural networks and potentially gives smaller constants and thus final privacy loss bound. This also requires additional investigation into what actual structural properties the neural networks have. We hope to see more collaboration between the theoretical and empirical ML community toward answering the last question.

Uniform strict improvement over standard composition theorem. Our current results show that there is no improvement before some burn-in period compared to the standard composition theorem for Noisy-SGD. A natural question to ask is whether a uniform strict improvement in the privacy-utility trade-off over the standard composition theorem can be made. Positive evidence to this question is the recent astonishing advances of DP-FTRL (Kairouz et al., ), which shows that a better privacy-utility trade-off can be achieved compared to standard composition theorem analysis if non-independent Gaussian noise is utilized. It is interesting to see if our analysis can be combined with DP-FTRL to further provide a better privacy-utility trade-off.

Lower bound aspect of our analysis. An interesting question is how tight is our derived privacy bound. We conjecture that our analysis is indeed relatively tight. The positive evidence is that our analysis degenerates to the result of Altschuler & Talwar () for smooth convex losses, where they have constructed an order-wise matching lower bound on the privacy loss. We conjecture that a similar analysis can be conducted for our setting, which may elucidate the tightness of our analysis.

Better privacy amplification by shuffling analysis. While we have a privacy amplification by shuffling analysis from Ye & Shokri () (see Corollary A.3), the resulting bound cannot be computed in a numerically stable way. Although Ye & Shokri () propose a numerically stable approximation, it is unclear how such approximation affects the actual privacy guarantee. Ideally, we need a provable privacy upper bound for numerical approximate as in standard privacy accounting (Gopi et al., ) for rigorous DP guarantee. It is interesting to see if the privacy upper bound of the approximation method in Ye & Shokri () can be established. A better privacy amplification by shuffling analysis is also an important open question as mentioned in Chua et al. ().

#### Acknowledgments

We thank Wei-Ning Chen for the help in identifying the optimal shifts in our main theorems. We thank Rongzhe Wei for the helpful discussion on the idea of Wasserstein distance tracking. We thank Jason M. Altschuler for clarification regarding their papers. We thank Ziang Chen for the helpful discussion and comments. E. Chien and P. Li are supported by NSF awards CIF-2402816 and 2023 JPMC faculty award.

## Appendix A Appendix

### A.1 Standard Definitions

Let $f:\mathcal{K}\subseteq\mathbb{R}^{d}\mapsto\mathbb{R}$ be a mapping. We define smoothness, Lipschitzsness, and strong convexity as follows:

$$ $\displaystyle\text{$L$-smooth: }\forall~{}x,y\in\mathcal{K},\;\|\nabla f(x)- \nabla f(y)\|\leq L\|x-y\|$ (22) $\displaystyle\text{$m$-strongly convex: }\forall~{}x,y\in\mathcal{K},\;\left \langle x-y,\nabla f(x)-\nabla f(y)\right\rangle\geq m\|x-y\|^{2}$ (23) $\displaystyle\text{$M$-Lipschitz: }\forall~{}x,y\in\mathcal{K},\;\|f(x)-f(y)\| \leq M\|x-y\|.$ (24) $$

Note that a function $f$ being $L$-smooth is equivalent to $f$ having $L$-Lipschitz continuous gradients. It is also equivalent to $f$ having $(L,1)$-Hölder continuous gradient. Furthermore, we say $f$ is convex if it is 0 0-strongly convex.

### A.2 Privacy guarantees for shuffled cyclic mini-batch

In this section, we assume for simplicity that $b$ divides $n$ so that $B=n/b$ is a positive integer(^3^33When $b$ does not divide $n$, we can simply drop the last $n-\lfloor n/b\rfloor b$ points.). Given the number of total iterations $T$, there will be $E=\lfloor T/B\rfloor+1$ epochs so that $T=(E-1)B+\tilde{T}$. At the beginning of epoch $0\leq e<E$, we randomly partition the index set $[n]$ into $B$ mini-batches $\{\mathcal{B}_{i}^{e}\}_{i=0}^{B-1}$, where we denote $\mathcal{B}_{t}=\mathcal{B}_{i}^{e}$ if $t=eB+i$. Note that the mini-batch generation process is independent of the dataset $\mathcal{D}$ (as long as they have size $n$), the noise $G_{t}$, and the underlying model parameters $W_{t}$. In what follows, we will first derive the RDP guarantee for any fixed mini-batch sequence $\{\mathcal{B}_{t}\}_{t=0}^{T-1}$ and then improve the bound by taking into account the randomness of the mini-batches.

###### Theorem A.1 .

Assume $\nabla\ell_{i},\nabla\ell_{i}^{\prime}$ are $(L,\lambda)$-Hölder continuous for $L\geq 0$ and $\lambda\in(0,1]$. Let $h$ be the solution map defined in Lemma 3.7 with constant $\eta L,\lambda$. Given any mini-batch sequence $\mathcal{B}=\{\mathcal{B}_{t}\}_{t=0}^{T-1}$ from shuffled cyclic mini-batch strategy, define $\{t_{e}\}_{e=-1}^{E}$ be the set of time steps that we encounter $i^{\star}$ at epoch $e$, where $t_{-1}=0$ and assume we will encounter $i^{\star}$ in the last epoch up to time step $T$. Then the DP-SGD update (1) with the given mini-batch sequence $\mathcal{B}$ is $(\alpha,\varepsilon(\alpha,\mathcal{B}))$-RDP for $\alpha>1$, where

$$ $\displaystyle\varepsilon(\alpha,\mathcal{B})=\min_{\tau,\beta,a}\sum_{j=j_{ \tau}}^{E}\frac{\alpha(\frac{2K\eta}{b})^{2}}{2\beta_{t_{j}}\sigma^{2}}+\sum_{ t=\tau}^{T-1}\frac{\alpha a_{t}^{2}}{2\sigma^{2}(1-\beta_{t})},\;j_{\tau}=j \text{ iff }\tau\in(t_{j-1},t_{j}],$ (25) $\displaystyle s.t.\;\tau\in\{0,1\cdots,T-1\},\;\beta_{t}=0\;\forall t\notin\{t _{e}\}_{e=j_{\tau}}^{E},\;\beta_{t}\in[0,1]\;\forall t\in\{t_{e}\}_{e=j_{\tau} }^{E},\;a_{t}\geq 0\;\forall t\geq\tau,$ (26) $\displaystyle A_{\tau}\geq D_{\tau},\;A_{T}=0,\;A_{t-1}=h(A_{t}+a_{t-1}),\;D_{ t}\text{ is defined in Lemma~{}\ref{lma:W_dist_tracking}.}$ (27) $$

If we do not encounter $i^{\star}$ in the last epoch up to time step $T$, replace $E$ by $E-1$.

###### Theorem A.1 .

#### A.2.1 The analysis

We will need the following $W_{\infty}$ distance tracking lemma, which is crucial to contain privacy accounting based on the standard composition theorem (Mironov, ) as our special case. A similar idea is also used for proving unlearning guarantees for SGD unlearning (Chien et al., ) and tight DP guarantees for the hidden-state PageRank algorithm (Wei et al., ).

###### Lemma A.2 (Forward Wasserstein distance tracking) .

Consider the adjacent processes $W_{t},W_{t}^{\prime}$ defined in (1) and (2) respectively. Given any mini-batch sequences $\{\mathcal{B}_{t}\}$ and $\mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}$, denote $t_{e}$ be the time step that $i^{\star}\in\mathcal{B}_{t_{e}}$ at epoch $e$ so that $\lfloor t_{e}/B\rfloor=e$. Assume that $\nabla\ell(\cdot,d)$ is $(L,\lambda)$-Hölder continuous for any $d\in\mathcal{X}$. Then we have

$$ $\displaystyle W_{\infty}(W_{t},W_{t}^{\prime})\leq\min(D_{t},D),$ (28) $\displaystyle D_{t}=\begin{cases}0&\text{ if }t\leq t_{0},\\ 2\eta K/b&\text{ if }t=t_{0}+1,\\ \min(g(D_{t-1};\eta L(b-1)/b)+2\eta K/b,D_{t-1}+2\eta K)&\text{ if }t-1\in\{t_ {e}\}_{e=1}^{E},\\ \min(g(D_{t-1};\eta L),D_{t-1}+2\eta K)&\text{ otherwise },\end{cases}$ (29) $$

where $g(x;L)=x+Lx^{\lambda}$.

Now we are ready to prove Theorem A.1.

###### Proof.

The key idea of the shifted Rényi divergence analysis is constructing a coupling between $W_{T},W_{T}^{\prime}$ so that the analysis can be simplified (Altschuler & Talwar, ). According to our assumption, we have that $\mathcal{B}_{t}=\mathcal{B}_{t}^{\prime}$ is some given fixed mini-batch sequence. Let us define the overall update map at time $t$ to be $\psi_{t}(W)=W-\eta\frac{1}{b}\sum_{i\in\mathcal{B}_{t}}\Pi_{B_{K}}\left[\nabla
\ell_{i}(W)\right]$. Similarly, we can define $\psi_{t}^{\prime}(W)$ to be the overall update map for dataset $\mathcal{D}^{\prime}$. Then we construct a specific coupling between $G_{t},G_{t}^{\prime}$ as follows

$$ $\displaystyle W_{t+1}=\Pi_{\mathcal{K}}\left[\psi_{t}(W_{t})+Y_{t}+Z_{t}\right ],\;W_{t+1}^{\prime}=\Pi_{\mathcal{K}}\left[\psi_{t}^{\prime}(W_{t}^{\prime})+ Y_{t}+\tilde{Z}_{t}\right]\stackrel{{\scriptstyle d}}{{=}}\Pi_{\mathcal{K}} \left[\psi_{t}(W_{t}^{\prime})+Y_{t}+Z_{t}^{\prime}\right],$ (30) $$

where $Y_{t}\sim N(0,(1-\beta_{t})\sigma^{2}I)$, $Z_{t},\tilde{Z}_{t}\sim N(0,\beta_{t}\sigma^{2}I)$ and $Z_{t}^{\prime}\sim N(\psi_{t}^{\prime}(W_{t}^{\prime})-\psi_{t}(W_{t}^{\prime}
),\beta_{t}\sigma^{2}I)$. It is worth noting that $\psi_{t}^{\prime}(W_{t}^{\prime})=\psi_{t}(W_{t}^{\prime})$ for any $t$ such that $i^{\star}\notin\mathcal{B}_{t}$. Let us denote $t_{e}$ to be the time step such that $i^{\star}\in\mathcal{B}_{t}$ at epoch $e$. Then clearly $\psi_{t},\psi_{t}^{\prime}$ are only different at $\{t_{e}\}_{e=0}^{E}$.

Let us denote $t_{-1}=0$. If we condition on $Z_{t}=Z_{t}^{\prime}$ for all $t\in\{t_{e}\}_{e=j}^{E}$ for some $-1\leq j\leq E$, then we know that $W_{t},W_{t}^{\prime}$ are two processes with identical update mapping $\psi_{t}=\psi_{t}^{\prime}$ for any $t\geq t_{j}$. Thus, we can upper bound the Rényi divergence between $W_{T},W_{T}^{\prime}$ as follows: for any given $\tau\in\{t_{e}\}_{e=-1}^{E}$, let $j_{\tau}$ be the corresponding epoch index $e$ including $-1$. Let us denote $\hat{Z}_{j}=Z_{t_{j}}$ and $\hat{Z}_{j}^{\prime}=Z_{t_{j}}^{\prime}$, then we have

$$ $\displaystyle D_{\alpha}(W_{T}||W_{T}^{\prime})\stackrel{{\scriptstyle(a)}}{{ \leq}}D_{\alpha}((W_{T},\hat{Z}_{j_{\tau}:E})||(W_{T}^{\prime},\hat{Z}_{j_{ \tau}:E}^{\prime}))$ (31) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}D_{\alpha}(\hat{Z}_{j_{\tau}: E}||\hat{Z}_{j_{\tau}:E}^{\prime})+\sup_{z_{j_{\tau}:E}}D_{\alpha}(W_{T}|_{ \hat{Z}_{j_{\tau}:E}=z_{j_{\tau}:E}}||W_{T}^{\prime}|_{\hat{Z}^{\prime}_{j_{ \tau}:E}=z_{j_{\tau}:E}}),$ (32) $$

where $(a)$ is due to post-processing property of Rényi divergence (Lemma 2.3) and $(b)$ is due to strong composition property (Lemma 2.4).

The first term corresponds to the standard composition theorem but starts only after time step $\tau$. Let us first analyze the quantity $m_{t_{j}}=\psi_{t_{j}}^{\prime}(W_{t_{j}}^{\prime})-\psi_{t_{j}}(W_{t_{j}}^{
\prime})$. Observe that for any $W$, we have

$$ $\displaystyle\|\psi_{t_{j}}^{\prime}(W)-\psi_{t_{j}}(W)\|=\|\frac{\eta}{b}\sum _{i\in\mathcal{B}_{t_{j}}}\Pi_{B_{K}}\left[\nabla\ell_{i}(W)\right]-\Pi_{B_{K} }\left[\nabla\ell_{i}^{\prime}(W)\right]\|$ (33) $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\|\frac{\eta}{b}(\Pi_{B_{K}} \left[\nabla\ell_{i^{\star}}(W)\right]-\Pi_{B_{K}}\left[\nabla\ell_{i^{\star}} ^{\prime}(W)\right])\|$ (34) $\displaystyle\leq\frac{\eta}{b}(\|\Pi_{B_{K}}\left[\nabla\ell_{i^{\star}}(W) \right]\|+\|\Pi_{B_{K}}\left[\nabla\ell_{i^{\star}}^{\prime}(W)\right])\|)$ (35) $\displaystyle\leq\frac{2K\eta}{b}$ (36) $$

where $(a)$ is due to the fact at $t_{j}$ we have $\ell_{i}=\ell_{i}^{\prime}$ except for $i=i^{\star}$ (i.e., the only data point that differs between $\mathcal{D},\mathcal{D}^{\prime}$. The rest is by triangle inequality and the projection operator $\Pi_{B_{K}}$. As a result, we know that $\|m_{t_{j}}\|\leq\frac{2K\eta}{b}$ for any $W_{t_{j}}$ and thus almost surely.

As a result, we can further bound the first term in (31) as follows

$$ $\displaystyle D_{\alpha}(\hat{Z}_{j_{\tau}:E}||\hat{Z}_{j_{\tau}:E}^{\prime})$ (37) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{j=j_{\tau}}^{E}\sup_{z_ {j_{\tau}:j-1}}D_{\alpha}(\hat{Z}_{j}|_{\hat{Z}_{j_{\tau}:j-1}=z_{j_{\tau}:j-1 }}||\hat{Z}^{\prime}_{j}|_{\hat{Z}^{\prime}_{j_{\tau}:j-1}=z_{j_{\tau}:j-1}})$ (38) $\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{j=j_{\tau}}^{E}\sup_{z_{j_ {\tau}:j-1}}D_{\alpha}(N(0,\beta_{t_{j}}\sigma^{2}I)||N(m_{t_{j}},\beta_{t_{j} }\sigma^{2}I))$ (39) $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{j=j_{\tau}}^{E}\sup_{\| m_{t_{j}}\|\leq\frac{2K\eta}{b}}\frac{\alpha\|m_{t_{j}}\|^{2}}{2\beta_{t_{j}} \sigma^{2}}$ (40) $\displaystyle\leq\sum_{j=j_{\tau}}^{E}\frac{\alpha(\frac{2K\eta}{b})^{2}}{2 \beta_{t_{j}}\sigma^{2}},$ (41) $$

where $m_{t_{j}}=\psi_{t_{j}}^{\prime}(W_{t_{j}}^{\prime})-\psi_{t_{j}}(W_{t_{j}}^{
\prime})$ condition on $\hat{Z}^{\prime}_{j_{\tau}:j-1}=z_{j_{\tau}:j-1}$. $(a)$ is due to strong composition of Rényi divergence (Lemma 2.4), $(b)$ is by the definition of $\hat{Z},\hat{Z}^{\prime}$ (see above), $(c)$ is due to (33) and the close-form of Rényi divergence between two gaussian of the same variance but different mean Mironov (). Together we have successfully bound the first term.

For the second term in (31), note that it is now condition on $\hat{Z}_{j_{\tau}:E}=\hat{Z}^{\prime}_{j_{\tau}:E}=z_{j_{\tau}:E}$ so that the two processes will have the same update iterations. For brevity, we omit the conditioning in the following derivation but all discussions are conditioning on $\hat{Z}_{j_{\tau}:E}=\hat{Z}^{\prime}_{j_{\tau}:E}=z_{j_{\tau}:E}$ if not specified. For all $t\in\{t_{e}\}_{e=j_{\tau}}^{E}$, the two process becomes

$$ $\displaystyle W_{t_{e}+1}=\Pi_{\mathcal{K}}\left[\psi_{t_{e}}(W_{t_{e}})+Y_{t_ {e}}+z_{e}\right],\;W_{t_{e}+1}^{\prime}=\Pi_{\mathcal{K}}\left[\psi_{t}(W_{t_ {e}}^{\prime})+Y_{t_{e}}+z_{e}\right],$ (42) $$

and for all other $t\notin\{t_{e}\}_{e=j_{\tau}}^{E}$, we already have

$$ $\displaystyle W_{t+1}=\Pi_{\mathcal{K}}\left[\psi_{t}(W_{t})+Y_{t}+Z_{t}\right ],\;W_{t+1}^{\prime}=\Pi_{\mathcal{K}}\left[\psi_{t}(W_{t}^{\prime})+Y_{t}+ \tilde{Z}_{t}\right].$ (43) $$

Note that we can simply choose the coupling for $\tilde{Z}_{t}$ to be $\tilde{Z}_{t}=Z_{t}$ for all $t\notin\{t_{e}\}_{e=j_{\tau}}^{E}$. Recall that by our definition of $Y,Z$, we know that $Y_{t}+Z_{t}=G_{t}\sim N(0,\sigma^{2}I)$. Now we are ready to bound the second term in (31), which is done as follows. For all $t\in\{t_{e}\}_{e=j_{\tau}}^{E}$, we have for any $z_{j_{\tau}:E}$ and $z\geq 0$,

$$ $\displaystyle D_{\alpha}^{(z)}(W_{t_{e}+1}||W_{t_{e}+1}^{\prime})$ (44) $\displaystyle=D_{\alpha}^{(z)}(\Pi_{\mathcal{K}}\left[\psi_{t_{e}}(W_{t_{e}})+ Y_{t_{e}}+z_{e}\right]||\Pi_{\mathcal{K}}\left[\psi_{t_{e}}(W_{t_{e}}^{\prime} )+Y_{t_{e}}+z_{e}\right])$ (45) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}D_{\alpha}^{(z)}(\psi_{t_{e}} (W_{t_{e}})+Y_{t_{e}}+z_{e}||\psi_{t}(W_{t_{e}}^{\prime})+Y_{t_{e}}+z_{e})$ (46) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}D_{\alpha}^{(z)}(\psi_{t_{e}} (W_{t_{e}})+Y_{t_{e}}||\psi_{t}(W_{t_{e}}^{\prime})+Y_{t_{e}})$ (47) $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}D_{\alpha}^{(z+a_{t_{e}})}( \psi_{t_{e}}(W_{t_{e}})||\psi_{t}(W_{t_{e}}^{\prime}))+\frac{\alpha a_{t_{e}}^ {2}}{2(1-\beta_{t_{e}})\sigma^{2}}$ (48) $\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}D_{\alpha}^{(h(z+a_{t_{e}}))} (W_{t_{e}}||W_{t_{e}}^{\prime})+\frac{\alpha a_{t_{e}}^{2}}{2(1-\beta_{t_{e}}) \sigma^{2}},$ (49) $$

where $(a),(b)$ is due to the that both $\Pi_{\mathcal{K}}$ and constant translation are $1$-Lipschitz. So the inequalities follow by the Lipschitz reduction lemma (Lemma 3.3). $(c)$ is due to shift reduction lemma (Lemma 3.2) for some $a_{t_{e}}\geq 0$ to be optimized later. $(d)$ is due to Hölder reduction lemma (Lemma 3.7), since $\psi=I+\phi$ where $\phi$ is the sum of mini-batch gradients. By our assumption that $\nabla\ell$ are $(L,\lambda)$-Hölder continuous (and thus $\eta\nabla\ell$ are $(\eta L,\lambda)$-Hölder continuous), indeed our Lemma 3.7 can be applied.

On the other hand, we can repeat a similar analysis for the case $t\notin\{t_{e}\}_{e=j_{\tau}}^{E}$, which leads to

$$ $\displaystyle D_{\alpha}^{(z)}(W_{t+1}||W_{t+1}^{\prime})$ (50) $\displaystyle=D_{\alpha}^{(z)}(\Pi_{\mathcal{K}}\left[\psi_{t}(W_{t})+G_{t} \right]||\Pi_{\mathcal{K}}\left[\psi_{t}(W_{t}^{\prime})+G_{t}\right])$ (51) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}D_{\alpha}^{(z)}(\psi_{t}(W_{ t})+G_{t}||\psi_{t}(W_{t}^{\prime})+G_{t})$ (52) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}D_{\alpha}^{(z+a_{t})}(\psi_{ t}(W_{t})||\psi_{t}(W_{t}^{\prime}))+\frac{\alpha a_{t}^{2}}{2\sigma^{2}}$ (53) $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}D_{\alpha}^{(h(z+a_{t}))}(W_{ t}||W_{t}^{\prime})+\frac{\alpha a_{t}^{2}}{2\sigma^{2}},$ (54) $$

where $(a)$ is due to the that both $\Pi_{\mathcal{K}}$ and constant translation are $1$-Lipschitz. So the inequalities follow by the Lipschitz reduction lemma (Lemma 3.3). $(b)$ is due to shift reduction lemma (Lemma 3.2) for some $a_{t}\geq 0$ to be optimized later.

As a result, we can unroll $D_{\alpha}(W_{T}||W_{T}^{\prime})$ using the bounds (49) (54) above until time $t=\tau$, which leads to the following bounds. For brevity, we denote $1_{t}:=1\{t\in\{t_{e}\}_{e=j_{\tau}}^{E}\}$ as the indicator function of whether $t\in\{t_{e}\}_{e=j_{\tau}}^{E}\}$ or not. For any $z_{j_{\tau}:E}$,

$$ $\displaystyle D_{\alpha}(W_{T}||W_{T}^{\prime})=D_{\alpha}^{(0)}(W_{T}||W_{T}^ {\prime})\stackrel{{\scriptstyle(a)}}{{=}}D_{\alpha}^{(A_{T})}(W_{T}||W_{T}^{ \prime})$ (55) $\displaystyle\leq D_{\alpha}^{(h(A_{T}+a_{T-1}))}(W_{T-1}||W_{T-1}^{\prime})+ \frac{\alpha a_{T-1}^{2}}{2\sigma^{2}(1-\beta_{T-1}1_{T-1})}$ (56) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}D_{\alpha}^{(A_{T-1})}(W_{T-1 }||W_{T-1}^{\prime})+\frac{\alpha a_{T-1}^{2}}{2\sigma^{2}(1-\beta_{T-1}1_{T-1 })}$ (57) $\displaystyle\cdots\leq D_{\alpha}^{(A_{\tau})}(W_{\tau}||W_{\tau}^{\prime})+ \sum_{t=\tau}^{T-1}\frac{\alpha a_{t}^{2}}{2\sigma^{2}(1-\beta_{t}1_{t})},$ (58) $$

where $(a),(b)$ is due to that we denote $A_{T}=0$, $A_{t-1}=h(A_{t}+a_{t-1})$ for all $t\geq\tau+1$. Finally, note that by Wasserstein forward tracking lemma (Lemma A.2), we know that $W_{\infty}(W_{\tau},W_{\tau}^{\prime})\leq\min(D_{\tau},D)$ (see Lemma A.2 for the definition of $D_{t}$). As a result, if $A_{\tau}\geq D_{\tau}$, then $D_{\alpha}^{(A_{\tau})}(W_{\tau}||W_{\tau}^{\prime})=0$. Thus by combining everything so far, we have the following optimization problem for the privacy loss

$$ $\displaystyle\min_{\tau,\beta,a}\sum_{j=j_{\tau}}^{E}\frac{\alpha(\frac{2K\eta }{b})^{2}}{2\beta_{t_{j}}\sigma^{2}}+\sum_{t=\tau}^{T-1}\frac{\alpha a_{t}^{2} }{2\sigma^{2}(1-\beta_{t})},$ (59) $\displaystyle s.t.\;\tau\in\{t_{e}\}_{e=-1}^{E},\;\beta_{t}=0\;\forall t\notin \{t_{e}\}_{e=j_{\tau}}^{E},\;\beta_{t}\in[0,1]\;\forall t\in\{t_{e}\}_{e=j_{ \tau}}^{E},\;a_{t}\geq 0\;\forall t\geq\tau,$ (60) $\displaystyle A_{\tau}\geq D_{\tau},\;A_{T}=0,\;A_{t-1}=h(A_{t}+a_{t-1}),\;D_{ t}\text{ is defined in Lemma~{}\ref{lma:W_dist_tracking}.}$ (61) $$

Together we complete the proof.
∎

###### Lemma A.2 (Forward Wasserstein distance tracking) .

###### Proof.

#### A.2.2 Improved bound by shuffling

Note that the privacy bound we derived in Theorem A.1 holds for any realization of shuffled cyclic minibatch sequences. As we can see, the bound indeed depends on the time step $\{t_{e}\}_{e=0}^{E}$ that we encounter $i^{\star}$ at each epoch $e$, which is inevitably controlled by the worst-case scenario when requiring a data-independent RDP bound. To alleviate the worst-case issue, it is critical to take the randomness of the shuffled cyclic minibatch sequence into account. The following corollary serves for this purpose

###### Corollary A.3 .

Let $\varepsilon(\alpha,\mathcal{B})$ be the optimal privacy loss derived in Theorem A.1 give a cyclic mini-batch sequence $\mathcal{B}$. Under the same assumption as in Theorem A.1, the DP-SGD update (1) is $(\alpha,\varepsilon(\alpha))$-RDP, where

$$ $\displaystyle\varepsilon(\alpha)\leq\frac{1}{\alpha-1}\log\left(\mathbb{E}_{ \mathcal{B}}\exp\left((\alpha-1)\varepsilon(\alpha,\mathcal{B})\right)\right).$ (62) $$

###### Corollary A.3 .

### A.3 Privacy guarantees for without replacement subsampling mini-batches

In this section, each mini-batch $\mathcal{B}_{t}$ is sampled independently and identically from $[n]$ for time step $t$ in the without replacement fashion of size $b$. That is, we randomly sample $\mathcal{B}_{t}$ out of the uniform random subset of size $b$ from $[n]$. This strategy of mini-batch sampling is known as without replacement subsampling. In what follows, we derive the RDP guarantee for DP-SGD update (1) under without replacement subsampled mini-batches.

#### A.3.1 The Analysis

Let us first introduce a technical lemma before we introduce our proof. Note that the original Sampled Gaussian Mechanism is defined in one dimension. Altschuler & Talwar () extends this notion to a higher dimension by identifying the worst-case scenario therein. Alternatively, one can directly work with high-dimensional Sampled Gaussian Mechanism as in Altschuler et al. ().

###### Lemma A.4 (Extrema of Sampled Gaussian Mechanism, Lemma 2.11 in Altschuler & Talwar ( 2022 ) ) .

For any $\alpha>1$, $q\in(0,1)$ and the noise parameter $\sigma>0$, dimension $d\in\mathbb{N}$ and radius $R>0$,

$$ $\displaystyle\sup_{\mu\in\mathcal{P}(B_{R})}D_{\alpha}(N(0,\sigma^{2}I_{d})||( 1-q)N(0,\sigma^{2}I_{d})+q(N(0,\sigma^{2}I_{d})\ast\mu))=S_{\alpha}(q,\sigma/R),$ (63) $$

where $\mathcal{P}(B_{R})$ denotes set of all Borel probability distributions over the $\ell_{2}$ ball of radius $R$ in $\mathbb{R}^{d}$.

In practice, $S_{\alpha}(q,\sigma)$ is computed via numerical integral for the tightest possible privacy accounting. Nevertheless, to have a better understanding of the quantity, Lemma 2.12 in Altschuler & Talwar () shows that it is upper bounded by $2\alpha q^{2}/\sigma^{2}$ for some regime of $(\alpha,\sigma,q)$. In what follows, we keep the notation of $S_{\alpha}(q,\sigma)$ but is useful to keep this simplified upper bound in mind.

Now we are ready to prove Theorem 3.11.

###### Proof.

Following the same analysis, we have that

$$ $\displaystyle D_{\alpha}(W_{T}||W_{T}^{\prime})$ (64) $\displaystyle\leq D_{\alpha}(Z_{\tau:T-1}||Z_{\tau:T-1}^{\prime})+\sup_{z_{ \tau:T-1}}D_{\alpha}(W_{T}|_{Z_{\tau:T-1}=z_{\tau:T-1}}||W_{T}^{\prime}|_{Z_{ \tau:T-1}^{\prime}=z_{\tau:T-1}}).$ (65) $$

For the first term, we bound it as follows

$$ $\displaystyle D_{\alpha}(Z_{\tau:T-1}||Z_{\tau:T-1}^{\prime})$ (66) $\displaystyle\leq\sum_{t=\tau}^{T-1}\sup_{z_{\tau:t-1}}D_{\alpha}(Z_{t}|_{Z_{ \tau:t-1}=z_{\tau:t-1}}||Z_{t}^{\prime}|_{Z^{\prime}_{\tau:t-1}=z_{\tau:t-1}})$ (67) $\displaystyle=\sum_{t=\tau}^{T-1}D_{\alpha}(N(0,\beta_{t}\sigma^{2}I)||(1- \frac{b}{n})N(0,\beta_{t}\sigma^{2}I)+\frac{b}{n}N(m_{t},\beta_{t}\sigma^{2}I))$ (68) $\displaystyle\leq\sum_{t=\tau}^{T-1}S_{\alpha}(\frac{b}{n},\frac{\beta_{t} \sigma}{2\eta K/b}),$ (69) $$

where we use the fact that $\|m_{t}\|\leq 2\eta K/b$ almost surely, since each gradient term is bounded by $\eta K$ due to gradient clipping $\Pi_{B_{K}}$ and there is at most $1$ out of $b$ term that corresponds to $i^{\star}$. Hence, one can apply Lemma A.4 for the last inequality. For the second term, the analysis follows similarly as in the proof of Theorem A.1. Hence we complete the proof.
∎

###### Lemma A.4 (Extrema of Sampled Gaussian Mechanism, Lemma 2.11 in Altschuler & Talwar ( 2022 ) ) .

###### Proof.

### A.4 Proof of Theorem 3.1

###### Proof.

We start with the argument of Altschuler & Talwar (), which constructs a specific coupling between the adjacent Noisy-SGD processes (1) and (2). To ease the notation, we denote $\psi_{t},\psi_{t}^{\prime}$ to be the gradient update map in (1) and (2) respectively. Then note that

$$ $\displaystyle W_{t+1}\stackrel{{\scriptstyle d}}{{=}}\Pi_{\mathcal{K}}[\psi_{t }(W_{t})+Y_{t}+Z_{t}],\;W_{t+1}^{\prime}\stackrel{{\scriptstyle d}}{{=}}\Pi_{ \mathcal{K}}[\psi_{t}(W_{t}^{\prime})+Y_{t}+Z_{t}^{\prime}],$ (70) $$

where $Y_{t}\sim N(0,(1-\beta_{t})\sigma^{2}I)$, $Z_{t}\sim N(0,\beta_{t}\sigma^{2}I)$ and $Z_{t}^{\prime}\sim N(\psi_{t}^{\prime}(W_{t}^{\prime})-\psi_{t}(W_{t}^{\prime}
),\beta_{t}\sigma^{2}I)$ for $\beta_{t}\in[0,1]$. Notice that condition on $Z_{t}=Z_{t}^{\prime}$, the two processes exhibit the same gradient update and additive noise. For any time step $0\leq\tau\leq T-1$ to be chosen later, we adopt this coupling for all $t\geq\tau$. Then by Lemma 2.4, we have the following decomposition of the privacy loss

$$ $\displaystyle D_{\alpha}(W_{T}||W_{T}^{\prime})\leq D_{\alpha}((W_{T},Z_{\tau: T-1})||(W_{T}^{\prime},Z_{\tau:T-1}^{\prime}))$ (71) $\displaystyle\leq D_{\alpha}(Z_{\tau:T-1}||Z_{\tau:T-1}^{\prime})+\sup_{z_{ \tau:T-1}}D_{\alpha}(W_{T}|_{Z_{\tau:T-1}=z_{\tau:T-1}}||W_{T}^{\prime}|_{Z_{ \tau:T-1}^{\prime}=z_{\tau:T-1}}).$ (72) $$

The first part can be handled by further applying Lemma 2.4 as follows.

$$ $\displaystyle D_{\alpha}(Z_{\tau:T-1}||Z_{\tau:T-1}^{\prime})\leq\sum_{t=\tau} ^{T-1}\sup_{z_{\tau:t-1}}D_{\alpha}(Z_{t}|_{Z_{\tau:t-1}-z_{\tau:t-1}}||Z_{t}^ {\prime}|_{Z_{\tau:t-1}^{\prime}-z_{\tau:t-1}})$ (73) $\displaystyle=\sum_{t=\tau}^{T-1}\sup_{z_{\tau:t-1}}D_{\alpha}(N(0,\beta_{t} \sigma^{2}I)||N(\psi_{t}^{\prime}(W^{\prime}_{t})-\psi_{t}(W^{\prime}_{t}), \beta_{t}\sigma^{2}I)|_{Z_{\tau:t-1}^{\prime}-z_{\tau:t-1}})$ (74) $\displaystyle\leq\sum_{t=\tau}^{T-1}\frac{\alpha}{2\beta_{t}\sigma^{2}}(\frac{ 2\eta K}{n})^{2},$ (75) $$

where the last step is due to the fact that $\|\psi_{t}^{\prime}(W)-\psi_{t}(W)\|\leq\frac{2\eta K}{n}$ for any $W$. This corresponds to part (A) in Figure 2 (b). The rest proof is the same as described in Section 3.1. Hence we complete the proof.
∎

###### Proof.

### A.5 Proof of Lemma 3.3

The proof is essentially follows Altschuler & Talwar (; ). We include the proof for completeness.

###### Proof.

Let $\nu$ be a probability distribution certifies $D_{\alpha}^{(z)}(\mu||\mu^{\prime})$. That is, $D_{\alpha}(\nu||\mu^{\prime})=D_{\alpha}^{(z)}(\mu||\mu^{\prime})$ and $W_{\infty}(\nu,\mu)\leq z$. Since $\phi$ is $c$-Lipschitz, we have

$$ $\displaystyle W_{\infty}(\phi\sharp\nu,\phi\sharp\mu)\leq cW_{\infty}(\nu,\mu) \leq c\cdot z.$ (76) $$

It implies that $\phi\sharp\nu$ is a feasible solution for $D_{\alpha}^{(cz)}(\phi\sharp\mu||\phi\sharp\mu^{\prime})$. Hence we have

$$ $\displaystyle D_{\alpha}^{(cz)}(\phi\sharp\mu||\phi\sharp\mu^{\prime})\leq D_{ \alpha}(\phi\sharp\nu||\phi\sharp\mu^{\prime})\stackrel{{\scriptstyle(a)}}{{ \leq}}D_{\alpha}(\nu||\mu^{\prime})\stackrel{{\scriptstyle(b)}}{{=}}D_{\alpha} ^{(z)}(\mu||\mu^{\prime}),$ (77) $$

where $(a)$ is due to data processing inequality of Rényi divergence and $(b)$ is due to our definition of $\nu$. Together we complete the proof.
∎

###### Proof.

### A.6 Proof of Lemma 3.4

The proof is essentially a simple application of Lemma 3.6 of Hardt et al. () or Lemma 2.2 of Altschuler & Talwar (). We denote $\psi(x)=x-\eta\Pi_{B_{K}}\nabla f(x)$.

When $f$ is $L$-smooth only, we have for any $x,y\in\mathbb{R}^{d}$:

$$ $\displaystyle\|\psi(x)-\psi(y)\|\leq\|x-y\|+\eta\|\Pi_{B_{K}}\nabla f(x)-\Pi_{ B_{K}}\nabla f(y)\|$ (78) $\displaystyle\leq\|x-y\|+\eta\|\nabla f(x)-\nabla f(y)\|\leq\|x-y\|+\eta L\|x- y\|=(1+\eta L)\|x-y\|.$ (79) $$

Here we use triangle inequality, the projection operation is $1$-Lipschitz and $L$-smoothness sequentially. Thus we complete the proof for the smooth case.

When $f$ is further $K$-Lipschitz, note that we always have $\Pi_{B_{K}}\nabla f(x)=\nabla f(x)$ since $\|\nabla f(x)\|\leq K$. Thus we can drop the projection operator directly. Then the convex and $m$-strongly convex cases directly follow Lemma 3.6 of Hardt et al. () or Lemma 2.2 of Altschuler & Talwar (). Together we complete the proof.

### A.7 Proof of Lemma 3.5

This is a special case of the proof of Lemma A.2. A similar proof also appears in Chien et al. (). We nevertheless prove this special case again for the readers.

Recall that by definition,

$$ $\displaystyle W_{\infty}(W_{t},W_{t}^{\prime})=\inf_{\gamma\in\Gamma} \operatorname*{ess\,sup}_{(X,Y)\sim\gamma}\|X-Y\|.$ (80) $$

It means that we may choose a specific coupling between $W_{t},W_{t}^{\prime}$ to serve as an upper bound. We choose the naive coupling $G_{t}=G_{t}^{\prime}$. Under this coupling, the only randomness is the initialization $W_{0}$. Let us denote the index that is differ between $\mathcal{D},\mathcal{D}^{\prime}$ to be $i^{\star}$. Then we have

$$ $\displaystyle\|W_{t}-W_{t}^{\prime}\|=\|W_{t-1}-W_{t-1}^{\prime}-\frac{\eta}{n }\sum_{i\in n}(\Pi_{B_{k}}[\nabla\ell_{i}(W_{t-1})]-\Pi_{B_{k}}[\nabla\ell_{i} ^{\prime}(W_{t-1}^{\prime})])\|$ (81) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{n}\sum_{i\in[n] \setminus\{i^{\star}\}}\|W_{t-1}-W_{t-1}^{\prime}-\eta(\Pi_{B_{k}}[\nabla\ell_ {i}(W_{t-1})]-\Pi_{B_{k}}[\nabla\ell_{i}(W_{t-1}^{\prime})])\|$ (82) $\displaystyle+\frac{1}{n}\|W_{t-1}-W_{t-1}^{\prime}-\eta(\Pi_{B_{k}}[\nabla \ell_{i^{\star}}(W_{t-1})]-\Pi_{B_{k}}[\nabla\ell_{i^{\star}}^{\prime}(W_{t-1} ^{\prime})])\|,$ (83) $$

where (a) is due to the fact that $\ell_{i}=\ell_{i}^{\prime}$ for all $i\neq i^{\star}$. For the first term, notice that the gradient update map is identical. By the assumption that the map is $c$-Lipschitz, we have

$$ $\displaystyle\frac{1}{n}\sum_{i\in[n]\setminus\{i^{\star}\}}\|W_{t-1}-W_{t-1}^ {\prime}-\eta(\Pi_{B_{k}}[\nabla\ell_{i}(W_{t-1})]-\Pi_{B_{k}}[\nabla\ell_{i}( W_{t-1}^{\prime})])\|$ (84) $\displaystyle\leq\frac{1}{n}\sum_{i\in[n]\setminus\{i^{\star}\}}c\|W_{t-1}-W_{ t-1}^{\prime}\|\leq c\frac{n-1}{n}\|W_{t-1}-W_{t-1}^{\prime}\|.$ (85) $$

For the second term, we may further bound it with triangle inequality.

$$ $\displaystyle\frac{1}{n}\|W_{t-1}-W_{t-1}^{\prime}-\eta(\Pi_{B_{k}}[\nabla\ell _{i^{\star}}(W_{t-1})]-\Pi_{B_{k}}[\nabla\ell_{i^{\star}}^{\prime}(W_{t-1}^{ \prime})])\|$ (86) $\displaystyle\leq\frac{1}{n}\|W_{t-1}-W_{t-1}^{\prime}-\eta(\Pi_{B_{k}}[\nabla \ell_{i^{\star}}(W_{t-1})]-\Pi_{B_{k}}[\nabla\ell_{i^{\star}}(W_{t-1}^{\prime} )])\|$ (87) $\displaystyle+\eta\frac{1}{n}\|\Pi_{B_{k}}[\nabla\ell_{i^{\star}}(W_{t-1}^{ \prime})]-\Pi_{B_{k}}[\nabla\ell_{i^{\star}}^{\prime}(W_{t-1}^{\prime})]\|$ (88) $\displaystyle\leq c\frac{1}{n}\|W_{t-1}-W_{t-1}^{\prime}\|+\frac{2\eta K}{n}.$ (89) $$

Combining the two parts, we arrive the bound

$$ $\displaystyle\operatorname*{ess\,sup}_{W_{0}}\|W_{t}-W_{t}^{\prime}\|\leq \operatorname*{ess\,sup}_{W_{0}}c\|W_{t-1}-W_{t-1}^{\prime}\|+\frac{2\eta K}{n}.$ (90) $$

Notice that choosing $D_{t}=\operatorname*{ess\,sup}_{W_{0}}\|W_{t}-W_{t}^{\prime}\|$ and $D_{t-1}=\operatorname*{ess\,sup}_{W_{0}}c\|W_{t-1}-W_{t-1}^{\prime}\|$ will give the desired recurssive relation. Also note that by definition $W_{t},W_{t}^{\prime}$ both start with the same initialization $W_{0}$, and thus $D_{0}=0$. Finally, notice that we always have a trivial bound $W_{\infty}(W_{t},W_{t}^{\prime})\leq D$ do to the projection $\Pi_{\mathcal{K}}$ where $D$ is the diameter of $\mathcal{K}$. Together we complete the proof.

### A.8 Proof of Lemma 3.7

###### Proof.

Let $\nu$ be a probability distribution certifies $D_{\alpha}^{(z)}(\mu||\mu^{\prime})$. That is, $D_{\alpha}(\nu||\mu^{\prime})=D_{\alpha}^{(z)}(\mu||\mu^{\prime})$ and $W_{\infty}(\nu,\mu)\leq z$. By definition, we know that there exist a coupling $\gamma^{\star}\in\Gamma(\nu,\mu)$ such that

$$ $\displaystyle\operatorname*{ess\,sup}_{(X,Y)\sim\gamma^{\star}}\|X-Y\|\leq z.$ (91) $$

Now, let us consider this specific coupling $\gamma^{\star}$ and $(X,Y)\sim\gamma^{\star}$. We have

$$ $\displaystyle W_{\infty}((I+\phi)\sharp\nu,(I+\phi)\sharp\mu)$ (92) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\operatorname*{ess\,sup}_{(X, Y)\sim\gamma^{\star}}\|X+\phi(X)-(Y+\phi(Y))\|$ (93) $\displaystyle\leq\operatorname*{ess\,sup}_{(X,Y)\sim\gamma^{\star}}\|X-Y\|+\| \phi(X)-\phi(Y)\|$ (94) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\operatorname*{ess\,sup}_{(X, Y)\sim\gamma^{\star}}\|X-Y\|+L\|X-Y\|^{\lambda}$ (95) $\displaystyle\leq\operatorname*{ess\,sup}_{(X,Y)\sim\gamma^{\star}}\|X-Y\|+ \operatorname*{ess\,sup}_{(X,Y)\sim\gamma^{\star}}L\|X-Y\|^{\lambda}$ (96) $\displaystyle\leq\operatorname*{ess\,sup}_{(X,Y)\sim\gamma^{\star}}\|X-Y\|+L( \operatorname*{ess\,sup}_{(X,Y)\sim\gamma^{\star}}\|X-Y\|)^{\lambda}$ (97) $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}z+Lz^{\lambda},$ (98) $$

where $(a)$ is due to the fact that any coupling $\gamma\in\Gamma$ will give an upper bound to the infimum over $\Gamma$, $(b)$ is due to the assumption that $\phi$ is $(L,\lambda)$-Hölder continuous, $(c)$ is due to our construction (91).

As a result, we know that when $W_{\infty}((I+\phi)\sharp\nu,(I+\phi)\sharp\mu)\leq z^{\prime}$ for some $z^{\prime}\geq 0$, if we can find a $z\geq 0$ such that $z^{\prime}=z+Lz^{\lambda}$, then the construction (91) is valid. By our definition of $h$, we know that $z=h(z^{\prime})$ gives such a valid choice. This implies that

$$ $\displaystyle D_{\alpha}^{(z^{\prime})}((I+\phi)\sharp\mu||(I+\phi)\sharp\mu^{ \prime})$ (99) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}D_{\alpha}((I+\phi)\sharp\nu| |(I+\phi)\sharp\mu^{\prime})$ (100) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}D_{\alpha}(\nu||\mu^{\prime})$ (101) $\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}D_{\alpha}^{(z)}(\mu||\mu^{ \prime})$ (102) $$

where $(a)$ is due to the fact that $\nu$ indeed satisfies $W_{\infty}((I+\phi)\sharp\nu,(I+\phi)\sharp\mu)\leq z^{\prime}$ by setting $z=h(z^{\prime})$, $(b)$ is from post-processing property of Rényi divergence (Lemma 2.3), $(c)$ is due to our construction in the beginning. By plugging in the relation $z=h(z^{\prime})$ we complete the proof.
∎

###### Proof.

### A.9 Proof of Lemma 3.8

Recall that we define $h(z)$ to be the solution map of the equation $x+Lx^{\lambda}=z$ for all $z\geq 0$ and $x\geq 0$. When $L\geq 0,\lambda\in(0,1]$, we essentially want to show that $h$ is the inverse map of $f(x)=x+Lx^{\lambda}$. Observe that $\frac{d}{dx}f(x)=1+Lx^{\lambda-1}>0$ for all $x\geq 0$, we know that $f(x)$ is strictly monotone increasing. Furthermore, it is not hard to see that $f$ is continuous. Then combining with facts that $f(0)=0$ and $f(x)\rightarrow+\infty$ as $x\rightarrow+\infty$, we know that $f:\mathbb{R}_{\geq 0}\mapsto\mathbb{R}_{\geq 0}$ is bijective. As a result, $h=f^{-1}$ is bijective, $h:\mathbb{R}_{\geq 0}\mapsto\mathbb{R}_{\geq 0}$ and $h$ is strictly monotonic increasing as well. We are left to show the close-form characterization of $h$ when $\lambda=\frac{1}{2}$. In this special case, we have

$$ $\displaystyle f(x)=x+Lx^{\lambda}=x+L\sqrt{x}.$ (103) $$

Let us denote $u=\sqrt{x}$, then we know that the solution of $u^{2}+Lu=z$ is

$$ $\displaystyle u^{\star}=\frac{-L+\sqrt{L^{2}+4z}}{2},$ (104) $$

where we always have $u\geq 0$. As a result, the solution $h(z)=(u^{\star})^{2}$. Thus we complete the proof.

### A.10 Proof of Lemma 3.9

This is a full batch special case of Lemma A.2. We refer readers to the more general proof of Lemma A.2 and leave the proof of this special case as an exercise for readers.

### A.11 Proof of Lemma A.2

Recall that by the definition of DP-SGD iterates (1) and (2), we have

$$ $\displaystyle W_{\infty}(W_{t+1},W_{t+1}^{\prime})=W_{\infty}(\Pi_{\mathcal{K} }\left[W_{t}+\phi_{t}(W_{t})+G_{t}^{\prime}\right],\Pi_{\mathcal{K}}\left[W_{t }^{\prime}+\phi_{t}^{\prime}(W_{t}^{\prime})+G_{t}^{\prime}\right])$ (105) $$

Clearly, the diameter $D$ of the projection set $\mathcal{K}$ is a natural upper bound. Also, note that $\Pi_{\mathcal{K}}$ is $1$-Lipschitz, thus we have

$$ $\displaystyle W_{\infty}(W_{t+1},W_{t+1}^{\prime})$ (106) $\displaystyle\leq W_{\infty}(W_{t}+\phi_{t}(W_{t})+G_{t}^{\prime},W_{t}^{ \prime}+\phi_{t}^{\prime}(W_{t}^{\prime})+G_{t}^{\prime})$ (107) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\operatorname*{ess\,sup}\|W_{ t}+\phi_{t}(W_{t})-(W_{t}^{\prime}+\phi_{t}^{\prime}(W_{t}^{\prime}))\|$ (108) $\displaystyle\leq\operatorname*{ess\,sup}\|W_{t}-W_{t}^{\prime}\|+\|\phi_{t}(W _{t})-\phi_{t}^{\prime}(W_{t}^{\prime})\|$ (109) $$

where $(a)$ is due to the fact that we take a specific coupling $G_{t}=G_{t}^{\prime}$ for all $t$.
Now, let us denote the $t_{e}$ to be the time step that we encounter $i^{\star}$ (i.e., the index that $\mathcal{D},\mathcal{D}^{\prime}$ differs) at epoch $e$. Clearly, for all $t\leq t_{0}$, since we have not encountered $i^{\star}$ yet so the two adjacent processes have identical updates. Combining with the fact that $W_{0}=W_{0}^{\prime}$, we have $W_{t}=W_{t}^{\prime}$. This proves the case $t\leq t_{0}$. For $t=t_{0}+1$, know that we have

$$ $\displaystyle W_{\infty}(W_{t_{0}+1},W_{t_{0}+1}^{\prime})\leq\operatorname*{ ess\,sup}\|W_{t_{0}}-W_{t_{0}}^{\prime}\|+\|\phi_{t_{0}}(W_{t_{0}})-\phi_{t_{0 }}^{\prime}(W_{t_{0}}^{\prime})\|$ (110) $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\|\phi_{t_{0}}(W_{t_{0}})-\phi_{ t_{0}}^{\prime}(W_{t_{0}})\|$ (111) $\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\frac{\eta}{b}\|\Pi_{B_{K}} \nabla\ell_{i^{\star}}(W_{t_{0}})-\Pi_{B_{K}}\nabla\ell^{\prime}_{i^{\star}}(W _{t_{0}})\|\leq\frac{2K\eta}{b}.$ (112) $$

where $(a)$ is due to our discuss that $W_{t}=W_{t}^{\prime}$ for all $t\leq t_{0}$, $(b)$ is due to the fact that $\ell_{i}=\ell_{i}^{\prime}$ for all $i\neq i^{\star}$. Thus we have proved the case $t=t_{0}+1$.

For the case $t-1\in\{t_{e}\}_{e=1}^{E}$, we similarly have

$$ $\displaystyle W_{\infty}(W_{t_{e}+1},W_{t_{e}+1}^{\prime})\leq\operatorname*{ ess\,sup}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|+\|\phi_{t_{e}}(W_{t_{e}})-\phi_{t_{e }}^{\prime}(W_{t_{e}}^{\prime})\|$ (113) $\displaystyle\leq\operatorname*{ess\,sup}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|+ \frac{\eta}{b}\sum_{i\in\mathcal{B}_{t_{e}}}\|\Pi_{B_{K}}\nabla\ell_{i}(W_{t_{ e}})-\Pi_{B_{K}}\nabla\ell^{\prime}_{i}(W_{t_{e}}^{\prime})\|$ (114) $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\operatorname*{ess\,sup}\|W_{t_{ e}}-W_{t_{e}}^{\prime}\|+\frac{\eta}{b}\sum_{i\in\mathcal{B}_{t_{e}}\setminus \{i^{\star}\}}\|\Pi_{B_{K}}\nabla\ell_{i}(W_{t_{e}})-\Pi_{B_{K}}\nabla\ell_{i} (W_{t_{e}}^{\prime})\|$ (115) $\displaystyle+\frac{\eta}{b}\|\Pi_{B_{K}}\nabla\ell_{i^{\star}}(W_{t_{e}})-\Pi _{B_{K}}\nabla\ell_{i^{\star}}(W_{t_{e}}^{\prime})\|$ (116) $\displaystyle\leq\operatorname*{ess\,sup}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|+ \frac{\eta}{b}\sum_{i\in\mathcal{B}_{t_{e}}\setminus\{i^{\star}\}}\|\Pi_{B_{K} }\nabla\ell_{i}(W_{t_{e}})-\Pi_{B_{K}}\nabla\ell_{i}(W_{t_{e}}^{\prime})\|$ (117) $\displaystyle+\frac{2K\eta}{b},$ (118) $$

where $(a)$ is due to the fact that $\ell_{i}=\ell_{i}^{\prime}$ for all $i\neq i^{\star}$. Note that now we have two valid upper bounds. One is to utilize $\Pi_{B_{K}}$ directly for the rest gradient difference terms, this leads to

$$ $\displaystyle W_{\infty}(W_{t_{e}+1},W_{t_{e}+1}^{\prime})\leq\operatorname*{ ess\,sup}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|+2K\eta\stackrel{{\scriptstyle(a)}}{{ \leq}}D_{t_{e}}+2K\eta,$ (119) $$

where $D_{t}$ is the upper bound of $\operatorname*{ess\,sup}\|W_{t}-W_{t}^{\prime}\|$ under the coupling that $G_{t}=G_{t}^{\prime}$ for all $t$. The other one is to leverage the Hölder continuous properties of $\nabla\ell_{i}$, which leads to

$$ $\displaystyle W_{\infty}(W_{t_{e}+1},W_{t_{e}+1}^{\prime})\leq\operatorname*{ ess\,sup}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|+\frac{2K\eta}{b}$ (120) $\displaystyle+\frac{\eta}{b}\sum_{i\in\mathcal{B}_{t_{e}}\setminus\{i^{\star} \}}\|\nabla\ell_{i}(W_{t_{e}})-\nabla\ell_{i}(W_{t_{e}}^{\prime})\|$ (121) $\displaystyle\leq\operatorname*{ess\,sup}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|+ \frac{2K\eta}{b}+\frac{\eta(b-1)L}{b}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|^{\lambda}$ (122) $\displaystyle\leq\operatorname*{ess\,sup}\|W_{t_{e}}-W_{t_{e}}^{\prime}\|+ \frac{2K\eta}{b}+\operatorname*{ess\,sup}\frac{\eta(b-1)L}{b}\|W_{t_{e}}-W_{t_ {e}}^{\prime}\|^{\lambda}$ (123) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}D_{t_{e}}+\frac{\eta(b-1)L}{b }D_{t_{e}}^{\lambda}+\frac{2K\eta}{b}$ (124) $\displaystyle=g(D_{t_{e}};\frac{\eta(b-1)L}{b})+\frac{2K\eta}{b}.$ (125) $$

where $D_{t}$ is the upper bound of $\operatorname*{ess\,sup}\|W_{t}-W_{t}^{\prime}\|$ under the coupling that $G_{t}=G_{t}^{\prime}$ for all $t$. By taking the minimum of the two bounds, we have proved the case $t-1\in\{t_{e}\}_{e=1}^{E}$. Finally, for the rest $t$ we can repeat the same analysis above, but this time we will not encounter $i^{\star}$ so we have $g(D_{t_{e}};\eta L)$ instead. To conclude the proof, note that all our iterations for $D_{t}$ are derived for the specific coupling $G_{t}=G_{t}^{\prime}$. Thus $D_{t}$ is indeed a valid upper bound for $\operatorname*{ess\,sup}\|W_{t}-W_{t}^{\prime}\|$. This concludes the proof.

### A.12 Proof of Corollay A.3

The proof follows by applying the joint convexity of KL divergence, which is also used in Chien et al. ().

###### Lemma A.5 (Lemma 4.1 in Ye & Shokri ( 2022 ) ) .

Let $\nu_{1},\cdots,\nu_{m}$ and $\nu_{1}^{\prime},\cdots,\nu_{m}^{\prime}$ be distributions over $\mathbb{R}^{d}$. For any $\alpha\geq 1$ and any coefficients $p_{1},\cdots,p_{m}\geq 0$ such that $\sum_{i=1}^{m}p_{i}=1$, the following inequality holds.

$$ $\displaystyle\exp((\alpha-1)D_{\alpha}(\sum_{i=1}^{m}p_{i}\nu_{i}||\sum_{i=1}^ {m}p_{i}\nu_{i}^{\prime}))$ (126) $\displaystyle\leq\sum_{i=1}^{m}p_{i}\exp((\alpha-1)D_{\alpha}(\nu_{i}||\nu_{i} ^{\prime})).$ (127) $$

By applying the lemma above, we can convert the $\mathcal{B}$ dependent result in Theorem A.1 to an average case bound. Thus we complete the proof.

###### Lemma A.5 (Lemma 4.1 in Ye & Shokri ( 2022 ) ) .

### A.13 Numerical evaluations

Numerical setting for Figure 1. We choose smoothness constant $L$ and the strong convexity constant $m$ to be $1$ for simplicity. We set gradient clipping norm $K=2$, noise standard deviation $\sigma=1.0$, domain diameter $D=1.0$, the dataset size $n=5$, and the step size $\eta=0.1$.

Numerical setting for Figure 2. For the experiment shown in Figure 2 (a), our model is a 2-layer MLP with a hidden dimension of 64. The task is classification on the UCI Iris dataset (Fisher, ) as a toy example. We set the learning rate to be $0.1$, training epoch $200$, gradient clipping norm $1.0$, and use cross-entropy loss with an additional $0.1$ multiplicative factor. To estimate the Hölder constant, for each weight along the training trajectory we sampled $100$ points uniformly at random from a $\ell_{2}$ ball of radius $1$ centered at the weight. Then we compute the maximum ratio between the norm of gradient difference and weight difference of power $\lambda$, which is the estimated Hölder constant. We further repeat this process with $20$ different initialization and take the maximum of the estimated Hölder constant as the final estimated for computing the privacy loss under the same setting as Figure 1.

We emphasize that this experiment is merely a proof of concept, and in reality, we conjecture that the loss is at least locally satisfying the Hölder continuous gradient condition. As we discussed in Section 5, one may need to explore these properties in a per-layer fashion. We also conjecture that a non-uniform Hölder continuous gradient condition involving different $\lambda$ locally is the actual case for deep neural networks.

### A.14 An example non-smooth function that has Hölder continuous gradient

This example and the proof are from Martin R(^4^44https://math.stackexchange.com/q/3213522). We repeat it here for completeness.

Consider $f(x)=\text{sign}(x)\frac{3}{4}|x|^{4/3}$. It is not hard to see that $G(x)=f^{\prime}(x)=|x|^{1/3}$. Here we show that $G(x)$ is $(2^{2/3},\frac{1}{3})$-Hölder continuous but not Lipshitz.

Case 1. $x,y\geq 0$. Without loss of generality assume $x>y\geq 0$. Then

$$ $\displaystyle x^{1/3}-y^{1/3}\leq(x-y)^{1/3}\Leftrightarrow x^{1/3}\leq(x-y)^{ 1/3}+y^{1/3}.$ (128) $$

Note that for all $a,b\geq 0$, $s\in(0,1]$, we have

$$ $\displaystyle 1=\frac{a}{a+b}+\frac{b}{a+b}\leq(\frac{a}{a+b})^{s}+(\frac{b}{a +b})^{s}.$ (129) $$

This inequality is due to the fact that $z^{s}\geq z$ for all $s\in(0,1]$ and $z\in[0,1]$. Then by choosing $a=x-y,\;b=y$, we have

$$ $\displaystyle 1\leq(\frac{x-y}{x})^{1/3}+(\frac{y}{x})^{1/3}\Leftrightarrow x^ {1/3}\leq(x-y)^{1/3}+y^{1/3}\Leftrightarrow x^{1/3}-y^{1/3}\leq 1\cdot(x-y)^{1 /3}.$ (130) $$

Clearly $1\leq 2^{2/3}\approx 1.587$. So our claim is true for case 1.

Case 2. $x,y\leq 0$. Without loss of generality assume $x<y\leq 0$. Then the same analysis from case 1 applies since $|G(x)-G(y)|=|G(-x)-G(-y)|\leq|(-x-(-y))|=|x-y|$. So our claim is true for case 2.

Case 3. $x,y$ are of opposite sign. Without loss of generality assume $x<0<y$. Then

$$ $\displaystyle|G(x)-G(y)|\leq C|x-y|^{1/3}\Leftrightarrow|x|^{1/3}+y^{1/3}\leq C (|x|+y)^{1/3}$ (131) $\displaystyle\Leftrightarrow(\frac{|x|}{|x|+y})^{1/3}+(\frac{y}{|x|+y})^{1/3} \leq C.$ (132) $$

Note that both fractions are less than $1$, so $C$ can be chosen to be $2$. A tighter estimate can be obtained by solving the maximization $u^{1/3}+(1-u)^{1/3}$ for $u\in(0,1)$, which gives $C=2^{2/3}$. Together we complete the proof that $G$ is $(2^{2/3},\frac{1}{3})$-Hölder continuous.

To show that $G$ is not Lipschitz (and thus $f$ is non-smooth), observe that for $x>0$

$$ $\displaystyle\frac{|G(x)-G(0)|}{|x|}=x^{-\frac{2}{3}},$ (133) $$

which is unbounded when $x\rightarrow 0^{+}$. Hence $G$ is not Lipschitz continuous.

## Peer Reviews

confidence: 3
contribution: 4
initial_rating: 8
presentation: 4
questions: - In equations on lines 297-305, the inequalities are under the conditioning that $Z_{1:T-1}=Z_{1:T-1}'$, right? Could the authors clarify how the dependence assumptions of Lemma 3.2 and 3.3 holds for applying the (b) inequality?
- Can the bounds presented be computed exactly or we need numerical approximations to realize them?
soundness: 4
strengths: - The paper improves upon the state-of-the art DP bounds for Noisy-SGD on strongly-convex and smooth losses.
- The relaxation of assumption on Lipschitz-continuity to Holder-continuity is a step forward towards assumption lean convergent DP bound for Noisy-SGD.
- The paper provides DP bounds under two batch subsampling techniques that are most common.
- The ideas in the paper are well illustrated and presented well for a technical audience.
- The paper claims that under non-convex but smooth losses, their DP bound remains finite with number of iteration, unlike composition based-bounds.
summary: The paper refines the hidden-state privacy analysis of Noisy-SGD algorithm under various loss assumptions from strong-convex to non-convex and from Lipschitz smooth to Holder smooth. Building on the analysis of Feldman et al., 2018, and Altschuler & Talwar, 2022, the paper shows that the shift-reduction can be applied in a more effective way by noting that a better bound on the forward Wasserstein distance is possible rather than relying on the degenerate domain diameter. The paper also notes that the Lipschitz-reduction lemma of Altschuler & Talwar, 2022 can be generalized to a Holder-reduction lemma that applies to maps that satisfy the weaker condition of Holder-continuity. Applying the findings, the paper shows better DP bounds than existing work under strongly convex and smooth losses. For convex and smooth losses, their bounds matches that of Altschuler & Talwar, 2022. Additionally, for non-convex but smooth losses, the paper promises a better DP bound than the best via composition or that of output perturbation (or any Pareto-optimal combination of the two).
weaknesses: - The main results in Theorem 3.1, 3.6 and 3.11 and Theorem aren't provided in a closed-form. This makes them hard to operationalize.
- The computational complexity of the presented bounds should be discussed.
- Full batch setting of strongly-convex and smooth case in Theorem 3.1 isn't compared with the bound in Chourasia et al., under identical assumptions.
- Utility analysis is missing. For (strongly) convex and smooth losses, the improved DP bounds can yield a better utility bounds that should be compared against the known lower-bounds [1].

[1] Bassily, Raef, Adam Smith, and Abhradeep Thakurta. "Private empirical risk minimization: Efficient algorithms and tight error bounds." 2014 IEEE 55th annual symposium on foundations of computer science. IEEE, 2014.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. **Comparison with Non-Private and Smooth/Convex Cases**: Could you provide more detail on any existing comparison with non-private results? Additionally, how do these results compare specifically to the smooth and convex cases?

2. **Simplified Upper Bound for Summations**: Is it possible to present a more concise upper bound for the summations in the final results to enhance readability and ease of comparison?

3. **Challenges in Removing Smoothness and Convexity**: While the paper does extend to non-smooth and non-convex scenarios based on the condition of Hölder continuity, the results appear inherently limited by this assumption. I am particularly interested in understanding the main challenges that arise when attempting to remove the smoothness and convexity requirements entirely.

4.** Lower bound and tightness**:  Is the result in the paper tight? In other words, is there a lower bound provided?
soundness: 4
strengths: The strengths of this paper lie in its innovative approach to privacy loss analysis in Noisy-SGD. Unlike prior work that requires assumptions of smoothness and convexity, this paper successfully establishes privacy bounds under more general conditions, making it applicable to a broader range of non-smooth, non-convex problems. Key strengths include:

1. **Generalization with Hölder Continuity**: The paper introduces the concept of Hölder continuous gradients, allowing the privacy analysis to hold even without the smoothness assumption. This broadens the applicability of Noisy-SGD to various challenging settings.

2. **Tighter Privacy Bounds**: For cases involving smooth and strongly convex losses, the paper presents a stricter privacy bound than prior results, offering enhanced privacy-utility trade-offs.

3. **Refined Analytical Techniques**: By optimizing privacy loss bounds through careful shift allocation and forward Wasserstein distance tracking, the analysis is robust and offers concrete improvements over existing methods.

Overall, this work contributes a significant advancement in privacy-preserving machine learning by providing a more flexible and precise analysis framework that can benefit a wide range of applications.
summary: This paper investigates the differential privacy (DP) guarantees of Noisy Stochastic Gradient Descent (Noisy-SGD) without relying on traditional assumptions of convexity or smoothness in the loss function, thereby addressing significant limitations in prior research. Traditional DP analysis for Noisy-SGD often assumes convexity and smoothness, restricting its applicability to various real-world machine learning problems. The authors demonstrate that it is possible to achieve convergent privacy loss bounds even when these assumptions are relaxed, requiring only that the loss function has a Hölder continuous gradient. This generalization broadens the applicability of DP-SGD to a wider range of non-smooth, non-convex problems.

#### Main Contributions:
1. **Generalized Privacy Bounds**: Establishes a new privacy bound for Noisy-SGD that applies to non-convex, non-smooth losses under the less restrictive condition of Hölder continuity.
2. **Improved Privacy Bounds for Smooth Convex Losses**: Refines analysis techniques involving forward Wasserstein distance tracking and optimal shift allocation, resulting in improved privacy bounds for cases with smooth, strongly convex losses.

By advancing hidden-state analysis, this work deepens the understanding of DP in machine learning models and introduces a more flexible framework for balancing privacy and utility in Noisy-SGD, making it more suitable for deep learning applications.
weaknesses: 1. **Unclear Structure**: The structure of the paper lacks clarity. The main text includes numerous proofs, while some theorem statements are placed in the appendix, which disrupts the flow and clarity of the overall structure.

2. **Figure Quality**: Figure 2(a) appears somewhat rough and could benefit from refinement to improve visual quality.

3. **Typo in Lemma 2.3**: There is a typo in Lemma 2.3, where the function notation shifts from \( f \) to \( h \), which should be consistent.

4. **Overly Complex Parameters**: The large number of parameters results in overly complex expressions, making it difficult to clearly interpret and compare the results.

5. **Lack of Comparative Analysis**: The paper lacks a comparison with prior results, as well as with the non-private version of the results, which would provide a better context and understanding of its contributions.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: Is there a typo in Equation (11)?
Do any classic neural networks exhibit Hölder continuous gradients? Why is this assumption appropriate?
soundness: 3
strengths: This paper is well-written and well-structured, clearly discussing prior works and their methodologies. The topic of convergent privacy loss in noisy SGD is significant, and this work makes meaningful progress in addressing it. Additionally, the results concerning non-convex functions, which can outperform output perturbation, are particularly intriguing.
summary: This paper investigates the convergent privacy loss of noisy SGD within a convex bounded domain. Applying standard composition results indicates that the final privacy loss after $T$ iterations can scale with $\sqrt{T}$. However, if only the last iterate is revealed, two recent works (Ye & Shokri, 2022; Altschuler & Talwar, 2022) demonstrate that running noisy SGD on smooth and (strongly) convex functions can result in convergent privacy loss after a burn-in phase. This paper enhances the shifted divergence analysis, presenting a strictly better privacy bound under the same assumptions, and also provides convergent privacy bounds for non-convex functions with Hölder continuous gradients.
weaknesses: The novelty and improvements presented are somewhat limited. The Forward Wasserstein distance tracking lemma appears straightforward, and the primary enhancement in the shifted divergence analysis seems to lie in identifying a better allocation of shifts. Regarding the non-convex case, I am concerned that the improvements may not be substantial when compared to output perturbation in practical applications. Hence,  I would not be surprised if other reviewers lean towards rejecting the paper, given the concerns raised.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: While I believe that the topic of the paper is significant, (1) the originality of ideas is not clear to me and (2) the applicability of the results it introduces could invalidate the progress I believe the paper makes in the area. The following questions are mostly to clarify this.



**Q1** Is there a practical setting where one would use the function exhibiting Holder continuity ? Or is there another function used in a practical setting that meets this assumption?

**Q2** How tractable are the problems in theorem statements 3.1, 3.6, 3.11? I assume it is easy since the plots for different settings are provided but I would suggest:
- Can the authors clarify how the bounds are calculated for the provided plots?
- Provide simplified versions or corollaries of these theorems that give more intuitive bounds? even if they are slightly looser. 
- Provide concrete examples comparing these bounds to prior work for specific parameter settings?

**Q3** From Figure 1 (b) one can assume there is a regime where the presented bounds are better than [AT22]. Is there a closed characterization for this regime? And can we compare with the convergence rate to see if this number of iterations is sufficient? This would prove the presented bounds are more practical than previous ones. 

**Q4** The $\hat{L}$-Lipschitz constant estimated in Figure 2 is necessary to calibrate the noise value in practical deployment of DP-SGD. After reading the methodology in the appendix it is still unclear to me how it is estimated and if this estimate is an upper bound on the real constant. Can the authors comment on how to guarantee that $\hat{L}$ is an upper bound and that this approach would not break privacy guarantees? 

**Q5** In Fig 2. a) what happens as $\lambda \to  0$? The paper only shows values for $\lambda>0.5$… 

**Q6** What are the differences between the introduced Lemma 3.5 and the lemma from Chien et al.? 

**Q7** I found the following related works that have related topics, can the authors comment on them and how they relate to their work? 
1. [https://arxiv.org/abs/2407.06496](https://arxiv.org/abs/2407.06496)
2. [https://arxiv.org/abs/2407.05237](https://arxiv.org/abs/2407.05237)
soundness: 4
strengths: **New Bounds and Relevance:** The paper studies a crucial problem: finding tight privacy bounds for solutions of non-convex optimization problems. Tight privacy accounting is essential for practical implementations of DP-SGD, particularly in sensitive domains like healthcare. When assumptions about a privacy guarantee are not met (e.g. convexity), the guarantee is inapplicable, forcing the use of  overly conservative bounds that can hinder accuracy. 

**Novel assumption:** The authors introduce an assumption that allows them to reuse previous techniques (shifted divergence) under a milder condition (holder continuous gradient).

**Clarity:** The techniques are clearly explained  for the full batch setting. While I did not check the math exactly, the proofs do follow logically. 

**Improved bounds:** The authors provide examples where their bound improves over prior work, even in the already studies (strongly) convex setting. 

**Broader impact:** The results are valuable for the broader ICLR community by enabling practical implementation of ML with sensitive data. The paper presents interesting techniques (Lemma 3.7) and assumptions (reduction of smoothness to Holder continuous gradient) in a clear and insightful way.
summary: This paper studies the problem of releasing the last iterate of noisy-SGD with Renyi DP guarantees. It presents:

- Bounds on the Renyi DP guarantee of order $\alpha$ for this problem that are independent of the number of iterations for non-convex, non-smooth functions that have a Holder continuous gradient. 
- Tighter bound for strongly convex, smooth loss functions.
- These bounds hold with the following batching strategies: Full batch, sampling without replacement, and shuffled cyclic.
weaknesses: Below I state some potential weaknesses of the paper and point to specific questions in the next question that would allow me to understand better. 

1. The authors present a contrived loss function that meets the Holder assumption to demonstrate it is not a vacuous  relaxation from the convex to the non-convex setting. While this function meets the assumption, it questions the applicability of their results in real world settings. (Q1)

2. Theorems 3.1, 3.6, 3.11. Present bounds parameterized by optimal values of $\tau$ and a sequence $\beta$ making it hard to parse and consequently unintuitive. It becomes hard to understand practical implications and compare to prior work, and the claims about the burning period are hard to verify. (Q2)


3. The originality of Lemma 3.5 is questionable since a similar result was introduced before by Chien et al (2024b). While the authors acknowledge this prior work, they argue that it applies to a different context, machine unlearning. However, this is a misleading distinction because machine unlearning literature also tracks unlearning with a DP definition. (Q6)

4. Minor comments:
- For a general reader it is not clear from the paragraph in the introduction why Output perturbation is not a good option. (It becomes more clear in figure 1 but I would suggest having it in the main body).

- The first sentence presents noisy SGD and DP-SGD as equivalent, which is not true, in general. Noisy SGD typically refers to SGD where gradients are noisy, but there is no expectation about privacy guarantees. DP-SGD, should provide DP guarantees which might involve more steps than Noisy-SGD, e.g.,  clipping. 

- Line 96, K having diameter D would suggest the set is bounded but it does not matter for the bounds, D could be infinite and the bound still holds. I would clarify this since it makes the paper stronger :) 

- I suggest proofreading for typos. A few are:
    - Line 106: “differing with one point.” differing by?

    - Fig 2 caption, line 125: “It done by constructing a coupling (G_t, G_t’), resulting a coupled process….”

    - Theorem 3.11 statement “Then the DP-SGD update (1) under without replacement…”

    - Missing parenthesis in Eq. 19.

** Update **
See discussion below addressing these weaknesses.

Meta-review: The paper got sufficient support from the reviewers (with a few of them have historically worked on similar problems). However, there were a few major concerns, a) The assumption on Holder continuous gradient is unclear how operational it is for natural optimization tasks, and b) the extension to privacy amplification by iteration is not very novel, and c) there were concerns on the comparability of the result to prior results using output perturbation.

Decision: Accept (Poster)