DPFormer: Learning Differentially Private Transformer on Long-Tailed Data

Regarding long-tailed data [W1].

Reply: Thanks for pointing out this perspective. We would like to make it clear that we made no attempt to deal with the fairness issue. Our motivation is long-tailedness in private learning will obstruct the training process (i.e., the attention distraction) and lead to (average) performance drop (i.e., low accuracy on both over-represented and under-represented data). Therefore, our goal in the task of 'improving private learning on long-tailed data' is to mitigate this additional issue and the ideal result is to recover the case of 'non-private (vanilla) learning on long-tailed data' (i.e., potentially low accuracy on under-represented data, but with a high average performance). We make no attempt to improve the model performance on under-represented data. Such goal can be achieved by combining existing method with our method.

[W2] In addition, the theory seems to assume that every token's attention value is an independent gaussian, which is also unrealistic as all tokens are dependent on each other due to previous layers and I don't see why adding gaussian noise to gradients results in gaussian distribution for token activations. The whole section 4 assumes these two things but there isn't any empirical or theoretical justification for this.

Reply: Thanks for pointing out. We would like to stress that these assumptions are commonly used and well-understood in the literature of variational inference and more broadly, bayesian deep learning. We directly adopt this methodolody from that area. The unfortunate fact is, (at this stage of history) we can only assume them being independent Gaussian and approximate it via moment matching. The development of more advanced techniques to help track the evolution of distribution through neural layers is beyond the scope of this work. In addition, we add a more detailed version of analysis of the attention distraction in Appendix A.3 in the revised paper.

why the experiments are limited to recommendation settings.

Reply: We believe that Recommendation task is the most prevailing sequential task in the real-world that features the property of long-tailedness and lack of pre-trained model. Therefore, we target recommendation settings in the work.

Is there a comparison with Li et. al?

Reply: We compare the efficiency of our phantom clipping with ghost clipping in Li et.al in Figure 3. For the accuracy aspect, the baseline transformer can be viewed as an instantiation of Li et.al since Li et.al did not propose algorithmically different methods.

Can the authors also try using a general pre-trained transformer for this recommendation tasks?

Reply: To our knowledge, how to use a general pre-trained transformer for recommendation task is still a largely open problem. One cannot naively adopt a pre-trained transformer model because the input space is different (in recommendation task, token $i$ is associatedd with the item with ID $i$ while in NLP token $i$ is associated with some (sub)word defined by the tokenizer).

What is the privacy guarantee for this method?

Reply: Thanks for pointing out. We have explicitly made the privacy statement in the revised version (Claim A.5). In particular, the privacy guarantee is inherited from that of DP-SGD. Details follow.

Phantom clipping is an efficient implementation of gradient clipping, having the same functionality as vanilla per-sample clipping (i.e., the same input-output behavior). Therefore, we can think of it as the vanilla gradient clipping when we analyze the privacy.

For Re-Attention mechanism, observe that the whole computation process only depends on the single data sample (i.e., we do not create dependency among samples between a mini-batch, thus violating DP like Batch Normalization). Another way to understand this is we can do whatever we like in the forward pass as long as the computation associated with one input sample does not rely on other input samples of the mini-batch. (A caveat is discussed in Remark A.2 of Appendix.A.4) Therefore, the private analysis reduces to DP-SGD: By clipping the gradient we can successfully bound the per-sample sensitivity (and add the calibrated noise to guarantee DP).

What do NDCG@10 and HIT@10 mean?

Reply: Thanks for pointing out. They are metrics commonly used in recommendation systems to measure the prediction accuracy. They can be simply understood as Top-10 accruacy and weighted Top-10 accuracy as in the classification task. We have included the definitions in Appendix A.9.4 in the revised paper.

Is Figure 3 based on Ghost Clipping or Book-Keeping [1]? BK is supposed to be more efficient than Ghost Clipping.

Reply: Yes, exactly. We use implementation in BK for the baseline.

In Equation 7, are the subscripts on the right-hand side supposed to be $X^{(l-1)}$.

