HEPrune: Fast Private Training of Deep Neural Networks With Encrypted Data Pruning

We thank Reviewer ADwT for his/her thorough reading of the manuscript and constructive comments.

Q1 Clarity and consistency

We thank the reviewer for the thorough reading. We will fix the typos in the future version.

Q2 The overhead of the proposed methods

The results in Section 4.2 include the running time for HE-based data pruning. The proposed data pruning mainly contains (1) computing the HEFS score and (2) performing ciphertext-wise pruning. We show the proportion of the proposed methods of total runtime in Table 2(rebuttal pdf).

We first benchmark the runtime of basic HE operations in our environment: addition:8ms, ciphertext-plaintext multiplication (cpMult):17ms, rotation:116ms, ciphertext-ciphertext multiplication (ccMult):146ms, max:1.37s and bootstrapping:35.89s.

HEFS. The proposed HEFS does not rely on the gradients. Instead, HEFS can be computed via the error vector as shown in the Equation (2). To compute HEFS, we only need subtraction, max and the rotation operation. Computing HEFS on a single ciphertext takes 1.72~1.84s.

Ciphertext-wise Pruning. While rotation is not fast compared with addition and cpMult, it is still faster than the ccMult in the CKKS scheme. Moreover, the rotation barely consumes the noise budget [1]. We remark that the non-linear SoftMax function is computed via approximation, which also relies on ccMult. The intensive evaluation of the ccMult in the forward pass and back propagation leads to frequent bootstrapping, which is the most expensive operation in practice.

In the worst case, the ciphertext-wise pruning needs $O(p(1-p)N)$ rotations, where $N$ is the number of total data samples and $p$ the pruning ratio. Take the CIFAR-10 dataset for an example. We choose a batch size of 128, and the 43750 training data samples are encrypted in 342 ciphertext blocks. When the pruning ratio is 99%, the ciphertext-wise pruning needs at most 430 rotations to combine the 342 sparse ciphertext blocks into 4 dense ones, which takes 0.04h. In contrast, evaluating one epoch without pruning takes more than 20h.

We remark that the main bottleneck of private training remains to be the evaluation of complex non-linear functions like the SoftMax function and the bootstrapping. We believe that optimizing these operations could further accelerate private training. This is orthogonal to the optimizations discussed in this paper.

Q3 The effectiveness of the proposed HEFS.

In Figure 2(rebuttal pdf), we compare HEFS with (1) the square of the EL2N score; (2) randomly dropping ciphertexts. However, these two methods yield inferior efficiency / utility trade off compared with the proposed HEFS.

The square of EL2N. The HEFS generally has a better accuracy than the squared EL2N. HEFS outperforms the squared EL2N by a noticeable margin when the pruning ratio is high, i.e., the remaining data is below 0.2. This is because the squared EL2N score enlarges the importance of samples that are predicted wrong. These samples can be noisy samples [2]. Emphasizing these samples too much makes the selected data less informative, which leads to an inferior accuracy. As the pruning ratio goes down, the proportion of such noisy samples decreases. Accordingly, the performance of the squared EL2N becomes closer to HEFS. In Table 1(rebuttal pdf), we show that computing the score is not the bottleneck and the savings from using the squared EL2N is marginal.

Random pruning. While random pruning strategy is simple, it ignores the importance of data samples. This leads to significant deterioration of accuracy, especially when the remaining fraction is low.

Q4 The novelty and the significance.

To the best of our knowledge, we are the first to explore encrypted data pruning to accelerate private training. Performing data pruning in the encrypted state is non-trivial. Directly adapting plaintext pruning methods is not viable. To start with, the importance score in the plaintext often involves complex nonlinear functions that are expensive in HE. Moreover, sorting samples are considered free in plaintext, but sorting in the encrypted state is expensive. Most importantly, the sample-wise pruning in plaintext leads to sparse ciphertexts and fails to effectively accelerate private training. We propose a series of HE-aware optimizations including HEFS, client aided masking and ciphertext-wise pruning. Our methods boost the efficiency of private training significantly without sacrificing accuracy.

Moreover, we would like to remark that EL2N has been treated as a static data pruning method. Prior works have assumed either that it remains unclear if EL2N reduces the total training time [3] or that EL2N cannot be used to accelerate training [4]. In this work, we innovatively adapt it to the dynamic data pruning setting and show its effectiveness.

Q5 The non-interactivity of HE

