On the Benefits of Public Representations for Private Transfer Learning under Distribution Shift

Authors: pratiksha  thaker
amrith  setlur
zhiwei steven wu
virginia  smith
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:48:58

Abstract: Public pretraining is a promising approach to improve differentially private model training. However, recent work has noted that many positive research results studying this paradigm only consider in-distribution tasks, and may not apply to settings where there is distribution shift between the pretraining and finetuning data---a scenario that is likely when finetuning private tasks due to the sensitive nature of the data. In this work, we show empirically across three tasks that even in settings with large distribution shift, where both zero-shot performance from public data and training from scratch with private data give unusably weak results, public features can in fact improve private training accuracy by up to 67\% over private training from scratch. We provide a theoretical explanation for this phenomenon, showing that if the public and private data share a low-dimensional representation, public representations can improve the sample complexity of private training even if it is \emph{impossible} to learn the private task from the public data alone. Altogether, our results provide evidence that public data can indeed make private training practical in realistic settings of extreme distribution shift.

Main paper: 
 introduction: 
 Learning models from user data can potentially disclose sensitive user information, violating privacy constraints [1] [2] [3] . Differential privacy is a standard framework that can be used when learning models from sensitive data to mitigate the risk of leaking private information [4] . However, differentially private learning may significantly degrade accuracy, which remains a barrier to adoption [5] . This has motivated recent works to explore the benefits of incorporating publicly available data into private training, e.g., by pretraining a model on public data and then finetuning it using private data. Empirically, this paradigm has been shown to substantially improve performance on private tasks relative to fully-private training [6] [7] [8] [9] [10] [11] [12] [13] .While these results are encouraging, Tramèr et al. [14] point out that much of the existing work focuses on in-distribution tasks, where the public and private tasks are very similar. For example, many private vision models [15] [16] [17] [18] [19] use public features pretrained on ImageNet [20] , CIFAR-10 or CIFAR-100 [21] , but these works also simulate private transfer performance by finetuning on one of these datasets. In fact, Tramèr et al. [14] point out that "every single class contained in the CIFAR-10 dataset has an identical class label in the ImageNet dataset!" This is particularly problematic when attempting to understand the utility of public pretraining for private tasks, because in practice the private task is likely to contain sensitive data that is not perfectly represented by public data, such as in applications in medicine [22] or law [23] . Indeed, if data is already well-represented in a public dataset, the zero-shot performance of a model trained only on public data should be good enough that no private "transfer" learning is required, potentially making these benchmark datasets uninformative for evaluating the benefits of transfer learning.From a practical perspective, it is particularly important to understand transfer learning in the private setting: if a non-privacy-sensitive task is poorly represented by the pretrained features, one solution might be to simply add the data from that task into the public training dataset and learn a more general set of features for downstream use. But privacy-sensitive data cannot be used to train a public backbone, and individual private datasets often cannot be combined or shared. Thus, the ability to leverage public features to improve the sample dependence of private learning is critical.Our contributions. In this work, we provide evidence to alleviate these concerns, showing theoretically and empirically that public pretraining can be helpful even in settings with realistic and possibly extreme distribution shift between public (training) and private (transfer) tasks. In particular, we focus on concept shift, where the conditional distributions P (Y | X) can vary drastically between public and private tasks. Our results are summarized as follows.First, we conduct empirical case studies 1 on three datasets to show that public features improve private training accuracy even under extreme distribution shift. In particular, we use a pretrained CLIP ViT-B vision model for public features and measure the accuracy of private transfer learning on datasets including the PatchCamelyon (PCam) [24] , Functional Map of the World (fMoW) [25] , and Remote Sensing Image Scene Classification (RESISC45) [26] . On all three datasets, the pretrained model has unacceptably low zero-shot accuracy (random guessing on both PCam and fMoW), indicating that "perfect privacy" with zero-shot queries is likely hopeless. In comparison, on CIFAR-10, the CLIP ViT-B/32 model achieves 91.3% zero-shot accuracy [27] , making transfer learning performance far less relevant as the zero-shot accuracy is already high. We observe that across all datasets, private finetuning and linear probing using public features outperform differentially training from scratch -by up to 67%. In addition, private linear probing consistently outperforms private finetuning.Motivated by our empirical results, we provide a stylized theoretical model to understand and explain our findings. We study a simple linear transfer learning model, a common theoretical model in the non-private meta-learning literature [28] [29] [30] [31] [32] [33] [34] , to show the statistical benefit of learning a shared, lowdimensional representation (in our model, a low-rank linear subspace) using public data. Our transfer learning model captures an extreme form of concept shift in the sense that the target model on private data is entirely different from those on public data, even though they are all contained in the same subspace. Analogous to the paradigm of public pre-training then private linear probing, we analyze a simple twostage algorithm that (1) first estimates the shared, low-dimensional representation (or subspace) from a diverse set of tasks in public data, and (2) performs private linear regression within the learned subspace. By leveraging the dimensionality reduction, we provide a better sample complexity that scales with the rank of the shared subspace instead of the ambient dimension of the features. To complement this sample complexity bound, we also show a novel lower bound that shows that our bound is tight among algorithms that search for regression parameters within a fixed low-rank subspace estimate.In short, our findings provide optimistic insights regarding the concerns raised by Tramèr et al. [14] . Specifically, Tramèr et al. [14] suggest that "current methods for large-scale pretraining may be less effective." In contrast, our results indicate that pretrained features can indeed benefit private learning, even under concept shift. Additionally, our findings address another concern from Tramèr et al. [14] regarding the necessity of uploading private data to cloud services for finetuning large models due to high resource requirements. We demonstrate that training a linear probe privately is more effective, potentially requiring significantly fewer resources (both memory and computation) than finetuning a full model. 
related work: 
 Empirical studies of public pretraining for private learning. As Tramèr et al. [14] point out, existing empirical studies on public pretraining for private learning largely focus on transfer between similar datasets. For example, [15] [16] [17] [18] [19] 35] pretrain on CIFAR-100 or ImageNet and finetune on CIFAR-10 or STL-10 (a dataset very similar to CIFAR-10). [8] pretrains on Places365 and finetunes on ImageNet. [18, 36] pretrain on JFT and finetune on ImageNet. Finally, [37, 38, 9, 39] pretrain and finetune on publicly available text on the Web.All of these works build evidence that pretraining could be beneficial for private learning. Unfortunately, because the public and private tasks are so similar, these results are unlikely to be representative of real-world private training in which the private task requires learning a model on sensitive data with a very different distribution from data available on the Web.Recent work [40] evaluates their algorithm on private learning tasks that are out-of-distribution for the feature extractor they use, including the PCam dataset that we also study. However, their algorithm requires access to (nearly) in-distribution public data in order to learn a projection matrix into a low-dimensional space. We argue that this is a strong and unrealistic assumption considering the arguments put forth in Tramèr et al. [14] that private data, because of its sensitive nature, will not be well-represented by public datasets. Our work instead focuses on understanding the improvements from using off-the-shelf feature extractors, with no in-distribution public data, over fully-private learning.Transfer or meta-learning. Our results build on the framework of Tripuraneni et al. [28] for nonprivate transfer learning with a low-dimensional subspace. This linear, low-dimensional subspace assumption has been studied extensively in the nonprivate meta-learning literature as a tractable model for real shared representation learning [28] [29] [30] [31] [32] [33] [34] . However, none of these works consider the setting of public subspace estimation followed by private transfer learning. PILLAR [40] makes a shared subspace assumption in the private setting, but on the input features rather than on the models.Private algorithms that leverage public data. A number of prior works have theoretically studied the benefits of public data in other settings, including mean estimation [41] , query release [42] [43] [44] , and optimization when gradients lie in a low-rank subspace [45] [46] [47] . Kairouz et al. [45] in particular gives a similar analysis using the principal angle error of the subspace, but the analysis does not apply directly as we assume that models, rather than gradients, lie in a shared low-dimensional subspace. As a result, the algorithm in that work requires expensive subspace oracle calls on every iteration and would be computationally suboptimal in our setting.Finally, as discussed earlier, pretraining has empirically been shown to be useful in a number of domains, including vision [6] [7] [8] and NLP [9] [10] [11] [12] . While our work does not model the complexities of neural networks, we can understand our results as a stylized version of finetuning in which the public network is tuned with linear regression on the last layer, potentially giving insight into these more complex models.Theoretical analyses of pretraining for private learning. Ganesh et al. [35] provides a lower bound construction for a related setting in which public data is abundant and the private task is out of distribution, though does not consider the case where the public and private task explicitly share structure. In our setting, learning from the public data alone provides no guarantees on the transfer task, as we do not assume any bounded shift in the data distributions or target parameters between the public tasks to the private tasks; the key information enabling more efficient learning is the shared structure among the tasks. PILLAR [40] incorporates public pretraining, but their analysis focuses on the benefits of dimensionality reduction using in-distribution public data, rather than transfer from out-ofdistribution public data. Finally, Ke et al. [19] study the tradeoffs between linear probing and finetuning in the private setting. While their empirical results focus on the in-distribution image recognition settings outlined previously, their theoretical results corroborate our findings that even under extreme distribution shift, linear probing is more effective than finetuning under differential privacy.k = ± 1-i∈[k-1] ω 2i with equal probability for either sign. 
