Why Is Public Pretraining Necessary for Private Model Training?

Introduction

As modern machine learning models are increasingly capable of memorizing the training data, membership inference attacks and data reconstruction attacks have successfully demonstrated the vulnerability of sharing models trained on sensitive data. Differential Privacy (DP), introduced in , is now a gold standard measure of privacy leakage in training a model, which is parameterized by two scalars: $\varepsilon>0$ and $\delta\in$. By introducing enough randomness in the training, one can ensure that the model does not depend too much on each individual training example. This provides plausible deniability to the participants and evades privacy attacks, achieving strong DP with small values of $(\varepsilon,\delta)$. We give a formal definition in Definition 1.1.

One of the main challenges in training on private data is that utility and privacy trades off unfavorably on standard benchmark tasks. Given a target task, such as table-to-text generation, on a private dataset, say E2E dataset , state-of-the-art techniques suffer from significant performance degradation to achieve even an acceptable level of privacy. For example, a weak privacy guarantee of $\varepsilon=8$ significantly deteriorates the performance of the trained model compared to the one trained without privacy, i.e. $\varepsilon=\infty$ (second row of Table 1). Perhaps surprisingly, there is one simple change to the training algorithm that can significantly reduce this cost of privacy: pretraining the model on some public data (first row of Table 1).

Such remarkable gain of public pretraining has been widely observed in standard benchmark vision and language tasks, which we survey in Appendix B. This includes CIFAR-10, MNIST, and Fashion MNIST in , CIFAR-100, ImageNet, and Places-365 in , text generation with E2E and DART in , and next word prediction on Reddit dataset . Note that in all these cases, the public data distribution differs from the target task distribution. Nevertheless, we expect some gain from public pretraining, drawing analogy from its success in non-private training of large models (e.g., first column in Table 1). However, the stark difference in the gain of pretraining between the non-private case, i.e., $\varepsilon=\infty$, and the weakly private case, say $\varepsilon=8$, is striking. This suggests that the benefit of public pretraining in differentially private machine learning is a fundamentally different phenomenon from the typical benefits of standard transfer learning . Our goal is to give an insight into when such a phenomenon can be observed by carefully constructing synthetic public and private tasks. Recently, in a closely related work, formally demonstrated that public data mitigates the curse of dimensionality when fine-tuning with privacy. However, to the best of our knowledge, ours is the first work to understand the necessity of public data in private model training.

In this paper, we provide a theoretical example of a loss function that requires pretraining on public data and fine-tuning with private data. Our construction is guided by our hypothesis that the typical population loss landscape of standard machine learning tasks necessitates gradient based algorithms to go through two stages. A conceptual two-dimensional sketch of the landscape we envision is shown in Fig. 1. We start from a random initialization close to the origin. In the first stage, the algorithm is directed by the data towards a good basin with small local minima. This is followed by the second stage, where the algorithm solves what is effectively a convex optimization in the selected basin to arrive at the local minima. The key insight is that the first stage of selection should require significantly more samples to solve privately, compared to the number of samples required to solve it without privacy. Concretely, for the example in Fig. 1, the gradient at the origin directs to the correct basin containing the global minima, but the gradient is small. A private gradient descent adds additional noise to the update, increasing the chance of ending up at worse basins. Hence, a significantly larger private dataset is needed to overcome the privacy noise. This construction is motivated by the private hypothesis selection problems where a similar fundamental separation in sample complexity is known . This intuition would explain the widely observed failure of private training when starting from a random initialization. We turn this hypothesis into concrete constructions in Section 2, where we formally prove the separation in sample complexity.

Main contributions: In Section 2, we construct theoretical tasks to demonstrate the fundamental separation in sample complexity. First, we construct a theoretical loss function and a corresponding data distribution such that given $n_{pub}$ public samples and $n_{priv}$ private samples from this distribution with $n_{pub}\ll n_{priv}$, pretraining on the public data and fine tuning with the private data achieves a much better loss than any algorithm with access to either alone. Next, we extend our result to a more relevant setting where $n_{pub}$ is large but the public data is out of distribution. This construction exhibits the need to have little to no privacy noise in the first “phase” of non-convex optimization. To the best of our knowledge, this is the first theoretical analysis demonstrating the need for public pretraining.

