Pre-training Differentially Private Models with Limited Public Data

Authors: zhiqi  bu
amazon xinwei zhang
mingyi  hong
george  karypis amazon
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 19:36:21

Abstract: The superior performance of large foundation models can be attributed to the use of massive amounts of high-quality data. However, such datasets often contain sensitive, private and copyrighted material that requires formal protection. While differential privacy (DP) is a prominent method used to gauge the degree of security provided to large foundation models, its application in large foundation models has been met with limited success because there are often significant performance compromises when applying DP during the pre-training phase. Consequently, DP is more commonly implemented during the model fine-tuning stage, hence not capable of protecting a substantial portion of the data used during the initial pre-training process. In this work, we first provide a theoretical understanding of the efficacy of DP training by analyzing the per-iteration improvement of loss through the lens of the Hessian. We observe that DP optimizers' deceleration can be significantly mitigated by the use of limited public data, and thus propose the DP continual pre-training strategy. Our DP continual pre-training on vision models, using only 10% of public data, have achieved DP accuracy of 41.5% on ImageNet-21k (with epsilon=8) and non-DP accuracy of 55.7% on Places365 and 60.0% on iNaturalist-2021, which are on par with state-of-the-art standard pre-training and outperform existing DP pertained models. Our DP pre-trained models are released in *fastDP* library (https://github.com/awslabs/fast-differential-privacy/releases/tag/v2.1)