preliminaries: 
 Notation. Throughout the paper, we use lower-case v for vectors, upper-case V for matrices and calligraphic V for sets. Generally, we use the "hatted" notation B, α to refer to estimates of the underlying population variables. The use of O,Ω,Θ is standard and Õ, Ω hides polylog factors in quantities we specify separately. We use ∥•∥ F for Frobenius, ∥•∥ op for operator and ∥•∥ p for ℓ p norms.Differential privacy (DP) is a quantitative constraint on the information gained from a released statistic [48] . Definition 3.1 restates the standard (ε,δ)-differential privacy introduced in [4] . Definition 3.1 ( (ϵ,δ)-differential privacy [4] ). Given ϵ ≥ 0, δ ∈ [0,1] and a neighboring relation ∼, a randomized mechanism M : X n → Y from the set of datasets of size n to an output space Y is (ϵ,δ)-differentially private if for all neighboring datasets S ∼ S ′ ⊆ X , and all events E ⊆ Y,Pr[M(S) ∈ E] ≤ e ϵ •Pr[M(S ′ ) ∈ E]+δ.Here, probabilities are taken over the random coins of M.The "neighboring" relation differs according to the desired privacy guarantee. In this paper, we will study row-level privacy in which neighboring datasets S ∼ S ′ differ in a single element.We will study a setting in which the learner first sees n 1 public samples (x i ,y i ), possibly drawn from multiple different underlying tasks (i.e., sample distributions) P 1 ,...,P t , and then sees n 2 private samples from a new task P t+1 . The goal is to learn a predictor f : R d → Y that maps inputs x ∈ R d to outputs y ∈ Y with the constraint that f must satisfy (ε,δ)-differential privacy. We aim to minimize the population loss on the private task:EQUATIONThe private learner may or may not use the public samples. We assume the samples are drawn i.i.d. conditioned on the task, but make no other assumptions on the task distribution or the number of samples drawn from each task. In Section 5, we develop a theoretical model of the relationship between the public and private tasks that allows the learner to effectively leverage information from the public tasks to improve private learning.Similarly, we can define a class of misspecified linear regression problem instances. We use P 2stg (d,k,γ) to denote the following class of problem instances for the private task t+1:1. The input product distribution over (x,y) is given by the model in (2) , and additionally the noise η ∼ N (0,σ 2 ). 2. Let the true regression vector be Bα t+1 . A subspace B is known such that: sinθ( B,B) ≤ γ.Also, α t+1 ∈ R k . 3. The i.i.d. sampled dataset S from the above model satisifies: ∥x∥ 2 ≤ 1 for every x ∈ S.In the above, both B and B are d×k matrices with orthonormal columns, i.e., B, B ∈ Gr k,d (R), where, Gr k,d (R) is the Grassmann manifold [66] and consists of the set of k-dimensional subspaces within an underlying d-dimensional space. Also, for both M 2stg (ϵ,δ,γ),P 2stg (d,k,γ) we omit the dependence on B, which is fixed. We note here that our proof works for any fixed B. Now, we are ready to restate our Theorem 5.5.Theorem 5.5 (Two-stage single-task private transfer lower bound). Let M be an (ε,δ)-DP private algorithm where ε ∈ (0,1), δ < 1 /n 1+ω , ω > 0, that takes as input: (i) publicly estimated subspace Bpub from an oracle that only uses public samples; and (ii) a dataset S of n 2 private samples. For any such M , there exists a private problem instance given by the pair (B,α t+1 ) where B ∈ Gr k,d (R), α t+1 ∈ R k , sin θ(B, Bpub ) ≤ γ, and ∥Bα t+1 ∥ 2 ≤ 1, such that for S sampled i.i.d. from this instance using the model in (2), we have:EQUATION)Proof. Given the estimate B, the goal is to lower bound the following minimax risk:EQUATIONLet us begin by defining the class of regression vectors constiuting the set of all possible Bα t+1 that can be realized by a problem instance in P 2stg (d,k,γ). Given some rank k subspace defined by the matrix B ∈ Gr k,d (R), we define the following set of d-dimensional ℓ 2 norm bounded vectors that are γ ≤ 1 close to given B:EQUATIONFrom the definition of the principal angles and P 2stg (d,k,γ) it follows that for any θ ∈ θ(B,γ):∥ Bθ∥ 2 ≥ 1-γ 2 ⇐⇒ ∥(I d -B B⊤ )θ∥ 2 ≤ γWe can break the above set Θ( B,γ) into disjoint sets:Θ( B,γ) = ρ∈[ √ 1-γ 2 ,1] Θ ρ ( B), where Θ ρ ( B) is defined as:Θ ρ ( B) =: θ ∈ Θ( B,γ) : ∥ Bθ∥ 2 = ρ (22)The above subclass of regression vectors results in a convenient subclass of problem instances class P 2stg (ρ). Just as we did for P 2stg (d,k,γ), we can define the following minimax risk for P 2stg (ρ).infEQUATION)Based on the above definitions we get:EQUATION= infEQUATIONEQUATION)where the final inequality uses inf sup ≥ sup inf [67] . We can do this because inf and sup are defined over non-empty sets and the loss function remains bounded over the product space M 2stg (ϵ,δ,γ)× Θ ρ ( B). The loss function is bounded because the norm of the regression vector and the input covariates is bounded. Further, the linearly independent noise η in y (2) has finite variance.For the next part of the proof, we focus on lower bounding the minimax risk in ( 23) when the adversary is searching over the set Θ ρ ( B). The lower bound for the minimax risk over this subclass is given by two parts: (i) statistical error rate that is suffered by any non-private algorithm for which we lower bound hypothesis testing lower bounds; and (ii) the risk suffered by any (ε,δ)-DP private estimator which we lower bound by constructing a tracing attack. We will begin the proof for the latter part and then plug in standard statistical risk lower bounds.The following Lemma D.2 (proven later) states a lower bound over the class P 2stg (ρ).Lemma D.2 (Lower bound for P 2stg (ρ)). For any fixed B and any (ε,δ)-DP private algorithm M (where 0 < ε < 1, δ < 1 /n 1+ω for some ω > 0) that belongs to class M 2stg (ϵ,δ,γ), there exists a problem instance for the transfer task in the class P 2stg (ρ) such that for the B,α t+1 given by the problem instance:EQUATION)We can now come back to (27) and compute the supremum over ρ after plugging in the lower bound in Lemma D.2. Since ρ ≥ 1-γ 2 , plugging in this value for ρ in Lemma D.2, and from the minimax risk lower bound on P 2stg (d,k,γ) in ( 27), we obtain the result in Theorem 5.5.Proof. The proof for the subclass lower bound relies upon re-parameterizing the problem instance as a k-dimensional linear regression in the problem, but now in the column span of B.Let the worst case in instance in P 2stg (ρ) be θ = Bα t+1 , where ∥ B⊤ θ∥ 2 = ρ. We shall derive a low-dimensional linear regression problem posed by the the unknown worst case instance θ, and the projected inputs: x → B⊤ x. Recall that the joint data distribution for private samples is given by:EQUATIONEQUATIONAdditionally, we also recall that the learning algorithm is given n 2 private i.i.d. samples from the above distribution S =: {(x i ,y i )} n i=1 . In addition, it is also given a rank k matrix with orthonormal columns: B ∈ Gr k,d (R) that is close to the unknown low rank subspace B, i.e., sinθ( B,B) ≤ γ =⇒ ∥(I d -B B⊤ )B∥ 2 ≤ γ. Next, we write each sample in S in terms of the projection of the regression vector Bα on to the column span of B, when the input x is also projected in the following way: x → Bx:EQUATIONwhere α := B⊤ Bα is a k-dimensional vector in the column span of the given subspace B.For any output M (S, B) for an algorithm in M 2stg (ϵ,δ,γ), from the independence of the two projections: B B⊤ x and (I d -B B⊤ )x argued in Lemma C.1.:EQUATIONSince, the norm of θ in the nullspace of B can be chosen without affecting the hardness of the above rejection problem, the worst case problem instance will maximize the additive error by picking any component along the null space (note that direction along null space does not impact the regression error) that has the maximum norm of 1-ρ 2 (recall that for any θ ∈ P 2stg (ρ), ∥θ∥ 2 ≤ 1). Now, from (31) it follows that the i.i.d. samples in S for the worst case instance are drawn from the following low-dimensional linear regression model:x ∼ N (0,I d )EQUATIONFrom the above model in (33) and equivalence in (32) , we have the following equality for the minimax risk over P 2stg (ρ).infEQUATIONwhere S = {(x B i ,y i )} n2 i=1 and y i = α⊤ x B i +z i , where z i ∼ N (0,σ 2 +1-ρ 2 ). Our main technique for proving lower bounds for the minimax risk in (34) is based on the tracing adversary technique proposed by [59] . Next, we prove that there exists a prior over the effective regression vector α, and a tracing attack that is successful in recovering an element of the i.i.d. sampled dataset S, in expectation over the prior and the dataset. Consider the following tracing attack:EQUATIONSimilar to the tracing attacks for mean estimation problems [58] , Lemma D.3 proves that the attack A α((y, x B ), M (S)) takes large value when (x B , y) belongs to S and small value otherwise. We compare the attack success with estimation error, and show that whenever the estimation error is small, the attack has to be fairly successful. Since, we are only searching over private algorithms where the attack takes small values, this yields a lower bound on the estimation error.The minimax lower bound stated in Lemma D.2, i.e., the lower bound for the minimax risk over subclass P 2stg (ρ) (for a fixed ρ), is given by the summation over two terms: the statistical lower bound and a second term implied by the tracing attack sucess lower bound stated in Lemma D.3 (proven later).Lemma D.3. For any fixed 0 < σ, 1-γ 2 ≤ ρ ≤ 1, (B, α) satisfying sin θ( B, B) ≤ γ, and ∥α∥ 2 = ∥ B⊤ Bα∥ 2 = ρ ≤ 1, let (x B ,y) be an i.i.d. sample (and S a dataset of n 2 i.i.d. samples) drawn from the distribution defined in (33) . Then, for every (ε,δ)-differentially private estimator M that takes as input S, B and satisfies E S|B,α,σ,ρ ∥M (S, B)-α∥ 2 2 = o(1), for every α, the following are true:1. For each i ∈ [n], let S ′ i denote the data set obtained by replacing (x B i , y i ) in S with an independent copy from the distribution in (31) , then EA α((x B i ,y i ),M (S ′ i )) = 0 andE |A α((x B i ,y i ),M (S ′ i , B))| ≤ ( σ 2 +1-ρ 2 )• E∥M (S, B)-α∥ 2 2 .2. There exists a prior distribution of π = π(α) supported over α ∈ R k such that α = ρ, andi∈[n] E α∼π E S| α,ρ,σ A α((x B i ,y i ),M (S i , B)) ≳ (σ 2 +1-ρ 2 )•(k-1).From Lemma C.2 and from the first part of Lemma D.3,i∈[n] E S| αA α((x B i , y i ), M (S, B)) ≤ 2n 2 ε σ 2 +1-ρ 2 E S| α∥M (S, B)-α∥ 2 2 +2n 2 δT +n 2 ∞ T P |A α((x B i , y i ), M (S,B))| > t .For the tail probability term,P |A α((x B i , y i ), M (S, B))| > t = P   y i -x ⊤ i α k-1 j=1 (M (S, B) j -αj )•x B j > t   ≤ P y i -x ⊤ i α ∥α∥∥x B ∥ > t ≤ P y i -x ⊤ i α √ k > t ≤ 2exp -t 2 2k(σ 2 +1-ρ 2 ).By choosing T = 2(σ 2 +1-ρ 2 )klog(1/δ), we obtain i∈[n] E S| αA α((x B i , y i ), M (S, B)) < ∼ 2n 2 ε σ 2 +1-ρ 2 E S| α∥M (S, B)-α∥ 2 2 +O n 2 δ σ 2 +1-ρ 2 )klog(1/δ) .Now plugging in the second part of Lemma D.3 gives us 1+ω) for ω > 0, for every (ε,δ)-differentially private M we have(σ 2 +1-ρ 2 )k ≤ E π i∈[n] E α∼π E S| αA α((x B i , y i ), M (S, B)) < ∼ 2n 2 ε σ 2 +1-ρ 2 E π E S| α∥M (S)-α∥ 2 2 +O n 2 δ (σ 2 +1-ρ 2 )klog(1/δ) . Since δ < n -(EQUATIONAdding the statistical lower bound of k(σ 2 +1-ρ 2 )n2to the lower bound from (36) , and from (34), we complete the proof of Lemma D.2.Proof. Let us begin by looking at EA α((x B i ,y i ),M (S ′ i , B)), where we use the fact that yi -(x B i ) ⊤ α is independent of x B i , and E[y i -(x B i )] = 0: EA α((x B i ,y i ),M (S ′ i , B)) = E   (y i -(x B i ) ⊤ α) k-1 j=1 (M (S ′ i , B) j -αj )x B i,j )   = E (y i -(x B i ) ⊤ α) k-1 j=1 E[M (S ′ i , B)-αj ]E[x B i,j ] = 0• k-1 j=1 E[M (S ′ i , B)-αj ]E[x B i,j ] = 0This proves the first claim about the expected value of the attack when the datapoint is not a part of the training set, i.e., EA α((x B i ,y i ),M (S ′ i )) = 0. Next, we look at the expected magnitude of the same random variable and upper bound it with a term that scales with the estimation error.EQUATIONwhere the last inequality uses the following derivation:E ((y i -(x B i ) ⊤ α)) 2 = σ2 = σ 2 +∥(I d -B B⊤ )Bα∥ 2 2 = σ 2 +1-ρ 2This completes the proof for the first part of the Lemma. For the second part we will begin by constructing a convenient prior for α.Note that α can take any value in the column span of B if the adversary has complete control over B and α. Thus, defining a prior over α would involve defining a prior over the column span of B such that ∥α∥ 2 = ρ. We define a sample from the prior π as a multi step procedure:1. For all i ∈ [k-1], sample ω i from the truncated Gaussian, with mean 0, variance ρ 2 /(k-1), and truncation at points -ρ / √ k-1 and ρ / √ k-1.= i∈[k] ω i •v i , where v i is the i th column of B. Consequently, α = B⊤ Bα = [ω 1 ,ω 2 ,...,ω k ] ⊤ .For the second part of the claim we need to lower bound i∈[n] E α∼π E A α((y i ,x B i ), M (S)) α which we can decompose over co-ordinates in the following way:EQUATIONwhere the final equation uses the log-derivative trick.Next, we focus on E α∼π∂ ∂ αj E[M (S, B) j ] for any j ∈ [k -1].Recall, that for any dimension j ∈ [k -1], the prior π draws a sample from the Gaussian N (0, ρ 2 /k-1), truncated at ρ / √ k-1, ρ / √ k-1 independently. We will now apply Stein's Lemma (see Lemma C.3) for the termE α∼π ∂ ∂ αj E[M (S, B) j ] .Denoting α-j as the set {α j } k j=1 \{α j }, and π j as the marginal prior over j th dimension of αj , we can lower bound E α∼π ∂ ∂ αj E[M (S) j ] in the following way:EQUATIONNext, we use the density of the truncated Normal:π j ( αj ) = exp -(k-1) 2ρ 2 • α2 j √ 2π ρ / √ k-1•(Φ(1)-Φ(-1)), where Φ(•) is the CDF function for a standard Normal distribution. Thus,π ′ j ( αj ) πj ( αj ) = -(k-1) ρ 2 αj .Substituting the above and applying Cauchy-Schwarz followed by Jensen's inequality we get,EQUATIONFrom directly applying the density of the truncated Normal distribution we get,EQUATIONPlugging ( 40), ( 39) into (38) , and using (37) we get,EQUATIONNote that E α∼π k-1 j=1 Justification: The assumptions for the theorems are provided in Section 5.1, and the proofs are provided in the Appendix.• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