In Section 3, we empirically validate our two-phase hypothesis. First, treating CIFAR-10 as our target private task, we consider a setup where we are allowed $T$ epochs of pre- or post-training on in-distribution public data, out-of-distribution public data, or private data with low noise. In all settings we demonstrate it is best to use all these low- or non-private training epochs on pretraining (as opposed to post-training). This demonstrates that early rounds of training are more sensitive to privacy noise, as conjectured in our two-phase hypothesis. Secondly, we look at a manifold of the loss landscape interpolated between three models trained on LibriSpeech. We show that a publicly pretrained and privately fine-tuned model ends up in the same basin as a fully publicly trained model. On the other hand, a fully privately trained model ends up in a different basin. This provides evidence that public pretraining’s benefits are in part due to selecting a better basin for fine-tuning.

Pretraining on public data is now a default choice in large scale private training for NLP tasks , including 175 billion parameter GPT-3 with $\varepsilon=1$, and vision tasks . Motivated by pretraining providing good feature representations, propose using handcrafted features for small scale problems, as opposed to learned features, to improve utility-privacy tradeoff. On the other hand, cautions against the indiscriminate use of large-scale public data in DP training, which we discuss in depth in Section 4.

Besides the aforementioned empirical results, public data has been used to show theoretical improvements for problems such as query release , mean estimation , and optimization . In the optimization case, besides pretraining, these papers use public data to learn the geometry of the private loss in various ways and use geometry-aware gradient descent methods, rather than vanilla DP-SGD.

showed that for the problem of selecting the $k$ coins out of $d$ coins that land heads with the highest probability, any $(\varepsilon,\delta)$-DP algorithm with constant error requires $n=\Omega(\sqrt{k}\log d)$ samples from each coin. This is in contrast with the non-private case, where $n=O(\log d)$ suffices for any $k$. Selection and non-convex optimization are tightly connected: show a reduction from selection to non-convex optimization, by designing a loss with $d$ locally convex basins, each corresponding to a different coin in the selection problem. This gives a different perspective on why the first stage of non-convex optimization may be difficult privately but not with public data: it effectively involves solving a selection problem on the basins in the loss function.

2 Background on differential privacy and DP-SCO

Differential privacy is a privacy guarantee for algorithms that can be viewed as random functions of datasets:

Let $\mathcal{D}$ be a data domain, and $\mathcal{C}$ be a set of outputs. An algorithm $\mathcal{A}:\mathcal{D}^{*}\rightarrow\mathcal{C}$ is $(\varepsilon,\delta)$-differentially private if for any $D,D^{\prime}\in\mathcal{D}^{*}$ such that $D$ and $D^{\prime}$ differ in at most one element and any set of outputs $S\subseteq\mathcal{C}$: $\mathop{\mathbf{Pr}}_{\theta\sim\mathcal{A}(D)}\left[\theta\in S\right]\;\;\leq\;\;e^{\varepsilon}\mathop{\mathbf{Pr}}_{\theta\sim\mathcal{A}(D^{\prime})}\left[\theta\in S\right]+\delta$.

Perhaps the simplest problem captured by DP-SCO is private mean estimation with identity covariance. The following lemma gives a lower bound on private mean estimation. It follows from Theorem 5.5 of and standard translation of ERM lower bounds to SCO lower bounds (see Appendix C of ):

Furthermore, for some $M=\Omega(\frac{\sqrt{p}}{\varepsilon n})$ and all such $\tau\in\mathcal{T}_{1}$, $|\left\|\theta^{*}(\tau)\right\|_{2}-M|\leq 1/n$.

These lemmas are the basis of the results in Section 2. Results in and standard translations from empirical loss bounds to population loss bounds via uniform stability (see e.g. ) show that DP-SGD achieves upper bounds for mean estimation that match these lower bounds up to polylogarithmic factors.

Necessity of public pretraining

