Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness

Q1: Typo in equation (11)

Thanks for the catch! Yes, there is a typo, where there should not be an $\alpha$ in the second term in front of $a_t^2$. No other results are affected though and we will correct it in our revision.

Q2: Why Hölder continuous gradients assumption is appropriate?

We apologize for the confusion. It is unclear if neural networks indeed have Hölder continuous gradients in general. The experiment in Figure 2 (a) only tries to convey the message that a smaller order of Hölder continuous $\lambda$ can potentially lead to a much smaller constant $L$, which in combination gives a better privacy bound. This is in the same spirit as [ref 1], which also assumes the local smoothness assumption and estimates the corresponding constant empirically. It is interesting to investigate what structural property we can leverage for a popular class of neural networks, which is an important future direction. Nevertheless, the Hölder continuous gradient assumption is indeed a generalization of the commonly used smoothness assumption. As a result, we believe our contributions here are still meaningful.

Reference

[ref 1] Why gradient clipping accelerates training: A theoretical justification for adaptivity, Zhang et al., ICLR 2020.

Q5: In Figure 2 (a), what happen when $\lambda \rightarrow 0$?

This is a great question! Note that when $\lambda \rightarrow 0$, the Holder continuous gradient condition says that the gradient difference norm is upper bounded by a constant. This in fact degenerates to the case of standard composition theorem, since the purpose of clipped gradient norm is exactly for such condition. As a result, when $\lambda \rightarrow 0$, the bound will become identical to the Pareto frontier of the standard composition theorem and output perturbation. In our experiment, we did test the case $\lambda < 0.5$ and find that it will become worse whenever $\lambda$ is too small.

W3, Q6: Comparison of Lemma 3.5 and the lemma in Chien et al. 2024.

Thanks for the great comment. Indeed, Lemma 3.5 and Lemma 3.3 in Chien et al. 2024 coincide in the strongly convex setting. However, for the general smooth case that $c>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 $c<1$ the minimum will always be the first term. However, for the general case $c>1$, it is possible that the minimum will be the second term. This happens whenever $(c-1)D_{t-1} > 2\eta K(1-1/n)$. Nevertheless, we agree with the comment of reviewer 8m94 and we will give more credit to Chien et al. 2024 when we mentioned Lemma 3.5.

Q7: Relations to recent related works.

Thanks for the references. These two works are indeed relevant to ours and we will include them in the related works section in our revision. For the work [ref 5], the author 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., Holder continuous gradient) is needed for the reduction lemma type of result. The work [ref 6] studies a different condition where they have a parameter to control the degree of convexity. As mentioned by the author in the public comment above, our results are tighter by roughly a factor of 8 and we study the Holder continuous gradient condition that relaxes the smoothness assumption. We believe both of our works have their own contributions and complement each other.

References

[ref 1] On the quality of first-order approximation of functions with Hölder continuous gradient, Berger et al., JOTA 2020.

[ref 2] Universal gradient methods for convex optimization problems, Yurri Nesterov, Mathematical Programming 2015.

[ref 3] Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization, Guanghui Lan, Mathematical Programming 2015.

[ref 4] Why gradient clipping accelerates training: A theoretical justification for adaptivity, Zhang et al., ICLR 2020.

[ref 5] It’s Our Loss: No Privacy Amplification for Hidden State DP-SGD With Non-Convex Loss. Meenatchi Sundaram Muthu Selva Annamalai, AISec 2024.

[ref 6] Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite losses, Kong et al., Arxiv 2024.

[ref 7] On the Stability of Expressive Positional Encodings for Graphs, Huang et al., ICLR 2024.

W1, Q1: The practical setting of Holder continuous gradient.

Thanks for the great comment. We would like to first emphasize that the condition of Holder continuous gradient is a generalization of the commonly studied smoothness assumption. We agree that there is currently no popular practical setting for the Holder continuous gradient setting that we can think of. Nevertheless, the theoretical optimization community has studied problems with such conditions for a while [ref1-3]. Also, stable positional encoding in the graph learning literature is shown to be Holder continuous [ref 7], albeit it is not the same as the Holder continuous gradient condition. It is interesting to investigate what structural property we can leverage for a popular class of neural networks, which is an important future direction. We believe our work serves as an important first step toward this goal.