public data improves out-of-distribution private transfer: 
 We begin by studying three datasets and show empirically that public data can provide benefits for private transfer learning even when the public data alone gives unusable zero-shot results on the private task. Each of the tasks we evaluate on has unusably low zero-shot performance on CLIP [27] , indicating that these are highly out-of-distribution relative to the pretraining data. This directly contrasts with existing work: the CLIP model that we use (pretrained with LAION-2B) achieves 66.6% zero-shot performance on ImageNet and 93.5% accuracy on CIFAR-10.PatchCamelyon. The PatchCamelyon (PCam) medical images dataset is a binary lymph node tumor detection task highlighted by [14] . [14] point out that CLIP [27] as well as other similar text-vision models [22] have notably poor zero-shot performance on PCam: CLIP ViT-B/32 achieves 51.2%, or close to random, in our evaluation. The poor zero-shot performance (relative to tasks like ImageNet or CIFAR) indicates that the task is truly "out of distribution" in comparison to the source (public) data. Moreover, being medical image data, PCam more faithfully represents a highly privacy-sensitive dataset.While the next two datasets are not medical image datasets, they are widely studied distribution shift datasets that have poor zero-shot performance on the training data, making them suitable for understanding transfer learning performance. In particular, they are remote sensing datasets; Wang et al. [49] analyze LAION-2B and find that only 0.03% of samples are remote sensing images, another strong indication that this data is underrepresented in pretraining.fMoW. The Functional Map of the World (fMoW) dataset [25, 50] the weights, while for pretrained features, we use OpenCLIP [52] models initialized with weights pretrained using LAION-2B (a 2B-sample subset of LAION-5B [53] ). We use the Opacus library [54] to implement private training. For each training setting we performed a hyperparameter sweep over learning rate ({1e-6,...,1e-2}) and number of epochs (1-10 for full training and 1000-2500 for linear probing), and for private learning, clipping norm ({0.5,1.0,2.5,5.0}). For both private and nonprivate models, we evaluate training from scratch, full finetuning, and linear probing. We train private models for ε ∈ {0.3,0.4,0.5,1.0,2.0,5.0} for each training setting. For PCam and RESISC45, we use SGD with momentum (parameter 0.9), while for fMoW we found that Adam gave better performance [55] . We use a cosine learning rate schedule for all experiments and a batch size of 32. Each finetuning run is performed on an A100 or A6000 GPU. Across all datasets, we find that any type of finetuning significantly outperforms training privately from scratch. This indicates that the pretrained features are indeed contributing to training accuracy. Further, we find across all datasets that linear probing (fixing the pretrained features) outperforms full finetuning, sometimes by a large margin, as in the case of RESISC45. This finding is consistent with theoretical work [19] that models the benefits of linear probing over finetuning under differential privacy. This is also consistent with earlier empirical findings on (in-distribution) private finetuning [8] .The key takeaway is positive: that features that work well for nonprivate transfer learning also benefit private transfer learning even when the distribution shift is large. While the conclusions are similar, these results are especially important in the private setting: training models from scratch with strong privacy is simply infeasible for many tasks, resulting in only around 10% test accuracy for fMoW and RESISC at small values of ε.To further support our results, we additionally evaluate linear probing for all three datasets with features pretrained on a 14M subset of Datacomp-1B [56] in Figure 2 . The trends in this setting are the same and linear probing still outperforms private training from scratch on all datasets, but the smaller pretraining dataset leads to lower-quality features that impact the final accuracy of linear probing.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: The experimental setup is provided in Section 4.2.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. Justification: Our work contributes to the theory of differentially private learning, which is essential to preserving user privacy under increasing amounts of data collection. Our work has the potential benefits of making private learning more practical by incorporating public data. However, we echo cautions pointed out in recent work [14] that care must be taken to ensure that publicly available data does not contain sensitive information for real deployments, and applying our techniques without such measures could inadvertently leak sensitive information. 
