Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness
Authors: Eli Chien
Pan Li
Venue: ICLR 2025 Poster (2025)
Keywords: privacy
differential privacy
hidden state SGD
nonconvex
nonsmooth
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We show the convergent privacy loss of hidden state noisy SGD even without convexity and smoothness assumptions.

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\'enyi 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\'enyi DP bound for non-convex non-smooth losses, where we show that requiring losses to have H\"older 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\"older reduction lemma. Our results further elucidate the benefit of hidden-state analysis for DP and its applicability.

Published as a conference paper at ICLR 2025
CONVERGENT PRIVACY LOsS OF NOISY-SGD WITHOUT CONVEXITY AND SMOOTHNESS
Eli Chien & Pan Li
Department of Electrical and Computer Engineering Georgia Institute of Technology Georgia, U.S.A.
{ichien6, pan i J@gatech. edu
ABSTRACT
We study the Differential Privacy (DP) guarantee of hidden-state Noisy-SGD al- gorithms over a bounded domain. Standard privacy analysis for Noisy-SGD as- sumes 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 sufficient. We also provide strictly better privacy bound compared state-of-the-art results for smooth strongly convex losses. Our analysis relies on the improvement of shifted divergence analysis in multiple aspects, including for- ward 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.
INTRODUCTION
Noisy Stochastic Gradient Descent (Noisy-SGD), also known as DP-SGD (Abadi et al.] 2016). is now the fundamental workhorse for privatizing machine learning models with the guarantee of differential privacy (DP) Dwork et al. (2006). The popularity DP-SGD due to its effective- ness and simplicity - it is nothing but SGD with per-sample gradient projected to lg ball (also known as gradient clipping) and additive Gaussian noise. Despite the simplicity and ubiquity of the DP-SGD algorithm,
still do not have holistic understanding regarding its privacy loss One such evidence is that standard privacy analysis based on composition theorem (Kairouz et al. 2015 Mironov 2017) gives a divergent privacy loss with respect 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. 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.
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, 2022 Ye & Shokri 2022) 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 an important open question in Ye & Shokri (2022); Altschuler & Talwar 2022 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?
We refer privacy loss the DP parameters for the last iterate of Noisy-SGD.

---

Published as a conference paper at ICLR 2025
6.525
smooth locues
RDP for smooth strongly convex losses
0.500
Alschuler Talwaa (2022)
Ours
64455
1e6 Shokrt (2022)
Standard Composition
Outgut
Strengly
Compostiio
0.00
0.00
0.00
20
30
T
[Itorations)
T (Iterations]
(8)
(b)
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 diameter of the bounded domain. (b) The detailed comparison of
privacy bound with Altschuler & Talwar 2022); Ye & Shokri (2022) for smooth strongly convex
losses. The setting is the same as (a). We relegate the detail setting to Appendix|A.. A.13
Table I: Summary of the required assumptions of existing analysis. v indicates the assumption is necessary and @ indicates one can optionally incorporate that assumption for a better privacy bound. IIf 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 (0022)
Altschuler & Talwar 2022
Ours
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 indeed convergent over a bounded domain even without convexity smoothness assumptions. The least restrictive assumption we need is Hölder continuous (see Definition 2.5 gradients of order À E (0, 1]. which is more general assumption compared to the loss being smooth. We say a function f has Hölder continuous gradient with constant L and order if satisfies [x) V fy(ill < L||x~y/|* for any in the domain. Specifically, when À = 1 recover the standard smoothness assumption. Note that there are non- non-smooth functions that still have Hölder continuous gradient. An iconic example f(x) = sign (2) ] 1/3, where ('(x)) = [ One can show that has Hölder continuous derivative of order 1/3 with constant 22/3 but not smooth (Appendix A. Even for a smooth function, the corresponding Hölder constant may be significantly smaller than the smooth constant for smaller Hölder order X, which potentially leads to better privacy bound. See Figure (a) for neural network example. Note that this experiment is the similar spirit of of et al. (2020)
non-trivial value
where we do not assert that neural networks necessarily have Hölder continuous gradient in general. Instead, our goal is to demonstrate that generalizing hidden-state DP analysis to Hölder continuous gradient can be beneficial. Interestingly, our analysis also gives strict improvement privacy bounds (Altschuler Talwar 2022 Ye Shokri 2022) under the same set of assumptions with smoothness and strong convexity (Figure (b)).
existing
Analysis. We study the projected Noisy-SGi algorithm with sam-se gradient clipping, which is the projected version of the popular DP-SGD (Abadi et al., 2016). We defer all missing definitions in the preliminaries section 2 Let D [d E X be training datasets of n data points, where each data point d; associate with loss function E(: d() on convex set K. of diameter D. For any
2

---

Published as a conference paper at ICLR 2025
for losses with (L.olerö continous gradient
0.5
W/11 11x
G3
W4
Standard Composition
Output Perturbation
0.4
À - 1.0
(A)
Wes1
nat La (5%) [.]
À 0.9
Wo
À = 0.7
(C)
W
0.2
W;
W.41
Txx Iw (W)) G.]
(B)
0.1
(A): Standard compasition (B): Shifted divergence analysis (C): Forward Wes distance tracking
W
0
25
50
100
125
150
Vee Vi gradients on D, D' reapectively.
(Iterations)
(a)
(b)
Figure 2: (a) Our RDP bound for non non-smooth loss with (L, A)-Hölder continuous gradient, where we empirically estimate the Hölder continuous constant I. of 2 layer Multi-Layer Perceptron (MLP) for each X. See Appendix A..3 for the detailed setting. (b) The illustration of the overall analysis. The decomposition of (A) (B) parts is developed by Altschuler & 'Tawwrr (2022). It is done by constructing a coupling (Gr, Gj), resulting coupled process W,. Part (A) 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 ampli- fication by iteration and will depend on the infinite Wasserstein distance W (W,, W Altschuler & Talwar (2022) use the domain diameter as an upper bound. In contrast, we perform a careful forward W 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 becomes applicable to even non-convex non-smooth losses with Hölder continuous gradients.
step size 1). batch size b and initialization Wo E K. we iterate T times the Noisy-SGD update
BBx [V((W)]] + +G iEB.
W41 ITx W. "
where πy is the Euclidean projection to the closed convex set K., I is the projection the l ball of radius K (also known as gradient clipping), G. ~ N(O and B, is the mini-batch of indices time t. Our goal is to establish a worst-case upper bound of the Rényi divergence between distributions of the last iterate WT and W that are trained on any two adjacent datasets differing by one point. Prior work (Altschuler Talwar, 2022) 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 for some intermediate time step 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 W.. This part is handled by the shifted divergence analysis, which is originally known as privacy amplification by iteration (Feldman et al.) (018)) and requires smoothness and convexity. Our main technical contributions are 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 (part (C)). Compared to Altschuler & Talwar (2022) that utilize the domain diameter D di- rectly, 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 E [r, 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 per- turbation for smooth non-convex losses but also strictly tighter privacy bound for smooth strongly convex losses. Our key intuition is that shifted divergence analysis provides us with a way to dis- tribute the maximum discrepancy W (Wr, W?) to shifts in each time step E [T, 1J. This phenomenon does not rely on the convexity of losses, where the convexity only plays 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
3

---

Published as a conference paper at ICLR 2025
step. We alleviate this issue by proving the Hölder reduction lemma (Lemma 3.8 which allows us to work with the general Hölder continuous gradient condition.
PRELIMINARIES
Notations. We consider the empirical risk minimization problem, where the loss for weight w
dataset DD is [(w; D) = > f(w; d;). We denote [n] == (1,2,-.. ..). We denote fūj the
pushforward of distribution 1a under function We denote Xx: as shorthand for the vector concatenating , Xy,
(Rényl) differential privacy. In this work we focus on replacement DP for simplicity, while exten- sions to notions of dataset adjacency are possible. We say two datasets D, D' are adjacent (denoted as D D') 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. 2021) for smaller privacy loss as well. A popular way of deriving DP guarantees 2017], which relates to the Rényi divergence defined below.
work with Rényi Differential Privacy (RDP) (Mironov)
Definition 2.1 (Rényi divergence). For any a >> the a-Rényi divergence between two probability measures μ and v is (a [)) = - log (((((t))(((=))))(()))) if Ja < v, and oo otherwise.
Definition 2.2 (Rényi differential Privacy). randomized algorithm A satisfies (aDE)-RDP D& (a((())))A(())
for all possible D ~ D'.
With slight abuse of notation, for random variables X μ and Y v we define Do (X (a(ullv) 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 a > 1, any function h, and any probability distri- bution μ. v, D, (htullltvv) S (.)lv))).
Lemma 2.4 (Strong composition for Rényi divergence). For any a > 1 and any Iwo sequences of random variables XI, Xx and Vi,",, Ys. Pa(Xia|(\1ss) <
Σ sup..... (x lal:ll/Y///i yn. 1))
Both of the above lemma are known to the literature and we refer interested readers to Altschuler & Talwar (2022) for more thorough discussion.
Potential assumptions on the loss & Throughout, the loss function corresponding to a data point dj d' is denoted by (-(-) E(:: d,) and (-)- ((::d') respectively. Let K. IRd be an arbitrary closed convex set in which our model parameters w lie.
Definition 2.5 (Hölder continuity). For function f f IC C Rdd say is (L, Hö-öle continu- ous if for all w, w/ E IC, (w]( - f(w')l < Tl|l w/|l,, where 2 and E ().
Note that (L, 1)-Höld continuous is equivalent to I--Lipschitz continuous. Thus function has (L, 1)-Höld continuous gradient is equivalent to L-smoothness when gradient exists. Hence, the (L, A--Hölder continuous gradient assumption is indeed more general. The other standard defini- tions such as Lipschitz, convexity, and smoothness are deferred to Appendix A.I
Shifted Rényi divergence analysis. Our analysis generalizes the shifted Rényi divergence analysis (Atschuul
developed by Feldman et al. (2018); AAttshhulrr & Talwar (2022), where we merely need the Hölder continuous gradient instead of requiring the loss to be Below we introduce the definitions of infinite Wasserstein distance and shifted Rényi divergence which will play a central role in proof.
smooth, and Lipschitz continuous.
Definition 2.6 (Woo distance). Let μ,, be probability distributions over R.d. The infinite Wasser- stein distance between μr, is defined as W (,, inf,er((w.)) ess sup((.)))>)) || -Y], where I'4, v) is the set of all possible coupling of p.
Definition 2.7 (Shifted Rényi divergence). Let μ,v be probability distributions over Rd For any 2 2 0 and a > 1, the shifted Rényi divergence defined as D (H||P) = inf Wi (p(p()l))
4

---

Published as a conference paper at ICLR 2025
3 OUR HIDDEN STATE DP-SGD PRIVACY LOSS ANALYSIS
Our goal is to show that the last iterate of the DP-SGD update T WT is (a, (a.=(D))RRD and charac- terize the bound E(x) under our weak assumptions. This is equivalent to bound the Rényi divergence of any two adjacent processes Wr, W1 defined by D = D' respectively in the worst case. The ad- jacent process of ( with respect to the dataset DD' is defined follows
W = [l
Wi
T
Σ Bxx (V((W)) G 1E8;
where the initializations are identical almost surely Wo W
Note that there different possible mini-hatch strategies adopted in practice such without placement subsampling, shuffled cyclic mini- and full-batch cases, All of these are compatible with our analysis and will study them separately. For simplicity, we start with the full batch set- ting B: = [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 state-of-the-ar 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 unified manner.
Theorem 3.1 (Privacy loss of Noisy-GD with smooth loss). Assume E is L-smooth. Then the Noisy- SGD update ① filh batch setting (a, (a)))((()DDD))) for a where
2
min 2nk Σi= c 2n,,T, D)2) Et- 3.) ((t-4))))+1
E(a) S min TB
a 20
Σ
(3)
3
s.1. T E (0.1...,TT1)) B E [0, 1], vt 2 c= 1 n,l..
(4)
If E is also convex, K K-Lipschitz and choose 7 S 2/ L, we have c If is also m-strongly convex, K K-Lipschitz and choose v) < 1/L, we have 1 mmm
Theorem 3.1 indicates that after burn-in period of iterations, there is further privacy loss for both convex and non-convex cases as shown in Figure [ (a). Our result degenerated to the results of Altschuler & Talwar (002) for the convex case, and show that similar phenomenon also holds without convexity but requires a longer burn-in period of iterations with larger final privacy loss. When the loss is m-strongly convex, our Theorem 3.1 provides strict improvement over the result of Altschuler & Talwar (2022); : Ye & Shokri 2022 See Figure
(b) for the illustration.
Below we provide sketch of proof for Theorem 3.1 and the missing part be found in Ap- pendix 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 introduc- ing 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 ps, v on Rdd
and a, z O. we have
on
D(=) (n+ N(O, o²D) N(O, onn) < D(=+a) (1||P)
(5)
202
Lemma 3.3 (Lipschitz reduction lemma Altschuler & Talwar 2022
Assume the mapping e is and O, we have
c-Lipschitz.for 2 Then for any probubility distribution μs, u on 12a
D((=)) (otallott))) < D(=)) (pllv).
(6)
In recent work concurrent to this paper, Altschuler et al. (024) also proposed the improved analysis for strongly convex case that does not require hounded domain and match our results asymptotically. Still, analysis provides strict improvement in the non-asymptotic regime.
5