W2, Q2: How to compute the bound in the main results? Is it possible to have a closed-form even for a loose bound?

This is a great question. We first answer the question of computation and then comment on the close-form of our results. The computation of the optimization in our main theorems is simple. First note that any (sub-optimal) feasible solutions are valid bounds. As a result, we first fix a choice of $\tau$ and then utilize the minimize function of scipy.optimize in scipy library to solve $\beta$. To optimize for $\tau$, we simply use a binary search. For the smooth setting, this routine is very efficient where Figure 1 (a) can be computed in a few seconds. For the Holder continuous gradient case, computing one point in Figure 2 (a) takes longer but still within a few minutes. Regarding the close-form of our results, note that we can indeed obtain close-form bounds for special cases. For example, if the loss is smooth and convex, we know that the gradient update would be 1-Lipschitz (i.e., $c=1$). This allows us to further simplify the bounds and solve the optimization directly. In fact, this degenerates to the results of Altschuler & Talwar (2022). For general smooth loss cases, we have $c\neq 1$ but a close-form solution is still possible. Unfortunately, the expression is complicated so we do not include it in our manuscript. For non-smooth losses with Holder continuous gradient, the close-form bound is unfortunately intractable. Nevertheless, we agree with reviewer 8m94 that it is possible to have a looser but close-form bound. We will investigate this further in our future work, and we really appreciate the insightful comment. Regarding the comparison to prior works, we believe Figure 1 (b) serves exactly this purpose. Specifically, all bounds in Figure 1 (b) are compared under the same parameter setting.

Q3: Comparison with [AT22]

