Differentially Private Network Training under Hidden State Assumption

Thanks for your detailed reading and problems, we are willing to answer it one by one:

1. The proof of Theorem A.2 The proof of Theorem A.2 is not a step-by-step copy, although we have mentioned that it is an extension of Ye and Shokri’s Lemma 3.1 in line 314. For Theorem 4.2, we consider the proximal gradient descent with adaptive calibrated noise. Therefore, we have two pushforward functions and per iteration adaptive Gaussian noise $o(\eta,k,j)$(line 705). More specifically, although we follow the basic framework as mentioned in line 314, the proof details are different from Equation (17). For the integrity of the work, we feel it necessary to put the full proof of Theorem A.2 in the appendix.

**2. The proof of Corollary 4.4 **

The proof of Corollary 4.4 basically follows the proof of Ye and Shokri (2022, Lemma 3.2), so we omit this part. We realize that in the original text, we inadvertently overlooked the explanation for the omission of corollary 4.4’s proof. We have rectified this problem in the updated version line 325.

3. The difference between Ye and Shokri in Corollary 5.3 and the order of RDP and the value of $L_T$ in Figure 2.

This answer elucidates the difference between the parameter $\lambda$ as delineated in Ye and Shokri, and our paper's $L_T$. The disparities in privacy loss analysis between our works and Ye and Shokri’s work that reviewer concerns will be answered in the response to the next question (4b), where corresponding numerical comparison is also presented.

First, the effect of $\lambda$ in Ye & Shokri and $L_T$ in our work is different. $\lambda > 0$ is necessary in the framework of Ye & Shokri and they use $\lambda > 0$ as the coefficient of the $l_2$ regularization term to ensure that the overall loss objective function is strongly convex (See Equation (7) in Ye & Shokri). By contrast, the regularization term in our framework is optional. When there is no regularization, we can simply let $L_T = 1$ and our method still works. In addition, our framework supports any regularization term, as long as it is convex (in contrast to strongly-convex required in Ye & Shokri), which means our framework includes more regularization schemes such as lasso. Fundamentally, we can obtain feasible privacy loss under the hidden state assumption because the update rules mapping the old parameters to the new parameters (e.g. function $T$ and $F$ in Equation (9)) have bounded Lipschitz constants. Such bounded Lipschitz constants are achieved in different ways in Ye & Shokri and our framework. In Ye & Shokri, it is achieved by introducing an $l_2$ regularization scheme to make the loss function of regularized logistic regression strongly convex (See Equation (7) in Ye & Shokri). By contrast, we decompose deep neural network training into several sub-problems and each of these sub-problems have a convex loss function, this guarantees the bounded Lipschitz constant for the update rule (See Lemma 4.1 of our work which bounds $L_F$). The regularization scheme is optional and more generic in our framework. We discuss the regularization terms in line 304 to 308 to demonstrate our framework is generally applicable. In a nutshell, both Ye & Shokri and our work manage to bound the Lipschitz constant of the update rule so that we can have a tight privacy loss estimation under the hidden state assumption, but the techniques used in our work to achieve Lipschitz bound are totally different from Ye & Shokri

In Figure 2, the RDP order is $\alpha = 100$ and $L_T=1$. We clarify this in our revised manuscript. This again reflects that our framework is more generic regarding the regularization scheme. Our framework supports no regularization and any convex regularization (the value of $L_T$ for some examples are discussed in the paragraph from line 304 to 308), while Ye & Shokri requires an $l_2$ regularization term.

Thank you for the replies! You wrote:

Thanks for your question. As shown in our paper Figure 1(Left) and Ye and Shokri’s paper Figure 1, the privacy loss under the hidden state assumption (HSA) is dramatically smaller than the composition theorem when the number of iterations $K$ is large. Conversely, under an equivalent privacy loss, the HSA requires much smaller calibrated noise. Given that calibrated noise is one of the key factors for utility degradation, the utility under the HSA can dramatically increase.

I agree the DP guarantees can get much smaller, but in Ye and Shokri’s analysis this requires such a strong L2-regularization, that it is very difficult to beat the privacy-utility of DP-SGD. Recently, Bok et al. (Bok, Jinho, Weijie J. Su, and Jason Altschuler. "Shifted Interpolation for Differential Privacy." ICML 2024) gave bounds in the hidden state analysis that are lower than those of Ye and Shokri. And their experiments on logistic regression already show that it is very difficult to beat the privacy-utility of DP-SGD

You also write:

Furthermore, we realize that carefully comparing the RDP bound between ours and Ye and Shokri’s work needs to analyze the dynamics of privacy loss w.r.t different hyperparameters, such as the learning rate, number of batches, which is not the main topic of this paper. In this paper, we mainly aim to derive the privacy loss bound for neural networks under the hidden state assumption

If I understand correctly from your replies, you haven't really carried out hyperparameter tuning for various methods. This might explain why DP-SGD's experimental results are so bad.