A typical scenario in pretraining on public data is when the public dataset is large but is Out-Of-Distribution (OOD); there is a potentially large distribution shift between the public and the private dataset . In this section, we start with a simpler scenario where a small number of In-Distribution (ID) samples are used in public pretraining. This simplifies the explanation of our construction and also corresponds to realistic scenarios where public data comes from users who consented. The more common OOD case is addressed in Section 2.4.

When a small number of in-distribution samples are publicly available, several techniques have been proposed to improve the accuracy-privacy trade-off. An immediate use is to reduce the sensitivity of a mini-batch gradient by including the public data in the mini-batch. The public data can also be used to compute useful statistics; one can reduce the privacy noise by projecting the gradient onto a low-dimensional subspace computed from public data and by improving the adaptive clipping method with the geometry of the gradients estimated from public data . However, by far the most dominant technique in terms of the accuracy gain is pretraining on the in-distribution public data. For example, on CIFAR-10 dataset, one can train a $(\varepsilon=2,\delta=10^{-5})$-DP model that achieves 64.9% test accuracy. Treating 4% of the training dataset as public data, the accuracy can be improved by 7.1% [40, Table 1]. All the other techniques only give 2.8% extra gain, which includes using public data in fine-tuning, public data assisted adaptive clipping, and averaging past iterates. Such pretraining with in-distribution public data has been successful also in training variational autoencoders . We provide systematic study of these gains with numerical experiments on benchmark datasets in Section 3.

2 Construction

We first give a high-level overview of a construction for our main theorem and defer details to Appendix C.1. While our construction builds on upper/lower bounds for public/private mean estimation, one can build a similar construction using upper/lower bounds for linear regression instead. This follows via standard reductions from mean estimation to linear regression. We focus here on mean estimation for simplicity of presentation. A reference for notation is in Appendix A.

3 Analysis

With the above construction, we formally guarantee that for certain sizes of public and private datasets, both datasets are necessary to optimize the loss to a desired level. We defer the proof to Appendix C.1.

For $\delta=o(1/p^{2})$, any $(1,\delta)$-DP algorithm $\mathcal{A}_{priv}:\mathcal{D}^{p^{2}}\rightarrow\mathcal{C}$, and any $\mathcal{A}_{pub}:\mathcal{D}^{p}\rightarrow\mathcal{C}$ there exists $\tau\in\mathcal{T}$ such that:

For any $\delta\geq 2^{-p}$, there exists an algorithm $\mathcal{A}_{mixed}:\mathcal{D}^{p+p^{2}}\rightarrow\mathcal{C}$ which runs gradient descent on the first $p$ examples, followed by $(1,\delta)$-DP-SGD on the last $p^{2}$ examples, such that for any $\tau\in\mathcal{T}$:

This demonstrates that there exist data distributions where a small number of public in-distribution data is necessary to achieve small loss, and pretraining on that public data is sufficient for DP-SGD to achieve the desired level of loss. The first part of the theorem shows that there are data distributions where neither a small-size, $n_{pub}=p$, public data or a large-size, $n_{priv}=p^{2}$, private data can reach the desired loss. However, on the same data distribution, pretraining on the small-size public data, followed by finetuning on the large-size private data, achieves a desired level, $O(1/p)$, of the excess loss.

4 Pretraining on out-of-distribution public data

A more common setting in practice is when out-of-distribution large-scale public data is used in pretraining, as we surveyed in the introduction and at the beginning of Section 2. We modify our previous construction in Theorem 2.1 so that $(i)$ there is a distribution mismatch between the public and private examples and $(ii)$ an arbitrarily large amount, $n_{pub}$, of public data is available.

For $\delta=o(1/p^{2})$, any $(1,\delta)$-DP algorithm $\mathcal{A}_{priv}:\mathcal{D}^{p^{2}}\rightarrow\mathcal{C}$, and any $\mathcal{A}_{pub}:\mathcal{D}^{p}\rightarrow\mathcal{C}$ there exists $(\tau_{pub},\tau_{priv})\in\mathcal{T}$ such that:

For any $\delta\geq 2^{-p}$, there exists an algorithm $\mathcal{A}_{mixed}:\mathcal{D}^{n_{pub}+p^{2}}\rightarrow\mathcal{C}$ which runs gradient descent on the first $n_{pub}$ examples, followed by $(1,\delta)$-DP-SGD on the last $p^{2}$ examples, such that for any $\tau\in\mathcal{T}$:

Here, $\mathcal{L}$ refers to the population loss over $\tau_{priv}$.

This demonstrates that there exist data distributions where out-of-distribution public data is necessary to achieve small test loss on the target private task, and pretraining on the OOD public data is sufficient for DP-SGD to achieve the desired test loss. Note that all three cases are evaluated on the same private population loss, as is the case in real-world scenarios where we care about the performance on the private task.

Data abundance: If we had $p^{2}$ ID public examples or $p^{5}$ private examples in Theorem 2.1, we could achieve risk $O(1/p)$ in the above construction using only public data or only private data. Of course, if we also have the distribution mismatch in the preceding paragraph, no amount of public data achieves low risk on the private population. In light of this, Theorem 2.1 should not be interpreted as saying that both public and private data are strictly necessary to optimize some loss functions. Instead, a better interpretation might be that a small amount of public data greatly reduces the amount of private data needed to solve an optimization problem. This can be seen as theoretical backing for an empirical observation made in .

Experiments

In this section, we conduct experiments to verify our hypothesis about the two-stage optimization phenomenon.

Setup: For the ID public data experiment in Figure 4 (left), we train a ConvNet model on CIFAR10 using DP-SGD. We train for 60 epochs with a clipping norm of one, learning rate of 0.001, batch size of 256, and Adam optimizer. Simulating an ID public data setting, we split CIFAR10 (60,000 images) into a public dataset of size 2,000 and a private dataset of size 58,000. We use Adam optimizer with learning rate of 0.002 for the public dataset. For the large-size OOD public data in Figure 4 (right), we used 20,000 images from the training part of the CINIC10 images as the public data.

Results: In Figure 4, we allow a limited number of epochs $T_{pub}$ on the public data. We show test accuracy as a function of $t$ (the x-axis), which is the number of epochs used in public pretraining. The remaining $T_{pub}-t$ epochs are used in public post-training after the private training. For ID public data in the left panel, we choose $T_{pub}=200$. Using this budget for pretraining has the highest accuracy. This demonstrates that the initial rounds of training are the most sensitive to noise, as is the case in both our hypothesis from Section 1 and our theoretical construction in Section 2. Note that the benefits of longer pretraining is small after $t=100$. It is possible that after around 100 epochs, pretraining converges to a good basin and the benefits of public pretraining plateaus afterwards. We see the same trend with OOD public data using CINIC10 dataset with $T_{pub}=30$, shown in Figure 4 (right). Again, we observe that reducing privacy noise in the earlier rounds of training is more beneficial.

To further demonstrate the importance of the earlier iterations in the training, we designed an experiment where instead of using the same privacy budget for all iterations of private training, we train the first iteration with a lower noise multiplier (using more privacy budget) and compared it a setting where we train the last iteration with the lower noise multiplier. Table 2 compares the results for various choices of the end-to-end $\varepsilon$. Again, we observe that reducing privacy noise in the earlier rounds of training is more beneficial.

2 Manifold on Large Speech Model

To better understand the geometry of the loss function for training machine learning models, we evaluate training a ConformerM model on Librispeech dataset with/without public data pretraining using DP-Adam. Specifically, we train the following three models:

Oracle model: We train a ConformerM model on the complete Librispeech dataset for 100k steps. This is considered as the global minima of the manifold.

Private model: We train a ConformerM model on 90% samples drawn uniformly from the Librispeech dataset using DP-Adam for 20k steps.

Private model with public pretraining: We pretrain a ConformerM model on the 10% of the samples with Adam for 10k steps and then fine-tune on the remaining 90% samples with privacy for 1k steps.

Note that the hyper-parameters for the latter two settings are tuned to optimize the test word error rate under the same privacy budget $\varepsilon=9.8$. We fix the privacy parameter $\delta$ to $10^{-6}$, ensuring that $\delta<n^{-1}$, where $n$ is the number of private samples.