Main paper: 
 introduction: 
 Large pre-trained models have been the backbone of computer vision and natural language processing. Finetuning or zero/few-shots learning (including in-context learning) based on these models can achieve superior performance. In particular, differentially private (DP) fine-tuning, such as fullparameter training, LoRA, Adapter, BiTFiT, and linear probing [89, 49, 14, 12, 58, 24] , has shown to be almost as accurate as the standard non-DP fine-tuning on GPT [68, 6] , ViT [27] , and ResNet [39] models, while protecting the privacy of fine-tuning data. To be more specific, DP language models (GPT/BERT/RNN) and vision models are highly effective in defending against canary insertion attacks [66, 40, 42] and membership inference attacks [20, 69, 32, 16] ; DP fine-tuned GPT2 also reduces the personally identifiable information leakage by 5 ∼ 10 times compared with its non-DP counterpart [53] .These DP fine-tuned models all follow a two-stage training procedure, in which the first stage trains a model on large public datasets from scratch (without privacy protection), and the second stage fine-tunes on relatively small private datasets. However, a growing concern has been raised against the pre-training on the vast amount of web-collected data [18, 17, 79, 41, 62, 67] . The pre-trained models could memorize and re-generate the sensitive information in the training data, which include copyright content in books and codes, images of faces and nudity, and other personally identifiable information such as address and phone numbers, even if the data have been pre-processed by some content filters. While it is common to use close-source or proprietary datasets (e.g. JFT [75, 24, 58] ) instead and to not release the models trained on these datasets, this approach renders the models not reproducible and may still violate the data privacy in a more implicit way.Consequently, because of the uncertainty in seemingly safe-to-use public datasets, it is important to apply DP to the pre-training phase, which is computationally feasible, since DP optimization can be as efficient as the standard non-DP training [13, 38] . However, DP optimization without any public data suffers from slow convergence, and suboptimal performance: even on CIFAR10, the accuracy drops from > 95% to < 70% at ϵ = 8 [63] ; on GPT2, the non-DP BLEU score degrades from 65.73 (quality often better than human) to 15 .457 (hard to get the gist) at ϵ = 3 [49] . In short, pre-training and fine-tuning differ significantly in the amount of data and computation resources used, as well as in optimization setups. We summarize the difference in Table 1 . Our main contributions are listed below. We emphasize that we have taken the privacy accounting and the convergence (i.e. the dependence of loss on σ(B, T, ϵ), B) jointly into consideration.(1) We provide a new perspective of analyzing the loss improvement in DP training with different optimizers. Specifically, we propose a Hessian-based framework to analyze the per-iteration improvement on the generalization loss and the effects of per-sample gradient clipping, noising, and hyperparameter choices (e.g., batch size, learning rate).(2) Based on the framework, we can analyze the effect that DP mechanisms, especially the DP noise but less so the DP clipping, have on pre-training and fine-tuning stages, leading to some theoretical justifications about why pre-training is more vulnerable to DP noise; see Figure 1 for some empirical comparisons, and Section 3 for some in-depth discussion.(3) Our analysis suggests that the deceleration due to DP mechanisms can be mitigated by using a certain amount of public data. We then propose a DP continual pre-training strategy that continues the pre-training privately from a non-DP initialization. Our strategy is easily implementable, automatic, and effective, which obtains accuracy on upstream and downstream tasks that is on par with its non-DP variants, while significantly outperforming state-of-the-art DP pretraining algorithms (see Figure 2 ). This work is closely related to other works in DP convergence analysis, DP fine-tuning of large models, the continual training and the Hessian-based analysis. We refer to Appendix C for an extended discussion. We study DP optimization under a fixed computation budget (with a fixed number of samples), a fixed privacy budget (with a fixed DP guarantee), and limited availability of public data.We consider a fixed computation budget, so that the training ends when a fixed number of samples S := BT have been processed. As B increases, the number of iterations T decreases linearly, while the per-iteration training time increases almost linearly. This is because foundation models are generally trained with large batch size, which requires the use of distributed learning and gradient accumulation 2 . For example, Vision Transformers (ViT, [27, 74] is trained with B = 4k, GPT-3 [6] and LLaMA [77] with B ≈ 2k, DP-ResNet/ViT with B = 4k in [24] and B = 1M in [58] , DP-RoBERTa with B = 2k in [89] , and DP-GPT2 with B = 1k in [49] .As a consequence, the batch size B has nearly zero influence on the total training time, leaving its effect only on the convergence speed.Definition 1.1 ( [29, 26] ). A randomized algorithm M is (ε, δ)-DP if, for any two neighboring datasets S, S ′ that differ by one sample and for any event E, We consider a fixed privacy budget (ϵ, δ), to be realized through the DP optimizers in (2) . Essentially, a noise σN (0, I) is injected to the gradient at each iteration, whereas the noise magnitude σ(B) is determined by privacy accountants such as RDP (default) [59] , PRV [34] and GDP [26, 8] (see Figure 3 ).P[M(S) ∈ E] ⩽ e ε P [M (S ′ ) ∈ E] + δ, where δ < 1/n. 
understanding dp training through the lens of hessian: 
 In this section, we derive the impact of different components in DP training, including the per-sample clipping, the noising, and hyper-parameter choices. To do so, we characterize the per-iteration persample loss improvement through the lens of Hessian.We aim to optimize the generalization loss (equivalently the expected risk) for any differentiable loss function, e.g. the cross entropy, mean squared error, or adversarial loss [33] :EQUATIONWe denote the per-sample gradient g i (w ∈ R d×d . In Assumption 2.1, samples follow identically and independently (i.i.d.) from some data distribution, with no restriction on the covariance structure Σ(w). Assumption 2.1. Per-sample gradients g i (w) are i.i.d with) := ∂L(w,xi) ∂w ∈ R d , the oracle gradient G(w) := ∂Ex[L(w,x)] ∂w ∈ R d ,E[g i (w)] = G(w), Cov(g i (w)) = Σ(w).To simplify the notation, we drop the dependence on w.Consider the general DP optimizers, such as SGD and Adam [46] , which update the parameters with the privatized gradient,EQUATIONHere C i := C(∥g i ∥; R) is the per-sample clipping factor that restricts the sensitivity of i C i g i to some constant R, i.e. ∥C i g i ∥ ≤ R. We set ∥C i g i ∥ ≤ 1 (thus omitting R throughout the paper) following the re-parameterized gradient clipping [24] and the automatic (AUTO) clipping [14] , whose C i 's are listed below:EQUATION)Figure 4 illustrates the values of C i under different clipping functions. Note that in (2), we employ a crucial approximation c ≈ E[C i ] so as to unify the formula of DP and non-DP SGD in Remark 2.2. This approximation only holds when the directions of vectors i C i g i and i g i are very close, i.e., there is little per-sample clipping bias. Such approximation is empirically validated in Figure 1 , where we observe from the 'SGD' and 'SGD+clipping' curves that the convergence (without noising) is not much influenced by the bias of per-sample gradient clipping. Remark 2.2. Setting c = 1 and σ = 0, the gradient (2) reduces to the standard mini-batch gradient. Hence, the difference between SGD and DP-SGD is characterized by (σ, c).Next, we characterize and analyze the per-iteration improvement of DP-SGD through the lens of Hessian, under different choices of hyperparameters and clipping functions: w t+1 = w t -ηg t . The extension of the analysis to more general optimizers (e.g., DP-Adam) is given in Section 3.4. We are interested in minimizing the second-order Taylor approximation of L(w -ηg), which is sufficiently accurate since parameter updates are often quite small [57] . The loss improvement in one iteration can be approximated as:L(w) -L(w -ηg) ≈ ηG ⊤ g - η 2 2 g ⊤ Hg.Taking the expectation of the right-hand side, we obtain the expected per-iteration loss improvement (derived in Appendix A.1):EQUATIONBy applying Assumption 2.1 and (2), we have E[g] = cG, Cov(g) = c 2 Σ/B +σ 2 /B 2 . Substitute to (4), we obtain a quadratic function of η:EQUATION)We denote the batch size used for SGD and DP-SGD as B non-DP and B DP , respectively. Then by optimizing the learning rate η3 , the per-sample and per-iteration improvement simplifies toEQUATIONGiven that the total number of processed samples is fixed at S = BT , (6) can be used as a metric to evaluate the data efficiency of DP and non-DP training with different T, B and (ϵ, δ).We can analyze the loss improvement of standard SGD (which uses the full public data) as a sub-case of DP-SGD by substituting c = 1, σ = 0 into (5), according to Remark 2.2:EQUATIONWe visualize ( 6), (7) , and their individual terms in Figure 5 . 6) and (7) . Left sub-plots depict the denominators in ( 6) and (7) . Right sub-plots depict the whole terms and optimal batch sizes. Implication 2.3 (Better DP mechanism helps). From (6) , it is clear that smaller σ and larger c (hence larger C i ) can help DP training. To reduce σ, we refer to Section 3.1 for a discussion of methods. For the clipping, under the same sensitivity bound, AUTO clipping [14] gives the largest C i among all clipping functions (see Figure 4 ), and therefore is more preferred to use in practice. Implication 2.4 (Batch size should be large, but not too large). As visualized by the red solid curves in Figure 5 , there exists an optimal batch size (marked in red dashed vertical lines)500B ⋆ DP := argmax B ∆L ⋆ priv (B) ≈ σ 2 tr(H) c 2 G ⊤ HG .Compared to previous DP literature, which encourages the batch size to be as a large as possible, our derivation of B ⋆ DP indicates a sweet pot: while we also support the use of large batch size, we highlight the data inefficiency if B DP is too large, a case that is often overlooked. 
impact of per-sample clipping and noising: 
 In this section, we examine the effects of per-sample gradient clipping and noising on the DP training, leveraging the per-iteration per-sample loss improvement derived in Section 2. Specifically, we define and analyze a "decelerator" term that characterizes the slowdown by DP optimizers.Comparing DP-SGD to SGD, we can attribute the slow convergence of DP optimization to the term σ 2 tr(H)/(Bc 2 ) in (6) , which is not present in the standard training (7) . We refer to such a term as decelerator:EQUATIONwhich couples the effects of per-sample gradient clipping and noise through the trace of Hessian. We note that tr(H) in (8) characterizes the curvature (i.e. sharpness or flatness) of the loss landscape, which strongly correlates with the downstream performance [51, 45, 96, 31] .Next, we discuss how the decelerator impacts the non-DP training, DP pre-training and fine-tuning.When σ = 0 (i.e., no DP noise), the decelerator vanishes and hence (6) reduces to (7) , even if the per-sample gradient clipping is used. We empirically verified this in Figure 1 (see blue and black curves), where we see that the difference in convergence with or without clipping is negligible.Given that DP noise is critical to the convergence speed, we highlight some techniques to reduce σ under the same budget of (ϵ, δ): the advances in privacy accounting theory can justify smaller noise; algorithms such as LoRA, low-pass and Kalman filters [93, 92] can reduce the effective noise.When σ ̸ = 0, the decelerator is non-zero. Therefore, DP training is slowed down by the noise; in Figure 1 , SGD with noise (yellow and red curves) has worse performance than SGD without noise (black and blue curves). Furthermore, in pre-training, the decelerator is relatively large in the denominator of ( 6), i.e., BG ⊤ HG + tr(HΣ) ≤ σ 2 tr(H)Bc 2when B ≤ B * DP (see left sub-plot of Figure 5 (a)), and therefore the slowdown can be significant.Note that the deceleration issue cannot be resolved by increasing B. Although increasing B improves the relative speed of DP convergence in comparison to non-DP, i.e., the decelerator decreases, it hurts the absolute speed since BG ⊤ HG increases, and thus the loss improvement (6) also worsens (c.f. right sub-plot of Figure 5(a) ). Therefore, to design an efficient DP pre-training strategy, we must keep B moderate and reduce the decelerator simultaneously.Empirical evidence has shown that DP fine-tuning is comparable to (though slightly worse than) the standard non-DP fine-tuning [89, 49, 24, 58, 10, 14, 12] , despite that σ ̸ = 0. Such a phenomenon implies that comparing public and DP finetuning, we have ∆L ⋆ pub (B) ≈ ∆L ⋆ priv (B). That is, the decelerator becomes small after the public pre-training. This is conceptually illustrated in Figure 5(b) , where the DP curve is close to the non-DP curve at moderate B during fine-tuning, but not so during pre-training.To understand the stark contrast between DP fine-tuning and DP pre-training, we plug in the optimalB ⋆ DP = σ 2 tr(H) c 2 G ⊤ HG from Implication 2.4 to ∆L ⋆ priv (B). Then, we have the optimal improvement of DP-SGD as∆L ⋆ priv (B ⋆ DP ) = 1 2 |G| 4 2 G ⊤ HG • σ 2 tr(H)/c 2 + tr(HΣ) .Implication 3.1. Notice that by choosing B non-DP = 2B ⋆ DP in (7) , we have that DP-SGD with the optimal batch size is as fast as the standard SGD with twice the batch size,EQUATIONMoreover, if B ⋆ DP is moderate, then DP-SGD can converge at similar speed to a fast converging SGD that uses a moderate batch size. Remark 3.2. From (7), we observe that non-DP training is data-efficient only if B non-DP G ⊤ HG ≪ tr(HΣ). Otherwise, we can decrease B non-DP to effectively improve ∆L ⋆ pub . Therefore, DP training is data-efficient only if B ⋆ DP ≈ 1 2 B non-DP ≪ tr(HΣ) 2G ⊤ HG , which holds in fine-tuning but not in early stage of pre-training 4 We illustrate the magnitude of the three terms in (6) for pre-training and finetuning stages in Figure 6 . 6) and ( 7) that explains the deceleration of DP optimization, during pre-training (left two) and fine-tuning (right two) ViT-Base on CIFAR100.In the fine-tuning phase of Figure 6 , tr(H) quickly decreases and so does the decelerator. Hence a moderate B DP ≈ 100 can allow fast convergence. However, in the pre-training phase, tr(H) increases to a large value within 5 epochs and remains for a long time (say epoch 5 to 40) before it decreases again. Consequently, DP convergence is initially fast but only for a short period and overall DP optimization is much slower than non-DP optimization, as shown in Figure 1 (a)(c).The analysis in the previous two sections can be easily extended to arbitrary optimizers as well as techniques such as weight decay, gradient clipping, and parameter-efficient fine-tuning (PEFT). Let p be an optimizer's post-processor of gradient and consider w t+1 = w t -ηp(g t ).For examples, following the notation in Pytorch library [65] , we can write Adam and SGD with momentum (µ) and weight decay (λ),Adam: p(g; m, v) = β1m+(1-β1)g 1-β t 1 β2v+(1-β2)g 2 1-β t 2 + 10 -8 SGD(µ, λ): p(g; b, w) = µb + g + λw.Similarly, we can write any PEFT for any optimizer, e.g. PEFT (SGD): p(g; M) = M ⊙ g where M ∈ {0, 1} is an element-wise mask, with M = 0 indicating that the parameter is non-trainable or frozen.Specially, we consider optimizers such that p(•) is scale-invariant (i.e. p(cG) = p(G)), such as SignSGD/Adam [4] or normalized SGD/LAMB [61, 55, 87] . Applying Assumption 2.1 and the optimal learning rate, we derive the expected per-sample per-iteration improvement in Implication 3.3, leaving the details Appendix A.5. Implication 3.3. Suppose the post-processor p(•) is scale-invariant. Denote p = p(G), p ′ = p ′ (G), the per-sample per-iteration improvement max η ∆L(η)/B simplifies to 1 2|p ⊤ G| 2 Bp ⊤ Hp + tr(p ′⊤ Hp ′ Σ) + σ 2 tr(p ′⊤ Hp ′ )/(Bc 2 )Interestingly, similar to the decelerator of DP-SGD (8), the decelerator σ 2 tr(p ′⊤ Hp ′ )/(Bc 2 ) of these DP optimizers also couples the per-sample gradient clipping, the noise and the Hessian, rendering the theoretical implications from DP-SGD extendable to general DP optimizers. 