Private training with the proposed encrypted data pruning remains largely non-interactive compared with the MPC-based methods. This is because all HE computation is performed solely by the server. The client is only required to be online for less than 0.1% of the total training time, to handle the early stop signal and pruning mask. As shown in prior works like HETAL, these communications are both secure and necessary.

To sum up, we show that the squared EL2N and randomly pruning are less effective than the proposed HEFS. Additionally, the proposed HEFS and ciphertext-wise pruning are efficient at runtime. We sincerely hope our responses have addressed the reviewer's concerns.

Reference

[1] Bossuat, Jean-Philippe, et al. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys.

[2] Paul, Mansheej, et al. Deep learning on a data diet: Finding important examples early in training.

[3] Truong, Thao Nguyen, et al. KAKURENBO: adaptively hiding samples in deep neural network training.

[4] Qin, Ziheng, et al. Infobatch: Lossless training speed up by unbiased dynamic data pruning.

We sincerely appreciate the reviewer's thoughtful feedback and are grateful for the increased score. Thank you for your consideration and support.

We thank Reviewer ADwT for his/her thorough reading of the manuscript and constructive comments.

Q1 The effectiveness of HEFS

The proposed HE-friendly score relies on the observation that the importance of a data sample can be quantified by its gradients [1]. We denote the input vector as $x\in\mathbb{R}^d$ where $d$ is the input dimension and the one-hot label as $y\in \{0,1\}^K$ where $K$ is the number of class. We denote the logit outputs of the model as $f(x;w)$ and the prediction vector as $p(x;w)=\sigma(f(x;w))$, where $\sigma(\cdot)$ is the SoftMax function. We denote the cross-entropy loss as $\ell(p,y)=\sum_{i=0}^{K-1}y^{(i)}\log p^{(i)}$.

We denote a minibatch of $B$ samples as $S=\{(x_i,y_i)\}_{i=0}^{B-1}$.

We denote a single sample's gradient to the weights at time $t$ as $g_t(x,y)=\nabla_{w_t}\ell(p,y)$. The change of a sample's contribution to training at time $t$ can be quantified by the time derivative of the loss on the sample, i.e., $\Delta_t((x,y), S)= -\frac{d \ell(p,y)}{dt}$. Accordingly, we can evaluate the importance of some data sample $(x_k,y_k) \in S$ by investigating how removing the $(x_k,y_k)$ from the minibatch change the loss of other samples. The impact of removing the sample $(x_k,y_k)$ is bounded by its gradients. More formally, for $\forall (x_i,y_i)\in S$ where $i\neq k$, we have: $\| \Delta_t((x_i, y_i), S) - \Delta_t((x_i, y_i), S_{\neg k}) \|_2 \leq c \| g_t(x_k, y_k) \|_2 \cdots (1)$

We provide a proof of the correctness of the Equation (1) as follows. By the chain rule, we have $\Delta_t((x_i, y_i), S) = -\frac{d \ell(p,y_i)}{dt} = -\frac{d \ell(p,y_i)}{dw_t}\frac{dw_t}{dt}$. When the weights are updated via SGD, we have $\frac{dw_t}{dt}=-\eta\sum_{(x_j,y_j)\in S}g_t(x_j,y_j)$ where $\eta$ is the learning rate. Accordingly, the change of the loss of the sample $(x_i,y_i)$ is $-\frac{d \ell(p,y_i)}{dw_t}\cdot\eta\sum_{(x_j,y_j)\in S}g_t(x_j,y_j) + \frac{d \ell(p,y_i)}{dw_t}\cdot\eta\sum_{(x_j,y_j)\in S_{\neg k}}g_t(x_j,y_j) = \eta\frac{d \ell(p,y_i)}{dw_t}g_t(x_k, y_k)$. By the submultiplicative property of norms, we have $\| \Delta_t((x_i, y_i), S) - \Delta_t((x_i, y_i), S_{\neg k}) \|_2 \leq \eta \| \frac{d \ell(p,y_i)}{dw_t} \|_2 \| g_t(x_k, y_k) \|_2$. Since $\eta$ and $\frac{d \ell(p,y_i)}{dw_t}$ is independent of $k$, we can set $\eta \| \frac{d \ell(p,y_i)}{dw_t} \|_2$ as a constant $c$. Thus, we have proved the correctness of the Equation (1).

The above bound can be simplified. Specifically, by the chain rule, we have $g_t(x,y)=\frac{d \ell(p,y)}{d f}\frac{d f}{d w_t}$. Given the number of class $K$, the bound can be written in the logit-wise form as $\sum_{i=0}^{K-1}\| \nabla_{f^{(i)}}\ell(p,y)^T\nabla_{w_t}f^{(i)}(x;w_t) \|_2$.