Results

Discussion

In this paper, we show that there exist natural learning tasks where public data is necessary and sufficient to achieve a target accuracy under DP model training. This conclusion is independent of whether the public data is in-distribution with the private training data or not. Recently, discussed the perils of indiscriminate use of public data in DP training, few of which are: $(i)$ Publicly available data does not necessary mean that one can use that dataset for training models without privacy consideration, as the trained model can release information from the dataset verbatim, and $(ii)$ Many existing empirical works on achieving better accuracy for DP training by using public data do not necessarily reflect realistic scenarios for model training. In particular, in real-world settings the available public data can be far out-of-distribution from the private dataset. The authors provide prescriptive recommendations on being judicious in the choice of public data for DP training. Our work is complementary to , and we concur with all the concerns in their paper. Given our current impossibility result, and the concerns in , an important research question for future exploration is given a public dataset which may be far out-of distribution from the private training data, what is the best DP training procedure that exploits the public dataset to obtain higher accuracy? To the best of our knowledge, all current works (see Section 1 for reference) on the use of public data in DP training do not provide an answer.

Another question raised by our work is whether one can use the insight that the geometry changes after public pretraining to improve private fine-tuning in practice. That is, in practice the ideal algorithm for training from scratch on private data may not be the ideal algorithm for fine-tuning a pretrained model. While some works observe that DP-SGD can inherently benefit from the geometry of the loss having certain properties, and others develop algorithms that adapt to the local geometry, we are not aware of any work that uses properties of the geometry specific to the fine-tuning phase. One possibility is that if the loss function is locally convex after public pretraining, theoretical techniques whose utility guarantee depends on convexity might offer larger improvements for private fine-tuning in practice than for training from scratch.

In our experiments, we observed that the first phase of model training is more sensitive to noise when we do fully private training from random initialization. As our two-phase hypothesis suggests, this phenomenon only occurs in non-convex optimization. In convex optimization, an opposite strategy of reducing the privacy noise towards the end of training helps more, as theoretically analyzed and empirically demonstrated in . For non-convex optimization, proposes the use of a decreasing noise multiplier under a strong condition on the loss function known as the Polyak-Lojasiewicz condition. This implies that vanilla gradient descent converges fast and does not apply for the typical loss landscapes of deep learning problems. For typical non-convex optimization experiments in our setting, smaller privacy noise at the beginning of the training improves performance (compared to having smaller privacy noise at the end of training). Of course, the need to choose a strategy for scheduling the privacy budget adds a hyperparameter for the training process. In particular, this hyperparameter is not needed if we do public pretraining instead. It would be useful for practitioners to give guidelines on how to schedule the privacy budget across training rounds such that we improve over a fixed noise multiplier, while minimally increasing the number additional hyperparameters to tune.

References

Appendix A Notation Reference

In Table 3, we give a summary of the notation used throughout the paper.

Appendix B Survey of the gain of pretraining

The stark difference in the gain of public pretraining between private and non-private model training has been widely observed in several tasks both in natural language and vision.

Table-To-Text Generation. The experiment details can be found in .

Image classification. The experimental details can be found in .

Appendix C Missing Details from Section 2

Before turning to the proof, we fill in the details of the construction given in Section 2: We choose $R_{1}=1/p^{2}+\kappa\log(p)/\sqrt{p}$, where $\kappa$ is a sufficiently large constant. Any $R_{2}<M-R_{1}$ suffices for our proof. We choose $r=O(\frac{1}{p^{5/2}\sqrt{\log(1/\delta)}})$. We formally define the range of data distributions we use in our construction as a set of products of two distributions: $\mathcal{T}:=\{\tau_{1}\times\tau_{2}|\tau_{1}\in\mathcal{T}_{1},\tau_{2}\in\mathcal{T}_{2}^{\prime}\}$, where $\mathcal{T}_{1}$ is defined as in Lemma 1.2, and $\mathcal{T}_{2}$ is defined as in Section 2.

In our proof we will use DP-SGD as instantiated in . Combined with results on uniform stability of gradient descent on strongly convex losses (see e.g. ), Theorem 2.4 of and its proof implies the following:

