Year: 2021

Abstract:
In this paper, we revisit the problem of using public data to improve the privacy/utility trade-offs for differentially private (DP) model training. Here, public data refers to auxiliary data sets that have no privacy concerns. We consider public training data sets that are from the same distribution as the private training data. For convex losses, we show that a variant of Mirror Descent provides population risk guarantees which are independent of the dimension of the model (p). Specifically, we apply Mirror Descent with the loss generated by the public data as the mirror map, and using DP gradients of the loss generated by the private (sensitive) data. To obtain dimension independence, we requireGQ ≤ p public data samples, where GQ is the Gaussian width of the smallest convex set Q such that the public loss functions are 1-strongly convex with respect to ‖ · ‖Q. We further show that our algorithm has a natural “noise stability” property: If in a bounded region around the current iterate, the public loss satisfies αv-strong convexity in a direction v, then using noisy gradients instead of the exact gradients shifts our next iterate in the direction v by an amount proportional to 1/αv (in contrast with DP stochastic gradient descent (DP-SGD), where the shift is isotropic). Analogous results in prior works had to explicitly learn the geometry using the public data in the form of preconditioner matrices. Our method is also applicable to non-convex losses, as it does not rely on convexity assumptions to ensure DP guarantees. We demonstrate the empirical efficacy of our algorithm by showing privacy/utility trade-offs on linear regression, deep learning benchmark datasets (WikiText-2, CIFAR-10, and EMNIST). We show that our algorithm not only significantly improves over traditional DP-SGD, which does not have access to public data, but also improves over DP-SGD on models that have been pretrained with the public data to begin with.

text: In this paper, we revisit the problem of using public data to improve the privacy/utility trade-offs for differentially private (DP) model training. Here, public data refers to auxiliary data sets that have no privacy concerns. We consider public training data sets that are from the same distribution as the private training data.
For convex losses, we show that a variant of Mirror Descent provides population risk guarantees which are independent of the dimension of the model (p). Specifically, we apply Mirror Descent with the loss generated by the public data as the mirror map, and using DP gradients of the loss generated by the private (sensitive) data. To obtain dimension independence, we requireG2Q ≤ p public data samples, where GQ is the Gaussian width of the smallest convex set Q such that the public loss functions are 1-strongly convex with respect to ‖ · ‖Q. We further show that our algorithm has a natural “noise stability” property: If in a bounded region around the current iterate, the public loss satisfies αv-strong convexity in a direction v, then using noisy gradients instead of the exact gradients shifts our next iterate in the direction v by an amount proportional to 1/αv (in contrast with DP stochastic gradient descent (DP-SGD), where the shift is isotropic). Analogous results in prior works had to explicitly learn the geometry using the public data in the form of preconditioner matrices. Our method is also applicable to non-convex losses, as it does not rely on convexity assumptions to ensure DP guarantees.
We demonstrate the empirical efficacy of our algorithm by showing privacy/utility trade-offs on linear regression, deep learning benchmark datasets (WikiText-2, CIFAR-10, and EMNIST). We show that our algorithm not only significantly improves over traditional DP-SGD, which does not have access to public data, but also improves over DP-SGD on models that have been pretrained with the public data to begin with.

heading: 1 INTRODUCTION
text: Differentially Private Stochastic Gradient Descent (DP-SGD) (Song et al., 2013; Bassily et al., 2014; Abadi et al., 2016), and its variants (Kairouz et al., 2021b) have become the de facto standard algorithms for training machine learning models with differential privacy (DP) (Dwork et al., 2006). While DP-SGD is known to be optimal in terms of obtaining both optimal excess empirical risk (Bassily et al., 2014), and excess population risk (Bassily et al., 2020b) for convex losses, the obtained error guarantees suffer from an explicit polynomial dependence on the model dimension (p). This polynomial dependence significantly impacts the privacy/utility trade-off when p ≥ npriv, where npriv is the number of private training samples. Thus, even empirically, when DP-SGD is used to train large deep learning models, there is a significant drop in accuracy compared to the nonprivate counterpart (Papernot et al., 2020). In this paper, we revisit the problem of effectively using public data (i.e., data drawn from the same distribution as the private training data set, but without privacy concerns) to improve the privacy/utility trade-offs for DP model training. Specifically, we design a central DP variant of mirror descent (Nemirovsky & Yudin, 1983) that uses the loss function generated by the public data as the mirror map and DP gradients on the private/sensitive data as the linear term, ensuring population risk guarantees for convex losses with no explicit dependence on dimensions as long as npub ≥ p, where npub is the number of records in the public data set.
We show both theoretically and empirically that our DP variant of mirror descent, assisted with public data, can improve the privacy-utility trade-offs by effectively reducing the variance in the noise added to the gradients in DP model training. Our empirical results are on standard benchmark data sets like CIFAR-10, EMNIST, and WikiText-2.
Learning Geometry with Mirror Maps: Common to most DP model training algorithms, including DP-SGD, DP-FTRL (Kairouz et al., 2021b), and our algorithm, is a DP estimator of the gradient of the loss ∇θL(θt;Dpriv) = ∑ d∈Dpriv ∇θ`(θt; d) generated by the private data set Dpriv at a given model state θt ∈ Rp. This DP estimator essentially adds isotropic Gaussian noise N (0, σ2Ip) to ∇θL(θt;Dpriv), where σ depends on the privacy parameters (ε, δ) and the maximum allowable value of ‖∇θ`(θt; d)‖2 (a.k.a. the clipping norm (Abadi et al., 2016)).1 It is well known that for most learning tasks, the set of gradients vectors in L(θt;Dpriv) are seldom isotropic (Gur-Ari et al., 2018; Agarwal et al., 2019). Hence, it is natural to wonder if the Gaussian noise in the DP estimator can be made to respect the geometry of the gradients. Prior works (Zhou et al., 2020; Asi et al., 2021; Kairouz et al., 2021a) have used public data (Dpub) to explicitly learn this geometry, mostly in the form of preconditioner matrices (Duchi et al., 2011) to be multiplied to the estimated noisy gradients. In this paper, we take an implicit approach towards respecting this geometry, by using the loss L(θ;Dpub) generated by the public data as the mirror map in classical mirror descent. As a first order approximation (formalized in Section 4), one can view it as doing DP-SGD on L(θ;Dpriv) while using L(θ;Dpub) as a regularizer. This approach has the following advantages: (i) The information of the geometry is “free”, i.e., one does not need to learn the preconditioner explicitly from the public data, (ii) Unlike prior works (Zhou et al., 2020; Kairouz et al., 2021a), one does not need to assume that the gradients of L(θ;Dpriv) lie in a fixed rank subspace, (iii) The achieved excess population risk guarantees have better dependence on npub = |Dpub| compared to prior results (Asi et al., 2021), and (iv) Because the geometry is implicitly defined, the implementation does not need to maintain an additional data structure for the preconditioner, and hence is much easier to implement. Empirically, under our best-effort comparison, our baseline algorithm improves over the state of the art (Asi et al., 2021).2 We note that differentially private mirror descent has been considered before by Talwar et al. (2014) and Wang et al. (2017). Their results are not directly comparable to ours because (i) they do not have access to in-distribution public data (ii) as shown in Bassily et al. (2014), without public data, it is impossible to achieve the dimension independent bounds we achieve (iii) in our experiments we solve unconstrained optimization problems, but those works choose the mirror map based on the constraint set rather than the data set. We note that the utility bounds we prove in this paper also apply to a public data-assisted variant of the accelerated mirror descent algorithm considered in Wang et al. (2017).
In-distribution vs. Out-of-distribution Public Data: Prior works have considered both settings where the public data set Dpub comes from the same distribution as the private data Dpriv (a.k.a. indistribution) (Bassily et al., 2018a; Zhou et al., 2020; Kairouz et al., 2021a; Asi et al., 2021), and where the distributions are different (a.k.a. out-of-distribution) (Abadi et al., 2016; Papernot et al., 2016; 2018; Liu et al., 2021). In principle, our algorithm can be used in out-of-distribution settings, but our results in this paper are for the in-distribution case. In the in-distribution setting, it is typical that there are fewer public data samples available than private data samples – i.e., npub npriv – as it is harder to obtain public data sets than ones with privacy constraints attached. In-distribution public data could come from either altruistic opt-in users (Merriman, 2014; Avent et al., 2017) or from users who are incentivized to provide such data (e.g., mechanical turks). Out-of-distribution public data may be easier to obtain but can have various degrees of freedom; e.g., the domains of private and public data may not be identical, the representation of some classes may vary, the distributions can be mean shifted, etc. It is usually hard to quantify these degrees of freedom to the extent that we can provide precise guarantees. Hence, we leave this aspect for future exploration, and work with the idealized assumption that the public data comes from the same distribution as the private data, or, at least, that the differences between these two distributions are not material.
Design of Algorithms without Relying on Convexity for Privacy: While most of our theoretical utility guarantees are specific to convex functions, our algorithm can be used seamlessly in nonconvex settings. The main reason is that its DP guarantee does not rely on convexity. Prior work
1For the ease of presentation, at this point we do not consider the noise due to stochastic mini-batching. 2The implementation of Asi et al. (2021) is not publicly available. Since the algorithms can be sensitive to
hyperparameter choices, for a fair comparison we directly consider the results quoted in (Asi et al., 2021).
that provided similar dimension-independent excess population risk guarantees under the the same conditions as ours (i.e., npub ≥ p) (Feldman et al., 2018) heavily relied on convexity to ensure DP and hence, cannot be used in non-convex settings.
Choice of Benchmark for Empirical Comparison: Mirror descent (Nemirovsky & Yudin, 1983; Hazan, 2019) as a first step optimizes the mirror map function. In our setting, this corresponds to pre-training on the public loss function L(θ;Dpub) before running the DP optimization procedure on L(θ;Dpriv). Since pre-training on public data is intuitive and easy, we always compare to DP-SGD (and its variants) that have been pre-trained to convergence with the public loss. We show that our algorithm outperforms even pre-trained DP-SGD. To the best of our knowledge, ours is the only empirical work that compares to this strong (but fair) benchmark.
Other Uses of Public Data in DP Learning: The use of in-distribution public data has been extensively explored both theoretically and empirically. On the theoretical side, it has been shown (Alon et al., 2019; Bassily et al., 2020a) that a combination of private and public data samples can yield asymptotically better worst-case PAC learning guarantees than either on their own. Another line of work (Papernot et al., 2016; 2018; Bassily et al., 2018b; Dwork & Feldman, 2018; Nandi & Bassily, 2020) considers public data that is unlabelled, but otherwise comes from the same distribution as the private data; the primary goal is to use the private data to generate labels for the public data, which can then be used arbitrarily. So far only two papers have considered out-of-distribution data. Bassily et al. (2020c) assume that whether a data record is public or private depends on its label; e.g., the public data may contain many negative examples, but few positive examples. They show that halfspaces can be learned in this model. Liu et al. (2021) consider synthetic data generation and provide guarantees that depend on the Rényi divergences between the public and private distributions. Abadi et al. (2016) and Tramer & Boneh (2020) provided techniques to effectively use out-of-distribution public data for pre-training for DP-SGD. However, they did not consider techniques to improve a pre-trained model using private and public data, which is the focus of our work.