Under the cross entropy loss, the derivative with respect to the $i$-th logit is $p(x;w_t)^{(i)}-y$. It was observed that logit gradients $\{\nabla_{w_t}f^{(i)}(x;w_t)\}_{i=0}^{K-1}$ are generally orthogonal among classes [2,3]. Thus, the bound can be simplified as $\| p(x;w_t)-y \|_2$, which is the EL2N score.

The proposed HEFS further simplifies the computation as the $\ell_1$-norm of the error vector. We observe that the $\ell_1$-norm of the error vector has identical properties as the $\ell_2$-norm. If a sample's prediction vector is largely similar to the label vector, it will have both a small EL2N score and a HEFS score. This indicates that the sample is easier to learn and less informative for the training process. Our experiments also supports our analysis. HEFS can effectively select informative data samples to accelerate training without compromising the accuracy. Additionally, while computing the square root in EL2N is expensive in HE, HEFS can be computed in HE much more efficiently.

Q2 Why encrypted data pruning is challenging

While the idea of leveraging data pruning to accelerate the private training seems straightforward, we note that encrypted data pruning differs from data pruning in the plaintext in several key aspects.

Computing these metrics such as the entropy loss and the $\ell_2$-norm is considered as free in the plaintext. However, evaluating the complex non-linear functions in HE is non-trivial. Evaluating a single square root function on a ciphertext can take up to 2 minutes. This implies that simple metrics like EL2N could negate the benefits of data pruning. We highlight that HEFS rely solely on the prediction vector and the label vector, which are directly available from the private training process. Evaluating the HEFS score only requires subtraction, max and the rotation operation, which takes only 1.72~1.84s for one ciphertext.

Another key difference is that removing the less important data samples directly reduce the computation overhead of training in the plaintext. However, merely excluding the less important data samples does not effectively reduce the overhead of private training. This is because the runtime of private training is determined by the number of ciphertexts, and one ciphertext can contain multiple data samples. Performing sample-wise data pruning leads to a large number of sparse ciphertext. We introduce ciphertext-wise data pruning to effectively reduce the number of ciphertext and boost the efficiency of private training.

The proposed data pruning methods are lightweight, taking only as little as 0.4%~2.5% total runtime, while effectively accelerating private training. We believe this work enables more practical private training in real-world. We thank the reviewer's suggestions and will incorporate the detailed analysis of HEFS in the future version for better clarity.

Reference

[1] Paul, Mansheej, et al. Deep learning on a data diet: Finding important examples early in training.

[2] Fort, Stanislav, et al. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel.

[3] Fort, Stanislav, et al. Emergent properties of the local geometry of neural loss landscapes.

Q1 Clarification on the threat model

We would like to clarify some misunderstandings about the privacy threats this paper focuses on. The proposed method protects both the data privacy and the model privacy. In our threat model, both training data and the model weights belong to the client. The client does not have adequate resource or knowledge for training and outsources the training task to the server. Neither the training data nor the model weights are revealed to the server at any time. All the intermediate features and gradients are also encrypted and protected by HE. This threat model is commonly used in private training works [1].

Weakness 1. Since the model belongs to the client, it is reasonable that the client can decrypt the model. Additionally, we note that the client does not need to send the decrypted model to the server. Since the model is already well-trained, the client can keep it for local use. Alternatively, if the client requires the server to provide private inference service on the trained model, it is possible to store the encrypted final model on the server side.

Weakness 2. As mentioned above, the model does not belong to the server and is not publicly available.

Weakness 3. As mentioned above, the goal and privacy threats are different from those in federal leaning. In our threat model, the client outsources the training task to the server because the client does not have enough resource or knowledge for training. In the meantime, the gradients are encrypted and not revealed to the server. Federal learning typically needs local training on the client side and does not directly protect the gradients.

Q2 The security of the pruning mask

(1) Unencrypted mask. In response to weakness 5, we explain why client aided masking is secure and reasonable. As explained above, the both the data and the model belong to the client. Therefore, revealing the mask to the client does not pose security risk against the data privacy or model privacy. In our client aided masking algorithm, the importance score is revealed to the client. The client performs a quick selection algorithm to find the score threshold and generate a pruning mask. This happens in the unencrypted state on the client side.