We also have the following lemma, which effectively says that unconstrained and DP-SGD stays within a ball with high probability.

With probability $1-T2^{-\Omega(p)}$ over (unconstrained) DP-SGD using the parameters in Theorem C.1, for all $0\leq t\leq T$, we have $\left\|\theta_{t}-\theta^{*}\right\|_{2}\leq\max\{2\sqrt{p}\sigma/m,\left\|\theta_{0}-\theta^{*}\right\|_{2}\}$.

We will prove (1) in two parts. First, we will show that for any $\mathcal{A}_{priv}$, there exists $\tau_{1}\in\mathcal{T}_{1}$ such that the desired lower bound holds for $\tau_{1}\times\tau_{2}$ for all $\tau_{2}\in\mathcal{T}_{2}^{\prime}$. Second, we show that for any $\mathcal{A}_{pub}$ there exists $\tau_{2}\in\mathcal{T}_{2}^{\prime}$ such that the desired lower bound holds for $\tau_{1}\times\tau_{2}$ for all $\tau_{1}\in\mathcal{T}_{1}$. Then taking $\tau_{1}$ from the first statement and $\tau_{2}$ from the second statement, both lower bounds hold for $\tau_{1}\times\tau_{2}$ as desired.

In other words, if we choose $\theta_{2}$ to be the minimizer of $\mathcal{L}_{2}$, then our risk on $\mathcal{L}$ is at least our risk on $\mathcal{L}_{1}$ alone. Putting it all together:

Using Lemma 1.2, since we are solving a $p^{4}$-dimensional mean estimation problem with $p^{2}$ samples and $(1,o(1/n)$-DP, we know that the final expression (the risk of $\mathcal{A}_{priv}^{\prime}$) is $\Omega(1)$ for some $\tau_{1}\in\mathcal{T}_{1}$, which implies the same lower bound on the risk of $\mathcal{A}_{priv}$ for $\tau_{1}\times\tau_{2}$.

Proof of (1) for $\mathcal{A}_{pub}$: Fix an arbitrary $\tau_{1}\in\mathcal{T}_{1}$. Let $\tau(\tau_{2})$ denote $\tau_{1}\times\tau_{2}$. Given any $\mathcal{A}_{pub}$, consider $\mathcal{A}_{pub}^{\prime}$ that takes $p$ samples from $\tau_{2}$, pads them with i.i.d. samples from $\tau_{1}$ to get $p$ samples from $\tau(\tau_{2})$. It then runs $\mathcal{A}_{pub}$ on these samples, clips the norm of the $\theta_{2}$ in $\mathcal{A}_{pub}$’s output to be at most $r$, and uses this as its output.

The proof is almost exactly the same as Theorem 2.1, so we only highlight the changes to that proof.

We define $\mathcal{T}$ similarly to Theorem 2.1: For each $\tau=\tau_{1}\times\tau_{2}$ in $\mathcal{T}$ as defined in Theorem 2.1, we replace it with $(\tau_{pub}=\tau_{1}\times Z,\tau_{pub}=\tau_{1}\times\tau_{2})$ where $Z$ is a point distribution on the origin.

The upper bound in (2) follows since the algorithm only evaluates gradients on the public data where $q(\theta_{1})=0$, i.e. it never uses the coordinates in the public data that are changed between this theorem and Theorem 2.1. ∎

Appendix D Quadratic Example

In this section, we show that our construction holds even if the loss function is quadratic, as long as we are okay with using a constrained optimization problem.

For $\delta=o(1/p^{2})$, any (non-private) algorithm $\mathcal{A}_{pub}:\mathcal{D}^{p}\rightarrow\mathcal{C}$, and any $(1,\delta)$-DP algorithm $\mathcal{A}_{priv}:\mathcal{D}^{p^{2}}\rightarrow\mathcal{C}$ there exists $\tau$ such that:

For any $\delta\geq 2^{-p}$, there exists an algorithm $\mathcal{A}_{mixed}:\mathcal{D}^{p+p^{2}}\rightarrow\mathcal{C}$ which runs projected gradient descent on the first $p$ examples, followed by $(1,\delta)$-DP-SGD on the last $p^{2}$ examples, such that for any $\tau$:

As in the proof of Theorem 2.1, we will show (1) in two parts: for any $\mathcal{A}_{priv}$, there exists $\tau_{1}\in\mathcal{T}_{1}$ such that the desired lower bound holds for $\tau_{1}\times\tau_{2}$ for all $\tau_{2}\in\mathcal{T}_{2}^{\prime}$, and that for any $\mathcal{A}_{pub}$ there exists $\tau_{2}\in\mathcal{T}_{2}^{\prime}$ such that the desired lower bound holds for $\tau_{1}\times\tau_{2}$ for all $\tau_{1}\in\mathcal{T}_{1}$.

Now, consider an algorithm $\mathcal{A}_{priv}^{\prime}$ that takes $p^{2}$ samples from $\tau_{1}$, pads them with the origin to get $p^{2}$ samples from $\tau(\tau_{1})$ in the preceding paragraph, runs $\mathcal{A}_{priv}$ on these samples, and then takes $\theta_{1}$ from the output of $\mathcal{A}_{priv}$. Notice that:

By 1.2, the final expression is $\Omega(1)$ for some distribution $\tau_{1}(\mathcal{A}_{priv})$. In turn, for the corresponding $\tau(\tau_{1}(\mathcal{A}_{priv}))$, $\mathcal{A}_{priv}$ has excess population loss $\Omega(1)$ in expectation as desired.

Proof of (1) for $\mathcal{A}_{pub}$: This follows by an argument symmetric to the previous part, except we use 1.3 instead of 1.2, and the observation that minimizing $\frac{p}{2r^{2}}\left\|\theta_{2}-d_{2}\right\|_{2}^{2}$ is equivalent to minimizing $\frac{p}{2}\left\|\theta_{2}-d_{2}\right\|_{2}^{2}$ over $B_{p}(0,1)$. In particular, the lower bound on just $\left\|\theta_{2}-d_{2}\right\|_{2}^{2}$ given by 1.2 is $\Omega(1/p)$, and the lower bound of $\Omega(1)$ on $\mathcal{L}$ follows after using the same reduction as in the proof of (1) and taking into account the multiplier $\frac{p}{2}$.

Proof of (2): This follows similarly to Theorem 2.1, so we only highlight the high-level proof and major changes here. A single step of projected gradient descent on the public data gets us to the empirical minimizer of $\theta_{1}$, which achieves excess risk $O(1/p)$ on $\frac{1}{2}\left\|\theta_{1}-d_{1}\right\|_{2}^{2}$. Then, since we are using projected gradient descent, we know $\theta_{2}$ is distance $O(r)$ from the population minimizer of $\theta_{2}$, so projected DP-SGD on the private data gets to a point which achieves risk $O(1/p)$ on $\frac{p}{2r^{2}}\left\|\theta_{2}-d_{2}^{2}\right\|_{2}$. By a similar argument to Theorem 2.1, projected DP-SGD does not cause $\theta_{1}$ to move by more than $O(1/p)$ with high probability if $r=O(\frac{1}{p^{5/2}\sqrt{\log(1/\delta)}})$. ∎

If we want to take this same example and make it unconstrained, an issue arises: A single step of gradient step with step size $1$ will cause $\theta_{2}$ to move by $1/r^{2}$, which is far larger than the radius of the ball that $\theta_{2}$ was restricted to in the constrained setting. In turn, the DP-SGD guarantees worsened. We can remedy this by taking smaller step sizes on the public data so that each step is non-expansive, i.e. $\theta_{2}$ does not leave the ball and the DP-SGD guarantees still hold. However, in order to do so we need to use step sizes where $\eta=O(r^{2})$, which means we will need to take $\Omega(1/r^{2})$ steps in order to reduce our distance to the minimizing $\theta_{1}$ by a constant. Since $r$ is being set to a small value, this is a large number of steps. In other words, it is possible to take this example and make it unconstrained, while still satisfying that public-then-private gradient descent achieves the desired excess loss, but the algorithm will not be efficient.