theoretical model: 
 Our empirical results show that even when distribution shift is extreme, public pretraining can indeed improve the accuracy of private training. In order to explain this observation, we study a simplified linear regression setting in which the goal is to estimate regression parameters privately for a single, unseen private task. This setting has been studied extensively in the nonprivate meta-learning literature as a theoretically tractable model to explain results on larger models [28] [29] [30] [31] [32] [33] [34] , and we propose a novel extension to the private setting that helps explain our empirical findings.We show that if the regression parameters for the private task lie in a low-dimensional subspace that is shared with the public tasks, the learner can use the public data to efficiently estimate the lowdimensional subspace, project the private data into the subspace, and thus achieve private estimation error rates that match optimal private linear regression rates (up to constant factors) in k dimensions (rather than d dimensions), with an additive term that accounts for the error in estimating the subspace publicly. These results hold even when we make no assumptions on the relationship between the public and private task other than that they share the same low-dimensional subspace.We additionally provide a novel lower bound that shows that the algorithm we analyze for our upper bound achieves the optimal rate among "two-stage" algorithms that estimate the transfer parameters within a fixed low-dimensional subspace. From these results, we see that the pretrained features are approximately low-rank for the outof-distribution task PCam, yet a linear probe over these features achieves good (83.5%) performance (Table 1 ). The fact that the representation still gives good performance when only a linear layer is trained on top suggests that the data does fundamentally lie in or near the low-rank space that is identified by the pretrained model.In Appendix A, we plot and see similar results for the fMoW and RESISC45 datasets, where linear probing is similarly successful (relative to full finetuning).We first describe our model of the data distribution for the private task, learning objective, any assumptions we make and results from prior works we use.We consider linear regression models in which every observation (x i ,y i ) for a given task is generated according to:x i ∼ N (0,I d ), η ∼ N (0,1)EQUATIONThe covariates x i and noise η are sampled i.i.d. Here, B ∈ R d×k is an unknown, low rank (k ≪ d) feature matrix with orthonormal columns. The matrix B, and consequently the subspace spanned by its columns, is shared across all tasks in our problem setting. This includes both the public tasks that may be used to derive the initial estimate of B, as well as the private tasks in single-task and multi-task transfer settings.The task vectors α j are all assumed to lie in the true shared subspace B. t(i) indexes the task α j for the covariate x i : public tasks are in α 1...t , and the transfer task is α t+1 . Note that the tasks are not random variables and we do not make distributional assumptions on the tasks for our results. In Appendix B we provide details on the requirements for the public tasks α 1...t (and also refer the reader to Tripuraneni et al. [28] ), but for now we simply require that the public tasks are sufficiently "diverse" within B.The learner sees n 1 samples from the public tasks (in total across all tasks) and n 2 samples drawn from the private task.We are interested in learning w that minimizes the following population risk:EQUATIONon the private task Bα t+1 .In stating our main results, we first assume access to an oracle that can output an orthonormal matrix B ∈ R d×k that is "close to" B. We measure the distance between subspaces in terms of the principal angle distance, denoted sinθ(B, B) = sinθ( B,B) (see supplement and Tripuraneni et al. [28] for more discussion).The following identities on sin θ will be useful: Lemma 5.1 (subspace estimation errors). The following inequalities are satisfied for matrices with orthonormal columns B, B ∈ R d×k (and when B, B are swapped):∥(I -B B⊤ )B∥ F ≥ ∥(I - B B⊤ )B∥ op = sin θ( B,B) ≥ ∥(I-B B⊤ )B∥ F / √ k.Instantiating the oracle with public data. The following corollary characterizes the error incurred from estimating the underlying subspace from public data using the method-of-moments estimator from Tripuraneni et al. [28] . We state this bound for use in subsequent results but refer the reader to the supplement for the conditions required on public data in order to achieve this bound. Theorem 5.2 ([28], Theorem 3, simplified). Let A = (α 1 ,...,α t ) ⊤ be the public task matrix, ν =σ k A ⊤ A t, and κ = tr( A ⊤ A t ) kν be the average condition number. If an equal number of samples is generated from each task, and κ ≤ O(1) and ν ≥ Ω( 1 k ), then the error of the method-of-moments estimator ( [28] , Algorithm 1) isEQUATIONwith probability at least 1-O(n -100).We will refer to γ ≥ sinθ(B, B) as an upper bound on the error of the subspace estimation oracle. We give upper bounds with respect to γ and also instantiate the bounds with the upper bound from Theorem 5.2.Algorithm 1 Two-phase algorithm for public-private linear regression using subspace estimation Input: n 1 public samples drawn according to (x i ,y i ),x i ∼ N (0,I d ), y i = x ⊤ i Bα t(i) +η, η i ∼ N (0,1)and n 2 private samples where x i , η i have the same distribution, and y i = x ⊤ i Bα t+1 +η i 1: Use method-of-moments estimator ( [28] , Algorithm 1) to estimate B using public data 2: Project private data x i to k-dimensional subspace: [57] on projected private data to estimate α t+1 Output: Parameter estimate B αt+1x ′ i = x ⊤ i B 3: Use DP-SGD variant ofWe use in our analysis a known upper bound for private linear regression in d-dimensions. Theorem 5.3 states an informal result from [57] that upper bounds the excess risk for a variant of DP-SGD [15] (see Appendix B for more details). Furthermore, results from [58] imply that this upper bound is tight. Theorem 5.3 (Corollary 11 from [57] , simplified). Suppose we have n 2 i.i.d. datapoints (x i ,y i ), where x i ∼ N (0,I d ) and y i = x ⊤ i w+ϵ i , and ϵ i ∼ (0,σ 2 ). Given sufficient private samples n 2 , there exists an (ε,δ) private estimate ŵpriv such that, with high probability:EQUATION)5.2 Private transfer learning for a single task Algorithm. Our proposed algorithm (Algorithm 1) first projects x into the estimated subspace Bpub , i.e., x → B⊤ pub x, and then runs private linear regression in the k-dimensional subspace. This is analogous to linear probing in our experiments, which first uses the public encoder to compute a low-dimensional feature representation of the data and then learns a linear model using the features. While full finetuning of the model is also a common paradigm in the transfer learning literature, we point to [19] which shows that when the feature representation is sufficiently informative, linear probing outperforms finetuning under differential privacy -a result that supports our empirical findings.The following theorem states that Algorithm 1 achieves a rate that matches optimal rates for private linear regression in k-dimensions, up to the subspace estimation error γ. Theorem 5.4 (single-task private transfer upper bound). Assume we have access to a subspace estimation oracle that solely uses public samples to provide estimate Bpub for the unknown subspace B of a private task defined by the pair (B,α t+1 ) in (2). Further, the estimate satisfies sin θ( Bpub ,B) ≤ γ. Given n 2 i.i.d. samples from the distribution of this private task, Algorithm 1 outputs an estimate Bpub αt+1 that is (ε,δ)-differentially private, and with high probability incurs a risk of:EQUATIONEQUATION)Proof sketch. The proof nearly follows from existing bounds on subspace estimation and private linear regression. The key difficulty is that regression on the input x ∼ N (0,I d ) projected into the estimated subspace Bpub still leaves the residual that does not lie in Bpub , which can be treated as a noise term if we can show that the residual is independent of the projected x. We can show this because Bpub is orthogonal to B⊥ pub (spans null space of Bpub ), so under the i.i.d. Gaussian assumption on x, the residual is independent of the projected x. As a result, we obtain the private linear regression rate in k dimensions with a variance of 1+γ 2 rather than 1 and an additive γ 2 bias.Discussion. From Theorem 5.4, we can break down the errors into an unavoidable bias due to the subspace estimation error (dependent only on the number of public samples) and the subsequent linear regression error due to privacy. For a subspace estimation error γ we require n 1 ≥ dk 2 γ 2 . Given this inevitable error we can hope to achieve an accuracy of err + γ 2 where err is the additional linear regression error and sin θ (B, Bpub ) ≤ γ. This requires approximately:n 2 ≥ k err + k ε √ err (8)samples. That is, if the subspace estimation error is zero then we achieve the rate of private linear regression in k dimensions, and consequently optimal non-private rates when ϵ → ∞.In the previous subsection, we proved an upper bound on the single-task transfer for row-level (ε,δ)-DP private algorithm, when the publicly estimated subspace Bpub is γ accurate. In this section, we show that our upper bound is tight among algorithms for our problem that search for solutions within a fixed subspace.In EQUATION)Proof Sketch. Our proof relies mainly on tracing attacks in [59, 58] , but our analysis additionally needs to handle the misspecification of the subspace B which influences the construction of the worst case problem instance. When we project inputs x → B⊤ pub x, we can show that the projected samples can now be treated as i.i.d. samples from a k-dimensional linear regression model with independent noise. For a fixed Bpub , any choice of B,α t+1 affects both the scaling of the noise (∝ ∥(I -Bpub B⊤ pub )Bα t+1 ∥ 2 2 ), and the direction of the regression vector, based on how much of the true parameter Bα t+1 is captured in given subspace Bpub . To handle this, we first construct subclasses of the adversary, where each subclass fixes the norm of ∥ B⊤ pub Bα t+1 ∥ 2 . Then, we lower bound the minimax risk over this subclass by via a Bayes risk which we further lower bound by constructing a tracing adversary.We show that there exists a prior π over Bα t+1 where the probability of the intersection of the following two events is very low: (i) small estimation error E π L(M (S, Bpub )), and (ii) small success rate for the tracing adversary to infer the membership of some element in S. Since, M has to be (ϵ,δ) private, this reults in a Bayes risk lower bound. Discussion. Our lower bound for the class of two-stage algorithms matches our upper bound in Theorem 5.4. This implies that our Algorithm 1 is optimal when Bpub is the estimate given by the optimal subspace estimation oracle over public samples. When we use Algorithm 1 from [28] , the estimation error matches lower bounds (Theorem 5 in [28] ) upto a factor of √ k.Finally, we complement the results in this section through a simulated empirical study matching the setup described in Section 5.1.Setup. We simulate n 1 samples (x i ,y i ) from t = 100 public tasks where the true dimension d = 25 but the underlying subspace B has rank 5. As baselines, we compare against nonprivate linear regression, DP-SGD without a subspace estimate, and DP-SGD initialized with the true subspace B, and compare against DP-SGD initialized with the subspace estimated using the method-of-moments estimator [28] . We use the Google Tensorflow implementation of DP-SGD for private learning [60] . We used a grid search of hyperparameters to set the clipping norm to 0.5, learning rate to 0.1, and used 50 epochs of training for DP-SGD. We use the RDP accountant to set ε = 1.1 and δ = 1e-5.Our results are shown in Figure 4 . We observe that, as expected, private training from scratch has high error, and additional public data (n 1 = 500 vs n 1 = 2000) improves performance, reducing the ℓ 2 parameter error close to that of using DP-SGD with the true underlying subspace B (matching our intuition, for example, from Figure 2 ). However, we also see that when performing private transfer there are diminishing returns for this more precise subspace estimation, as the noise introduced via private learning becomes a dominating factor.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). 