continual pre-training with dp 4.1 necessity of public data in dp pre-training: 
 In this section, we propose the DP continual pre-training strategy and demonstrate that the deceleration by DP can be effectively mitigated by using a certain amount of public data. We consider the mixed data training that uses both public data (with subscript 0 for related hyperparameters) and private data (with subscript 1 ). Then SGD becomesg α,t := α t B 0 j∈B0 g j,t + (1 -α t ) B 1 ( i∈B1 C i,t g i,t + σN (0, I d )).4 An intuitive explanation is that tr(HΣ)G ⊤ HG = E[(g i -G) ⊤ H(g i -G)] G ⊤ HG = E(g ⊤ i Hg i )E(g i ) ⊤ HE(g i ) -1 resembles the variance of per-sample gi in the space of H, which decreases as the model learns the common representation.Here α t ∈ [0, 1] controls the ratio of privatized and non-privatized gradients, taking different forms by public training (OnlyPublic, α t = 1), private training (OnlyPrivate, α t = 0), DPMD [2] , a tunable constant [32, 52] , and Sample [30, 44] . 1 0 Using the mixed gradient g α and following (4), we can show that expected loss improvement is a bivariate quadratic function of (η, α) (see Appendix A.3). After minimizing with respect to both variables, we obtain:EQUATIONRemark 4.1. We see that the optimal choice in (10) gives α ⋆ ̸ = 0, which indicates that the optimal improvement of mixed data training is larger than private training, i.e., ∆L ⋆ OnlyPrivate < ∆L ⋆ mixed and the public data helps. On the other hand, the fact that optimal α ⋆ ̸ = 1 also indicates that ∆L ⋆ OnlyPublic < ∆L ⋆ mixed i.e., the private data helps. We highlight that DP continual pre-training is as distinct from DP fine-tuning as their non-DP counter-parts, despite both methods extending the learning from a pre-trained phase: the continual pre-training learns common knowledge without adapting to a specific task and serves a richer foundation for many downstream tasks (see more discussion in Appendix C).In fact, we show in Appendix A.7 that the loss improvement of DP continual pre-training can be almost as fast as non-DP pre-training (FullyPublic), thus closing the utility gap.The switching, i.e. selecting s, can be automatically determined by public statistics without using any DP budget. For example, we can use early stopping based on the loss or accuracy, i.e., we switch after the metrics on the validation dataset stop improving (see Figure 7 ). Alternatively, we can monitor B ⋆ DP and switch when it drops to a moderate value so that the DP training converges fast by (9) . 