During the client aided masking and ciphertext-wise pruning, the plaintext pruning mask is revealed to the server to enhance the efficiency of data pruning on the server side. The server does learn the sparsity information of the training dataset implied by the pruning mask. However, since all the training data and model weights are strictly encrypted on the server side, the privacy of client's data and model is still protected. Similar to prior works [1], we allow revealing necessary meta information about training like the the size of the dataset or ciphertexts, the early stop signal and the pruning mask. Sharing these information does not pose direct security risk against the client’s data privacy or model privacy.

(2) Encrypted mask. We explain how the server can remove unimportant samples using encrypted mask without client aided masking. Performing data pruning without the client's aid and via an encrypted mask is possible. The server can first compute the importance score in the encrypted state and generate the encrypted pruning mask as shown in Algorithm 1. With the encrypted pruning mask, the serve can make the slots of unimportant samples empty via homomorphic multiplication and generate sparse ciphertexts. However, since the mask is encrypted, the server cannot learn which samples should be pruned. The server cannot merge the sparse ciphertexts via rotation either. This is because the sparsity of each ciphertext remains unknown to the server, and the server can not determine how to rotate each ciphertext to create pruned ciphertexts. Therefore, while data pruning with encrypted mask is possible, it incurs prohibitive overhead during homomorphic sorting in practice and is barely useful.

Our experiments are indeed based on the client aided masking and the unencrypted pruning mask. We will state this more explicitly for better clarity.

Q3 The approximated comparison in CKKS

The comparison function in the CKKS scheme is approximated and not accurate. We approximate the sign function to compute the comparison function and the max function in equation (3). Both the max and the comparison function can be constructed via the sign function and have similar complexity [3]. Specifically, the max function can be defined as $max(a,b) \approx \frac{(a+b)-(a-b)sign(a-b)}{2}$, where $sign(x)$ returns 1 if $x>0$, 0 if $x==0$ and $-1$ if $x<0$. We use a composition of polynomials to approximate the sign function, i.e., $sign(x) \approx f(g(x))$, where $f(x)=f(x) = 8.83133072x - 46.45750399x^3 + 83.02822347x^5 - 44.99284778x^7$ and $g(x)= 3.94881885x - 12.91030110x^3 + 28.08653622x^5 - 35.59691490x^7 + 26.51593709x^9 - 11.41848894x^{11} + 2.62558444x^{13} - 0.24917230x^{15}$. The approximation error of the max function $e = \left| \max(a,b) - \frac{(a+b) - (a-b)\text{sign}(a-b)}{2} \right|$ is bounded by $2^{-8}$ [3]. While increasing the number of compositions and the degree of each polynomial can lead to an even smaller bound, we find that above approximation is precise enough for computing the HEFS score. Prior works [1] find that polynomials of even lower degree is enough for private training.

We hope our responses address the reviewer's concerns. We will add the details about the max and comparison function to Appendix in future version for better clarity.

[1] Lee, Seewoo, et al. HETAL: efficient privacy-preserving transfer learning with homomorphic encryption.

[2] Lee, Eunsang, et al. Minimax approximation of sign function by composite polynomial for homomorphic comparison.

We thank Reviewer 98ig for his/her careful reading of the manuscript and constructive comments.

Q1 Deciding the pruning ratio.

In practice, the pruning ratio should be determined by the client during the client aided masking process. As shown in Figure 1 (in rebuttal pdf), a moderate pruning ratio around 0.5 has close accuracy to training with the full dataset across different datasets. Therefore, like the plaintext data pruning works, one straightforward strategy can be choosing a fixed pruning ratio [1]. Recent works show that one can also choose a set of pruning ratios for different epochs [2]. Moreover, the server can store checkpoints after each data pruning. Since the client can observe the test accuracy, the client can also roll back to certain checkpoint if needed. One should avoid running private training multiple times. This is because private training is orders of magnitudes more expensive than the non-private training.

Q2 The communication scalability.

The proposed data pruning methods are scalable to large datasets. The communication complexity of the proposed method is linear with respect to the number of total data samples and the frequency of the pruning. For the ImageNet, performing one encrypted data pruning over 1,281,167 training samples would only incur around 40MB communication overhead. Note that data pruning is performed every $\Delta_{\tau}$ epochs, so the overall communication are few multiples of 40MB.

The major challenge of scaling to larger datasets is the inefficiency of the HE constructions. As far as we know, the latest HE-based private training works still focus on small datasets like CIFAR-10 and MNIST [3]. Securely training on ImageNet can still take years even with GPU acceleration and more efficient cryptographic tools [4].

Q3 Threat model and indirect data leakage.