---

Published as a conference paper at ICLR 2025
On the other hand, one show that the gradient update x: nlI [V((x)] is Lipschitz if the loss E at least smooth (Hardt et al. [016,] Altschuler & Talwar 2023).
Lemma 3.4 (Lipschitz constant of the gradient update map). Let (()) = x- nIIBx [V[(x)] be the gradient update map with loss l and step size n O. If é is L-smooth, &b is + 7L Lipschitz. 8. is further convex, K-Lipschitz and Σ 2/ I,, 1/ is Lipschitz. If is further m-strongly convex, K K-Lipschitz and n L, v is 1pm 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. (2024b); Wei et al. (024) have also adopted the similar idea of Wasser- stein distance tracking analysis. but their analysis is for machine unlearning and DP-PageRank re- spectively, which are different from ours. See Appendix A.7 for a further discussion.
Lemma 3.5 (Forward Wasserstein distance tracking for Lipschitz gradient update). Consider the adjacent processes W, Wi defined in (1) and (2) respectively. Assume the gradient update map 2
2 Eieln) BB [V](x)) are e-Lipschitz for the full batch setting B, = B3 = [n]] Then we have
()(x)) = x n Lie(n] Bx [Vt(2))], v((x) =
Wo (W,, W() S min(D;, D), D. min(cD,-1 + 2n /n, Dz-1 + 2nK), Do = 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 (2022) which constructs a specific cou- pling between the adjacent Noisy-SGD processes (I) and (2). To ease the notation, we denote sha, by
to be the gradient update map in and respectively and d for equivalent in distribution.
Wi+1
4 II 2e (W,) Y Zı], W/+1 I.(()(W) Y2 + Z,].
(8)
where Y, N(0, (1 1)) Z. N(0, 3,o²1) and Zí (()(())) v.x (W)) 3,0²1) for 3, E [0. Notice that condition on Z, Zí. the two processes exhibit the same gradient update and additive noise. For any time step 0 S r T - to be chosen later, adopt this coupling for all t 2 r. Then by Lemma 2.4 we have the following decomposition of the privacy loss
Da(TT|WW/ < ZT. Z)T 2-rr-1)
(9)
S Da Da. + sup
Z. 1=2,eT | 7 1 .).
(10)
Z.T
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 - a 28,0= ( (2nK j2 and correspond to part (A) Figure
(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 as a₂ 2 O, which will be determined later. With slight abuse of notation, we neglect the conditioning of Z, Z' but keep in mind that the analysis below is under such conditioning.
Da DaWrl[WW = 00 [UIl/T-11WT-Ta + Yr-1 + zT - [ - (WG-1) + +Y-11 + zT-
(1/ -1 (Wr 1- + Yy 1 Yr-
(6)
an²
D -r- (or-:(((->))) (WT- || +
2(1 - BT-1)0"
T-1
< D Et -1(--+)))
(W+I
+ Σ
oxa
2(1 3
t=r
where (a) is due the projection and constant shift are 1-Lipshitz maps and thus by Lemma 3.3
due to Lemma 3.2 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 т. Note that while the shifted divergence term is in general non-tree con-tractable, when Wo. (W, I[W)) is less then the accumulated shifts according to its definition 2.7 By enforcing

---

Published as a conference paper at ICLR 2025
this constraint, we obtain closed- privacy loss bound to be optimized with respect S, dt, where the constraint can be characterized by forward Wasserstein distance tracking lemma 3.5
k Be
of ) + (1-B))
min T,B.a 20²
s.l. Σ (-(+r 2 min(Dr, D), (11)
11
where E 00, 11, E (), 0r 2 0 and D, is defined in Lemma 3.5 Finally, observing
this constrained optimization can further simplified by characterizing the optimum solution as follows. By
inequality, we have
Σ af 3r]
T-1 Ea (1- B.)( -)(--((--t))
T-1 Σ
2
a&c (1-
(12)
where the equality holds if the ratio (1-3)c (t .Ty is the same for all 7 S S - -1 Appar- ently, this is attainable by choosing a, properly according to Be, (t,c-((+++),, Note that (1 3) and (1-+7++1) are all non-negative so that this characterization of o still matches its non-negative constraint. As a result, the optimization problem above can be further simplified as stated Theo- rem 3.1 where we complete the proof.
worth noting the interpretation of Theorem 3.1 which the root of our key intuition stated in Section 1.1 Under the optimum choice of ae determined by (12), we know that dz & (1
(c)c-(1-T-) where the left-hand side is closely related to the denominator of the second term (1 -))--((tr++) in the privacy bound of Theorem 3.1 As result, the second term in the privacy bound of Theorem 3.T can be interpreted as how we distribute the maximum discrepancy min( 2n/ Eizo c² 21/KT, D) to the shifts aj each time step E [T,T - 1] along with weights e -t--++1), Even if the losses are non-convex so that > 1, it is still possible to distribute the maximum discrepancy to more than one shift and thus a bound better than output perturbation 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.
2(t-T+1)
Remark 3.6. The focus of our work is on the privacy upper bound. The utility analysis for smooth strongly convex case can be found and adopted from Chourasia et al. (202I). In the meanwhile, since our work degenerate to the bound of Altschuler & Talwar (2022) for the smooth convex case, their lower bound analysis, especially the worst-case construction, applies to our scenario as well. We leave full discussion on these aspects as future works.
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 2022 Ye & Shokri 2022), which restricts their application to non-smooth problems. Our Theo-
rem 3.7 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.7 (Privacy loss of Noisy-GD with Hölder continuous gradient). Assume Vi are X)- Hölder continuous with X E (0, Let g(x) = I + nLax> with domain and range being R20 and = g Then the Noisy-SGD update ([
with full batch setting is (a,é(a)))RDP for a 1, where
T-1
Knk
2
a(a) < min
Σ
2
(13)
T,8,a 20
Br
11
1- 8
1=7
s.t. r E (0, 1 ... . - 1}, B E [0,1], 0, 2 0 0 2 A, 2 Dr.
(14)
Ar Du 0. A h(A, + +.-1). D. = min(g(Dr-1) + +22K/n D.-1 2 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 mooohh,,th the gradient update map z can no longer be guaranteed to be Lipschitz, and thus Lemma 3.3 cannot be utilized. We prove the following key lemma which allows to work without smoothness assumption.
7

---

Published as a conference paper at ICLR 2025
Lemma 3.8 (Hölder reduction lemma). Assume the map ø is (L, X) -öölerr continuous for L and À E (0, 1]. Then for any probability distribution μ. v over R. a and 2 2 0,
0
D ((T + o)t,lI(TT + ))tv) ((h (nllp);
(16)
where h(2) is the solution map of the equation z + Lx for 2 0 and I is the identity map.
Note that the gradient update map & can indeed be written as I+ Φ. where is the identity map and é is the gradient term. We further prove that the map la is "well-behaved".
Lemma 3.9 (Properties of h). For any 2 2 0, let h(2) be the solution map of the equation x+ LL
for x 2 O. For any L 2 0 and X E (0, we have 1) h Rz0 + I2zu 2) h is strictly monotonic increasing and continuous,
is bijective, 4) when X = 1/2, we have the close-form
characterization h(z) -L++VI++ +4+
Finally, we perform the forward Woc distance tracking in this case.
Lemma 3.10 (Forward Wasserstein distance tracking). Consider the adjacent processes W., W defined in ① and (2) respectively. Assume that Vl,(a), VE((z) are (I., H)-öler continuous for all E [n). Denote g(r; L) = x + Lx.,, then we have Wo (W,, W() S min(D,, D), D. = min(g(De-1::LL) + 2n/Knn, D + 2nK), Do =. (17)
The proof of Theorem 3.7 follows by a similar analysis in Section 3.1 but replacing the Lipschitz reduction lemma with Lemma 3.8mmaa.88aaa Lemma with Lemma 3.10 The full proof can be found in Appendix A.2 by specializing the minibatch results full batch [7] setting.
3.3
MINI-BATCH CASES
Our analysis naturally supports two different popular mini-batch settings: subsampling without placement and shuffled cyclic mini-batch. While the privacy analysis for subsampling without re- placement 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 ex- cellent study on their pros and cons when deploying them in practice (Chua al. 2024).
Subsampling without replacement. To express the result, we first introduce the Sampled Gaussian Mechanism (Mironov al. 2019).
Definition 3.11 (Rényi divergence of Sampled Gaussian Mechanism). For any a > 1, mixing probability g E (0, 1) and noise parameter 0, define
Sa(g,o) = (N ()) - () + (N((1
(18)
Note that Sa can be computed in practice with a numerically stable procedure for precise computa- tion Mironow (2017). Now are ready to state the result for subsampling without replacement.
Theorem 3.12. Assume Vl,, Ve, are (L, X) -öööerr continuous for L 2 0 and X E (0. 1]. Let be the solution map defined in Lemma 3.8 with constant nL, X. Then the Noisy-SGD update ① under without replacement sampling mini-batches of size b is (ax, ((x)))DDP for >> 1, where
b 3,ob
e(a, B)- =min T.B.a Σ
Sa( n 2n
+
(19)
2n 3c)
s.t. E {0, I... T 1}, B, E [0, 11, a 2 20 T, A, > Dr, AT Do 0,
(20)
A,-1 = MAA, + a;-1), D. =
1)/b) 2n/ /b, D.-1 + 2n, D):
(21)
where g(;; L)
Lx and S. ()) o) is defined in Definition 3.11
The proof is similar to the proof of Theorem 3.7 except that we adopt the Sampled Gaussian Mech- anism 5. to bound the first term (i.e., part (A) in Figure (b)), which can be found Appendix A..3 A.3 One can further specialize Theorem 3..2 if more structure assumptions are given, which leads to the
subsampling without replacement version of Theorem 3.1 We leave it as 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 the space limit, we defer the results to Appendix A.2
8

---

Published as a conference paper at ICLR 2025
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. 2202T) is the first that leverages Langevin dynamic analysis for deriving convergent privacy bound in the full batch setting. Ye & Shokri (2022) extend and refine their analysis to the mini-batch setting, yet both of which require smooth strongly convex losses. CChin et al.] (2024a) also leverage the the meanwhile, [Asoodeh & Diaz (023) 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. Nevertheless, there are other benefits regarding this analysis, such as supporting Poisson subsampling and without the need of RDP-DP conversion. It is interesting to see if the one can achieve the best of the both worlds. Finally, Altschuler & Talwar (2022) developed the analysis that combines privacy amplification by subsampling and iteration (Feldman et al. 2018) in a clever way, which leads to the statc-of-the art privacy bound for Noisy-SGD under smoothness and convexity assumption. [Altshuuler & Talwar (2023); Chien et al.) (2024b) adopted a similar analysis for studying the mixing time of Noisy-SGID and its unlearning guarantee respectively. We improve their results with not only generalization to non-smooth non-convex losses with Hölder continuous gradients, but also tighter bound for the smooth strongly convex losses.
Langevin dynamic analysis but for machine unlearning problem.
After the submission our work, we notice that there are two recent works on hidden-state DP for Noisy-SGD. Annamalai [Annamaal (022)) shows that not all non-convex losses can be benefitted from hidden-state in privacy. This does not contradict our results, as we show that some "continuity" in gradient (i.e., Hölder continuous gradient) is needed for the reduction lemma type of result. Concur- rently, Kong & Ribero (202)) study the hidden-state DP analysis of Noisy-SGD but with different condition control the degree of convexity and do not consider the of Hölder continuous gradi- ent. Under the same set of assumptions on smoothness and convexity, our bound is provably tighter. See Appendix for for a more detail comparison.
CONCLUSIONS AND OPEN PROBLEMS
We provide an affirmative answer to the open question raised in Altschuler & Talwar (202)); Ye & Shokri 2022): 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 better privacy-utilig trade-off of NoD (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.7 and 3.1 directly rely on gradient clipping in non- convex cases, additionally requires losses 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 discontinu- ous derivative of gradients on a set with negligible measure. The same open question is raised in Altschuler Talwar (022). The key question is whether we can prove the gradient update map ((x)) x 7 Bx (z) to be e < 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. The concurrent work (Kong& & Ribero (024) prove that the clipped gradient update map with- out Lipschitz loss assumption is indeed a Lipschitz map. It is interesting to further combine their result with our analysis future work.
Better practical privacy accounting, For ease of analysis, current hidden-state Noisy- SGD litera- ture treats the model weight whole real vector 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 modified to satisfy these assumptions. A recent interesting
9

---

Published as a conference paper at ICLR 2025
proposes to directly enforce layer- Lipschitzness of neural networks, so that gradient clipping can be dropped to reduce the time and space complexity of DP-SGD. They show that per-layer analysis provides better privacy-utility trade-off compared to requiring the L Lipschitzness of the neural network as a whole. We conjecture similar idea is necessary to improve the practicality of hidden-state Noisy-SGID analysis.
work (Béthune et 2024)
Non-uniform Hölder continuous gradient. Another aspect of improving the practicality of our work is consider the non-uniform Hölder continuous gradient. Indeed, whenever the parameter difference | - yll < 1, smaller Hölder constant can be obtained for À < 1. One interesting idea to introduce the non- 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 the- orem 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-FTRI. (Kairouz et al.) (021). which shows that better privacy-utility trade-off can be achieved compared 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 further provide 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 indeed relatively tight. The positive evidence is that our analysis degenerates to the result of Alltccullr & Talwar (2022) for smooth convex losses, where they have constructed an order-wise matching lower bound on the privacy loss. We conjecture that 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 shuf- fling analysis from Ye & Shokri (2022) (see Corollary A.3). the resulting bound cannot be computed
in a numerically stable way. Although Ye & Shokri (2022) propose a numerically stable approxi- mation, 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 eet al.) 2021) for rigorous DP guarantee. It is interesting to see if the privacy upper bound of the approximation method in Ye & Shokri (2022) can be established. A better privacy amplification by shuffling analysis is also important open question as mentioned in Chua et al. (2024).
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, Jiayuan Ye, Weiwei Kong, Shahab Asoodeh, reviewers and the area chair for the helpful discussion and comments. E.Chien and P. Li are supported by NSF awards CIF-2402816, PHY-2117997 and JPMC faculty award.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communicutions security, pp. 308-318, 2016.
Jason Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35:3788-3800, 2022.
Jason Altschuler and Kunal Talwar. Resolving the mixing time of the langevin algorithm to its sta- tionary distribution for log-concave sampling. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2509-2510. PMLR, 2023.
10

---

Published as a conference paper at ICLR 2025
Jason M Altschuler, Jinho Bok, and Kunal Talwar. On the privacy of noisy stochastic gradient descent for convex optimization. SIAM Journal on Computing. 53(4):969-0011 2024.
Meenatchi Sundaram Muthu Selva Annamalai. It's our loss: No privacy amplification for hidden state dp-sgd with non-convex loss. arXiv preprint arXiv:2407.06443 2024.
Shahab Asoodeh and Mario Diaz. Privacy loss of noisy stochastic gradient descent might converge even for non-convex losses. arXiv preprint arXiv:2305.09903 2023.
Louis Béthune, Thomas Massena, Thibaut Boissin, Aurélien Bellet, Franck Mamalet, Yannick Pru- dent, Corentin Friedrich, Mathieu Serrurier, and David Vigouroux. DP-SGD without clipping: The lipschitz neural network way. In The Twelfth International Conference on Learning Repre- sentations, 2024. URL httptpss//ppeureieerr net wwwumoirumii.oooo BEriidd--EyyeeRee
Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li. Langevin unlearning: new perspective of noisy gradient descent for machine unlearning. arXiv preprint arXiv:2401.10377 2024a.
Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li. Stochastic gradient langevin unlearning, arXiv preprint wxXiv:2403.171003 2024b.
Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34:14771-
14781, 2021.
I Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. How private are DP-SGD implementations? In Forty-first International Conference Machine Learning, 2024. URL hottps://openxeviee net/ Eorum? wwwrruumiiiiiIIMMIIMIE XWIOMKWJSS
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284. Springer, 2006.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-52.. IEEE, 2018.
R. A. Fisher. Iris. UCI Machine Learning Repository, 1988. DOE: http:://6..oog//0222333///77
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems,
2021.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234. PMLR, 2016.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pp-
PMLR, 2015.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pp. 5213-5225. PMLR, 2021.
Weiwei Kong and Mónica Ribero. Privacy of the last iterate in cyclically-sampled dp-sgd on non- convex composite losses. arXiv preprint 2rXiv:2407.05237.200 2024.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations sympo- sium (CSF), pp. 263-275. IEEE, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Ry'eny 'nyyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 1908. 10530, 2019.
Rongzhe Wei, Eli Chien, and Pan Li. Differentially private graph diffusion with applications in personalized pageranks. arXiv preprint arXiv:2407.00077 2024.
Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems, 35:703-715, 2022.
11

---

In this section, assume for simplicity that b divides that B n/b is a positive integer Given the number of total iterations T, there will be E [T/B] + epochs that 7' (E B)B T. At the beginning of epoch 0 S E < E, we randomly partition the index set [n]] into B mini-batches {B;) 1 B-1 where we denote B, = B if t = eB + i. Note that the mini-batch generation process independent of the dataset D (as long as they have size n), the noise G,, and the underlying model parameters W, In what follows, we will first derive the RDP guarantee for any fixed mini- Published as a conference paper at ICLR 2025
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In Interaational Conference on Learning Rep- resentations, 2020. /tthttps::/ httttps://ppnrevieew httpeeerwrr.i.ttteeeooouuaaaaaaa
A APPENDIX
A.1 STANDARD DEFINITIONS
Let f K. C.C. R. + R be a mapping. We define smoothness, Lipschitzsness, and strong convexity
as follows:
I-smooth: V v EK, [V](()) v/(iill - L||= - yl
(22)
m-strongly convex: Vz,yE K, (x y, Vf(x) ff(v)) 2 m||a 11| vl?
(23)
M-Lipschitz: V y, E K, (If(z) f(y)l S M | yll-
(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 (I, 1) Hööder continuous gradient. Furthermore, say f is convex if it is O-strongly convex.
A.2 PRIVACY GUARANTEES FOR SHUFFLED CYCLIC HANI-BATCH
batch sequence (Br T- and then improve the bound by taking into account the randomness of the mini-batches.
Theorem A.1. Assume Vl,, VL, are (L, HoHöler continuous for 2 and X E (0, 1]. Let be the solution map defined in Lemma 3.8 with consiant nL, A. Given any mini-batch sequence B = {B, T from shuffled cyclic mini-batch strategy, define {te) {e)e__, be the set of time steps that we encounter at epoch e, where 1-1 0 and assume we will encounter in the last epoch up to time step T. Then the DP-SGD update I with the given mini-batch sequence B is (a, E(a, RDD
for a > 1, where
a 2Kny²
T-1
E(O, min
Σ
Σ
20 36) j- iff (1y-1,45)
(25)
T,8,0 /=
200,,02
s.t. r E (0, 10.1.... T 1}, Br = vt & (te) 3r 10, 1] E (te) ai 2 4 2
(26)
Ar 2 Dr, AT = 0, A = h(A, + az-1), ,), D2 is defined in Lemma A.2
(27)
If we do not encounter it in the last epoch up to time step T, replace E by E 1.
A.2.1 THE ANALYSIS
We will need the following Woc distance tracking lemma, which is crucial to contain privacy ac- counting based on the standard composition theorem (Mironov 2017) as our special case. similar idea is also used for proving unlearning guarantees for SGD unlearning (Chien et al.) 2024b) and tight DP guarantees for the hidden-state PageRank algorithm (Wei et al. 22044).
Lemma A.2 (Forward Wasserstein distance tracking). Consider the adjacent processes W., W defined in 1 and respectively. Given any mini-batch sequences (B.} and B, = B₁, denote ta
When b does not divide n, can simply drop the last [n/b] points.
12

---

Published as a conference paper at ICLR 2025
be the time step that i" E Bt_ at epoch that [te/B] Assume that Vi(.,d) is (L, X)- -öHder continuous for any d E X. Then we have
W WW., Wi) 2 min(Dr:)) D),
(28)
ift S lo: ift = to +o+1 if y E otherwise,
2n//6b /6
D2 =
(29)
min(g(D 1)/b) - D 2n)K
Inn) Di-1 + kn
where g( L) x Lx
Now are ready to prove Theorem A.T
Proof. The key idea of the shifted Rényi divergence analysis is constructing a coupling between Wr, Wi so that the analysis can be simplified (Altschuler & Talwar 2022). According our assumption, we have that B. = B is some given fixed mini-batch sequence. Let us define the overall update map at time to be (W) W o Eies, Ilx [W)]. Similarly, we can define vi( to be the overall update map for dataset D'. Then we construct specific coupling between Gt, G2, as follows
W++1 Txx (W,) + V. Zr), W4 IT (((W)) + V. 2/ _ Ixx [bh + Y, + %
(30)
where Yú ~ - is worth noting that (W()) = 2h (W() for any t such that it B,. Let denote te to be the time step such that i" E B, at epoch e. Then clearly Vh, vit are only different at [te]
Ze, 2, ~ N(, 1,021) and 2i ~ WWW)
3,021). It
Let us denote t-1 0. If we condition Z, Z for all t {te for some -1 S j E, then we know that W,, W are two processes with identical update mapping & vi for any t 2 ty. Thus, we can upper bound the Rényi divergence between Wr, W7. as follows: for any given T E
(te ) 1e=-1+ 11 let j. be the corresponding epoch index e including -1. Let us denote 2, Zi, and 2)- Zi then we have
(a) Da (Wr(( S (WWT, (((W,,2j.e))) 2..=)))(( k)y,))
(31)
(8) S Da (2 22,, + sup D (Wr 1 [7 )
(32)
25.:5
where (a) is due to post-processing property of Rényi divergence (Lemma strong composition property (Lemma 2.4
2.3p and (b) is due to
The first term corresponds to the standard composition theorem but starts only after time step r. Let us first analyze the quantity mi, = Vit, (W7,) the (W7,). Observe that for any W, we have
11, (W) 11, (W)ll '/ Σ
B [V)(W)
IIx [V((W)]
(33)
B
(a)
1/
[I
[e.- (W)) - IB VC. (W)III
(34)
(I
(W)] + |T [Ve, (W))II
(35)
2K b
(36)
where (a) due to the fact at t, we have 4, = & except for i = i* (i.e., the only data point that differs between D, D'. The rest is by triangle inequality and the projection operator II Tg-- As result, we know that [mm,] || < 2Kg for any We, and thus almost surely
13

---

Published as a conference paper at ICLR 2025
As result, can further bound the first term in 31 as follows
(a(
=112 12/
(37)
F
sup Do 22.0
2//10- 1 =
(38)
|=
3/13-1
E
(6)
Σ
sup Do(N(O, ,
(39)
j=h 3--311
(0)
E
a almm, 1| 2 x²
sup
(40)
j= |mag || b
2K j 2 x2
(41)
where ma; My, (W,,) We, (W condition on 2ー 2j. (a) is due to strong com-
position of Rényi divergence (Lemma 2.4 (b) is by the definition of 2, 7' (see above), (c) is due (33) and the close-form Rényi divergence between two gaussian of the same variance but different mean mean Mironov (2017). Together we have successfully bound the first term.
For the second term in (31, note that it is now condition on Zz-:E Zj. 2 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 2,.:E 2 = E not specified.
For all t E {te )teeeje the two process becomes
W1++ = TTx [t,e, (W..) Y,, + =e], W = TTx (W,) + Y. + ze],
(42)
and for all other& & {to)e=j, we already have
W441 II + Zı), W/41 II (v((W) + Y2 + 2,]
(43)
Note that we can simply choose the coupling for Z, be 2, Zi for all & (telemj, Recall that by our definition of Y, 2, we know that Y, + Zi = G. ~ NN0, Now we are ready to bound the second term in 31 which is done follows. For all E {te)emj. we have for any Zj.-E and z 2 O,
o0,
D (I.
(44)
= (IIx [/.. (W,,) + Yr, + 2dl |[T [1h, (W%) + Yr, + z)])
(45)
(vr. (W..) + Yr, + +zel)) + Yr, + ze)
(46)
(Mr. (W,.) + -...1.. + +Y.)
(47)
aa?
D (=tam)) (whe. (.,.)ll. 2(1 Bt,
(48)
a De (h(=+ai.)) 1) (W,, (W:)) 2(1
aaa 2
(49)
)
where (a), (b) is due to the that both IIx and constant translation are 1-Lipschitz. So the inequal- ities follow by the Lipschitz reduction lemma (Lemma 3.3). (c) is due to shift reduction lemma (Lemma 3.2 for some ar_ 2 to be optimized later. (d) due to Hölder reduction lemma
where ò is the of mini-bated gradients. By assumption that Vi are LL, A)-Hölder continuous (and thus ve are (nL, X) Höllerr continuous), indeed our
(Lemma 3.8 since 2 =
Lemma can be applied.
14

---

Published as a conference paper at ICLR 2025
On the other hand, we can repeat similar analysis for the case t & [te)em which leads to
(W D (Ik (W() + G.] (w,(W)) + G.))
(50)
(51)
D. (eb((() + Gollsa + Gt)
(52)
Wn ing D(atai) (1bx (w.)ll + 20
a0
(53)
aaf
((((+t)))) (W, (W))
+ 20
(54)
where (a) is due to the that both Il and constant translation 1-Lipschitz. So the inequalities fol- low by the Lipschitz reduction lemma (Lemma 3.3) (b) is due to shift reduction lemma (Lemma 3.2 for some o, 0 to be optimized later.
As a result, we can unroll Da (Wr((W))) using the bounds (49
554
above until time / = т, which E {telemj, } as the indicator
leads to the following bounds. For brevity, we denote 1,
1ft
function of whether & E {1e) ((o)e,,)) } or not. For any :F.
Da(WT| = (WT (4) D(An) D
(Wr(1W7)
(55)
< DMArrtrr- + 20 3T-11T-1
(56)
(b)
aa 2
S D(Ar-1 (
+
(57)
20 BT 1r
a0²
S D(A.) (W, W:)
+
(58)
20 BB11))
1=
where (a). (b) is due that we denote AT 0, A,-1 h(A, + a-11) for all t 2 J ++1. 1. Finally, note that by Wasserstein forward tracking lemma (Lemma A.2 we know that W SW,, W;) < min( (D,, D) (see Lemma A.2 for the definition of D,). As a result, A, 2 D,, then
D(AA) (W, (W)) = 0. Thus by combining everything so far, we have the following optimization problem for the privacy loss
E
2kn
T-1
min 7,0.0
b
+ Σ
a07
(59)
28t,002
20 3.) t=r
s.t. E te E
e= 8= = 0 Vt & (tele Be E [0,1] E (te)e a 0 2T,
(60)
A, 2 Dr, Ar = 0, A,1 A4A, + a De is defined Lemma
(61)
Together we complete the proof.
A.2.2 IMPROVED BOUND BY SHUFFLING
Note that the privacy bound we derived in Theorem A. holds for any realization of shuffled cyclic minibatch sequences. As can see, the bound indeed depends the time step {te) that we encounter i' 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 E(a, B) be the optimal privacy loss derived in Theorem A.l give cyclic mini- batch sequence B. Under the same assumption as in Theorem A.I the DGD update ① is (a, a(a)))()RO) RDPP, where
1 log (Eg exp ((a - 1)e(a, B)))
E(a) a
(62)
15

---

Published as a conference paper at ICLR 2025
A.3 PRIVACY GUARANTHES FOR WITHOUT REPLACEMENT SUBSAMPLING MINI- BATCHES
In this section, each mini-batch B, is sampled independently and identically from [r] for time step I in the without replacement fashion of size b. That is, randomly sample B, out of the uniform random subset of size b from [n]. This strategy of mini-batch sampling is known as without replace- ment subsampling. In what follows, we derive the RDP guarantee for DP-SGD update ( 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 Sam- pled Gaussian Mechanism is defined in one dimension, AAttschulrr & Talwar (2022) 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. (2024).
Lemma A.4 (Extrema of Sampled Gaussian Mechanism, Lemma 2.11 in Altschuler & Talwar (202 ) For any a > 1, q E (0,1) and the noise parameter o > 0, dimension E N and ra- dius R > O.
sup La)lI ())(11)))((000))) (g(NN(,, + Sa(g,o/R), nEP(Bn)
(63)
where P(Ba) denotes set of all Borel probability distributions over the Eg ball of radius R in Rd.
In practice, S. (g.or) or) 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 2022) shows that upper bounded by 20q² /o² for some regime of (ax, a, 4). what follows, we keep the notation of (g, o)) but is useful to keep this simplified upper bound in mind.
Now we are ready to prove Theorem 3.12
Proof. Following the same analysis, we have that
Da D& (Wr((Wh))
(64)
S D
sup Da
=
(65)
2----1
For the first term, we bound it as follows
Da -
(66)
sup Da (Ze 2 2 2.011-2011
(67)
Fra-1
b Da (N 8,000)
NN(0,80021 NN
b + NN(m,,
(68)
b
3.0
Σ Sa Km/K/b'
(69)
where we use the fact that ||mae|| < 2n/ /b almost surely, since each gradient term is bounded by K due to gradient clipping BB and there at most out of term that corresponds to i*. 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.I Hence we complete the proof.
A.4 PROOF OF THEOREM 3.1
Proof. We start with the argument of Altschuler & Talwar (2022). which constructs specific
pling between the adjacent Noisy- processes (1) and (2). To case the notation, we denote 4/2, oi be the gradient update map in and respectively. Then note that
W 4 (W, Y. Zz), W 4 Tgl.) Y, + Zj].
(70)
16

---

Published as a conference paper at ICLR 2025
where Y, ~ (1- 1)) Z N(0, 3 I) and Z ((e)(W)) (w()) 3,0²I) for St E [0. 1]. Notice that condition on Z Z₁, the two processes exhibit the same gradient update and additive noise. For any time step 0 S T S T to be chosen later, adopt this coupling for all /. 2 r. Then by Lemma 2.4 we have the following decomposition of the privacy loss
Da (W - ((WT, Zr: ZrT-1) (.T-11))
(71)
- Da(Zrrr-1lZZ..
sup (W 2. W Z..
(72)
2,
The first part can be handled by further applying Lemma 2.4 as follows.
Da (a -:T
sup Da Da Du 2: -8ma-1)
(73)
T-1
-W,"),, Σ sup (N (. (. 1 1 Fed
(74)
f-t-1
T-1 a
k
(75)
23,02
where the last step is due the fact that (W) v., S 2nk for any W. This corresponds to
part (A) in Figure (b). The rest proof is the same as described Section 3.1 Hence we complete the proof.
A.5 PROOF OF LEMMA 3.3
The proof is essentially follows Altschuler & Talwar (2022: 2023). We include the proof for com- pleteness.
Proof. Let be probability distribution certifies D (mll)²). That is, Da(ulln() D (ulle()
and W (M, p) S z. Since e is c-Lipschitz, we have
Woc otn) S (W, Sc.z.
(76)
It implies that Φtv is feasible solution for D (c=) (dtull022") Hence we have
Diez) (otallott)))) I Da (ottllot)))) (vllle) ( (ullu()
(77)
where (a) due to data processing inequality of Rényi divergence and (b) is due to our definition of v. Together complete the proof.
A.6 PROOF OF LEMMA 3.4
The proof is essentially simple application of Lemma 3.6 of Hardt et al. (2016) or Lemma 2.2
Altschurul & Talwar 2023). We denote v'xx) = z 7lI1 V((z).
When l is L-smooth only, we have for any x, y E Rdd
(x) (vv)) < | - vll + / I V((z) II v((y)]I
(78)
< || wll + 1 1| Vi(x)) - v < - yll + nL x - yll = +1+ - vll. (79)
Here we use triangle incquality, the projection operation is 1 1-Lipschitz and L-smoothness sequen- tially. Thus complete the proof for the smooth case.
When is further K K-Lipschitz, note that we always have II V((x)= = Vd(x) since |V(())] < K. Thus can drop the projection operator directly. Then the convex and mtstroggly convex cases directly follow Lemma 3.6 Hardt et al. (2016) or Lemma 2.2 of Altschuler & Talwar (2023). Together complete the proof.
17

---

Published as a conference paper at ICLR 2025
A.7 PROOF OF LEMMA 3.5
This is special case of the proof of Lemma A.2 A similar proof also appears in Chien et al. 2024b). We nevertheless prove this special case again for the readers.
Recall that by definition,
W (W,, W() = inf ess sup |X YII.
(80)
TET (X,Y)
It means that may choose specific coupling between Wi, W/ to serve upper bound. We choose the naive coupling G. = G₁ Under this coupling, the only randomness is the initialization Wo. Let us denote the index that is differ between D, D' to be i". Then we have
I|2 - Will = [|W-- W
(4(W--)) - BI (e 7 Σ B
(81)
n
in
|W W 7 BR Ve, n. (e
(82)
n
W (11 V4g- Bl VE (WI-))
(83)
where (a) is due to the fact that & = E. for all * i For the first term, notice that the gradient update map is identical. By the assumption that the map is e-Lipschitz, have
1
Σ
| W;-1 (II (4 II (W:
(84)
n
Σ
W - W/ S n n - Wi-ll
(85)
(E
For the second term, may further bound it with triangle inequality.
W W. (TT 1. (Wi-1)) BT V. (W )))
(86)
n
1W W 77 (II Bg Vl,- (W,-1)) IT. Ve. (W,-1)))
(87)
1/ B [V, - II Ba VE, (WL1))II
(88)
$ c- W W/-al++ 2nK
(89)
Combining the two parts, we arrive the bound
W/-1l++ 2nK
ess
I[, Will < ess sup W
(90)
Wo
Notice that choosing D, = ess supw, |W, WW-WW Will and D ess W W will give the desired recurssive relation. Also note that by definition W,, W/6 both start with the same initial- ization Wo. and thus Do 0. Finally, notice that we always have trivial bound W (W,, W') S D do to the projection 7Tx where D is the diameter of K. Together we complete the proof.
Comparison to Lemma 3.3 in Chien et al. (2024b). Our Lemma 3.5 and Lemma 3.3 in Chien jet al. (2024b) coincide in the strongly convex setting and have the similar spirit. However, for the general smooth case that > 1, our bound can be tighter. Note that Lemma 3.3 of Chien et al. 2024 can be viewed as always leveraging the first term in the minimum of equation 7 and writing out the recursion. Indeed, when general case с 1, it possible that the minimum will be the second term. This happens whenever (c 1)-11 > K 1/n).
1 the minimum will always be the first term. However, for the
18

---

Published as a conference paper at ICLR 2025
A.8 PROOF OF LEMMA 3.8
Proof. Let v be a probability distribution certifies D& (allaa). That is, Da(vila)) = D (ullx()
and (V) By definition, know that there exist coupling y E [(e, such that
ess sup I| YI <.
(91)
(x
Now, let consider this specific coupling 7* and (X,Y) ~ y We have
Wo ((1 + Ø) (I + d)du)
(92)
ess sup (X,Y))*
| + ((X) - (Y + (()))
(93)
csssup (X-Y)-7*
X Y| + (1x(X) +(YIl
(94)
esssup (X,Y))>*
|X - YI1 + D||X - -YIA
(95)
< ssssup (X,Y)ay*
X Y| + esssup L| M1A
(96)
(X,Y)my'
S esssup
| - Y| + L sss |X--|1> (X,Y)=>
(97)
(X,Y)
2 LZa,
(98)
where (a) is due to the fact that any coupling I will give upper bound to the infimum over I, (b) is due to the assumption that @ is (L, H--Hed continuous, (c) is due to our construction 91
As result, we know that when W Woo(1 ((1 + Φ) (I + d)Hn)) S z' for some z' > 0, if we can find z 2 0 such that 2 = z + Lzd, then the construction (9T) is valid. By our definition of h, we know
that 2 h(2²) gives such valid choice. This implies that
(1I+ + d)Hx()
(99)
Pa((T+o)tuil) #))mm)))
(100)
X Da(ulln')
(101)
(ull()))
(102)
where (a) is due to the fact that v indeed satisfies W( + Φ)ER, (1 + )) < x by setting
h(2'), (b) is from post-processing property of Rényi divergence (Lemma 2.3). (c) due to our
construction in the beginning. By plugging in the relation a = h(z') we complete the proof.
A.9 PROOF OF LEMMA 3.9
Recall that we define h(z) to be the solution map of the equation + Lx 2 for all 2 and x 2 0. When L > 0, A E (0, we essentially want to show that h is the inverse map of f(x) x + Lad Observe that (x)) = 1 + La > 0 for all x 2 O, we know that f(x) is strictly monotone increasing. Furthermore, is not hard to see that f is continuous. Then combining with facts that f(0) = 0 and f(x) too as x +oo, we know that f E2o R2 is bijective. As a result, / = f-1 is bijective, h R20 + R20 and h strictly monotonic increasing as well. We are left to show the close-form characterization of when X = 1.2 In this special case, we have
f(x) = x + Lx x LVE.
(103)
Let us denote = Vi, then we know that the solution of u² + Lu = 2 is
LL2 42
u
(104)
2
where we always have 2 0. As result, the solution M(2) (u+)², Thus complete the proof.
19

---

Published as a conference paper at ICLR 2025
A.10 PROOF OF LEMMA 3.10
This is full batch special case of Lemma A.2
We refer readers the 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
and (2 we have
Wo (1+ 11 = 5o ( W + (w, + G. Te W + ((W)) + GTI)
(105)
Clearly, the diameter of the projection set I. a natural upper bound. Also, note that IIx is 1-Lipschitz, thus we have
W (W L+1 W1+1) Woo (W, (:(W) + G. W/ + d((W) G
(106)
I WV IN
(107)
ssssup [W, + de (W,)) (W) + (WW)) ess |W; Will + (W)) ((W))
(108)
(109)
where (a) due the fact that take specific coupling G. = G¹ for all Now, let denote the te to be the time step that we encounter i* (i.c., the index that D, D' differs) at epoch e. Clearly, for all < to. since we have not encountered i* yet so the two adjacent processes have identical
updates. Combining with the fact that Wa = W we have W2 W/ This proves the case t S to- For = lo + 1, know that we have
W (Wa 11, W W10+1)= S ess sup I W% + 11 (Wi.) 0% (W,,))l
(110)
(a)
(W,,, - 0% (We,))
(111)
(b) " A Vle (W,)) - BR VG, (W., S 2K11
(112)
where (a) is due to our discuss that W, W for all S to. (b) is due to the fact that l for all i + it. Thus we have proved the case t = to + 1.
For the case - 1 E Jt
similarly have
WooWWe+ W W((+)) S ess sup | W. + (Wt.) (WW
(113)
< ess sup IWW, - -W, ||
b Σ
BBB (W.....) - IT Ve((W))
(114)
BEB.
@ esssup WW -W:.l 1
Σ
| vL(W.)) TT Ve(WW.)
(115)
iEB Me*
[T Vl, (W,,) BB Ves Ves
(116)
b
sup
IW: W/ + 7
Σ
[B ve(W..) 11 V4(WWIII
(117)
SEB, 1(P)
2Kg b
(118)
where (a) is due to the fact that L, = & for all i + it. Note that now we have two valid upper bounds. One is to utilize Blx directly for the rest gradient difference terms, this leads to
(a) W Wo W/ Wh+t)) esssup | W + +Kn S Dr. + 2Kn.
(119)
20

---

Published as a conference paper at ICLR 2025
where Di is the upper bound of css sup I|, Will under the coupling that G, G2 for all t. The other one is to leverage the Hölder continuous properties of Vlg which leads to
5o WW +1, WT. S ess sup |W,,- W || + 2Kn
(120)
1
Σ
[W,( - Ve((W)))
(121)
iEB }
S esssup IW -W + 2K + 776b 1)L
IW W.'l1*
(122)
b
S esssup i W., + 2Kn + ess sup
11b 1)L
1
W 11^
(123)
b
(a)
+ 17(b - 1)L DN + 2Kn
S Dr.
(124)
b
: 1( 1)T, ) 2K b
(125)
where D, is the upper bound of ess sup ||W, Will under the coupling that G2 G22 for all t. By taking the minimum of the two bounds, we have proved the case f - E [te]e=1- Finally, for the rest ((D_iiL) instead. To conclude the proof, note that all our iterations for Dr are derived for the specific coupling G, G²2, Thus D, is indeed valid upper bound for sss I|W W. This concludes the proof.
repeat the same analysis above, but this time will not encounter i we have
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. (2024b).
Lemma A.5 (Lemma 4.1 in Ye & Shokri (2022), ). Let v1, Pn and v'. vn be distributions over Red. For any 2 1 and any coefficients p1,'"" Pm 2 O such that Σm Pt = 1, the following inequality holds.
m
exp((a 1)Da( Puul p.ts))
(126)
S Σ exp((a 1=1
(127)
By applying the lemma above, we can convert the B dependent result in Theorem A.1 to an average case bound. Thus complete the proof.
A.13 NUMERICAL EVALUATIONS
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 = 1.0, domain diameter D = 1.0, the dataset size n = 5, and the step size
Numerical setting for Figure I
0.1.
Numerical setting for Figure For the experiment shown in Figure 2 (a), our model is 2-layer MLP with a hidden dimension of 64. The task is classification on the UCI Iris dataset (Fisher 1988) 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 random from &g ball of radius centered at the weight. Then compute the maximum ratio between the norm of gradient difference and weight difference of power X, 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
Note that when À + 0, the Hölder continuous gradient condition says that the gradient difference norm is upper bounded by constant. This in fact degenerates to the case of standard composition
21

---

Published as a conference paper at ICLR 2025
theorem, since the purpose of clipped gradient norm is exactly for such condition. As result, when + 0, the bound will become identical to the Pareto frontier of the standard composition theorem and output perturbation. In addition, we also test the case À < 0.5 and find that it will become worse whenever is too small.
We emphasize that this experiment is merely proof of concept, and in reality, conjecture that the loss is at least locally satisfying the Hölder continuous gradient condition. As we discussed in Section 5] one may need explore these properties in per-layer fashion. We also conjecture that a non-uniform Hölder continuous gradient condition involving different À locally is the actual case for deep neural networks.
Computational complexity. We optimize the proposed privacy bound as follows. For any fixed т, we optimize the privacy bound with respect parameters ar, Be by the "scipy.optimize.m "inpeoopiimieeemmmmiieee" minimize" function in scipy library. To optimize for т, we simply use binary search. Note that while this strategy does not guarantee feasible solution gives a valid (but potentially loose) privacy bound. In our numerical settings, any point in Figure (a) (i.e., smooth case) can be computed almost immediately (less than a second). For points in Figure 2 (a), the computational time is no more than few minutes in general.
find the global optimum of the problem, we emphasize that any
A.14 AN EXAMPLE NON-SMOOTH FUNCTION THAT HAS HÖLDER CONTINUOUS GRADIENT
This example and the proof are from Martin R We repeat it here for completeness.
Consider f(x) = sign(x) |x|4/8 /433, It is not hard to see that G(z) = f'(x) = |z|1/33 Here we show
that G(z) is (22/3, ) continuous but not Lipshitz.
Case 1. y, 2 O. Without loss of generality assume x y 2 0. Then
1/3 //3 S (rr 1/2/3 + 11/3 S (x y) 2/3 + 1/3
(128)
Note that for all a, b. 0, (0, 1], have
a
+
b
S (
a (
+
b
(129)
b
a a+b b
abb²
This inequality is due to the fact that a = x y. b = y, we have
23 z for all (0, 1] and
(0, 1]. Then by choosing
1 x b
1/3 < (x- 13 + y + 1/3 1/3 S 11 (x - 1/3 (130) +
Clearly 5 22/3 1.587. So our claim is true for case 1.
Case 2. x, S 0. Without loss of generality assume x < y S 0. Then the same analysis from case
I applies since [G(z) G(y) (((-))GG(--) S 1(-x (-y)) = |x y). So our claim is true for case 2.
Case 3. I, y are of opposite sign. Without loss of generality assume
y. Then
[G(x) - G(v)l 2/2/3 + |a|1/3 + 1/3 < C( | + y) 1/3
(131)
[x|] 1/3 (
y 113 SC
( |x| +
(132)
|x|| +
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 1/3 (1 u) u/3/3 for E 1), which gives C = 22/3
Together we complete the proof that G is (22/3, () -Hölder continuous.
To show that G is not Lipschitz (and thus f is non-smooth), observe that for x >> 0
GGxx) - G(O)
x
(133)
x
which is unbounded when x - 0+. Hence G is not Lipschitz continuous.
22

---

Published as a conference paper at ICLR 2025
A.15 DETAILED COMPARISON TO KONG & RIBERO (2024)
In addition to the difference in the problem setting and assumptions used, we would like to add more details the tightness aspect compare our privacy bound.
Comparison to output perturbation bound. As we have shown in our Figure (a), our privacy bound can be strictly and significantly better than the output perturbation bound, which is aD² where recall that D is the domain diameter, o² is the noise variance and is the parameter the meanwhile, from the main theorem (i.c., Theorem 2.2) of Kong & in e--ényi divergence. that their bound is 2n2 (Ci (C)) l for some problem-dependent constant Ribero 2024),
2
C1 > and C2 > 0. Apparently, this bound is strictly worse than the output perturbation bound abovementioned. This is the first key difference between our results.
Behavior as dataset size grows. Intuitively, a larger dataset size n. should lead to smaller privacy loss for DP-SGD, since only out of gradient term is changed between the adjacent dataset. This is apparently true for the classic composition theorem- based analysis. Note that for smooth convex losses, our result degenerates the bound of Altschuler Talwar (2022); Altschuler et al. (2024), which also exhibits this behavior. That is, as - 30 the privacy loss goes to O. In contrast, The main theorem (i.e., Theorem 2.2) of Kong & Ribero (2024) gives a bound a DCi in the 2n2
constant C₁ > 1 independent of n. Apparently, this bound does not decay to 0 which significantly different from our bound and bound in Altschuler & Talwar (2022): ; Altschuler et al. (2024).
full-batch setting when n - oc for some problem-depente
23


Reviews:
[{"review_id": "Uq5B2bLXVa", "reviewer": "Reviewer_rdb2", "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).", "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?\n- Can the bounds presented be computed exactly or we need numerical approximations to realize them?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper improves upon the state-of-the art DP bounds for Noisy-SGD on strongly-convex and smooth losses.\n- The relaxation of assumption on Lipschitz-continuity to Holder-continuity is a step forward towards assumption lean convergent DP bound for Noisy-SGD.\n- The paper provides DP bounds under two batch subsampling techniques that are most common.\n- The ideas in the paper are well illustrated and presented well for a technical audience.\n- The paper claims that under non-convex but smooth losses, their DP bound remains finite with number of iteration, unlike composition based-bounds.", "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.\n- The computational complexity of the presented bounds should be discussed.\n- 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.\n- 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].\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dQ5w2C9p6l", "reviewer": "Reviewer_WAgt", "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.\n\n#### Main Contributions:\n1. **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.\n2. **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.\n\nBy 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.", "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?\n\n2. **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?\n\n3. **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.\n\n4.** Lower bound and tightness**:  Is the result in the paper tight? In other words, is there a lower bound provided?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "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:\n\n1. **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.\n\n2. **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.\n\n3. **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.\n\nOverall, 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.", "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.\n\n2. **Figure Quality**: Figure 2(a) appears somewhat rough and could benefit from refinement to improve visual quality.\n\n3. **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.\n\n4. **Overly Complex Parameters**: The large number of parameters results in overly complex expressions, making it difficult to clearly interpret and compare the results.\n\n5. **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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WRXTEqEMms", "reviewer": "Reviewer_tQqF", "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.", "questions": "Is there a typo in Equation (11)?\nDo any classic neural networks exhibit Hölder continuous gradients? Why is this assumption appropriate?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CuEcVNyO0J", "reviewer": "Reviewer_8m94", "summary": "This paper studies the problem of releasing the last iterate of noisy-SGD with Renyi DP guarantees. It presents:\n\n- 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. \n- Tighter bound for strongly convex, smooth loss functions.\n- These bounds hold with the following batching strategies: Full batch, sampling without replacement, and shuffled cyclic.", "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.\n\n\n\n**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?\n\n**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:\n- Can the authors clarify how the bounds are calculated for the provided plots?\n- Provide simplified versions or corollaries of these theorems that give more intuitive bounds? even if they are slightly looser. \n- Provide concrete examples comparing these bounds to prior work for specific parameter settings?\n\n**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. \n\n**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? \n\n**Q5** In Fig 2. a) what happens as $\\lambda \\to  0$? The paper only shows values for $\\lambda>0.5$… \n\n**Q6** What are the differences between the introduced Lemma 3.5 and the lemma from Chien et al.? \n\n**Q7** I found the following related works that have related topics, can the authors comment on them and how they relate to their work? \n1. [https://arxiv.org/abs/2407.06496](https://arxiv.org/abs/2407.06496)\n2. [https://arxiv.org/abs/2407.05237](https://arxiv.org/abs/2407.05237)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "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. \n\n**Novel assumption:** The authors introduce an assumption that allows them to reuse previous techniques (shifted divergence) under a milder condition (holder continuous gradient).\n\n**Clarity:** The techniques are clearly explained  for the full batch setting. While I did not check the math exactly, the proofs do follow logically. \n\n**Improved bounds:** The authors provide examples where their bound improves over prior work, even in the already studies (strongly) convex setting. \n\n**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.", "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. \n\n1. 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)\n\n2. 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)\n\n\n3. 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)\n\n4. Minor comments:\n- 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).\n\n- 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. \n\n- 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 :) \n\n- I suggest proofreading for typos. A few are:\n    - Line 106: “differing with one point.” differing by?\n\n    - Fig 2 caption, line 125: “It done by constructing a coupling (G_t, G_t’), resulting a coupled process….”\n\n    - Theorem 3.11 statement “Then the DP-SGD update (1) under without replacement…”\n\n    - Missing parenthesis in Eq. 19.\n\n** Update **\nSee discussion below addressing these weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)