dp vision foundation models on imagenet: 
 We leverage the DP continual pre-training strategy discussed in Section 4 to train vision transformers [27] on ImageNet datasets. We use ImageNet-1k (1.3M images, 1k classes; [25] ) for public pretraining, then ImageNet-11k (formally known as ImageNet-21k-P5 , 11M images, 11k classes; [70] ) for private pre-training. Notice that ImageNet-11k/21k is significantly harder to learn, with SOTA accuracy ≈ 47% [70, 74] as compared to > 85% for ImageNet-1k. We apply data augmentation including random flipping, contract shift, rotation, and resizing to 224 × 224.We evaluate our DP ViT on upstream and downstream tasks (including few-shot), achieving high accuracy under low computation budget (compared to existing DP pre-trained models in Table 3 ).In short, we show that unlocking more data (90% of full ImageNet), which cannot be used by DINO due to privacy concern, is significantly beneficial. ViT-Base ImageNet-1k ImageNet-11k ImageNet-11k 1.4B Original [27] ViT-Base ImageNet-21k ImageNet-1k ImageNet-21k 1.2B AugReg [74] ViT-Base ImageNet-1k ImageNet-21k ImageNet-21k 4.3B NFnet-JFT [24] ResNet-50 JFT300M -JFT300M 4.0BFor the public pre-training, we follow the self-supervised learning by [19] (self-distillation with no labels, or DINO), whereas the private continual pre-training is a supervised learning following [70] 6 . We employ AdamW optimizer with batch size B = 4096 and learning rate η = 0.0002 set by the line search. Our training strategy is similar to a concurrent work [90] , with critical differences highlighted in Appendix C.When automatically switching from public to private pre-training, the classification head (the last layer) is re-initialized because the number of classes is different in the two pre-training phases. This switching is triggered by early stopping. In the continual pre-training phase, we train with DP linear probing for 10 epochs then with DP full-parameter training for 20 epochs, with a total ≈100k training steps. This strategy achieves an upstream accuracy 41.5% on ImageNet-11k by our ViT-Base under ϵ = 8, and 39.8% under ϵ = 2.We employ fastDP library to apply the DP optimizers with automatic per-sample clipping [14] and layer-wise clipping style [9] . Specifically, the DP optimization is under the multi-GPU distributed system, using DP-ZeRO [7] and mixed-precision training. We calibrate the DP noise using the improved Renyi accountant.Our DP pre-training learns highly transferable representations, demonstrated through the strong performance on a list of downstream datasets. We summarize in Table 3 a number of models from previous literature for comparison. The most informative baselines are DINO and MIIL, since our DP models continue the pre-training from DINO, following the strategy of MIIL. Next, we mark DP pre-trained models in green and leave non-DP ones in black.In Table 4 , we compare different pre-training strategies (all non-DP except ours) leveraging the same dataset and same model architecture -ViT-Base (86M param). Our evaluation shows that DP pretrained models achieve high downstream accuracy under standard and non-DP fine-tuning: 98.4% on CIFAR10, 90.2% on CIFAR100, 86.5% on Food101 and 96.8% on SVHN. Our DP continual pre-training clearly improves upon DINO, with +0.3 ∼ 2.0% on accuracy, and is comparable to the non-DP pre-trained MIIL that uses twice the data size (1.4B v.s. our 0.7B).In Table 5 , when the downstream tasks (non-DP) are more challenging with only a few data samples to learn from, our DP model substantially outperforms previous DP pre-trained models across all settings, for example, by +19 ∼ 38% on CIFAR100 when compared to ViP and TAN. We attribute the success to the high quality of pre-training data, i.e. ImageNet-1k/11k, in contrast to Shaders (by comparing DINO to (Syn)ViP) and LAION (by comparing the improvement from DINO to ours and from (Syn)ViP to ViP). [24, 27] and about 64% on iNat2021 [80, 60] after pre-training on 2.7 ∼ 4B images. This showcases the effectiveness of DP pre-training as our models only leverage 0.7B images.We employ a white-box membership inference attack (MIA) to evaluate the data protection by our DP pre-training: 1) for each image in ImageNet-11k, we compute its output logits and loss, which serves as the feature of the MIA dataset; 2) we randomly select 50% of the testing images and the same number of training images (522, 496 samples) as the MIA test set, and the rest data as MIA train set; 3) we label the training images as class "1" and testing images as class "0". This creates the MIA dataset with 11k features and binary labels.  