heading: 1.1 PROBLEM FORMULATION
text: Consider the classic differentially private stochastic convex optimization (DP-SCO) (Chaudhuri et al., 2011; Bassily et al., 2014; 2019; 2020b) setting. Let τ be a distribution over a fixed domain D. Given a data set D ∈ D∗ drawn i.i.d. from τ , and a loss function `priv : Rp ×D → R, the objective is to approximately solve arg min
θ∈C Ed∼τ [`priv(θ; d)], while preserving DP. Here, C ⊆ Rp
is the constraint set. Usually one solves the SCO problem via empirical risk minimization (ERM), i.e., θpriv ∈ arg min
θ∈C L(θ;D), where L(θ;D) = 1|D| ∑ d∈D `priv(θ; d), and then uses θpriv as a proxy.
Up to a dependence on dimensionality p, in the DP setting, a direct translation from ERM to the SCO setting provides the optimal rates (Bassily et al., 2014; 2019; 2020b). Since we will strive for dimension-independent convergence rates, we thus safely ignore the issue of non-optimality due to dimensionality, and treat the ERM and SCO problems as almost equivalent.
In this paper, we consider the DP-SCO setting with heterogeneous data, where there are two data sets Dpriv (with npriv samples) andDpub (with npub samples) drawn i.i.d. from the same distribution. The private data set Dpriv consists of records from individuals who require privacy protection, whereas the public data set Dpub does not require any privacy protection. Since obtaining such data can be expensive, for our empirical evaluation, we assume npub is a small fraction of npriv (e.g., < 5%).
We will also use a separate public loss function `pub. For our theoretical analysis, we will assume `priv is convex and L-Lipschitz, whereas `pub is strongly convex (both with respect to the `2-norm). In practice, one will likely choose `priv = `pub, but clip the gradients of `priv for privacy. In general, `pub can be arbitrary, but for the analysis, we will assume that `pub and `priv roughly share a minimizer and that ∇`pub(θ; d) has bounded variance (see Assumption 3.1 for a formal statement). We refer the reader to Appendix A for a reference for the notation used throughout the paper.

heading: 1.2 OUR CONTRIBUTIONS
text: Dimension Independent Excess Population Risk for Constrained ERMs: The standard private SCO excess empirical loss bound for a constraint set C is: O ( L ‖C‖2 · √ p log(1/δ)
εnpriv
) , where L is the
Lipschitz constant of the loss function and n is the number of samples in the dataset. If we pre-train on public data and are able to find a solution within distance O ( 1√ p ) of the optimal solution, we
can set C to be the ball of radius O (
1√ p
) centered on the pre-trained model and obtain a similar
dimension-independent error rate. There are a couple of issues with this approach: (i) It bakes in the utility assumption about the constraint set into the algorithm. This is unsatisfactory because if we are unlucky (due to stochasticity or choice of hyperparameters) and the optimal solution does not lie within this ball, using this choice of C may restrict us to a range of poor solutions that we cannot escape even if the number of private samples is very large, and (ii) It forces one to operate with projected gradient descent which may significantly impact accuracy in settings where the utility assumptions may not hold, e.g., in deep learning.
We improve upon this by showing that given npub public samples in addition to npriv private samples, using our PDA-DPMD (Public Data-Assisted Differentially Private Mirror Descent) algorithm, a variant of mirror descent that implicitly reshapes the noisy gradients according to the public loss
function, we can achieve excess empirical loss O ( LV · GQ √ log(1/δ)
εnpriv √ npub
) . The bound is proven in
Theorem 3.2. Here, V is a measure of the variance of the gradients of `pub, and GQ is the Gaussian width of the smallest set Q such that the public loss functions are 1-strongly convex with respect to ‖ · ‖Q. In particular, GQ is at most √ p if the public loss functions are 1-strongly convex, but can be constant if e.g. the public loss functions have a much larger strong convexity parameter in all but a constant number of basis directions. Note that if we have npub = G2Q public samples, then the 1/ √ npub and GQ terms cancel out, i.e. this error bound has no explicit dependence on dimension. Using standard techniques, we can turn this into a dimension-independent excess population loss bound (see Theorem 3.5), again assuming npub ≥ G2Q. In addition, to the best of our knowledge, ours is the first work on augmenting private training with public data to show a theoretical improvement over DP-SGD (here the dependence 1√npub ) due to pre-training on public data. In particular, we show pre-training improves the standard DP-SGD bounds even under a totally isotropic geometry.
Local Noise-stability of Mirror Descent: We show that in addition to achieving better excess population loss bounds, PDA-DPMD has the following “local noise-stability” property: If in a bounded region around the current iterate, the public loss satisfies αv-strong convexity in a direction v, then using noisy gradients instead of the exact gradients shifts our next iterate in the direction v by an amount proportional to 1/αv (see Theorem 3.6). That is, PDA-DPMD effectively rescales the effect of adding noise in any direction to be inversely proportional to the curvature in that direction. Note that this is in spite of the fact that for privacy, the noise we add to the gradients is usually isotropic. Furthermore, this rescaling is done purely as a function of the public loss function used by PDA-DPMD. In other words, a practitioner implementing PDA-DPMD simply needs to choose an appropriate loss function, and PDA-DPMD will “automatically” rescale the effects of noise to match the loss function’s curvature.
Empirical Evaluation: On both synthetic and real-world benchmark data sets, we show that PDADPMD outperforms DP-SGD, even when they are pre-trained on the public data set. We provide two sets of experiments. First, a linear regression on a synthetic data set which closely matches the utility assumptions in the theoretical analysis. Second, we provide results on standard deep learning benchmark data sets (WikiText-2, CIFAR-10, and EMNIST).
In Section 3, we consider using DP-SGD and PDA-DPMD to solve a least squares linear regression problem on a synthetic data set generated via the process bi ∼ N(〈ai, θ∗〉, σ2), where θ∗ ∈ Rp is the true model. The feature vectors ai’s are drawn i.i.d. from some fixed distribution. We fix the number of private data samples, and set the number of public samples to be a fixed constant times the dimension (p). We observe that as expected, public data allows us to substantially improve the error in two ways: (i) Pre-training: DP-SGD initialized from a model pre-trained on public data has nearly-constant mean-squared error, whereas DP-SGD from a random initialization has meansquared error scaling with the dimension, and (ii) Adapting to geometry using public loss: While DP-SGD initialized from a pre-trained model already achieves near-constant loss, we also observe that PDA-DPMD outperforms DP-SGD due to its error’s dependence on the Gaussian width GQ rather than the dimension. We note that the observed improvement is “automatic” once we choose the mean-squared error to be the loss function.
We also conduct experiments in Section 4 on two real world tasks: next word prediction on WikiText-2, and image classification on CIFAR-10 and EMNIST (ByMerge split). We consider 4% of the original training data as public and pretrain on it. On all datasets, we can observe that an approximate version of PDA-DPMD outperforms DP-SGD in terms of test loss. On CIFAR-10, the improvement is more than 5%; on EMNIST, 7%; on WikiText-2, log perplexity is improved by more than 0.3%, which is a notable improvement for perplexity.
For the deep learning experiments, running PDA-DPMD was computationally expensive. We derive a first-order approximation that can be viewed as regular DP-SGD on a convex combination of private and the public losses, i.e., α∇L(θ;Dpriv)+(1−α)∇L(θ;Dpub), α ∈ [0, 1], where∇L(θ;Dpriv) is privatized by clipping and adding noise. This approximation makes the running time of our algorithm comparable to DP-SGD when run on the data set Dpriv ∪Dpub.

heading: 2 BACKGROUND
text: Differential Privacy: Differential Privacy (DP) – originally defined by Dwork et al. (2006) – is a formal method for quantifying the privacy leakage from the output of a data analysis procedure. A randomized algorithm M : D∗ → Y is (ε, δ)-DP if, for all neighbouring dataset pairs D,D′ ∈ D∗ and all measurable sets of outputs S ⊆ Y , we have
P [M(D) ∈ S] ≤ eε · P [M(D′) ∈ S] + δ.
We define two datasets to be neighbouring if they differ only by the addition or removal of one person’s record. We ensure differential privacy by adding Gaussian noise to functions of bounded sensitivity. In particular, if ` is L-Lipschitz in its first parameter, then ‖∇θ`(θ; d)‖2 ≤ L for all θ and d ∈ D. Thus adding noise drawn from N (0, σ2 · Ip) to the sum
∑ i ∇θ`(θ, di) over people’s
records satisfies DP, where σ scales with L and the desired privacy parameters. The composition and postprocessing properties of differential privacy ensure that, as long as each step in our iterative algorithm satisfies differential privacy, then so does the overall system. We refer the reader to (Dwork & Roth, 2014) for further details of the standard privacy analysis of algorithms like ours.
Due to space constraints, we defer background on Mirror Maps and Gaussian Width to Appendix B.

heading: 3 PUBLIC DATA ASSISTED DIFFERENTIALLY PRIVATE MIRROR DECENT
text: In this section, we present our algorithm, PDA-DPMD, dimension-independent excess empirical and population loss bounds for PDA-DPMD (Theorems 3.2 and 3.5), and a “noise stability” property (Theorem 3.6). We defer all the proofs in this section to Appendix C.
Algorithmic Description: Our main algorithm, Public Data-Assisted Differentially Private Mirror Descent (PDA-DPMD), is given as Algorithm 1. PDA-DPMD is a variant of mirror descent using noisy gradients, but we also pre-train on public data and use the public loss as our mirror map Ψ.
Algorithm 1 Public Data-Assisted Differentially Private Mirror Descent (PDA-DPMD) Input: Public/private datasets Dpub, Dpriv of sizes npub, npriv, private/public loss functions `priv, `pub, privacy parameters (ε, δ), number of iterations T , learning rate η : {0, 1, . . . , T − 1} → R+, constraint set: C, clipping norm L: an upper bound on max
θ∈C ‖∇`priv(θ)‖2
1: Ψ(θ) := 1npub ∑ d∈Dpub `pub(θ; d), θ0 ← arg minθ∈C Ψ(θ), σ 2 ← 8L 2T log(1/δ) (εnpriv)2 2: for t = 0, . . . , T − 1 do 3: gt ← 1npriv ∑ d∈Dpriv ∇`priv(θ; d) 4: θt+1 ← arg minθ∈C [ηt〈gt + bt, θ〉+BΨ(θ, θt)], where bt ∼ N (0, σ2 · Ip) 5: end for 6: return θpriv := 1T ∑T t=1 θt
Note that Line 4 of PDA-DPMD is equivalent to the following: Choose θt+1/2 to be the point such that ∇Ψ(θt+1/2) = ∇Ψ(θt) − η(gt + bt), and then use the Bregman projection θt+1 =
arg minθ∈C BΨ(θ, θt+1/2). Intuitively, PDA-DPMD is similar to DP-SGD, with the main difference being we apply the gradient steps to ∇Ψ(θ) rather than to θ itself. Note that PDA-DPMD reshapes the gradient and noise automatically given `pub and Dpub. In contrast, e.g., private AdaGrad implementations (Kairouz et al., 2020; Asi et al., 2021) assume knowledge of the geometry of the loss function has already been learned prior to running their algorithms. Also, for an appropriate choice of Ψ, one can recover an algorithm that projects the private gradients to a low-dimensional subspace as in the algorithms of Zhou et al. (2020) and Kairouz et al. (2020).
Dimension Independent Empirical Risk Bounds for Convex Losses: We bound the excess empirical loss on the public loss function `pub, compared to the private population minimizer θ∗ (rather than the empirical minimizer). This is because the empirical minimizer θemp of the private loss function could be far away from θ∗, and in turn∇Ψ(θemp) could be much larger in expectation than ∇Ψ(θ∗). Our PDA-DPMD excess empirical loss bound will be in terms of ∇Ψ(θ), where θ is the point we are comparing to, so it is preferable to use θ = θ∗ for this reason.
We will use the following “bounded variance” assumption on the distribution of the datasets and the public loss function: Assumption 3.1. For some minimizer θ∗ ∈ arg minθ∈C Ed∼τ [`priv(θ; d)] we have that θ∗ is also the minimizer of Ed∼τ [`pub(θ; d)] in C and Ed∼τ [ ‖∇`pub(θ∗; d)− Ed∼τ [∇`pub(θ∗; d)]‖22 ] ≤ V 2.

heading: In particular, this implies
text: ED∼τnpub [∥∥∥ 1npub ∑d∈D∇`pub(θ∗; d)− Ed∼τ [∇`pub(θ∗; d)]∥∥∥22 ] = O ( V 2 npub ) .
We note that while Assumption 3.1 is written as generally as possible and thus captures scenarios where `pub and `priv could potentially be very different loss functions, the reader can think of them as differing only slightly. Indeed, Assumption 3.1 captures several scenarios we might see in practice, such as (i) `pub = `priv (which can occur if ‖C‖2 is small), (ii) `priv is the clipped version of `pub (see e.g., Song et al. (2021) for a discussion on the effects of clipping on the loss function), and (iii) `pub is `priv but with a regularizer added. Our empirical loss bound now follows by using Assumption 3.1 to control the Bregman divergence between the initial iterate and the population minimizer: Theorem 3.2. Suppose the private loss function L := 1npriv ∑ d∈Dpriv `priv(θ; d) is L-Lipschitz and convex. Suppose `pub is α-strongly convex, and let Q be the minimal convex body containing the origin such that each `pub(θ; d) is 1-strongly convex with respect to the Minkowski norm ‖ · ‖Q (defined as ‖x‖Q = min{c ∈ R≥0|x ∈ cQ}). Then PDA-DPMD is (ε, δ)-differentially private with respect to the private database Dpriv and choosing ηt = η for all t we have:
EDpub∼τnpub [L(θpriv)]− L(θ ∗) ≤ V
2
2αηTnpub + η ·O(L2 ‖Q‖22 + σ 2(G2Q + ‖Q‖ 2 2)).
The above bound is scale-invariant, so to simplify the presentation of this section, we assume, without loss of generality, that α = 1 (this also implies Q is contained within the unit `2-ball, i.e. ‖Q‖2 ≤ 1). By rescaling Ψ and η appropriately, we do not affect the behavior of PDA-DPMD, but get that Ψ is 1-strongly convex.
By chaining the following lemma with Theorem 3.2, we get an excess empirical loss bound with respect to the sample minimizer rather than the population minimizer as desired. Lemma 3.3. Let τ be a distribution over D, ` : C × D → R be a function such that `(θ; d) is L-Lipschitz and convex in θ for any fixed d ∈ supp(τ). Let θ∗ be the minimizer of Ed∼τ [`(θ; d)]. Then, we have ED∼τn [L(θ∗;D)−minθ∈C L(θ;D)] ≤ L‖C‖2√ n .
The lemma follows by using convexity and a bound on the expected `2-norm difference between the gradient of the empirical and population losses.
Excess Population Risk of PDA-DPMD: We now translate our excess empirical loss bound to a excess population loss. We use Lemma F.5 of Bassily et al. (2014), restated in Lemma 3.4 for convenience, which provides a black-box translation from empirical loss to population loss: Lemma 3.4. For any (ε, δ)-DP algorithm for minimizing 1npriv ∑ d∈Dpriv `(θ; d) over C, the expected excess population loss exceeds the expected excess empirical loss by O(L ‖C‖2 ε+ ‖C‖ 2 2 δ).
Given this lemma, it is straightforward to derive excess population loss bounds:
Theorem 3.5. For η = V L √ Tnpub
, T = ε2n2priv
G2Q log(1/δ) , and setting ε =
√ V GQ log
1/4(1/δ) √ nprivn 1/4 pub ‖C‖2 , the expected
population loss of PDA-DPMD is
O
( L √ V ‖C‖2 √ GQ log
1/4(1/δ) √ nprivn 1/4 pub + L ‖C‖2√ npriv + ‖C‖22 δ
) .
Theorem 3.5 follows immediately from Theorem 3.2, Lemma 3.3, and Lemma 3.4. Note that if npub ≥ G2Q, which is at most p, then the above bound has no explicit dependence on dimension. For comparison, if we were to only train on public data, the standard non-private excess population loss bound has dependence O(1/√npub) (and no dependence on dimension). So in the regime where npub ≈ G2Q and npriv npub, our bound is asymptotically much better than the baseline of training only on public examples. In Appendix D we show what values Q and GQ take on for some standard stochastic convex optimization problems to help the reader understand the bound in Theorem 3.5.
Local Stability Properties of PDA-DPMD: If the public loss function has a Hessian everywhere that has the same eigenvectors regardless of location (but perhaps different eigenvalues), we can bound the impact of adding noise to the gradient on each update in mirror descent: Theorem 3.6. Suppose for the public loss function Ψ, its Hessian is defined everywhere, and for a fixed orthonormal basis {vi}i, the Hessian at every point can be written as ∑ i wi(θ)viv > i for scalar functions wi : Rp → R+ such that for all i, θ, we have wi(θ) ≥ α. Fix an iteration t as well as private gradient gt in PDA-DPMD. Let θ∗ be the value of θt+1 after performing the mirror descent update with bt = 0 at iteration t, and let {w̃i}i, c ≥ 0 be such that for each i the smallest value of wi(θ) in the ellipsoid E := ( ∑ i 1 w̃i viv > i )BR (where BR is the `2 ball of radius
R := η(1 + c) √ pσ), centered at θ∗, is at least w̃i. Then for any (unit) direction v = ∑ i aivi,
E [ |〈θ̂ − θ∗,v〉| ] ≤ ησ √ 2 π · √√√√∑ i ( ai w̃i )2 + 3(1 + c)2 2α · e−c 2p/2  , where θ̂ is the value of the next iterate θt+1 if noise is added.
At a high level, Theorem 3.6 follows by observing that θ̂−θ∗ can be expressed as the inverse Hessian of Ψ evaluated at some point θ̃ times the noise vector bt. If the magnitude of bt is small enough, θ̃ stays within E and we can lower bound the inverse Hessian by 1w̃iviv > i . In the low-probability event bt’s magnitude is large enough, we can instead lower bound the inverse Hessian by 1α Ip.
Note that the condition wi(θ) ≥ α can be enforced by adding an `2-regularizer to the public loss function (since mirror descent only cares about differences in the gradients of the public loss function, the private training phase of PDA-DPMD behaves the same regardless of where this regularizer is centered). In contrast for DP-SGD, E [ |〈θ̂ − θ∗,v〉| ] = √ 2/π · ησ for any direction v.
Validation of Dimension-independence on Synthetic Linear Regression: To corroborate our theoretical results with empirical validation, we consider the linear regression problem with mean squared error loss: 1npriv ‖Xθ − y‖ 2 2. We vary the dimensionality of the problem p from 500 to 6000. For each p, we generate 10,000 private samples and 1.5p public samples. The optimal θ∗ is sampled fromN (0, Ip). To introduce a non-isotropic geometry, we sample the feature vector xi such that 40 of the first p/5 features and 80 of the last 4p/5 features, chosen uniformly at random, are set to 0.05, and the rest of the features are set to 0. In this way, the expected `2-norm of each feature vector (and in turn each gradient) is dimension-independent, and thus the effects of clipping should not vary with p. The predicted variable yi is sampled from N (θ∗ · xi, 0.01) so that the population mean squared error loss is always 0.01, i.e. independent of dimension. Since the norms of the gradients and number of private samples are dimension-independent, our error bound is proportional to GQ/ √ p, i.e. we do not expect it to vary much with dimension. We set ε = 1, δ = 10−5.
We consider three algorithms: (i) standard DP-SGD with a “cold start”, i.e. using a random initialization, (ii) standard DP-SGD with a “warm start” on the model pre-trained with public data, and (iii) PDA-DPMD after pre-training on public data.
1000 2000 3000 4000 5000 6000 Dimension
0.05
0.10
0.15
0.20
0.25
Em pi
ric al
lo ss
DP-SGD cold DP-SGD warm
(a) Cold start DP-SGD vs. warm start DP-SGD.
1000 2000 3000 4000 5000 6000 Dimension
0.020
0.022
0.024
0.026
0.028
0.030
Em pi
ric al
lo ss
DP-SGD warm PDA-DPMD warm
(b) Warm start DP-SGD vs. PDA-DPMD.
Figure 1: Comparisons of the empirical loss on synthetic linear regression data. The mean and error bars for a 95% confidence interval over 20 runs are plotted. The optimal population loss is 0.01.
0 1000 2000 3000 step
5.2
5.3
5.4
5.5
5.6
te st
lo ss
cos100 DP-SGD warm
DP-SGD cold
(a) σ = 0.5. ε = 15.7. 0 1000 2000 3000 step
5.3
5.4
5.5
5.6
5.7
te st
lo ss
cos50 DP-SGD warm
DP-SGD cold
(b) σ = 1.08. ε = 1.71.
Figure 2: WikiText-2. 4% public data. Validation and test loss. Averaged over 3 runs. Full plots available at Appendix F.3.
Figure 1a shows the empirical loss of cold- and warm-start DP-SGD. Since the dimension-dependent loss of DP-SGD is the excess empirical loss, we report empirical rather than population loss. As expected, pre-training with public data allows DP-SGD to achieve nearly dimension-independent error. Figure 1b compares warm-start DP-SGD and PDA-DPMD. The loss of PDA-DPMD is never worse than that of warm-start DP-SGD, and can be substantially lower for smaller dimensions. We observed that the ratio of the maximum and minimum eigenvalues of the Hessian X>X decreases as p increases, which means that the Hessian has poorly-concentrated eigenvalues at small p but gets closer to the identity matrix as p increases. Since PDA-DPMD recovers warm start DP-SGD when the Hessian is the identity, we can expect that PDA-DPMD obtains less of an advantage over DP-SGD as the Hessian gets closer to the identity. We provide additional details in Appendix E.

heading: 4 EMPIRICAL EVALUATION ON BENCHMARK DATA SETS
text: First-order Approximation to Mirror Descent: In practice, the Mirror Descent (MD) step in Line 4 of Algorithm 1 can be computationally expensive. For settings where (i) the problem is unconstrained, i.e., C = Rp and (ii) the public loss function Ψ(θ) may not be strongly convex with respect to the `2-norm, we can instead use the following more efficient approximation:
θt+1 ← θt − ηt (αt(gt + bt) + (1− αt)∇Ψ(θt)) , (1) where ηt is the learning rate, and αt ∈ [0, 1] balances the weight of private and public gradient. The derivation of this formula is in Appendix F.1. Notice that αt = 1 corresponds to DP-SGD on private data only. In our experiment, we decrease αt with a cosine schedule, i.e. αt = cos(πt/(2K)) where K is a hyperparameter that controls how fast αt decays. In practice, instead of computing gt and ∇Ψ(θt) using all the private and public data, we can estimate them with stochastic gradients. Now, we demonstrate the efficacy of our technique (Algorithm 1) with the update step in (1) on two real world tasks across three benchmark data sets: next word prediction on WikiText-2 (Merity et al., 2017), and image classification on CIFAR-10 (Krizhevsky, 2009) and EMNIST (ByMerge split) (Cohen et al., 2017). For each dataset, we randomly assign 4% of the original training data as public, and the rest as private. We do not consider a larger amount of in-distribution public data as that could make the problem trivial. We first pre-train on the public data, then use Algorithm 1 with update rule (1). We compare our algorithm with two baselines: “cold-start” DP-SGD, which uses the private data only, and “warm-start” DP-SGD, which pre-trains the model with public data and then fine-tunes with the private data. We demonstrate an increased benefit from the public data over and above just pre-training, which to our knowledge, has not been achieved in prior work. For WikiText-2, we use an LSTM model from Asi et al. (2021). For CIFAR-10 and EMNIST, we use network architectures considered in prior works (Papernot et al., 2020; Kairouz et al., 2021b). See Appendix F.2 for more details.
Empirical Evaluation on WikiText-2: Our setup mainly follows Asi et al. (2021). As a preprocessing step, we take the top 7,999 most frequent words and convert the rest into a special token representing unknown word. The data set is then split into 48,764 length-35 sequences, and we consider sequence-level privacy here. After pre-training, we fine-tune the model with batch size 250 for 20 epochs. We search for optimal K in {100, 200, 500}. For two different privacy levels, ε = 15.7 and 1.71 at δ = 10−5 (corresponding to σ = 0.5 and 1.08, respectively), Figure 2 shows the test
loss for PDA-DPMD with K = 100 and 50 respectively, and for the two baselines. From Table 1, we see that PDA-DPMD obtains the smallest test loss for both the privacy levels. Also, comparing the two DP-SGD baselines, we can see that using public data for pre-training provide trained models with higher utility.
Though our work’s focus is on in-distribution public data, we additionally compare with SoTA (Asi et al., 2021) which uses WikiText-103 (Merity et al., 2017) as the public data. In that setting, our warm start DP-SGD baseline is better than the proposed SoTA in (Asi et al., 2021) by 1.1% for ε = 1.0 and 6.6% for ε = 3.0 in terms of test perplexity. See Appendix F for more details.
Empirical Evaluation on CIFAR-10: CIFAR-10 consists of 50,000 training images and 10,000 test images from 10 classes. After pre-training, we fine-tune the model with batch size 500 for 100 epochs. We search for optimal K in {200, 500, 1000, 2000, 5000}. In Figure 3, for two different privacy levels, ε = 3.51 and 0.19 at δ = 10−5 (corresponding to σ = 1.51 and 20.0, respectively), we report the test loss and accuracy for K = 2000, and for the two baselines. From Table 1, we see that PDA-DPMD provides the best accuracy (even if by a small margin over the warm started DP-SGD baseline). Moreover, PDA-DPMD also results in significantly lower test loss compared to both the baselines for both privacy levels, which confirms with our theoretical analysis for the population loss.
Empirical Evaluation on EMNIST: EMNIST (ByMerge split) consists of 697,932 training images and 116,323 test images from 47 classes. After pre-training, we fine-tune with batch size 500 for 50 epochs. We search for optimal K in {200, 500, 1000, 2000, 5000}. In Figure 4 and Table 1, for σ = 0.41 and 1.89, corresponding to privacy ε = 25.80 and 0.48 at δ = 10−6, we report the test loss and accuracy forK = 500, and for the two baselines. We see a similar trend as with CIFAR-10.

heading: 5 ETHICS AND REPRODUCIBILITY
text: Ethics: This work focuses on improving the privacy/utility trade-offs for model training with sensitivity data by using publicly available data. We envision that this work will make the adoption of (differentially) private model training more ubiquitous, and hence improve on the current privacy landscape in the context of machine learning. Our experimental results are on standard benchmark data publicly available data sets, and do not have any ethical concerns.
Reproducibility: Our experiments are either on synthetic data sets, or on standard publicly available data sets. We have provided full details (including hyperparameter choices) for the experimental setup to reproduce the results in the paper. We will make the code for our experiments public as soon as possible. Additionally, we have detailed proofs for all our theoretical results in the appendix.

heading: A NOTATION REFERENCE
text: We recall here the notation used throughout the paper:
α A strong convexity parameter b Noise added to gradients for privacy BΨ The Bregman divergence induced by Ψ C The constraint set d A single sample
Dpub, Dpriv The public and private data sets respectively D The universe of samples ε, δ The privacy parameters η The learning rate/step size g A (batch) gradient GQ The Gaussian width of Q
`pub, `priv The (per-example) public and private loss functions respectively L The Lipschitz constant of `priv L The empirical (private) loss on dataset D, i.e. L(θ;D) = 1|D| ∑ d∈D `(θ; d) npub, npriv The number of public and private samples respectively p The dimensionality of the optimization problem Ψ The empirical public loss, i.e. Ψ(θ) = 1|Dpub| ∑ d∈Dpub `(θ; d); also the mirror map
Q A set such that Ψ is 1-strongly convex with respect to ‖ · ‖Q T The number of iterations in the optimization algorithm θ A solution to the optimization problem V A bound on the variance of the public gradients

heading: B MISSING BACKGROUND
text: Mirror Maps: A mirror map is a differentiable function Ψ : Rp → R that is strictly convex. Since Ψ is strictly convex and differentiable, ∇Ψ : Rp → Rp provides a bijection from Rp to itself. One can view θ as lying in a primal space and ∇Ψ(θ) as lying in a dual space. In turn, we could now consider optimizing over the value ∇Ψ(θ) in the dual space instead of θ primal space. Mirror descent does exactly that, performing gradient descent in the dual space by computing the gradient gt = ∇`(θt) (where θt lies in the primal space), taking a step in the opposite direction in the dual space, and then using the inverse of the mirror map to determine θt+1. Mirror descent is essentially motivated as minimizing a (linearized) loss plus a Bregman divergence (induced by Ψ) as the regularizer (Nemirovsky & Yudin, 1983). More formally, similar to proximal gradient descent, mirror descent is equivalent to taking the gradient gt and performing the update θt+1 = arg minθ∈C [η〈gt, θ〉+BΨ(θ, θt)] where BΨ(θ1, θ2) = Ψ(θ1)−Ψ(θ2)− 〈∇Ψ(θ2), θ1 − θ2〉 is the Bregman divergence generated by Ψ. Note that, if Ψ(θ) = ‖θ‖22, then the Bregman divergence is simply BΨ(θ1, θ2) = ‖θ1 − θ2‖22 and mirror descent is equivalent to the usual gradient descent.
Gaussian Width: Given a bounded set Q ⊂ Rd, the Gaussian width of Q, GQ, is a measure of how isotropic the set is. GQ is defined as Eg∼N(0,Ip) maxx∈Q〈g, x〉. Although the Gaussian width is well-defined for any bounded set, for this paper it suffices to consider defining the Gaussian width of convex sets containing the origin such that maxx∈Q ‖x‖2 = 1. If Q is just the unit `2-ball, the “most isotropic” set satisfying this condition, then we have GQ = √ p; in particular, since every set Q satisfying maxx∈Q ‖x‖2 = 1 is contained in the `2-ball, this is the maximum Gaussian width of any such set. On the other hand, if Q is just the line from the origin to a single unit vector, we have GQ = Θ(1). More generally, for any ellipsoid centered at the origin whose axes have radii 0 ≤ ri ≤ 1, 1 ≤ i ≤ p, we have that the Gaussian width of this ellipsoid is √∑p i=1 r 2 i . As other examples, the Gaussian width of the `1-ball of radius 1 is roughly log p, and the Gaussian width of the `∞ ball of radius 1/ √ p is roughly √ p.

heading: C MISSING PROOFS FROM SECTION 3
text: Proof of Theorem 3.2. The privacy guarantee follows from the moments accountant analysis of Abadi et al. (2016).
For the utility guarantee, following the analysis of Theorem 3.2 of Talwar et al. (2014), we have:
E[L(θpriv)]− L(θ∗) ≤ BΨ(θ
∗, θ0)
ηT + η ·O(L2 ‖Q‖22 + σ 2(G2Q + ‖Q‖ 2 2), (2)
Let θ∗ in particular be the minimizer satisfying Assumption 3.1. By α-strong convexity, we have:
BΨ(θ ∗, θ0) = Ψ(θ ∗)−Ψ(θ0)−∇Ψ(θ0) · (θ∗ − θ0) ≤ 1
2α ‖∇Ψ(θ∗)−∇Ψ(θ0)‖22 .
Plugging this into Eq. (2) and noting that any Ψ we sample is 1-strongly convex with respect to ‖ · ‖Q, we get:
E[L(θpriv)]− L(θ∗) ≤ E [ ‖∇Ψ(θ∗)−∇Ψ(θ0)‖22 ] 2αηT + η ·O(L2 ‖Q‖22 + σ 2(G2Q + ‖Q‖ 2 2)
We will show that without loss of generality, we can assume∇Ψ(θ0) = 0 and Ed∼τ [∇`pub(θ∗; d)] = 0. Once we have this assumption, Assumption 3.1 completes the proof.
The assumption follows since by convexity of C we have
〈∇Ψ(θ0), θ0 − θ∗〉 ≤ 0, 〈Ed∼τ [∇`pub(θ∗; d)], θ∗ − θ0〉 ≤ 0 (3)
Then for any choice of Ψ and C where either θ0 or θ∗ is on the boundary of C, suppose we extend C infinitesmally along the line {θ0 + c(θ∗ − θ)|c ∈ R} (i.e., take a point on this line infinitesmally outside of C and update C to be the convex hull of itself and this point). Then by (3) we have that θ∗, θ0, defined as the minimizers in C, move apart from each other along this line and in turn by strong convexity the quantity ‖∇Ψ(θ∗)−∇Ψ(θ0)‖22 cannot decrease. This implies that for any fixed `pub and τ , the quantity E [ ‖∇Ψ(θ∗)−∇Ψ(θ0)‖22 ] is maximized for a choice of C such that ∇Ψ(θ0) = 0 and Ed∼τ [∇`pub(θ∗; d)] = 0.
Proof of Lemma 3.3. By convexity, for all θ ∈ C we have L(θ;D) ≥ L(θ∗;D) + 〈∇L(θ∗;D), θ − θ∗〉. Note that by optimality of θ∗ and convexity, for all θ ∈ C we have 〈Ed∼τ [∇`(θ∗; d)], θ− θ∗〉 ≥ 0. In turn, by the Cauchy-Schwarz inequality we can conclude that L(θ∗;D) −minθ∈C L(θ;D) is always upper bounded by ‖C‖2 · ‖∇L(θ∗;D)− Ed∼τ [∇`(θ∗; d)]‖2. By L-Lipschitzness of each `(θ; d) we have:
ED∼τn [‖∇L(θ∗;D)− Ed∼τ [∇`(θ∗; d)]‖2] ≤ L√ n ,
Which completes the proof.
Proof of Theorem 3.6. Let bt be the noise added for privacy. Without noise, mirror descent would set θ∗ to be such that:
−ηgt = ∇Ψ(θ∗)−∇Ψ(θt).
Similarly, given the noisy gradient gt + bt, mirror descent would set θ̂ to be such that:
−η(gt + bt) = ∇Ψ(θ̂)−∇Ψ(θt).
We then have:
−ηbt = ∇Ψ(θ̂)−∇Ψ(θ∗).
Since we assume the Hessian of Ψ is defined everywhere, we have that ∇Ψ(θ̂) − ∇Ψ(θ∗) = ∇2Ψ(θ̃)(θ̂ − θ∗) for some θ̃ on the line between θ̂ and θ∗. In turn, we have:
θ̂ − θ∗ = −η(∇2Ψ(θ̃))−1bt
The norm x of bt sampled from N(0, σ2Ip) has the chi distribution, i.e. pdf proportional to (x/σ)p−1e−(x/σ) 2/2. In particular, this gives the following standard tail bound:
Pr[‖X‖2 > (1 + c) √ pσ] ≤ exp(−c2p/2).
So with probability at least 1 − e−c2p/2, we have the event E that ‖bt‖2 is at most (1 + c) √ pσ. Conditioned on this event, we have that θ̂, and thus θ̃, is in E, i.e. the lower bounds w̃i apply to ∇2Ψ(θ̃). Since conditioning on E only decreases the expectation of |〈θ̂ − θ∗,v〉|, we have:
E [ η|〈θ̂ − θ∗,v〉||E ] ·Pr[E ] = ηE [ |〈(∇2Ψ(θ̃))−1bt,v〉||E ] ·Pr[E ]
≤ ηE [ |〈( ∑ i 1 w̃i viv > i )bt,v〉||E ] ] ·Pr[E ] ≤ ηE [ |〈( ∑ i 1 w̃i viv > i )bt,v〉| ] = E [ | ∑ i ai w̃i 〈bt,vi〉| ]
= ηE [ | ∑ i N(0, (ai/w̃i) 2)| ] = ηE [ |N(0, ∑ i (ai/w̃i) 2)| ] = √ 2 π · ησ √√√√∑ i ( ai w̃i )2 .
When E does not happen, we have wi(θ) ≥ α everywhere. So we have:
E [ η|〈θ̂ − θ∗, v〉||¬E ] ·Pr[¬E ] = ηE [ |〈(∇2Ψ(θ̃))−1b, v〉||¬E ] ·Pr[¬E ]
≤ η · 1 α E [|〈b, v〉||¬E ] · e−c 2p/2
To determine E [|〈bt,v〉||¬E ], note that the distribution of 〈bt,v〉 conditioned on ¬E is equivalent to the distribution of the first coordinate of bt conditioned on ¬E . We can sample bt by first sampling its norm ‖bt‖2 conditioned on ¬E , and then sampling a point on the sphere with radius ‖bt‖2 (no conditioning is required here). The expected absolute value of any coordinate (bt)i given ‖bt‖2 can be bounded as:
E [|(bt)i|] ≤ √ E [(bt)2i ] = ‖bt‖2 / √ p.
The inequality is Jensen’s inequality, and the equality uses the fact that the coordinates bi on the sphere are identically distributed, and so we have:
p · E [ (bt) 2 i ] = E [∑ i (bt) 2 i ] = ‖bt‖22 .
We now just need to bound the expectation of ‖bt‖2, given that it is at leastR. Since the distribution of ‖bt‖2 /σ has pdf proportional to xp−1e−x
2/2, this expectation is σ times:∫∞ (1+c) √ p xpe−x
2/2∫∞ (1+c) √ p xp−1e−x2/2 = Γ((p+ 1)/2)(1− P ((p+ 1)/2, (1 + c)2p/2))√ 2Γ(p/2)(1− P (p/2, (1 + c)2p/2)) .
Where Γ is the gamma function and P is the regularized gamma function. Analytically, we can verify that Γ((p+1)/2)Γ(p/2) ≤ √ p/2 for all p ≥ 1, and (1−P ((p+1)/2,(1+c) 2p/2)) (1−P (p/2,(1+c)2p/2)) ≤ 3(1 + c)
2 for all p ≥ 1. So we get:
E [‖bt‖2 |¬E ] ≤ 3(1 + c)2
2
√ pσ
Putting it all together, we get:
E [ η|〈θ̂ − θ∗, v〉||¬E ] ·Pr[¬E ] ≤ η · 1
α · 3(1 + c)
2
2 · e−c 2p/2 · σ
Now applying the law of total expectation gives the theorem statement.

heading: D EXAMPLES OF STOCHASTIC CONVEX OPTIMIZATION PROBLEMS
text: In this section, we consider two canonical stochastic convex optimization problems and the associated quantity GQ, to help understand the bound in Theorem 3.5. In both cases we specify the public loss; as previously mentioned, a natural choice is to take the private loss to be the clipped version of the public loss to ensure Lipschitzness holds.
Mean Estimation: Suppose we assume we know the true covariance matrix Σ in the mean estimation problem for data drawn from a multivariate Gaussian. Then mean estimation is equivalent to minimizing loss function 12n ∑ i(xi−θ)>Σ−1(xi−θ), where xi is the ith sample point, and θ is our estimated mean. The Hessian is Σ−1. By rescaling, wlog assume the maximum eigenvalue of Σ is 1. Now, the smallest set Q such that the public loss function is 1-strongly convex with respect to the Q-norm is the ellipsoid centered at the origin whose axes are in the directions of the eigenvectors of Σ, and whose length in the direction of the eigenvector vi is the corresponding eigenvalue λi. The Gaussian width of Q is thus √∑p i=1 λ 2 i . In particular, if e.g. Σ only has a few large eigenvalues (i.e., the data only has variance in a few directions), this is much smaller than p.
Linear Regression: We choose the loss to be the mean squared error. Now, the public loss function is proportional to ‖Xθ−y‖22, where X is the (public) feature matrix, y are the dependent variables, and θ is our model. In particular, this has Hessian X>X. By normalizing, we can assume wlog the smallest eigenvalue of this matrix is 1, and so similarly to mean estimation the quantity GQ is √∑p
i=1 1/λ 2 i , where λi are the eigenvalues of X >X (i.e., the singular values of X). Note that unlike in the previous example (where we assumed we knew Σ a priori and thus the Hessian was fixed), the Hessian here depends on the public data.

heading: E ADDITIONAL DETAILS FOR THE EXPERIMENT ON LINEAR REGRESSION
text: Note that the exact optimum on the public data can be computed exactly as θ∗pub = (X >X)−1X>y. The mirror descent step can also be solved exactly by applying the inverse of the Hessian X>X to the gradient, since the Hessian is the same everywhere.
For numerical stability, we add a small constant times the identity matrix to the Hessian before computing its inverse. We also normalize the Hessian of the loss function so its inverse (which is applied to the gradient before taking a step in PDA-DPMD) has maximum eigenvalue of one. This ensures that if the Hessian were a multiple of the identity matrix, DP-SGD and PDA-DPMD would behave exactly the same for the same hyperparameter choice.
We perform a grid search over the learning rate, clipping norm, and number of epochs used and report the best empirical loss. We perform 20 trials for each algorithm and dimension.

heading: F ADDITIONAL DETAILS ON REAL-WORLD EXPERIMENTS
text: F.1 FIRST-ORDER APPROXIMATION TO MIRROR DESCENT
In practice, the Mirror Descent (MD) step in Line 4 of Algorithm 1 is computationally the most challenging. In the following, we provide an approximation of this step in the setting where i) the problem is unconstrained, i.e., C = Rp and ii). the public loss Ψ(θ) may not be strongly convex with respect to the `2-norm. This approximation makes Algorithm 1 efficient in practice.
Consider the following equivalence of Line 4 of Algorithm 1, with Ψ(θ), the public loss on Dpub, replaced by Ψ̂(θ) = Ψ(θ) + 12 ‖θ‖ 2 2. This follows from (Hazan, 2019, Lemma 5.5).
θt+1 ← arg min θ∈Rp 〈 t∑ i=1 ηi (gi + bi) , θ 〉 + Ψ̂(θ) (4)
= arg min θ∈Rp t∑ i=1 ηi ( 〈gi + bi, θ〉+ 1 tηi Ψ(θ) ) + 1 2 ‖θ‖22
≈ arg min θ∈Rp t∑ i=1 ηi 〈 gi + bi + 1 tηi ∇Ψ(θi), θ 〉 + 1 2 ‖θ‖22 , (5)
where (5) follows from the first-order approximation Ψ(θ) ≈ Ψ(θi) + 〈∇Ψ(θi), θ − θi〉. In the experiments, we replace gi + bi + 1t·ηi∇Ψ(θi) with αi(gi + bi) + (1 − αi)∇Ψ(θi), where αi ∈ (0, 1]. This reparamertization helps with more effective hyperparameter tuning while training deep learning models. We therefore have the update rule (1).
F.2 SETUP
Network architectures: Table 2 shows model architectures for CIFAR-10, EMNIST, & WikiText2.
Hyperparameter Tuning: We keep the clipping norm to be 1. One small difference with the standard DP-SGD update rule is that we enforce an additional clipping step for the privatized gradient for the image classification task, where the clipping norm is the same as the clipping norm of for
individual gradient. The reason for this additional step is that the norm of the averaged clipping gradients should still be upper bounded by the clipping norm.
The only hyperparameters that need to be tuned are the learning rate andK that controls the decaying of αt. For the learning rate, we consider a grid of {1, 2, 5}×10i for different is such that the optimal learning rate does not appear on the boundary. We search for the optimal K in {100, 200, 500} for WikiText-2 and {200, 500, 1000, 2000, 5000} for the image classification tasks.
F.3 FULL PLOTS FOR SECTION 4
In Figure 5, we plot the complete version of Figure 2, and in Figure 6, we show the complete version of Figure 3.
F.4 WIKITEXT-2 WITH WIKITEXT-103 AS PUBLIC DATA
We compare with the SoTA (Asi et al., 2021) which uses WikiText-103 as public data. Specifically, we consider their “LargeAux” setting under ε = 1.0 and 3.0. Since the implementation for Asi et al. (2021) is not public as of writing this work, we make our best effort to match their experiment setup. We note that the data preprocessing and the number of iterations used (thus the noise multiplier for achieving the same ε) might differ.
We preprocess WikiText-103 as follows. After processing WikiText-2 as described in Section 4, we convert all words that does not appear in the processed WikiText-2 as the unknown token. Then, we split the sentences into length-35 sequences, and remove all sequences that overlap with WikiText-2. Finally, we randomly sample 48,764 sequences, in order to match the “LargeAux” setting where the public dataset is of the same size as the private training dataset.
Figure 7 shows the results. In our setting, cold start DP-SGD reaches similar log perplexity as those in (Asi et al., 2021), while the warm-start DP-SGD is already better than Asi et al. (2021) (LargeAux). The final test log perplexities are summarized below, with the results in (Asi et al., 2021) converted from perplexity to log perplexity.
Algorithm ε = 3.0 ε = 1.0
Asi et al. (2021) DP-SGD (cold) 5.4819 5.6623 Asi et al. (2021) (LargeAux) 5.4324 5.5254
Our DP-SGD (cold) 5.4030 5.5956 Our DP-SGD (warm) 5.3646 5.5141

Review summaries:
In this paper, the authors study differentially private empirical risk minimization (DP-ERM). Specifically, they study the case where the constraint set $\mathcal{C}$ has additional geometric structure, i.e., its Gaussian width could much lower than the underlying dimension $p$, such as the $\ell_1$-norm ball. The paper has been studied previously. However, this paper assume there are some additional public data. Specifically, they apply Mirror Descent with the loss generated by the public data as the *mirror map*, and using DP gradients of the loss generated by the private (sensitive) data. They also provide some experiments to show the performance of their algorithm.

In this paper, a new algorithm has been proposed which leverages in-distribution public data to provide improvements in private training. The algorithm uses the loss on public data (with a strongly convex loss function) as a “mirror map” to implement private mirror descent on the private data. It is shown to give dimension independent bounds in certain regimes. Empirically, on both synthetic and real world datasets it is shown to perform favourably compared to recent work.

The paper is in the continuation of recent line of work that studies private algorithms when it has access to some public data. They also achieve a dimension independent bound as in some of the previous work. The idea of the paper is very simple: they use public data as the mirror map in the private mirror descent algorithm.