Thanks for the great comment. Note that the result of Altschuler & Talwar (2022) can be roughly understood as our Theorem 3.1 but without the forward Wasserstein tracking part. This means that the minimum term in equation (3) is replaced by $D^2$. Roughly speaking, whenever the minimum term in our equation (3) not happening at $D$ (i.e., $2\eta K/n (1-c^\tau)/(1-c)< D$), our bound will be better. Notably, the original result of Altschuler & Talwar (2022) is even worse since they simply choose a specific sub-optimal shift allocation of $a_t$ (i.e., $a_t = 0$ for all $t<T$ and $a_{T-1} = c^{T-\tau}D$. For simplicity, we have neglected this effect and adopted the optimal shift allocation for them in the discussion above and Figure 1 (a).

Q4: Question about Figure 2 (a)

Sorry for the confusion. The experiment in Figure 2 (a) only tries to convey the message that a smaller order of Hölder continuous $\lambda$ can potentially lead to a much smaller constant $L$, which in combination gives a better privacy bound. This is in the same spirit as [ref 4], which also assumes the local smoothness assumption and estimates the corresponding constant empirically. That being said, we are not asserting that the neural network indeed has Holder continuous gradients and our estimated constant serves as a valid upper bound. We will try to make it clear in our revision. Please let us know if you have further questions on how this experiment is done. We are happy to answer it as soon as possible.

We thank reviewer WAgt for their positive assessment of our theoretical contribution and valuable feedback. We address the proposed questions and weaknesses below.

Q1: Comparison with non-private results

Thanks for the suggestion. Our work currently focuses on the analysis of the privacy bound of the noisy SGD algorithm. Since non-private counterparts do not have privacy bounds, we do not think it is possible to make such a comparison from the privacy aspect. Nevertheless, we conjecture the reviewer WAgt might indicate the comparison of the other aspects, such as the utility bound. For smooth strongly convex losses, the formal utility bound for noisy SGD can be adapted from Chourasia et al. 2021. We will add it to our revision.

Q2: Simplified privacy bound for the main results

We agree. We have tried hard to further simplify it but unfortunately, we could not find a close-form solution for general cases. As we mentioned in response to Q2 of reviewer rdb2, there is indeed a special case (i.e., smooth convex loss) where the closed-form bound is available. We feel that it would be hard to get a tight close-form solution in general but it is possible to have a close-form sub-optimal bound. On the other hand, we want to mention that many current state-of-the-art privacy accounting also do not have close-form bounds and rely on numerical computations, such as the seminal work of Gopi et al. 2021. Making the privacy bound as tight as possible, including the constants, is of significant importance in DP practice. This is also the reason why we keep the tightest possible computable privacy bound as our main theorems.

Q3: Challenges in removing smoothness and convexity assumptions.

This is a great question. Firstly, although we do not prove it, if there is no assumption on the loss function, there will not be any reduction lemma pertaining to the gradient update in the worst-case scenario. As a result, we need some continuity of the gradient update $\psi$ for a non-trivial privacy bound compared to output perturbation asymptotically. In this work, we choose Holder continuous gradient as such assumption but other assumptions of similar spirit can be adopted.

Regarding the difficulty of removing the convexity assumption, the key is to observe that in Theorem 3.1, even for the non-convex case so that $c>1$, we still have a non-trivial privacy bound. Note that when $c>1$, the gradient update map $\psi$ is not a contraction mapping anymore. For relaxing the smoothness assumption, the key is to prove the reduction lemma pertaining to $\psi$ without smoothness as in our Lemma 3.7. Please also check lines 140-154 for a more thorough discussion.

Q4: Lower bound aspect

This is a great question. Note that in the special case where the loss is smooth and convex, our results degenerate to the bound in Altschuler & Talwar (2022), which is proven to be tight up to a constant. We conjecture a similar worst-case construction to Altschuler & Talwar (2022) can be adapted to our general settings and prove the corresponding tight lower bound, which we left as a future work.

W1: Typos and Figure quality

We appreciate the catch and suggestions. We will correct and improve them in our revision.

W2: Unclear structure and clarity

As mentioned by the reviewer WAgt, we have a lot of results for different cases and scenarios. Due to the space limit, we decide to only put the full “sketch of proof” of the simplest case in the main text. Nevertheless, we believe it captures most of the key ideas of the proofs of more complex cases. We also believe it is the most accessible one for the general audience, and leave more complex and technical details in the Appendix for the experts.

We thank reviewer rdb2 for their positive comments and valuable feedback. We address the proposed questions and weaknesses below.

Q1: Questions about inequalities in lines 297-305.

Yes, reviewer rdb2 understands it correctly. The analysis in lines 297-305 is conditioned on $Z_{\tau:T-1}=Z_{\tau:T-1}^\prime$, which is the same as in Altschuler & Talwar (2022).

Regarding the details of inequality (b) and their relation to Lemma 3.2, 3.3, we first apply the shift reduction lemma (Lemma 3.2) to turn the noise $Y_{T-1}$ in the Renyi divergence to an additive term in inequality (b). Note that there is no assumption needed at this step, since by our choice that $a_t\geq 0$ and $Y_{T-1}$ is indeed Gaussian noise. Then we apply Lemma 3.3, which removes the map $\psi$ in the Renyi divergence. Note that in this step, we need the map $\psi$ to be $c$-Lipschitz, where from Lemma 3.4 we know that the gradient update $\psi$ is indeed $c$-Lipschitz with $c$ depending on the assumptions on the loss. As a result, Lemma 3.2 add $a_{T-1}$ to the shift and Lemma 3.3 scale it by $c^{-1}$. In summary, condition on the event $Z_{\tau:T-1}=Z_{\tau:T-1}^\prime$, as long as the gradient update map $\psi$ is $c$-Lipschitz the inequality (b) will hold.

Q2: Can the bounds presented be computed exactly or do we need numerical approximations to realize them?

This is a great question. For the simple special case such as convex loss with proper step size, from Lemma 3.4 we know that the gradient update $\psi$ is 1-Lipschitz. In this case, a closed-form solution of Theorem 3.1 can be obtained, which is in fact the result of Altschuler & Talwar (2022). For general smooth loss cases, we have $c\neq 1$ but a closed-form solution is still possible. Unfortunately, the expression is complicated so we do not include it in our manuscript. For non-smooth losses with Holder continuous gradient, the close-form bound is unfortunately intractable. Nevertheless, we would like to emphasize that the optimization in both Theorem 3.1, 3.6, and 3.11 are for the purpose of best possible privacy bound. In fact, any sub-optimal feasible solution still gives a valid privacy bound (although looser), which is different from the situation of common privacy accounting for $(\epsilon,\delta)$. It is an interesting direction to further investigate close-form (suboptimal) solutions of both Theorem 3.1, 3.6, and 3.11.

W1: Main theorems are not in close-form and hard to operationalize.

We agree. We have tried hard to further simplify it but unfortunately, we could not find a close-form solution for general cases. As we mentioned in the response to Q2, there is indeed a special case (i.e., smooth convex loss) where the closed-form bound is available. We feel that it would be hard to get the tight close-form solution in general but it is possible to have a close-form sub-optimal bound. On the other hand, we want to mention that many current state-of-the-art privacy accounting also do not have close-form bounds and rely on numerical computations, such as the seminal work Gopi et al. 2021. Making the privacy bound as tight as possible, including the constants, is of significant importance in DP practice. This is also the reason why we keep the tightest possible computable privacy bound as our main theorems.

W2: Computational complexity of the bound should be discussed.

Thanks for the great comment. We will add it to our revision. To get a feeling, any point in Figure 1 (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 a few minutes in general. Compared to the training time of modern ML models this should be negligible.

W3: Did not compare to Chourasia et al. 2021 for the smooth strongly convex case.

Note that as mentioned by Ye & Shokri (2022), specifically in their Appendix D.7, their bound is tighter than Chourasia et al. 2021 for the smooth strongly convex case. We have compared with Ye & Shokri (2022) as in Figure 1 (a) and we think it is sufficient, where we have cited Chourasia et al. 2021 in the related work section as well.

W4: No utility bound

This is a great comment. Indeed, it would be great to have a delegate utility bound analysis. Unfortunately, this is hard in general to the best of our knowledge. For simpler special cases such as smooth strongly convex losses, the corresponding utility results can be adapted from Chourasia et al. 2021. We will add it to our revision and discuss the lower bound aspect [1].

Hi Weiwei Kong

Thanks for introducing your concurrent work and a comparison. We believe both of our works have their own contributions and complement each other. In addition to the difference in the problem setting and assumptions used, we would like to add more details on the tightness aspect to compare our privacy bound. We believe this will also help reviewers and post readers understand our works' differences.

Comparison to output perturbation bound.

As we have shown in our Figure 1 (a), our privacy bound can be strictly and significantly better than the output perturbation bound, which is $\frac{\alpha D^2}{2\sigma^2}$, where $D$ is the domain diameter, $\sigma^2$ is the noise variance and $\alpha$ is the parameter in $\alpha$ Renyi divergence. In the meanwhile, from the main theorem (i.e., Theorem 4.3) of Kong, W., & Ribero, M. (2024), we can see that their bound is $\frac{\alpha}{2\sigma^2}(C_1 D + C_2)^2$ for some problem-dependent constant $C_1>1$ and $C_2>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 $n$ grows.

Intuitively, a larger dataset size $n$ should lead to smaller privacy loss for DP-SGD, since only one out of $n$ 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 to the bound of Altschuler & Talwar (2022), which also exhibits this behavior. That is, as $n\rightarrow\infty$ the privacy loss goes to $0$. In contrast, The main theorem (i.e., Theorem 4.3) of Kong, W., & Ribero, M. (2024) gives a bound $\frac{\alpha}{2\sigma^2}(C_1 D)^2$ in the full-batch setting when $n=b \rightarrow \infty$ for some problem-dependent constant $C_1>1$ independent of $n$. Apparently, this bound does not decay to $0$ which is significantly different from our bound and bound in Altschuler & Talwar (2022).

Nevertheless, we emphasize that there are still scenarios where the result of Kong, W., & Ribero, M. (2024) is preferable. Like what Weiwei mentioned in their post, they can deal with clipped gradients without assuming the loss to be Lipschitz and they have a characterization of the different degrees of convexity in their bound (i.e., $C_1$). We will cite the work and add the discussion above to our revision. Really appreciate your introduction to your work!