discussion: 
 In this paper, we conduct an insightful and unified convergence analysis on DP optimization. Specifically, we identify the decelerator (8) of DP training as a result of the per-sample gradient clipping, the noise and the Hessian, which can be significantly mitigated by a small amount (< 10%) of public training. Consequently, we propose DP continual pre-training that is almost as accurate and implementable as the fully public pre-training.A.1 Derivation of Equation ( 4)∆L := ηG ⊤ E[g] - η 2 2 E[g ⊤ Hg] (a) = ηG ⊤ E[g] - η 2 2 tr HE[gg ⊤ ] (b) = ηG ⊤ E[g] - η 2 2 tr (HCov(g)) + tr HE[g]E[g] ⊤ (c) = ηG ⊤ E[g] - η 2 2 (tr (HCov(g)) + E[g] ⊤ HE[g])where (a) uses equations ( 13) and then (12) to the second term; (b) separates the expectation of gg ⊤ into its mean squared and covariance and uses (11) ; (c) uses equations (12) and then (13) to the last term.Substituting in the mixed gradient g α and following (4), we can write down the expected improvement of mixed data training:∆L mixed = η(α + (1 -α)c)G ⊤ G - η 2 (1 -α) 2 σ 2 2B 2 1 tr(H) - η 2 2 ( α 2 B 0 + (1 -α) 2 B 1 c 2 )tr(HΣ) - η 2 2 (α + (1 -α)c) 2 G ⊤ HG,which is a bivariate quadratic function ∆L mixed to be minimized over (η, α). To make the presentation easier, we denote η 0 = ηα, η 1 = η(1 -α), and the above equation can be rewritten as:∆L mixed = (η 1 c + η 0 )G ⊤ G - 1 2 η 2 1 σ 2 B 2 1 tr(H) - 1 2 ( η 2 1 B 1 c 2 + η 2 0 B 0 )tr(HΣ) - 1 2 (η 1 c + η 0 ) 2 G ⊤ HG.Note that if we set η 1 = 0 or η 0 = 0, we essentially train the model with only public data or private data, respectively. can be written as a bivariate quadratic function over (η 0 , η 1 ):∆L mixed = -(Aη 2 0 + Bη 2 1 + Cη 0 + Dη 1 + Eη 0 η 1 ) in which A = 1 2 G ⊤ HG + 1 2 tr(HΣ) B 0 , B = 1 2 c 2 G ⊤ HG + 1 2 c 2 tr(HΣ) B 1 + 1 2 σ 2 tr(H) B 2 1 , C = -G ⊤ G, D = -cG ⊤ G, E = cG ⊤ HG.The maximizer isη 0 = - 2BC -DE 4AB -E 2 , η 1 = - 2AD -CE 4AB -E 2 . Hence 1 -α * α * = 2AD -CE 2BC -DE =⇒ α * = 1/ 2AD -CE 2BC -DE + 1 Finally α * = ctr(HΣ)G ⊤ G/B 0 c 2 tr(HΣ)G ⊤ G/B 1 + σ 2 tr(H)G ⊤ G/B 2 1 + 1 -1 = 1 c tr(HΣ) • B 1 /B 0 tr(HΣ) + σ 2 tr(H)/(B 1 c 2 ) + 1 -1A.4 Explanation of Remark 3.2From (6), the optimal batch size for DP-SGD is arg max We emphasize that generally SGD(2B DP ) ̸ ≡ DP-SGD(B DP ).A.5 Loss improvement of general DP optimizers -Implication 3.3From w t+1 = w t -ηp(g t ), the expected per-iteration loss improvement becomesEQUATION)Applying Assumption 2.1 and delta method, with G = ∂L ∂w , we have√ B(p(g) -p(cG)) = √ Bp ′ (cG) • (g -cG) + o p (1) → N 0, p ′ (cG)[c 2 Σ + σ 2 /B]p ′ (cG) ⊤ where p ′ (cG) ≡ ∂p(cG) ∂cG ∈ R d×d . Hence E(p(g)) ≈ p(cG), Cov(p(g)) ≈ p ′ (cG) • c 2 Σ/B + σ 2 /B 2 • p ′ (cG) ⊤Next, the expected improvement contributed by one sample is a quadratic function of η:∆L/B ≈ ηp(cG) ⊤ G - η 2 2 σ 2 tr[p ′ (cG) ⊤ Hp ′ (cG)] B 2 - η 2 2 c 2 tr[p ′ (cG) ⊤ Hp ′ (cG)Σ] B - η 2 2 p(cG) ⊤ Hp(cG) /BApplying the optimal learning rate, the optimal per-sample loss improvement ∆L/B at each iteration simplifies to1 2 |p(cG) ⊤ G| 2 Bp(cG) ⊤ Hp(cG) + c 2 tr(p ′ (cG) ⊤ Hp ′ (cG)Σ) + σ 2 tr(p ′ (cG) ⊤ Hp ′ (cG))/BIn the special case that p is scale-invariant, e.g. in adaptive optimizers like Adam or in SignSGD, we get p ′ (cG) = ∂p(cG) ∂cG = ∂p(G) ∂G ∂G ∂cG = p ′ (G)/c and thus 1 2|p(G) ⊤ G| 2 Bp(G) ⊤ Hp(G) + tr(p ′ (G) ⊤ Hp ′ (G)Σ) + σ 2 tr(p ′ (G) ⊤ Hp ′ (G))/(Bc 2 )We now consider two extended cases when the optimization loss is different to the performance measures. For example, the model may be trained via the cross-entropy loss but measured on 0-1 accuracy.optimization performance example L L vanilla L is cross-entropy L L other vanilla L is cross-entropy; L other is BLEU or accuracy L mod L adversarial training L mod is adversarial loss; L is cross-entropy Table 8 : DP/non-DP optimization when the optimization loss is different to the performance measures.For the first case, we analyze many performance measures of DP models (denoted as L other ) beyond the optimization loss L. For instance, foundation models trained on cross-entropy loss can be evaluated on classification accuracy, F1 score, BLEU [64] , ROGUE [50] , fairness [37] , calibration [35] , adversarial robustness, etc.We demonstrate that our analysis in previous sections indeed generalizes: equivalent to (5), we have∆L other (η) = ηG ⊤ other E[g] - η 2 2 E[g ⊤ H other g]where G other , H other are the oracle gradient and Hessian of L other . The per-sample per-iteration improvement, max η ∆L other /B, simplifies to1 2 |G ⊤ other G| 2 BG ⊤ H other G + tr(H other Σ) + σ 2 tr(H other )/(Bc 2 ) ,with the decelerator being σ 2 tr(H other )/(Bc 2 ) in place of (8) . As implied by Section 3.3, we expect the public pre-training also mitigates this decelerator, so that well-trained DP models and non-DP models should be equally performant. Empirically speaking, DP fine-tuning has shown to be as accurate [49, 24] , adversarially robust [15] , calibrated [11] , and fair [5] as the standard fine-tuning.For the second case, e.g. adversarial, sharpness-aware, fairness-aware or calibration-aware training, the optimization is on the modified loss ∂Lmod ∂w but the performance is measured on the vanilla loss ∂L ∂w . For instance, we want an adversarially trained model to be sufficiently accurate. To be specific, FGSM and PGD (L 2 /L ∞ perturbation with norm ρ) lead to the modified lossL mod := max ||ξ||≤ρ E x [L(w, x + ξ)], G mod = ∂L mod ∂w .p = 1 B ( i C i g mod,i + σN (0, I d )) ≈ 1 B (c i g mod,i + σN (0, I d ))where per-sample gradient is g mod,i :=∂ max ||ξ||≤ρ L(w,xi+ξ) ∂w. Note that the modified gradient may be post-processed by optimizers like AdamW. To be clear, only in this section, we write p = ∂Lmod ∂w and omit the post-processing of the optimizer (i.e. we only show for SGD).Next, the expected per-iteration loss improvement becomesEQUATIONApplying Assumption 2.1, we haveE[p] = cG mod , Cov(p) = c 2 Σ mod /B + σ 2 /B 2Hence, the expected per-iteration improvement contributed by one sample is a quadratic function of η:∆L/B := (ηcG ⊤ G mod - η 2 2 σ 2 tr(H) B 2 - η 2 2 c 2 tr(HΣ mod ) B - η 2 2 c 2 G ⊤ mod HG mod )/BApplying the optimal learning rate, the optimal per-sample per-iteration improvement, max η ∆L/B, simplifies to1 2 |G ⊤ G mod | 2 BG ⊤ mod HG mod + tr(HΣ mod ) + σ 2 tr(H)/(Bc 2 ) (16)Again, the decelerator is the same as (8) . Therefore, DP training will be as good as the standard training when the decelerator is small under the modified loss. This supports the observation that DP adversarial training can be accurate in [15] , if DP natural training is comparable to non-DP natural training.Taking a step further than Remark 4.1, we claim that DP continual pre-training can converge as fast as non-DP pre-training (FullyPublic), conditioning on that the non-DP initialization is sufficiently strong: running sT iterations of public training followed by the DP training is only marginally weaker than FullyPublic in (7) :EQUATION⪅ sT t=1 |G t | 4 G ⊤ t H t G t + tr(HtΣt) B + T t=sT |G t | 4 G ⊤ t H t G t + tr(HtΣt) B ,given that the decelerator ( 8) is small for t > sT .In this section, we provide additional descriptions and experiment details for the numerical results in the main paper.We use the following datasets throughout this paper.• ImageNet: ImageNet-21k [25] is the full dataset with various releases which contain 14.2M images from 21,841 classes. ImageNet-1k is a subset of ImageNet-21k using 1k high-level classes. We use the ILSVRC2012 version, which contains 1.2 million training images and 100000 test images. ImageNet-11k [70] is another subset of ImageNet-21k that removes invalid/infrequent classes, retaining 11.1M images (train:test=10.5M :0.52M ) and 10,450 classes in the Winter21 version.• CIFAR-10/CIFAR-100: 50,000 training and 10,000 test images, with 10 or 100 classes, respectively.• Food101: it contains 101 classes of food, with 101,000 images in total, 1000 images per class (training 750 and test 250).• SVHN: it contains 10 classes of digits in natural scene images, with 73257 training and 26032 test images.• Aircraft: FGVCAircraft dataset contains 3334 training and 3333 test images with 100 classes.• Places365: Places365-Standard dataset contains 1.8 million training and 36000 test images from 365 scene classes.• iNat2021: iNaturalist 2021 dataset contains 10,000 classes of species, with 2.7 million training and 0.1 million test images.• CodeParrot: a GitHub dataset of about 180 GB containing roughly 20 million Python files. We use 3% of these files, that is 606,720 rows of training and 3322 rows of test data. We take sequence length 128.• E2E: a dataset of restaurant reviews, containing 42,061 training and 4693 test instances. We take sequence length 100.For images, we use 224 × 224 resolution and patch 16 for vision transformers. After pre-training, an additional classifier head is inserted for each downstream task.We use batch size 1000 and search over learning rate ∈ [5e -5, 1e -4, 2e -4, 5e -4].1. CIFAR10, ViT-Base, random initialization, η = 5e -5 without noise, η = 5e -4 with noise, 10 epochs.When switching from public pre-training to private continual pre-training, the DP gradient may have a different scale than the historical optimizer states and make the continual pre-training unstable. Therefore, we investigate different strategies to re-initialize the optimizer states during the switching.Throughout the training, we use AdamW, which have three states: the iteration index (t), the firstorder momentum (m), and the second-order momentum (v).In the experiment, we train a ViT-Base model from scratch on the CIFAR100 dataset. In the first three epochs, we use vanilla AdamW, then we switch to DP-AdamW and continue training for one epoch. During the switching, we fixed the learning rate and reset different states (t, v, m) to zeros. The ablation study result is shown in Figure 8 .From the figure, we observe that re-initializing the first-order momentum m (R1) results in the best performance when switching from public to private training. For the other cases, we observe a performance drop when switching. To conduct the membership inference attack (MIA) in Table 7 , we employ a white-box attack with full access to model parameters and data, to evaluate the data protection by our DP pre-training. The attack has two major steps.Step I: construct MIA dataset. To construct the MIA dataset, we use the following procedures: 1) for each image in ImageNet-11k, we compute its output logits and loss, which serves as the feature of the MIA dataset; 2) we randomly select 50% of the testing images and the same number of training images (522, 496 samples) as the MIA test set, and the rest 50% of the testing images and 10% of the training images as MIA train set; 3) we label the training images as class "1" and testing images as class "0". This creates the MIA dataset with 11k features and binary labels.Step II: evaluate MIA performance. Convergence analysis of DP training (the goals) Recent works have attributed the slow DP convergence to the large number of model parameters [95, 48] , the noise level added to gradients [84, 14, 86] , and the per-sample gradient clipping [11, 21, 94] . Our analysis in ( 6) and ( 8) covers these factors as well as the choice of hyperparameters. We note that a key quantity of DP convergence is tr(H), which implicitly covers the model dimension d and is also analyzed in [54] to give a dimension-free generalization bound. Moreover, existing works mostly study the empirical convergence on the training set, in terms of the gradient norm ||g t || → 0, the parameter space w t → w * , or the training loss L t → L * as t → ∞. Our work focuses on the generalization performance, and pays particular attention on the data efficiency (as well as computation efficiency) that is rarely captured in the literature.More on DP convergence analysis (the assumptions) The convergence analysis of non-convex DP deep learning is very challenging and under-studied. There are roughly 3 routes to walk around the challenge: (1) Working on convex models instead (see [73, 23] and more in Sec 4.1.2 [66] ), e.g. assuming some form of convexity or only optimizing the last layer (essentially a linear model). This route offers deep theoretical insights thanks to the simplified models, but generally fails to match the training dynamics nor the performance of deep learning. For instance, last-layer training may work reasonably well in computer vision but not so in language tasks, obtaining only 26 BLEU score for DP-GPT2 on E2E dataset compared to 63 BLEU score via DP full-parameter training. ( 2) Working on the continuous-time gradient flow, rather than the gradient descent in practice, in order to get rid of the per-sample gradient clipping or the Gaussian noise. This route essentially works with infinitely small learning rate, which falls short in the performance as SOTA DP models are trained with large learning rate [49] .(3) Assuming that the loss L is Lipschitz continuous (i.e. the gradient is bounded) [3, 81, 82] or Lipscthiz smooth [21, 14, 86] . While both assumptions lead to some insights of the DP training behaviors, the Lipschitz constant is hardly calculable and time-dependent (maybe even diverging) in practice. Particularly, in the Lipschitz continuous setting, the per-sample gradient clipping is not used in DP deep learning, reducing the technical difficulty significantly but missing the gist of DP-SGD from a practitioner's viewpoint.In contrast, our work does not rely on these and many other assumptions in the literature, because we do not study the loss convergence along all iterations. We instead scrutinize the per-iteration loss improvement in (5) . Put differently, we focus on the local behavior of DP optimizer rather than the global behavior.The literature of DP deep learning has predominantly focused on fine-tuning the pre-trained models (e.g. full-parameter [1, 49, 14] and PEFT [78, 89, 12, 58] ). Importantly, DP fine-tuning (1) can be as performant as the standard non-DP fine-tuning consistently, (2) achieves better empirical performance with larger models [14, 9] and (3) necessarily relies on the public data pre-training. Our work is distinct from previous works since we focus on DP pre-training with large sample size, large number of iterations, and very limited public data. Interestingly, we notice that DP pre-training also enjoy these desirable characteristics of DP fine-tuning, e.g. requiring public data (only a small amount) in Section 4.1 and benefiting from scaling up the models (see Figure 4 , Figure 5 and Table 9 in [90] ). This empirical evidence of similar training dynamics between DP pre-training and DP fine-tuning, despite their difference in learning goals, is well-supported by our decelerator analysis in Section 3.Continual pre-training Continual pre-training is a training strategy that accumulates knowledge from a large amount of data, in order to improve its generalization ability to unseen domains and datasets [36, 28, 83, 43, 72] . It is different from fine-tuning which focuses on a task-specific and often smaller dataset. Therefore, the (continually) pre-trained models possess strong few-shot (includign zero-shot) ability but may not be competent in specific functionality such as conversation, and vice versa for fine-tuned models like ChatGPT, Alpaca [76] , and Dolly [22] .Multiple DP pre-trained models have been developed [47, 24, 90] , but these models either (1) suffer from low accuracy, e.g. 6.9% on ImageNet-1k without additional data by [47] and 32.4% by [24] ; or (2) demand significantly more data and compute to match the non-DP pre-training, e.g. 100× in [90] when comparing DP ViP model to non-DP SimCLR; or (3) rely on uncommon tricks such as a huge batch size from 16-98K, that are not adopted in the standard deep learning community. Related to (3), we believe DP continual pre-training can further improve using the existing techniques from the non-DP continual training, including the replay mechanism and curriculum learning, and avoid catastrophic forgetting.Hessian-based analysis in deep learning Applying the second-order Taylor expansion of loss motivates the famous Newton's method and is commonly adopted in deep learning [57, 97, 85, 56, 91] , where the Hessian matrix is useful to analyzing the convergence and data efficiency (e.g. selecting the critical batch size [57] ), even though it is infeasible to derive H ∈ R d×d explicitly for large models. Our work follows the same path with a specific focus on DP related operations (i.e. the clipping and the noise). We use the Hutchinson method and Hessian-vector product to compute tr(H), HG and so on.To make DP deep learning broadly applicable, we believe it is necessary to not only evaluate DP algorithms on the utility, but also from a system design perspective.The design of a DP system, such as our DP continual pre-training, should resemble that of the standard non-DP system (see our extensive discussion in Remark 4.2). Such a design will be compatible to and benefit from new advances in the much larger non-DP literature, unifying DP and non-DP communities, instead of crafting techniques that are limited to DP learning only.Data distribution shift There may be some distribution shift between the public pre-training data and the private fine-tuning data or continual pre-training data. Empirically speaking, DP training can be robust to such distribution shift. For instance, DP fine-tuning has successfully transferred from ImageNet to CIFAR10, CIFAR100, SVHN, Food101, CelebA, FMNIST, GSTRB [14] , from JFT to ImageNet [24, 58] , and from Places365 to ImageNet [47] . Although this work does not address the distribution shift due to similarity between ImageNet-1k and ImageNet-11k, our analysis in Section 3, especially the formula of decelerator, still holds in this scenario. Therefore, we expect our DP continual pre-trainin to work withstanding the data distribution shift, as empirically demonstrated from Shaders to LAION [90] .The concurrent work -ViP [90] -also studies the DP continual pre-training, thus is the closest strategy to ours. We elaborate the similarity and differences between two strategies. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: No such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We cite properly. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?The mini-batch of size B (a.k.a. the logical batch size) is divided into B/b micro-batches, where the micro-batch size is b ≪ B (a.k.a. the physical or per-GPU batch size, which determines the training speed and memory cost). When b is fixed subject to GPU memory, the per-iteration training time is proportional to the number of micro-batches and thus to B.The optimal learning rate of DP-SGD cannot be used in practice because (i) the oracle G and H are unknown; (ii) it is data-dependent and hence violates the DP guarantee. Such an optimal learning rate is only used to help us understand the best possible per-iteration performance.ImageNet-11k improves the dataset quality and thus the resulting models (see Table3in[70]), by removing the infrequent classes from the full ImageNet-21k, thus remaining 78% of its 14M images and 48% of 21.8k classes.We observe that, using augreg (a supervised pre-training strategy) for public pre-training on ImageNet-1k and/or ImageNet-21k for private pre-training gives very similar result.For ImageNet-1k, we strike through some results because this dataset was used in the pre-training. It is only meaningful to compare our models to DINO and observe the benefit of continual pre-training, but not to others. 
 
 Appendix:  