Reply: Yes. Sorry for the confusion.

Some baselines for training with DP are missing where these methods also improve the performance of models for long-tailed data

Reply: Thanks for pointing these great works. We discuss them in the related work in Appendix A.1 in the revised paper. From our understanding, these works are operating on the optimizer level, while our method does not assume any specific optimizer and uses the underlying optimizer in a black-box manner. Therefore our method is orthogonal to them and can be potentially combined together.

Describing section 4 as an algorithm would be easier to read.

Reply: Thanks for your suggestion. We add an algorithm description in the Appendix A.7.

The math is not very strict. Please make some revise.

Reply: Thanks for your suggestion. In the revised paper, we give the detailed version of phantam clipping in Appendix A.2 and motivation behind re-attention in Appendix A.3.

I am not convinced why the phantom clipping has such great advantages over ghost clipping. I do not understand why the BM^2 complexity is inherent to the ghost clipping under a careful implementation.

Reply: $BM^2$ complexity is provided in the ghost clipping paper. Our contribution is to support parameter sharing along with a 'careful implementation'.

The ghost clipping has shown a much better memory effIciency. I do not quite understand the gap between Figure 3 and those results.

Reply: Our results are not contradictory to existing results. Previous results are obtained when using a large model while we use a relatively small model. Note that the advantage of ghost clipping vanishes as model size becomes smaller.

The attention distraction mainly happens when different parameters have different variance. However, in DP-SGD, the noise with the same std is added to each parameter.

Reply: A key observation is, for embedding-based models, not all embedding parameters are equal. As a thought experiment, let the embedding layer be parameterized by $E$ (of shape $m \times d$). Suppose we add a dummy embedding $e_{m+1}$ into $E$ to obtain $E'$ (of shape $(m + 1) \times d$) and start DP training, but no data is associated to that dummy token m+1. During each iteration t, we add Gassian noise $n_t$ to the whole $E'$. After $T$ iterations, it is obvious that e_m+1 will become very large (i.e., $e_{m+1} = n_1 + n_2 + ....+ n_T$, distributed as Gaussian with large variance $T \sigma$). Our definition of effetive error (section 4.2.1) is intended to capture this.

Is the assumption realistic assuming i.i.d. Gaussian for each dimension in parameter?

Reply: Note that Gaussian for each dimension in model parameter is not an assumption. It is induced by the DP Gaussian noise (fixing all other randomness). We presume the reviewer's concern is regarding 'use an approximating distribution $q$ to approximate the distribution $p$, where $q$ follows a indepent Gaussian distribution'. This is a commonly used and well understood assumption in the literature of variational inference and more broadly, Beyesian deep learning, since $p$ is computationally intractable. We can only approximate it using a Gaussian via moment matching. The development of more advanced techniques to help track the evolution of distribution through neural layers is beyond the scope of this work.

I do not quite follow how to estimate the mean and std of the start point?

Reply: For example, if the training sequence is [1, 2, 3], then the starting point is $[E_1, E_2, E_3]$ (where $E_i$ is the embedding of token i). The std is estimated by error instantiation (see section 4.2.1). The mean is estimated by itself, $E_i$ (note that access to this noisy parameter can be interpreted as a single sampling opportunity from its underlying Gaussian distribution, which can then be viewed as a one-time Markov Chain sampling. Therefore, the noisy parameter can serve as an estimate of its mean).

Since the paper is targeting large models, it is better to have some setting for fine-tuning instead of training from scratch. Also, revealing some results when eps = 0 will also be helpful.

Reply: We actually target small model in this paper, which is justified by considering the computing resource of end users (preferable for privacy protection through local inference.) Note that for recommendation tasks, how to use a general pre-trained transformer for recommendation task is still a largely open problem. One cannot naively adopt a pre-trained transformer model because the input domain is different (in recommendation task, token $i$ is associatedd with the item with ID $i$ while in NLP token $i$ is associated with some (sub)word defined by the tokenizer). Results when eps = 0 is nearly 0 for both metrics.