The threat model can be strengthened via additional integrity techniques like zero-knowledge proofs (ZKP). HE alone cannot ensure the integrity of the computation on the server side and we can introduce ZKP to verify the correct execution on the server side. Making HE verifiable via ZKP is an active research topic that is currently being explored [5]. In addition to ZKP, other integrity techniques such as Message Authentication Codes and Trusted Execution Environments can also be utilized to defend against malicious adversaries.

Protecting the indirect information, such as the training time and the size of the dataset and ciphertext, is indeed out of scope for this work. In the meantime, we believe the security risk of such indirect information leakage is limited, since all data and model weights are strictly encrypted during the whole training phase. In this work, we focus on protecting client’s data privacy and model privacy in the semi-honest setting, like prior works on private training [3]. Such a setting is reasonable because as a service provider, the server is motivated to adhere to the protocols to guarantee the quality of service. We will make more explicit declarations for better clarity.

Q4 Generality issue

We show the pruning/utility tradeoff on more datasets in Figure 1 (rebuttal pdf). The accuracy does differ for different datasets. We notice that extremely high pruning ratios like 0.99 only work for CIFAR-10 dataset and do not generalize well. On the other hand, moderate pruning ratios demonstrate reasonable pruning/utility tradeoff across all datasets. When we keep more than 10% data, the accuracy is only 0.05%~0.31% lower than training with full dataset. When we keep around 50% data, the accuracy can be even higher.

Q5 Explanations on details

We thank the reviewer’s thorough reading and constructive advice on the copyediting.

(1) The client's capability. The client does not have adequate resource or knowledge for training but has basic computation resource for at least encryption and decryption. The encryption and decryption algorithms are lightweight in HE, taking only 86ms and 49ms for one ciphertext respectively. Accordingly, it is reasonable to assume that the client can compute the pruning mask, which takes as little as 15ms for the CIFAR-10 dataset. Similarly, the client should be capable of computing the early stop signal [3].

(2) The effectiveness of the HEFS score. A sample's importance can be quantified by the $\ell_2$-norm of its gradients, which can be approximated by the $\ell_2$-norm of the error vector [1]. The more similar a sample's prediction vector is to the label vector, the smaller EL2N score will a sample have. This means the sample is easier to learn and less informative for the training process. From this perspective, HEFS has identical properties as EL2N. Additionally, HEFS can be computed in HE more efficiently.

(3) Batching data samples in ciphertext. Single Instruction-Multiple Data (SIMD) is a commonly used technique in HE. With SIMD, a single ciphertext has many slots, i.e., 32,768 slots in our setting. On the other hand, a single data sample can only occupy 768 slots in the transfer learning setting, and 784 slots for the MNIST dataset, 3,027 slots for the CIFAR-10 dataset. Packing multiple samples in one ciphertext is a commonly used strategy to reduce the number of ciphertexts as well as the number of HE operations [3,6].

We will incorporate the reviewer's suggestions into the future versions for better clarity.

[1] Paul, Mansheej, et al. Deep learning on a data diet: Finding important examples early in training.

[2] Truong, Thao Nguyen, et al. KAKURENBO: adaptively hiding samples in deep neural network training.

[3] Lee, Seewoo, et al. HETAL: efficient privacy-preserving transfer learning with homomorphic encryption.

[4] Jawalkar, et al. Orca: FSS-based Secure Training and Inference with GPUs.

[5] Viand, Alexander, et al. Verifiable fully homomorphic encryption.

[6] Crockett, Eric. A low-depth homomorphic circuit for logistic regression model training.

We appreciate the reviewer's thorough reading of our response. We first explain the choice of pruning ratio in more detail. Similar to data pruning studies in plaintext, the pruning ratio is set as empirical values such as 0.5 or 0.3. Manually setting the pruning ratio does not require client-side training or expert knowledge. As shown in our previous responses and also data pruning studies in plaintext [1] (Section 3.3), a moderate pruning ratio can achieve close generalization performance compared to the full dataset. The client can choose an initial pruning ratio around 0.5, and adjust the initial pruning ratio according to the size of the training dataset, the quality of the data and the budget for the outsource training service. Moreover, the client can also adjust the pruning ratio during training according to the test accuracy. If you still have concerns about the pruning ratio, please let us know, and we will be happy to respond. We will clarify the choice of pruning ratio in our revision.

We thank the reviewer for pointing out the side channel information during the threat model. We will clarify it and discuss the potential side channel risks and declare that securing the side channel risks is out of scope for this work more explicitly in the next-version manuscript.

[1] Truong, Thao Nguyen, et al. KAKURENBO: adaptively hiding samples in deep neural network training.