Decision: While most of the reviewers were positive about the paper, there were a few concerns regarding the importance of the result, as pre-training DP models with public data is a well-studied problem. There were also concerns regarding some of the theoretical claims and the practical implementation of the DP continual pre-training approach. 

We would recommend the authors to include rebuttal discussion (mainly with reviewer wr8p) in a future version of the paper.

Reviews: review: paper_summary: paper_summary: This paper provides a theoretical framework to analyze impact of various aspects (parameters) of DP training on the performance of resulting models. The framework uses hessian of per-sample gradient to compute per-iteration loss improvement. Using the framework, the paper shows how DP impacts performance of model in pre-training more than during fine-tuning, and suggests using public data pre-training as a remedy. Finally, based on the observations, the paper proposes a DP continual learning and shows how it can help improve the performance of upstream and downstream tasks.
strength_weakness: strength_weakness: - Some assumptions, especially about clip norm, need more clarification 
- Some of the theoretical claims could be paired with empirical evidence
- Proposed continual pre-training approach needs better explanation
questions: questions: - It looks like the conclusions made in the paper rely heavily on the assumption about clip norm multiplier being the same for all per-sample grads. The assumption is because in Figure 1 performances of models with and without clipping are similar. But, why would this be always true? If clipping is very aggressive, it will introduce bias and performance will reduce much more than what we see in Figure 1. Maybe it is good to clarify the scope of the assumption.