I still think the idea is interesting, but also I still don't see why the method would be better than DP-SGD. I do not yet see convincing evidence for that, especially due to the fact that there are no experiments showing this.

Also, if you look at the y-axis in Appendix Fig. 4, the differences are very small. The L2-regularization constant needed for Cor. 5.3 of Ye and Shokri seems to be missing.

Thanks for your question, As for the weakness part, we would like to answer your questions one by one:

1. How to compare with classical DP-SGD in terms of privacy and utility?

Our paper’s privacy loss analysis considers the hidden state assumption, which assumes that the intermediate states are hidden to adversaries. Previous work [1,2,3] shows that privacy loss under this assumption has some benign results such as smaller and converged privacy loss. However, these nice properties cannot be applied to neural network training using existing works, because these works require a strongly convex loss function. In order to obtain a tighter privacy loss estimation under the hidden state assumption for neural network training, we propose DP-SBCD algorithm and the corresponding privacy loss accountant in this paper.

Since there is no privacy loss accountant method for DP-SGD designed specifically for the hidden state assumption, when comparing the privacy and utility with our method, we have to use composition theorem to derive the privacy loss for DP-SGD. In this context, we provide the utility under the same privacy loss in Table 2 of Appendix B.2. Intuitively speaking, based on Corollary 4.4, the privacy loss for our algorithm under the hidden state assumption increases only once for each epoch and decreases for the rest iterations. The tight privacy loss accountant confers an advantage for DP-SBCD over DP-SGD in terms of utility with the same privacy loss.

On the other hand, as we discussed in line 468 to 476, directly comparing the privacy loss under two different assumptions and two different types of algorithms is unfair since these two kinds of algorithms share different hyper-parameters such as learning rate, batch size, which directly contribute to the privacy loss. In this regard, it is necessary but challenging to derive a tight privacy loss estimation method for DP-SGD under the hidden state assumption, which is, however, out of this paper’s scope and left as future works. The contribution of our paper is that we first solve an important but challenging problem, i.e., the privacy accountant under the hidden state assumption, in the context of deep neural networks.

2. The relaxation from a non-convex to a convex problem in the proposed method could impact utility. How does the utility of the proposed method compare to DP-SGD, especially in terms of balancing privacy and performance

The relaxation from a non-convex to a convex problem does not necessarily impact the utility. The reason why our algorithm could improve the utility compared with the DP-SGD is because our algorithm applies the privacy loss accountant under the hidden state assumption. As we explained above, our algorithm requires smaller calibrated noise compared with DP-SGD whose privacy loss is calculated by composition theorem under the same privacy budget. That’s the reason why our experiments in Table 2 of Appendix B.1 show that our algorithm provides better utility compared to DP-SGD.

3. Whether the relaxation to a sub-convex problem offers distinct privacy advantages or if it primarily facilitates privacy analysis?

We are not sure whether the relaxation to sub-problem offers distinct privacy advantages or not because it is out of the scope of this work. The DP guarantees now are always based on privacy analysis rather than employing the DP guaranteed model to different attack methods such as membership inference attack. Generally speaking, the failure rate of membership inference attacks and differential privacy guarantees indicate the upper bound and the lower bound of privacy, respectively. The exact privacy of a mechanism is usually intractable due to its complexity, and our work aims to derive a tight lower bound of privacy. Intuitively speaking, we think the coordinate descent type of method offers distinct privacy advantages because we do not calculate the gradient w.r.t all parameters. Moreover, our algorithm does facilitate privacy analysis because each subproblem is convex, which provides a guaranteed bound of the Lipschitz constant $L_F$ of the update scheme function.

As for questions, thanks for your comment, the typos mentioned have been fixed in the updated version.

[1] Ye J, Shokri R. Differentially private learning needs hidden state (or much faster convergence)[J]. Advances in Neural Information Processing Systems, 2022, 35: 703-715.

[2]Feldman V, Mironov I, Talwar K, et al. Privacy amplification by iteration[C]//2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018: 521-532.

[3]Chourasia R, Ye J, Shokri R. Differential privacy dynamics of langevin diffusion and noisy gradient descent[J]. Advances in Neural Information Processing Systems, 2021, 34: 14771-14781.

Thank for your response. The main contribution appears to be the application of block gradient descent to transform the original problem into a sub-optimal convex problem, enabling the use of standard privacy analysis techniques. While the idea is new, it does not strike me as particularly compelling. Shokri's work, which employs Langevin diffusion to trace the distribution of perturbed data, could potentially be applied to the sub-optimal convex problem as well. I will raise my score since the idea is new, though I am not entirely confident in my assessment. Overall, the approach does not feel particularly innovative to me.

Thanks for your comments and questions! Below are our point-to-point responses:

As for the weakness:

Typically, neural network training requires many iterations to obtain a well-trained model. Considering the common practice of only saving the final model checkpoints, the privacy loss derived by the composition theorem will be significantly overestimated when we have many iterations during training. We agree that DP-SGD is more generally applicable, but there is no tight privacy loss estimation method for DP-SGD and non-convex loss functions specifically designed for the hidden state assumption so far. That is to say, for DP-SGD and non-convex loss functions, we have to use the composition theorem to obtain the over-pessimistic privacy loss, which becomes infeasible for large numbers of iterations. To derive a tight privacy loss estimation for DP-SGD and non-convex loss function under the hidden state assumption will be an important future work.`

As for the complexity:

For time complexity: For one epoch, coordinate descent algorithms share the same time complexity as gradient descent. However, the DP-SGD requires per-sample gradient clipping, which requires the use of back-propagation for each sample. Our algorithm only clips the auxiliary variable $x_d$. Hence, our algorithm outperforms the DP-SGD in time complexity, especially under a large batch size.

For memory complexity: Coordinate descent is designed to provide a memory-friend algorithm in solving large scale problems. For each iteration, our algorithm only updates one layer with one-layer back-propagation. But the DP-SGD requires updating all parameters with the whole-layer back-propagation. Hence, our algorithm is more memory efficient as well.

Thanks for your constructive comments, we answer your questions one by one:

1. For a series of problems related to the LSI, we would like to first review the previous papers and introduce why we requires LSI constant:

The mathematical definition of the LSI is demonstrated in Definition A.1 of Appendix A.4 (line 697 - 701). The LSI assumption is related to the distribution of the parameter space and is independent of the loss function. The LSI is a very mild assumption since strongly logconcave distributions, such as Gaussian distribution and uniform distribution, satisfy the LSI assumption. Moreover, [1] indicates that the LSI can also be satisfied by some non-logconcave distributions.Then, we would like to answer the sub-questions one by one:

a) Yes, the LSI is an additional assumption.

b) The constant in Line 350 is the LSI constant $c$ with the detailed definition in Equation (13) in Definition A.1 of Appendix A.4 (line 697 - 701). Based on Equation (4) in [1], the LSI constant of a distribution $\mu$ is related to the lower bound of the ratio of the KL divergence and relative Fisher information for any other distribution $\rho$. For strongly logconcave distribution $\mu$, if $- \log \mu$ is $c$-strongly convex, then $\mu$ satisfies LSI with constant $c$. For example, the tightest LSI constant for standard Gaussian distribution is $1$. In our analysis, the LSI constant of the parameter distribution is calculated in Lemma A.3 in Appendix A.5, it helps us to bound the gradient of the Renyi divergence and thus the privacy loss. Specially, we initialize the LSI constant as $0$ in the beginning in line 854. It is because we consider the $\nu$, which is the distribution for the adjacent dataset $D’$, as the other distribution in the definition of LSI. Therefore, in the initialization point, the two distributions are the same. Hence, the $c_0^0=\infty$ based on Equation (4) in [1]. The same initialization has also been used by [2].

c) The strongly convexity assumption in previous work [2] means the loss objective is a strongly convex function w.r.t. parameters. while the LSI assumes the distribution of parameters, which are totally different and independent. As mentioned above, the LSI is a mild condition on parameters; it can be easily satisfied if we initialize the parameter with Gaussian distribution or uniform distribution, which are the most popular initialization schemes.

d) As we mentioned above, the LSI is a very mild assumption on the distribution of parameter space. Moreover, the parameter is initialized i.i.d. Hence, the subproblems also satisfy the LSI assumption. We realize that our paper should provide more details about the LSI assumption; we have improved this part in the revised version (from line 312 to line 315) .

2. What causes the fluctuations in the unseen privacy loss shown by the dashed green and red lines in Figure 1 (right)?

Corollary 4.4 shows that for each epoch, the privacy loss will increase once when $i_0 \in B_k^j$ and decrease otherwise. Figure 1 graphically represents this dynamic behavior. The distinct colors employed in the figure correspond to different values of $i_0$ as delineated in Corollary 4.4. Moreover, as indicated in line 934 to 942, the final privacy loss would be the average over different cases of $i_0$, which will be smoother than the red/green dash lines in Figure1(right).

3. For the sentence "Otherwise, the privacy loss will increase exponentially" in Lines 78-79? Are the authors referring to DP-SGD or other methods in this statement? I.e., the DP-SGD leads to exponentially increasing privacy loss in settings that are not strongly convex or smooth?

Sorry for the confusing statement. In Lines 78-79, we intend to point out that the privacy loss of DP-SGD under the hidden state assumption will exponentially increase if we follow the same analysis framework as in [2]. It does not mean that the actual privacy loss of the DP-SGD would increase exponentially. I have clarified this in our revised manuscript (line 79).

When the loss function is non-convex, the Lipschitz constant of the update scheme (i.e., $L_F$ in our analysis) will be larger than 1. The privacy loss derived in the framework of [2] will thus increase exponentially with the number of update iterations.

[1] Vempala S, Wibisono A. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices[J]. Advances in neural information processing systems, 2019, 32.

[2] Ye J, Shokri R. Differentially private learning needs hidden state (or much faster convergence)[J]. Advances in Neural Information Processing Systems, 2022, 35: 703-715.