discussion and limitations: 
 Our results answer questions posed by [14] positively. Empirically, we show that across three datasets with significant shift between the public and private tasks, publicly pretrained features do make private learning far more effective, taking models from unusable when trained from scratch to close-to-nonprivate performance when trained privately with linear probing. In addition, we provide a theoretical model to explain our findings, based on models of nonprivate transfer learning. Our model supports our empirical findings, suggesting that public features should indeed reduce private sample complexity under even extreme distribution shift when the public and private tasks share a low-dimensional representation. Altogether, our conclusions are optimistic and provide confidence that public data can indeed support private training even for highly sensitive tasks that cannot and should not be used in public training. However, our linear subspace model has the clear limitation of being a simplified model for the neural network representations used in practice. As this is a limitation shared by literature on nonprivate transfer learning [28] [29] [30] [31] [32] [33] [34] , improvements in this area would contribute to both the private and nonprivate transfer learning literature.A Empirical evidence for shared subspace assumption (a) PCam.(b) fMoW.(c) RESISC45. It is natural to ask whether the assumption that public (pretraining) tasks and private tasks truly share a low-dimensional subspace as we model in our theoretical analysis. In order to validate this, in figure 5 , we plot the eigenspectra of the feature covariance matrices for each of the datasets we evaluate in Section 4. The key takeaway is that even though the three datasets are out of distribution for the pretraining data, the extracted features are low rank. In addition, these features are effective when used to train a linear probe (in contrast, if the subspace were misspecified, the features may be low-rank but lead to poor results with linear probing).B.1 Preliminaries for Tripuraneni et al. [28] In this section, we elaborate on the assumptions required to use algorithms from Tripuraneni et al. [28] for subspace estimation using public data (i.e., instantiating the subspace oracle).Our analysis requires a notion of distance between subspaces, for which we use the maximum principal angle [61] . We give a definition here and refer the reader to [62] or [63] , Appendix A, for more details.Definition B.1 (Maximum principal angle). Let U,V ∈ R d×k be orthogonal matrices. Let U and V be the subspaces spanned by the columns of U and V respectively. The maximum principal angle θ ∈ [0,π/2] between U and V is defined by sinθ(U,V ) = ∥U U ⊤ -V V ⊤ ∥ = ∥U ⊤ V ⊥ ∥ = ∥V ⊤ U ⊥ ∥.In our model each data point (x i ,y i ) is associated with a task α t(i) ∈ R k . We do not make distributional assumptions on these tasks, but estimating the subspace accurately requires certain diversity assumptions on the tasks. We inherit the following assumption from [28] :Assumption B.2 (Task diversity and normalization). Define A = (α 1 ,...,α t ) ⊤ and ν = σ r A ⊤ A t. The t underlying task parameters α j satisfy ∥α j ∥ = Θ(1) for all j ∈ [t]. Moreover, we assume ν > 0.In the following, we will also use the average condition number κ = EQUATIONwith probability at least 1-O(n -100 1).We restate the full bound given by [57] for private SGD. Theorem B.3 ([57], Corollary 11, simplified). Suppose we have data (x i ,y i ) such that x i ∼ N (0,I k )andy i = x ⊤ i w * +ϵ i , where ϵ i ∼ (0,σ 2 ). Then, assuming n 2 ≥ Ω k(1+ √ log(1/δ) ε) , we have:1. Algorithm DP-AMBSSGD ([57], Algorithm 2) with parameters η = 1/4k, α = √ 8log(1/δ) ε is (ε,δ)-DP.2. The output ŵpriv satisfies the following risk bound:EQUATIONwith probability 1-O(n -100).In this section we state or restate key lemmas that we will refer to in the following proofs.We will use the following lemma to argue that we can project x into the estimated subspace B and treat the residual (that lies outside of B) as i.i.d. Gaussian noise.Lemma C.1 (Independence of x residual). Consider orthonormal matrices B and B ∈ R d×k and α ∈ R k . Let (x, y) be generated according to the model in Equation 2where x ∼ N (0, I d ) and y = x ⊤ Bα+η. Then the projection of x into B, x ⊤ ( B B⊤ )Bα, is independent of the residual that lies in the complement of B, i.e. x ⊤ (I d -B B⊤ )Bα. Moreover, this residual is i.i.d. Gaussian.Proof. We can rewrite the distribution of y | x in terms of the projection of the regression vector Bα on to the column span of B, when the input x is also projected in the following way: x → Bx:EQUATIONwhere α := B⊤ Bα is a k-dimensional vector in the column span of the given subspace B.Next, we note that the projection of input x in the column span of B and its projection into the corresponding null space are independent, i.e., x ⊤ ( B B⊤ ) |= x ⊤ (I d -B B⊤ ). This is easy to show since both x ⊤ ( B B⊤ ) and x ⊤ (I d -B B⊤ ) are jointly Gaussian and are marginally distributed as zero mean Gaussian random variables with their covariance:E[( B B⊤ )xx ⊤ (I d -B B⊤ )] = ( B B⊤ )E[xx ⊤ ](I d -B B⊤ ) = ( B B⊤ )I d (I d -B B⊤ ) = B B⊤ -B B⊤ = 0.This implies independence of the two projections. Note that the last step in the above calculation uses the fact that B⊤ B = I k . Since the two projections are independent, we can rewrite the conditional distribution y | x as: 58, 64, 65] ). Let M be an (ε,δ)-differentially private algorithm with 0 < ε < 1 and δ > 0. Further, letx B =: x ⊤ B y | x B ∼ N ((x B ) ⊤ α, σ2 ), where, σ2 = σ 2 +∥(I d -B B⊤ )Bα∥ 2 2 . Lemma C.2 ([A i = A α((y i ,x B i ), M (S)) and A ′ i = A α((y i ,x B ), M (S ′ i )) when (y i ,x B i ) ∈ S and S ′ i replaces (y i ,x B i )with another IID draw from the same distribution. Then, for every T > 0,EQUATIONProof. let Z + = max(Z,0) and Z -= -min(Z,0) denote the positive and negative parts of random variable Z respectively. We haveEA i = EA + i -EA - i = ∞ 0 P(A + i > t) dt- ∞ 0 P(A - i > t) dt.For the positive part, if 0 < T < ∞ and 0 < ε < 1, we have∞ 0 P(A + i > t) dt = T 0 P(A + i > t) dt+ ∞ T P(A + i > t) dt ≤ dt T 0 e ε P(A + i > t)+δ dt+ ∞ T P(A + i > t) dt ≤ ∞ 0 P(A ′ i + > t) dt+2ε ∞ 0 P(A ′ i + > t) dt+δT + ∞ T P(|A i | > t) dt.Similarly for the negative part,∞ 0 P(A - i > t) dt = T 0 P(A - i > t) dt+ ∞ T P(A - i > t) dt ≥ T 0 e -ε P(A ′ i -> t)-δ dt+ ∞ T P(A - i > t) dt ≥ T 0 P(A ′ i -> t) dt-2ε T 0 P(A ′ i -> t)-δT + ∞ T P(A - i > t) dt ≥ ∞ 0 P(A ′ i -> t) dt-2ε ∞ 0 P(A ′ i -> t)-δT.It then follows thatEA i ≤ ∞ 0 P(A ′ i + > t) dt- ∞ 0 P(A ′ i -> t) dt+2ε ∞ 0 P(|A ′ i | > t) dt+2δT + ∞ T P(|A i | > t) dt = EA ′ i +2εE|A i |+2δT + ∞ T P(|A i | > t) dt.Lemma C.3 (Stein's Lemma). Let Z be distributed according to some density p(z) that is continuously differentiable with respect to z and let h : R → R be a differentiable function such that E|h ′ (Z)| < ∞, then:Eh ′ (Z) = E -h(Z)p ′ (Z) p(Z) .D Proofs for Section 5 D.1 Proof of Theorem 5.4In this section we prove the upper bound result on the two-phase algorithm for single-task transfer learning, which first estimates the subspace publicly, projects the inputs into the estimated subspace and then privately performs linear regression on the projected data.Proof. Let sinθ( B,B) ≤ h(n 1 ) and E[(⟨α priv , B⊤ x⟩-y) 2 ]-min α E[(⟨α, B⊤ x⟩-y) 2 ] ≤ g(n 2 ).Let α = min α E[(⟨α, B⊤ x⟩-y) 2 ] (the best α using x projected into B), and let αpriv be the output of DP-AMBSSGD on x projected into the estimated B. then we haveE ⟨α priv , B⊤ x⟩-y 2 -E ⟨α * ,B ⊤ x⟩-y 2 = E ⟨α priv , B⊤ x⟩-y 2 -E ⟨α * ,B ⊤ x⟩-y 2 +E ⟨α, B⊤ x⟩-y 2 -E ⟨α, B⊤ x⟩-y 2 .We can break this into two parts: we will first boundEQUATIONand thenEQUATION)We first bound (14) . Note that according to the model (2),EQUATION)where ϵ is N (0,1).However, our algorithm first projects x into the space of the estimated B before performing linear regression in the lower-dimensional space, which introduces additional error.We can rewrite y as:EQUATIONdecomposing the first term into the projection into B and the remaining error due to projection.By Lemma C.1, this residual term is independent of the first term (with x projected into B) and ϵ.We claim that the variance of the residual is sin(θ) 2 +∥α * ∥ 2 2 : LetEQUATIONand note that the total variance is the sum of the variances because the terms are independent. Moreover, the first term is a rescaled i.i.d. Gaussian with zero mean. Then the variance ofϵ ′ is E[(x ⊤ B⊥ B⊤ ⊥ Bα * ) ⊤ x ⊤ B⊥ B⊤ ⊥ Bα * ]+σ 2 = E[α * ⊤ B ⊤ B⊥ B⊤ ⊥ xx ⊤ B⊥ B⊤ ⊥ Bα * ]+σ 2 = E[α * ⊤ B ⊤ B⊥ B⊤ ⊥ Bα * ]+σ 2 = sin(θ) 2 ∥α * ∥ 2 2 +σ 2 .Moreover, we assume σ 2 = 1 so we have var(ϵ ′ ) = sin(θ) 2 ∥α * ∥ 2 2 +1. Using the rewritten y, we can treat the new private regression problem as estimating B⊤ Bα * . Thus we will instantiate g(n 2 ) with the linear regression bound from Theorem B.3 with k dimensions and variance σ 2 = sin(θ) 2 ∥α * ∥ 2 2 +1. Now we bound the second half of the expression,E ⟨α, B⊤ x⟩-y 2 -E ⟨α * ,B ⊤ x⟩-y 2 = E ⟨α, B⊤ x⟩-⟨α * ,B ⊤ x⟩+⟨α * ,B ⊤ x⟩-y 2 -E ⟨α * ,B ⊤ x⟩-y 2 = E (⟨ B α-Bα * ,x⟩) 2 = ∥ B α-Bα * ∥ 2 2Finally this leaves us to bound ∥ B α-Bα * ∥ 2 2 . We will make use of the following lemma: Lemma D.1. Let α be the (public) linear regression estimate of the task α on the projected data B⊤ x.Then ∥ B α-Bα * ∥ 2 2 ≤ (sinθ(B, B)) 2 ∥Bα * ∥ 2 2 . Proof. B α-Bα * = B(E[ B⊤ xx ⊤ B] -1 ) B⊤ E[xx ⊤ Bα * ]-Bα * = B(E[ B⊤ xx ⊤ B] -1 ) B⊤ E[xx ⊤ ]Bα * -Bα * = B(E[ B⊤ xx ⊤ B] -1 ) B⊤ E[xx ⊤ ]( B B⊤ Bα * +(I -B B⊤ )Bα * )-Bα * = B(E[ B⊤ xx ⊤ B] -1 ) B⊤ E[xx ⊤ ] B B⊤ Bα * -Bα * = B B⊤ Bα * -Bα * = B B⊤ Bα * -BB ⊤ Bα * = ( B B⊤ -BB ⊤ )Bα * Then ∥ B α-Bα * ∥ 2 2 = ( B B⊤ -BB ⊤ )Bα * ≤ (sinθ(B, B)) 2 ∥Bα * ∥ 2 2Then we have E ⟨α, B⊤ x⟩-y2 -E ⟨α * ,B ⊤ x⟩-y 2 ≤ h(n 1 ) 2 ∥Bα * ∥ 2 2 .Putting these together givesE ⟨α priv , B⊤ x⟩-y 2 -E ⟨α * ,B ⊤ x⟩-y 2 ≤ g(n 2 )+h(n 1 ) 2 ∥Bα * ∥ 2 2For the generic result with γ subspace error, we substitute h(n 1 ) = γ, or Theorem 5.2 to instantiate the bound with the method of moments estimator [28] . Substituting B.3 for g(n 2 ) and taking a union bound over failure probabilities gives the result.Here, we prove our result lower bounding the lowest possible transfer error achieved by any (ε,δ)-DP algorithm in our single-task transfer setting. We denote the class of two-stage algorithms of interest as M 2stg (ϵ,δ,γ). Each algorithm in our class satisfies the following:1. The algorithm takes as input private dataset S of n 2 i.i.d. samples from task α t+1 , along with a γ-accurate public estimate B, 2. Projects the input data point x → B⊤ x for any (x,y) in the private dataset S. 
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: The method we evaluate is itself a form of a safeguard (differentially private training). Above that, the methods do not suggest obvious new safeguards necessary. 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 use the OpenCLIP [52] library for models and the Opacus [54] library for private training. We provide citations to these as well as the datasets we use in the paper. 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?Answer: [NA] Justification: We have not (yet) released any new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: We do not perform any human subjects experiments.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: We do not perform any human subjects experiments.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Code will be made available at https://github.com/pratiksha/private-transfer. 
 
 Appendix:  


Decision: The reviewers were overall positive about the paper. However, there were a lingering concern regarding the disconnect between the theory and the experiments. We recommend the authors to discuss this aspect in more detail in the paper, in order, to ensure a better readability of the paper. We do acknowledge the authors address this point a fair bit in the rebuttal. It would be great if some of the discussion from the rebuttal can be ported to the paper.

Reviews: review: paper_summary: paper_summary: This paper studies the role of using public training data for fine-tuning private tasks. The paper begins by showing, empirically, on three datasets, that fine-tuning significantly outperforms training privately from scratch. The experiments are conducted on several image classification datasets. Then, the paper provides a stylized theoretical model to explain the findings, based on models of nonprivate transfer learning. This model focuses on linear regression with isotropic noise corruption. The results are complemented by simulations matching the linear regression setup.
strength_weakness: strength_weakness: - The theoretical setup may be too simplistic. For instance, the resulting algorithm 1 is different from what was implemented in the experiments.

- The experiments only focus on image classification. Additional data modality could be utilized to broaden the interest of these results.
questions: questions: See Weaknesses above.
limitations: limitations: The authors discussed the limitations of their work in Section 6.
paper_summary: paper_summary: The paper proposes a theory for the benefit of transfer learning in DP ML even when public data and private data differ significantly from each other. This theory relies on a subspace shared between public and private data. They empirically verify the algorithm in their theory.
strength_weakness: strength_weakness: The advantage over prior work is mild for linear regression tasks. In linear regression, gradients, input data, or models being constrained to a linear subspace are all roughly the same thing.

The paper does not attempt to reconnect the theory back to the original experiments. This explanation does not seem refutable.

The paper does not quantitatively argue that there is limited overlap between the datasets considered and the base pretraining data.
questions: questions: Can you verify that there is limited overlap between the benchmark datasets evaluated and the DataComp dataset? I think even some sort of textual overlap is sufficient if not exhaustive.
limitations: limitations: There is a fair discussion of limitations.
paper_summary: paper_summary: There are many contexts where deep learning models trained to preserve differential privacy have much worse performance than models trained without the differential privacy constraint. One common way to improve model quality in these cases is to pre-train a model on publicly available data then fine-tune with the private data. These pre-trained models often demonstrate much better empirical performance than models trained exclusively on private data, even when the public data used for pre-training is very different from the private data. This phenomenon is not well understood theoretically so it is unclear what to expect from out-of-distribution pre-training.

This work seeks to understand public pre-training under distribution shift. The authors start by demonstrating the utility of public pre-training in the case of extreme distribution shift. Having demonstrated the phenomenon, the authors develop a theoretical model to explain the effectiveness of public pre-training. This model poses public data as coming from a sequence of linear regression tasks where the features of each task lie in a low-dimensional subspace. Working in this model, the authors develop a two stage algorithm for public-private linear regression that first approximates the subspace $B$ then uses DP-SGD to estimate the regression parameters $\alpha$. The authors analyze this algorithm to prove an upper bound on the error and they provide a matching lower bound among algorithms that solve the regression problem on a subspace. To support the theoretical results, the authors provide empirical results on simulated data.
strength_weakness: strength_weakness: - The disconnect between the setting for the experiments and the stylized theoretical model is very apparent. It is difficult to say how much of the empirical results from section 4 can be explained by the theoretical results in section 5. That being said, the authors provide citations showing that this theoretical model is common in the meta-learning literature. I am not familiar enough with that literature to know if there are other alternate models that are common in that literature or how they would compare to the model used in this work. It would improve the paper if the authors compared to other potential models, if they exist, or stated that they do not.
questions: questions: - The authors discuss public data assisted query answering in the background section, are you aware of [this](https://proceedings.mlr.press/v238/fuentes24a.html) more recent work in the area? 
- An alternative to linear probing for parameter efficient fine tuning is [LoRA](https://arxiv.org/pdf/2106.09685), would you expect this method to perform similarly to linear probing in your transfer learning experiments?
- How does the bound for your two stage algorithm compare to the error you would attain if you simply ignored the public data? It would be useful to say exactly what you gain from the subspace estimation step and if the naive approach would ever be better (like in a situation where the embedding dimension is almost as large as the latent dimension).
limitations: limitations: - The authors have adequately addressed the main limitation of the work (the fact that the theoretical model is limited and does not totally account for the neural representations used in practice). They accurately describe their model as being stylized and acknowledge the impacts of this limitation in the discussion section.
paper_summary: paper_summary: The work aims to bridge an important gap in literature, looking at using public pretraining to improve differentially private model training, even when there is a distribution shift, particularly concept shift, in the public and private data. They report impressive improvements in accuracy. Further, they provide a justification for these observations, citing the representation sharing nature of the private and public data.
strength_weakness: strength_weakness: - [W1] Strong assumption that the shared, low-dimensional representation is even learnable across the private and public data.
questions: questions: - [Q1] Referencing W1 it might be interesting to look at the naturally learnt representations, when the public data and private data is used independently to train different models. It would help verify the assumption that a common representation space is even learnable. What kind of representations are learnt? What is the difference between the representations learnt in a disjoint way and those learnt by forcing a common latent space?
limitations: limitations: All the limitations, if any, have been adequately discussed and addressed.

Comments: title: Response to Rebuttal
comment: Hello, we would like to thank the reviewer again for their thoughtful feedback. We hope our responses have provided clarity on the concerns regarding the theoretical model and the experimental evaluation. We would like to gently follow up in case there are any further questions so that we have time to respond appropriately before the discussion period ends. Thank you!
Hello, we would like to thank the reviewer again for their thoughtful feedback. We hope our responses have provided clarity on the concerns regarding the theoretical model and the composition of the datasets. We would like to gently follow up in case there are any further questions so that we have time to respond appropriately before the discussion period ends. Thank you!
Thank you to the authors for clearly answering my questions about the work. I have reviewed the rebuttal along with the comments from other reviewers and decided to stick with my original score.
- I appreciate the authors' effort to undertake the plotting exercise in the short rebuttal deadline. The outcome on PCam does look reassuring! The inclusion of the plots for eigenspectrum for RESISC45 and fMoW would help round off the paper quite well.

- I further agree that the measurement of distance between two representations is not quite obvious, especially for the high dimensional ones. A very very recent ICML paper (that I don't expect the authors to discuss at all now, but could be interesting for the future) looks into this problem it seems, and does a reasonably good job of providing measures to compare them. [1]
  - Also, as the privately trained representations are in fact not usable is a valid observation. I would personally still err on the side of comparison against the private one to understand what differences arise when using public pre-training, and how the change in representation helps the model learn better.
  - On the other hand, comparing representations against the well performing non-private training ones, could act like the other side of the spectrum? 
  - I'm curious to see which side the public-pretraining but privately trained models lie in this hyper-spectrum (if they do even lie somewhere useful), or do they lie in a completely unrelated subspace to either of these in the latent space. Something as simple as representing the latent representations as vectors for some smaller (maybe even toy) datasets and then analyzing them could be a good starting point.
  - But then again, I do agree that this might require rigorous definitions in themselves and is too involved to be discussed in this paper. But I do find this direction fascinating and hope the authors' can follow up in a future version.

- All in all, I've read the comments and feedback provided by the other reviewers', and am happy to recommend acceptance for the submission and keep my score :)

[1] Wayland, Jeremy, Corinna Coupette, and Bastian Rieck. "Mapping the multiverse of latent representations." arXiv preprint arXiv:2402.01514 (2024).