- In the “Per-iteration improvement of DP-SGD” it says that parameter updates are generally small. When is this true in practice?  

- In Table 3, why do performances of many fine-tuning cases reduce from DINO to Ours(eps=2)? I think the performance should always improve? At the same time, few-shot performance of proposed method is significantly higher than DINO in all cases. Can you clarify this difference?
limitations: limitations: - Assumptions made in the work to set up the theoretical framework need better clarification in terms of the scope of theory.
- It would be good to formally write an algorithm of DP continual pre-training, as I found section 4.2 a bit confusing.
paper_summary: paper_summary: This paper proposed a Hessian-based analysis of the per-iteration loss for DP-SGD and non-private training, and provide a theoretical explanation for slower convergence of differentially private training. Authors identified the *decelerator* compontent in per-iteraton loss improvement, associated with the gradient clipping and noising, providing a theoretical backing for differences between DP impact on pre-training vs. fine-tuning. Using the same framework, authors also suggest the derivation for the optimal batch size for private training under the fixed computation budget (i.e. fixed number of samples processed), which strikes the balance between lower per-sample noise and training slowdown associated with growing batch size.

Based on this analysis above, authors suggest the impact of DP on convergence can be mitigated by public pre-training data. While using public pre-training data to complement DP fine-tuning has been explored before, authors emphasize the difference between fine-tuning and continual pre-training, provide a theoretical analysis for the optimal mixing proportion for private/public data, and evaluate their models after private continual pre-training on a downstream fine-tuning tasks.
strength_weakness: strength_weakness: The major weakness of the paper (at least its theoretical part) is the assumption that per-sample gradient clipping does not introduce bias into the gradient approximation (line 116). This is a very strong assumption, and something that, to the best of my knowledge, is not generally accepted in the field (e.g. see [this paper](https://proceedings.neurips.cc/paper_files/paper/2020/file/9ecff5455677b38d19f49ce658ef0608-Paper.pdf)). To justify the assumption authors point to Fig. 1, which to me doesn't look like it supports their claim - there's a significant difference between vanilla optimizer and optimizer + clipping in pre-training.

Additionally, the analysis in this paper assumes the oracle knowledge of matrices G (gradient expectaition) and H (Hessian). For practical applications where this is infeasible, it would be useful to look at, e.g. optimal batch size not only from an optimal loss perspective, but also take into account how well the batch gradient approximates the actual gradient G. 

Oh the evaluation side, I see a slight disconnect with the theoretical results. For instance, after the results in Sec. 4.1 it would be natural to explore different mixing ratios of public/private data in training - however authors only focus on a setup with fixed pre-training and continual training datasets. 

The results presented in Tables 3,4 and 5 do make a good case that the proposed approach is valid, but lack proper baselines. Comparisons are made either with non-private models, models trained on different dataset, or model trained for different number of epochs - contradicting the scenario with fixed compute budget.

Authors do not report compute resources used for the experiments, which is especially relevant for reproducibility of the paper's results, as it works with Hessian matrices which can be very computationally expensive to compute.
questions: questions: * I think the formatting for Fig.5 is wrong - in the text you refer to "upper left" plot, while in the submitted version it's rendered as a single line of 4 plots
* I would be interested in reading how did you compute the data for Fig.6 - did you explicitly compute full matrices `G` and `H` or used some approximations?
* I don't fully understand why in Fig.5 (pre-training) the blue dashed line is linear, suggesting that $G^THG$ is constant.
* In Table 2, a) does number of images include continual pre-training? and b) what does "non-privacy" column refer to?
* What is the criteria for distinguishing continual pre-training from fine-tuning? For example, in your experiments you perform continual pre-training with a different objective than earlier pre-training (supervised vs non-supervised). Does it not justify the "fine-tuning" term?
limitations: limitations: Authors do not discuss limitations explicitly, but are very upfront about assumptions they make (e.g. fixed compute budget, assuming no bias from clipping, etc). Authors also briefly mention limitations in the checklist (but not the main body of the paper).
paper_summary: paper_summary: This paper addresses the challenge of DP pretraining, which has been limited due to performance degradation. The authors first analyze per-iteration improvements of the optimization process and then propose a novel DP continual pre-training strategy that uses a small amount of public data to mitigate the negative effects of DP noise. They then empirically demonstrate the effectiveness of their approach on large-scale vision models.
strength_weakness: strength_weakness: - The authors claim that *a certain amount of public data can mitigate deceleration*. However, Section 4 lacks discussion about deceleration. The given claim is that per-iteration improvement is increased, which is obvious given public data. Also, it's unclear why *limited* public data is emphasized, as the analysis does not involve public sample sizes. This makes the article somewhat incoherent, as the interesting theoretical analysis in Section 3 does not provide strong suggestions for the methodology.
- The experiments lack some ablation studies to support the key methodological proposal.
- Citations should be updated to published versions rather than arXiv preprints where possible.
- In line 14, there's an extra "and".
questions: questions: Overall, this paper is interesting. I am happy to raise my score if some of the questions are addressed. 


- Can the authors provide some comments on the first weakness?
- Section 3.3 is somewhat confusing. First, Remark 3.1 investigates the differences between pre-training and fine-tuning by comparing $B_{non-DP} G^{\top} H G$ and $tr(H\Sigma)$, while in fact, public per-iteration improvement is monotonic with respect to $B$. Why use a comparison between $B_{DP}$ and $B_{non-DP}$ for deriving the explanation? Also, can the authors more rigorously explain what is meant by "data-efficient"?
- Moreover, the difference between public improvement (7) and private improvement (6) lies in the decelerator $\sigma^2 tr(H) / (Bc^2)$, which seems smaller for pre-training where the loss landscape is flatter and thus the curvature $tr(H)$ is smaller. What is wrong with this intuition?
- It is observed that prediction accuracy is linear in $\log B$, for instance in Figure 4 in [1], while the statement here is that $B$ should be moderately chosen. Though these are not the same quantity, could the authors comment on the impact of $B$ on DP-SGD?
- Based on analysis in Section 3, is there any off-the-shelf rule for choosing $B$? 
- Can the authors provide some ablation studies (can be on toy datasets) on the impact of $s$?



[1] Tom Sander, Pierre Stock, and Alexandre Sablayrolles. Tan without a burn: Scaling laws of dp-sgd. In International Conference on Machine Learning, pages 29937–29949. PMLR, 2023.
limitations: limitations: The limitations should appear in the main text.
paper_summary: paper_summary: This work theoretically justifies the loss of utility under DP pre-training under the lens of a Hessian. This theoretical result can then be leveraged to perform efficient pre-training of models on public data (small amount) to significantly improve DP-trained model's performance.
strength_weakness: strength_weakness: My fundamental issue with the positioning of this work is that we already know that public data improves DP - [1,2,3,4,6]. We also know that DP training during pre-training is harming utility more than it would have harmed the pre-trained model [2,3,4]. Therefore my question is what is the main scientific output of this paper? The conclusions are already widely established and I do not see any new outcomes that can be derived from the conclusions of this work. It would have been interesting to see if this result it linked to model's generalization/memorization capacities as described in [5], showing some novel contextualized understanding of the training dynamics, but there was no discussion on the interplay of the training time and memorization capacity under DP.

The theoretical justification of why this phenomenon arises is indeed interesting and can be useful, but on its own does not provide any novel insights into the training process that are 'actionable'. This is, again, because it was already previously established that a) DP pre-training harms utility [1,6,7], b) public data aids utility of DP models [2] and c) when models are untrained, they are more susceptible to various phenomena that can affect the training dynamics (e.g. loss of information via clipping [5]). So I am struggling to understand what can one gain from the results of this work? The 10% data threshold is a purely empirical result, which may or may not scale to other settings and datasets.

[1] - Bu, Zhiqi, Jialin Mao, and Shiyun Xu. "Scalable and efficient training of large convolutional neural networks with differential privacy." Advances in Neural Information Processing Systems 35 (2022): 38305-38318.
[2] - Kurakin, Alexey, et al. "Toward training at imagenet scale with differential privacy." arXiv preprint arXiv:2201.12328 (2022).
[3] - Nasr, Milad, et al. "Effectively using public data in privacy preserving machine learning." International Conference on Machine Learning. PMLR, 2023.
[4] - Ganesh, Arun, et al. "Why is public pretraining necessary for private model training?." International Conference on Machine Learning. PMLR, 2023.
[5] - Feldman, Vitaly. "Does learning require memorization? a short tale about a long tail." Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 2020.
[6] - Mehta, Harsh, et al. "Large scale transfer learning for differentially private image classification." arXiv preprint arXiv:2205.02973 (2022).
[7] - Mireshghallah, Fatemehsadat, et al. "Differentially private model compression." Advances in Neural Information Processing Systems 35 (2022): 29468-29483.
questions: questions: Can the framework be used to explain the reason behind DP being 'more difficult' for untrained models through the prism of memorization?

Is there a more theoretically sound way to define the threshold of public data that is required for appropriate performance?
limitations: limitations: As outlined above: while the theoretical justification of the results is indeed interesting, there are no novel conclusions our takeaways from this work that we have not previously had from similar works in the area of DP training.

Comments: title: Thanks for the response!
Response to the rebuttal
comment: We agree "ignorable" is over-stating and that clipping bias is indeed important to DP training. We will surely add the clarification in next revision.
Thanks for the detailed rebuttal.

> We agree that gradient clipping definitely introduces bias to the gradient approximation, but the extent of the bias is less significant and hence ignorable, compared to the effect of DP noising <...> We are using this assumption to prioritize the analysis of noising (which leads to trace of Hessian and decelerator), which is necessary to simplify our analysis.

I understand the author's point to prioritize the noise over clipping in their analysis. I agree it is justifiable and provide a foundation for the important theoretical analysis presented in the paper. I would not, however, call the clipping bias "ignorable" - I would argue that it remains an important direction for future research to understand the DP training dynamics.

I also appreciate clarifications provided, they were useful for me to understand the paper better.

Overall, I believe it's a strong paper and choose to maintain my high score.
Thanks for the response. Rebuttal clarifies my questions and concerns, and i have raised my score accordingly.
Thanks for the detailed clarification and I have updated my score.
Thank you for joining the discussion! We understand your concern that the clipping bias may be non-ignorable in some settings that we haven't covered. From our experience with DP model training in all projects that consist of hundreds of experiments, we always observe that "clipping without noising" gives similar performance to non-DP empirically. Nevertheless, we can not rigorously claim this regardless of how many settings/experiments we test. Hence we would state "this analysis only approximates the scenario where the clipping introduces ignorable bias, e.g. when the clipping threshold is large or when unbiased clipping is used (c.f. 'Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach')". 

Additionally, we highlight that our connection between tr(H) and noising (to which we attribute the slowdown of DP) still holds even if we take the clipping bias into consideration: Equation (5) will become
$$\Delta L_\text{priv}=\eta\hat{G}^\top G-\frac{\eta^2}{2}\left(\hat{G}^\top H \hat{G}+\frac{tr(H\hat{\Sigma})}{B}+\frac{\sigma^2 tr(H)}{B^2}\right)$$
where the hat stands for **biased gradient** from per-sample clipping.

Regarding the actionable items specifically from our results, we would recommend noise reduction like low-pass filtering (we are working on it) and sharpness-aware minimization (to reduce tr(H), known as the sharpness). It would also be desirable to experiment our DP continual training on more settings such as NLP. Happy to extend the discussion!

Given that this work is on the borderline, we would appreciate it if the reviewer can consider raise the score.
I would like to thank the authors for their responses! I still have some points I would like to note.

From the discussion with reviewer JCrd I am not sure I agree with your response to them:

>  the extent of the bias is less significant and hence ignorable, compared to the effect of DP noising

This may very well be the case for the specific settings of your experiments, but I am not convinced this is a general 'rule' you can follow and claim that this bias is 'ignorable'.

>  and noise reduction (e.g. via tighter privacy accounting in Implication 2.3)

When I said 'actionable results', telling the community to use better DP tools (i.e. tighter accountant) is not really something actionable from YOUR results (i.e. we would always use the tightest accounting all else aside anyway).

After reading the rest of the response, I am keeping my score unchanged.