Public Data-Assisted Mirror Descent for Private Model Training
Authors: Ehsan Amid
Arun Ganesh
Rajiv Mathews
Swaroop Ramaswamy
Shuang Song
Thomas Steinke
Vinith Menon Suriyakumar
Om Thakkar
Abhradeep Guha Thakurta
Venue: ICLR 2022 Submitted (2022)
Keywords: Differential Privacy
Public Data
Mirror Descent

Abstract: In this paper, we revisit the problem of effectively 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 set.

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 require $G_Q^2 \leq p$ public data samples, where $G_Q$ is the Gaussian width of the smallest convex set $Q$ such that the public loss functions are 1-strongly convex with respect to $\|\cdot\|_Q$. Our method is also applicable to non-convex losses, as it does not rely on convexity assumptions to ensure DP guarantees. 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 $\alpha_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/\alpha_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.

We demonstrate the empirical efficacy of our algorithm by showing privacy/utility trade-offs on linear regression, and deep learning benchmark datasets (CIFAR-10, EMNIST, and WikiText-2). 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.

Under review as a conference paper at ICLR 2022
PUBLIC DATA-ASSISTER MIRROR DESCENT FOR PRIVATE MODEL TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we revisit the problem of using public data to improve the pri- vacy/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 variant of Mirror Descent provides population risk guarantees which are independent of the dimension of the model (p). Specif- ically, 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 require G2 S p public data samples, where Go is the Gaussian width of the smallest convex set Q such that the pub- lic loss functions are I-strongly convex with respect to || |lo. 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 av--trong convexity in a direc- tion v. then using noisy gradients instead of the exact gradients shifts our next iterate in the direction by an amount proportional to 1/ 1/a.y (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, it does not rely 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 im- proves over traditional DP-SGD, which does not have access to public data, but also improves over DP-SGD models that have been pretrained with the public data to begin with.
INTRODUCTION
Differentially Private Stochastic Gradient Descent (DP-SGD) Song al. 2013 Bassily et al, 2014 Abadi et al., 2016), and its variants (Kairouz et al. 2021b) have become the de facto stan- dard algorithms for training machine learning models with differential privacy (DP) (Dwork 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 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 Rerivs where Prriv is the number of private training samples. Thus, even empirically, when DP-SGD is used train large deep learning models, there is a significant drop in accuracy compared to the non- private counterpart (Papernot et al., 2020). In this paper, we revisit the problem of effectively using public data (i.c., data drawn from the same distribution as the private training data set, but without privacy concern)) to improve the privacy/utility trade-off's for DP model training. Specifically, we design a central DP variant of mirror descent (Nmirovssy & Yudin 1983) that uses the loss function generated by the public data the mirror map and DP gradients the linear term, ensuring population risk guarantees for convex losses with no explicit dependence on dimensions as long as nppb p, where Upub is the number of records in the public data set.
the private/sensitive data as

---

Under review as a conference paper at ICLR 2022
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, 10, EMNIST, and WikiText-2.
Learning Geometry with Mirror Maps: Common to most DP model training algorithms, includ- ing DP-SGD, DP-FTRL (Kairouz et al. 2021b), and our algorithm, is a DP estimator of the gradient of the loss V VoL(0;; Ppriv) de Dain Vol(o,; d) generated by the private data set D priv at a given model state 8, E I... This DP estimator essentially adds isotropic Gaussian noise A o I2 to (oL(O(:Dpriv)) where a depends on the p parameters (E,6) and the maximum allowable value of [|Vo((0;;d]]l (a.k.a. the clipping norm (Abadi et al. 2016)). It is well known that for most learning tasks, the set of gradients vectors in 2(0; ((ip: Drric] are seldom isotropic (Gur-Ari et al., 2018 Agarwal 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) [As et al.) 202 Kairouz et al. (021a)) have used public data pub) to explicitly learn this geometry, mostly in the Torm of preconditioner matrices (Duchi et al. [011]) to be multiplied to the estimated noisy gradients. In this paper, we take an implicit approach towards respecting this geometry, by using the loss C(;; pubb) generated by the public data as the mirror map in classical mirror descent. As first order approximation (formalized in Section 4 one can view it as doing DP-SGD on [(0; D Dprv)) while using L(0; Pubb) as regularizer. This approach has the following advantages: (i) The infor- mation 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 [(;; Dpriv) lie in a fixed rank subspace, (iii) The achieved excess population risk guarantees have better dependence on Rppb pubb compared to prior results (Asi ett al. 2021), and (iv) Because the geometry is implicitly defined, the implementation does not need to maintain additional data structure for the preconditioner, and hence is much easier to imple- ment. 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 [assily eet 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-distributioo Public Data: Prior works have considered both settings where the public data set Pub comes from the same distribution as the private data Dpriv (a.k.a. in- distribution) (Bassily et al. 2018aa] Zhou et al.) [2200] Kairouz et al. 2021a: Asi et al., (222I), and where the distributions are different (a.k.a. oft-oo-distributinn 2016 2018. Liu et al., [022]. In principle, our algorithm can be used in out-of -fssttrbbbbtio 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., 7lpb << 7prrv - 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). Oft-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.
(Abadi et al. 2016, Papernot et al.,
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 non- convex settings. The main reason is that its DP guarantee does not rely on convexity. Prior work
For the ease of presentation, at this point we do not consider the noise due to stochastic mini-batching. 2The implementation of Asi al. (202)) is not publicly available. Since the algorithms can be sensitive to hyperparameter choices, for fair comparison we directly consider the results quoted in (Asi al. 2021
2

---

Under review as a conference paper at ICLR 2022
that provided similar dimension-indeeeedenn independent excess population risk guarantees under the the same conditions as ours (i.e., Roub 2 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 first step optimizes the mirror map function. In our setting, this corresponds to pre-training on the public loss function [(#: pubb) before running the DP optimization procedure on [(;; P.rv). 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 exten- sively explored both theoretically and empirically. On the theoretical side, it has been shown (Alon) ct 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 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 halfs- paces can be learned in this model. Liu et al. (2221) consider synthetic data generation and provide guarantees that depend on the Rényi divergences between the public and private distributions. (Abadi) et al.] (2016) and Tramer & Boneh (020) provided techniques to effectively use outto--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 the focus of our work.
1.1 PROBLEM FORMULATION
Consider the classic differentially private stochastic convex optimization (DP-SCO) (Chaudhuri
al., 2011 Bassily al. 2014 2019 2020b) setting. Let t be distribution over fixed do- main D. Given a data set D E Dr drawn i.i.d. from and a loss function Epriv RP x D + R, the objective is to approximately solve arg min Ed7T [erri d)], while preserving DP. Here, C S R. BEC is the constraint set. Usually one solves the SCO problem via empirical risk minimization (ERM), E (priv(); d), and then uses @priv as a proxy.
i.., (priv E arg min C(;; D), where [(0; D) = [D] dED
Σ
dEc
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 -nneeeendnndeeeeeeent 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 Drriv (with Mpriv samples) and Duub (with nup 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 require any privacy protection. Since obtaining such data can be expensive, for our empirical evaluation, we assume pub is a small fraction of Uprivv (e.g.. < 5%).
We will also use separate public loss function fpub- For theoretical analysis, we will assume fpriv is convex and L-Lipschitz, whereas pub is strongly convex (both with respect to the formm).) In practice, one will likely choose épriv lpub. but clip the gradients of priv for privacy. In general, pub can be arbitrary, but for the analysis, we will assume that fpbb and Epriv roughly share mini- mizer and that pl (f): d) has bounded variance (see Assumption 3.1 for formal statement). We refer the reader to Appendix A for a reference for the notation used throughout the paper.
1.2 OUR CONTRIBUTIONS
Dimension Independent Excess Population Risk for Constrained ERMs: The standard private
(oggg(1 where I, is the
SCO excess empirical loss bound for a constraint set C is: O T.11C]]2
etiphe
3

---

Under review as a conference paper at ICLR 2022
Lipschitz constant of the loss function and 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 of the optimal solution, we can set C to be the ball of radius O V/ inneessiooniddeeedden error rate. There are a couple of issues with this approach: (i) 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 range of poor solutions that 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.
centered on the pre-trained model and obtain similar
We improve upon this by showing that given пpbb public samples in addition Ppriv private sam- ples, 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 Goy/log(1/8)
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 |l llq-- In particular, Go is at most vp if the public loss functions are I-strongly convex, but can be constant if e.g. the public loss functions have much larger strong convexity parameter in all but a constant number of basis directions. Note that if we have Ropub = Gā public samples, then the
1/ /Poub and GQ terms cancel out, i.c. this error bound has no explicit dependence on dimension. Using standard techniques, we can turn this into a inneension-indpeenae bound (see Theorem 3.5). again assuming Puub 2 Gg. In addition, to the best of our knowledge, ours is the first work on augmenting private training with public data to show a theoretical improve- ment over DP-SGD (here the dependence Ariu
excess population loss
due to pre- pre-training on public data. In particular, we show pre-training improves the standard DP-SGD bounds even under a totally isotropic geometry.
We show that in addition to achieving better excess pop- ulation loss bounds, PDA-DPMD has the following "local noise stiee-stablltty" property: If in a bounded region around the current iterate, the public loss satisfies ay Strong convexity in a direction using noisy gradients instead of the exact gradients shifts our next iterate the direction v by an amount proportional to 1/av (see Theorem 3.6). That is, PDA-DPMI effectively rescales the ef- fect 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 add to the gradients is usually isotropic. Furthermore, this rescaling is done purely as a function of the public loss function used by PDA-DPMID. In other words, practitioner implementing PDA-DPMI 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.
Local Noise-stability of Mirror Descent:
then
Empirical Evaluation: On both synthetic and real-world benchmark data sets, we show that PDA- DPMD outperforms DP-SGD, even when they 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 2WikiText-2, CIFAR-10, and EMNIST).
In Section 3 we consider using DP-SGD and PDA-DPMD to solve least squares linear regression problem on a synthetic data set generated via the process by ~ N ((a,, o²), where 0* E IR is the true model. The feature vectors a,'s '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 mean- squared 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 's dependence 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.
4

---

Under review as a conference paper at ICLR 2022
We also conduct experiments in Section two real world tasks: next word prediction WikiText-2, and image classification on CIFAR-10 and EMNIST (ByMerge split). We consider 4% of the original training data 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%; Wiki'Text-,, 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 pri- vate and the public losses, i.e., a (L(); prriv) +1 (1-a))11)))) V pubb), a E [0. 1], where VL(0; D privv) is privatized by clipping and adding noise. This approximation makes the running time of our algo- rithm comparable to DP-SGD when run on the data set Ppriv Dubb
2 BACKGROUND
Differential Privacy:
Differential Privacy (DP) - originally defined by Dwork et al. (2066) is
formal method for quantifying the privacy leakage from the output of a data analysis procedure. A randomized algorithm M D + y is (c, 6D-D if, for all neighbouring dataset pairs D, D' E D and all measurable sets of outputs $ C V, we have
IP (M(D) E $) S e" P[M(DD) E S] 6.
We define two datasets to be neighbouring they differ only by the addition or removal of one person's 's record. We ensure differential privacy by adding Gaussian noise to functions of bounded sensitivity. In particular, É is L-Lipschitz in its first parameter, then (e d)llz S L for all and d E D. Thus adding noise drawn from NN o² Ip) to the sum Σ Vol(O, d,) 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 itera- tive 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
PUBLIC DATA ASSISTED DIFFERENTIALLY PRIVATE MIRROR DECENT
In this section, present algorithm, PDA-DPMD, ieiieension-inneeendeeee 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
Our main algorithm, Public Data-Assiste Differentially Private Mirror Descent (PDA-DPMD), given as Algorithm [ PDA-DPMD is variant of mirror descent using noisy gradients, but we also pre-train on public data and use the public loss as our mirror map V
Algorithmic Description:
Algorithm Public Data-Assisted Differentially Private Mirror Descent (PDA-DPMI)
Input:
Public/private datasets D Puub; prriv of sizes Ropub Nerive private/public loss functions l fpiv bpub. privacy parameters (e, 6), number of iterations T,, learning rate 7) : {0, 1, 1} R+ (0))()))122
constraint set: C, clipping norm L: upper bound max
BEC
(0) Tipuh EdeDae bpub (0;40:0 d), Oo < arg aigmingee (0),,, o² 8L Tlog/o)(
(ENpm)))
2: for t = 0 0....,
do 3: g: - Mppi EdeD Pe (0;
4: 0.+1 t arg mingec (ge + by, (0, 0z)), where b, ~ ~N Ip))
5: end for
6:
return Ppriv Σt= Oz
Note that Line 4 PDA-DPMD is equivalent to the following: Choose 0.+1/2 to be the point such that (1(411//)) (V,).) 1/(: + b.), and then the Bregman projection 0++1
5

---

Under review as a conference paper at ICLR 2022
arg mingen By (8, 11+1/2) Intuitively, PDA-DPMD is similar to DP-SGD, with the main differ- ence being we apply the gradient steps to V rather than to 0 itself. Note that PDA-DPMID reshapes the gradient and noise automatically given Loub and pub- In contrast, e.g., private Ada- Grad implementations (Kairouz et al., 2020; Asi 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 V. one recover an algorithm that projects the private gradients to low-dimensional subspace as in the algorithms of Zhou et al. (2020) and Kairouz et al. (020)).
Dimension Independent Empirical Risk Bounds for Convex Losses: We bound the excess empirical loss on the public loss function fub. compared to the private population minimizer 0* (rather than the empirical minimizer). This is because the empirical minimizer Demp of the private loss function could be far away from 0", and in turn (Oepp)))) could be much larger expectation than V (0"). Our PDA-DPMD excess empirical loss bound will be in terms of V L (f), where @ is the point we are comparing to, so it is preferable to use 0 = 0" for this reason.
We will use the following "bounded variance" assumption the distribution of the datasets and the public loss function:
Assumption 3.1. For some minimizer 0" E arg mingec Eaar [epriv (0;; d)] we have that Or is also the minimizer of Thaer pu (0; (0:d)] in C and Eaeu |i [ (0= (0*:d) Beder Elpub (0* []]]]] S V2. In particular, this implies
E ED- "pub
Pipus Eded pub Bader [V pub (f" d)) =
V2
We note that while Assumption 3.1 is written as generally as possible and thus captures scenarios where pub and ppriv 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 = Errv (which can occur if [CIl, is small), (ii) fpri is the clipped version of pub (see e.g., Sonn al. (2021) for discussion on the effects of clipping on the loss function), and (iii) Loub. 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 == Tipir EdeDa. f (f; d) is L-Lipschitz and convex. Suppose pub is a-strongly convex, and let Q be the minimal convex body containing the origin such that each pub (0; d) is 1-strongly convex with respect to the Minkowski norm || llo (defined as |xilq- minfc E R20/= E {Q}). Then PDA-DPMD is (s, d)diiferrentially private with respect to the private database Dpriv and choosing T)- = nofor all t we have:
V2
E Dous nor "mu (C(0pri)) L(0))
Poubll'ppub n O(L2 11012 + +Z (1Q11).
The above bound is scale-invariant, so simplify the presentation of this section, we assume, with- out loss of generality, that a = 1 (this also implies Q is contained within the unit balbll, i.e. |lQl1, < 1). By rescaling v and v appropriately, we do not affect the behavior of PDA-DPMD, but get that V is I-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 T be a distribution over D. l D + R. be a function such that E(O: d) is L-Lipschitz and convex in 0 for any fixed d E supp(T). Let 0* be the minimizer of Ea-- d)). Then, we have E [C(6": D) minsec [(]:D)] LICII2
Vn
The lemma follows by using convexity and a bound on the expected no-n 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 BDDP algorithm for minimizing _
Thyte EdED E(0; d) over C, the expected
excess population loss exceeds the expected excess empirical loss by ((T ||[|2 1IC1)2)..

---

Under review as a conference paper at ICLR 2022
Given this lemma, it is straightforward to derive excess population loss bounds:
Gg 1/g and setting E /VGa log" (1/6)) ttee expected
Theorem 3.5. For 1) = I. L
V
T
VMuui 1/2 [CIl
population loss of PDA-DPMDE is
L LVVicllyy log (110))
||C||22 Vpv
o
||C122
1/4 Aprii pub
3.3 and Lemma 3.4 Note that if pppb 2 GO which 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 /Tppb)))b (and no dependence on dimension). So in the regime where Ppubb R G3 and Plrriv >> "ppub. our bound is asymptotically much better than the baseline of training only public examples. In Appendix [ we show what values Q and Gg take on for some standard stochastic convex optimization problems to help the reader understand the bound in Theorem 3.5
Theorem 3.5 follows immediately from Theorem 3.2 Lemma
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 the gradient on each update in mirror descent:
Theorem 3.6. Suppose for the public loss function V, its Hessian is defined everywhere, and for a fixed orthonormal basis {vili, the Hessian at every point can be written as E, (,)vvv:v for sealar functions wi : R + R+ such that for all i, we have w;( 2 a. Fix an iteration as well private gradient g: in PDA-DPMD. Let Or be the value of 0c+1 after performing the mirror descent update with b, O at iteration I, and let (ws)er 2 0 be such that for each i the smallest value of w,( in the ellipsoid E == (Ei v.v BR (where BR is the Ez ball of radius R = n1(1 + /po), centered at 0", is at least w.. Then for any (unit) direction E. a,V.
E | 0r, v, sna
Σ
a4 Wi
2
3(1
c)2
-cpp/
V
2a
where ô is the value of the next iterate 8t41 if noise is added.
At a high level, Theorem 3.6 follows by observing that Ô-0" can be expressed as the inverse Hessian of V evaluated at some point 9 times the noise vector b, If the magnitude of b, is small enough, i stays within E and we can lower bound the inverse Hessian by V.V. In the low-probability event b, magnitude is large enough, we can instead lower bound the inverse Hessian by ITp
Note that the condition (f) 2 a can be enforced by adding an fz-regularizer to the public loss function (since mirror descent only cares about differences in the gradients of the public loss func- tion, the private training phase of PDA-DPMD behaves the same regardless of where this regularizer is centered). In contrast for DP-SGD,
[K0 8", .v) = 22/T no for any direction v.
Validation of Dimension-indeepeddence on Synthetic Linear Regression: To corrohorate our theoretical results with empirical validation, we consider the linear regression problem with mean squared error loss:
XX - y112. We vary the dimensionality of the problem p from 500 to 6000.
For each we generate 10,000 private samples and 1.5p public samples. The optimal 0* is sampled from (O0, Ip). To introduce non-isotropic geometry, we sample the feature vector x; 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 f2-norm of each feature vector (and in turn each gradient) is dimensionninndeeedeen -nddepnndeete., and thus the effects of clipping should not vary with p. The predicted variable y; is sampled from A0 x,, 0.01) so that the population mean squared error loss is always 0.01, i.c. independent of dimension. Since the norms of the gradients and number of private samples are dimension- wwwpssiioo-indeeedeeen. our error bound is proportional to Go/ Vp. ie. we do not expect it to vary much with dimension. We set E = 1, 5 = 10-b.
We consider three algorithms: (i) standard DP-SGD with "cold start", i.e. using random initial- ization, (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.
7

---

Under review as a conference paper at ICLR 2022
Cc5300
DP 500 cold
09230
DP-5GD coll
0.00
-0 5GD war
3P-500
5.7
3:35
5.6-
0-060
322
5.5
145
0.022
00.500 ware
3.4
1009 200
3009
so0e
6300
1506
1890
2000
4800
5000 6690
(a) Cold start DP-SGD vs. (b) Warm DP-SGD
DP-
5.-
warm start DP-SGD.
PDA-DPMD.
1000
sics
2000
2000
1092
2009
2000
(a) 07
0.5.
E 15.7.
(b) 07
1.08.
E 1.71.
Figure/ 1: Comparisons of the empirical loss on
Figure 2: WikiTexx-2. 4% public data. Validation and test loss. Averaged over 3 runs. Full plots available at Appendix
synthetic linear regression data. The mean and er- ror bars for a 95% confidence interval over 20 runs are plotted. The optimal population loss is 0.01.
Figure Ia shows the empirical loss of cold- and warm-start DP-SGD. Since the dimension-deeeendntt loss of DP-SGD is the excess empirical loss, we report empirical rather than population loss. As expected, pre- pre-training with public data allows DP-SGD to achieve nearly error. Figure compares warm-start DP-SGD and PDA-DPMD. The loss of PDA-DPMD 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 p increases, which means that the Hessian has concee-oncentrated eigenvalues at small but gets closer to the identity matrix as increases. Since PDA-DPMID recovers warm start DP-SGD when the Hessian is the identity, we can expect that PDA-DPMD obtains less of advantage over DP-SGD as the Hessian gets closer to the identity. We provide additional details in Appendix E
innension-independen
4 EMPIRICAL EVALUATION ON BENCHMARK DATA SETS
In practice, the Mirror Descent (MD) step in Line E of Algorithm can be computationally expensive. For settings where (i) the problem is unconstrained, i.e., C IR and (ii) the public loss function (0) may not be strongly convex with respect the fg-norm,
First-order Approximation to Mirror Descent:
instead use the following more efficient approximation:
8+11 < 0₂ T) (ar(ge + b,) + - 04 (0.)),
where 7/ is the learning rate, and aa [0. balances the weight of private and public gradient. The derivation this formula is in Appendix M Notice that a = corresponds to DP-SGD on private data only. In experiment, K is a hyperparameter that controls how fast a decays. In practice, instead of computing ge and V (0.) using all the private and public data, we can estimate them with stochastic gradients.
decrease ag with cosine schedule, i.e. a cos(at/(22)) where
Now, we demonstrate the efficacy of our technique (Algorithm I with the update step in 11 on two real world tasks across three benchmark data sets: next word prediction WikiText-2 (Merity et al.) 2017), and image classification on CIFAR-10 (Krizhevsky) 2009) and EMNIST (ByMerge split) (Cohen 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 with update rule (I). We compare our algorithm with two baselines: "cold-start" DP-SGD, which uses the private data only, and "warm-start" DP-SGI, 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 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. (202I). As a prepro- cessing step, we take the top 7,999 most frequent words and convert the rest into special token representing unknown word. The data set then split into 48,764 length-35 sequences, and we con- sider 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, E = 15.7 and 1.71 at 8 10-5 (corresponding
0.5 and 1 1.08, respectively). Figure shows the test
8

---

Under review as a conference paper at ICLR 2022
Table 1: Metrics for the final models for each configuration for each data set.
Data sct, metrics
Algorithm
Smaller
Larger or
DP-SGD cold
5.2626
5.5627
WikiText-2,
DP-SGD warm
5,1914
5.3288
lest loss
PDA- DPMD
5.1736
5.2956
DP cold
62.9633 1.4225
40,6000)
CIFAR-10. 10. accurncy test loss
SGD warm
66.3933 1.2371
53,4100/
1.3462
PDA-DPMD
67.0300 1.1435
55.3950 1.2788
DP DP-SGD cold
87. 06.661 / 00.5422
84.7270 0.6170
FMNIST, accurncy / test loss
DP. PDA-DPMD
8134534// 0.5008
86.3352 0.5556
87,9860 / 0.4706
86.7229 / 0,4982
loss for PDA-DPMD with K 100 and 50 respectively, and for the two baselines. From Table I 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 al., (017)) the public data. In that setting, warm start DP-SGD baseline is better than the proposed SoTA in (Asi et al.) (202I) by 1.1% for
= 1.0 and 6.6% for 3.0 in terms of test perplexity. See Appendix | 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, fine-tune the model with batch size 500 for 100 epochs. We search for optimal privacy levels, 3.51 and 0.19 at 10-5 (corresponding to a 1.51 and 20.0, respectively), we report the test loss and accuracy for K = 2000, and for the two baselines. From Table [ we that PDA-DPMD provides the best accuracy (even if by small margin over the warm started DP-SGD baseline). Moreover, PDA-DPMD also results in significantly lower test loss compared both the baselines for both privacy levels, which confirms with our theoretical analysis for the population loss.
in {200, 500, 1000, 2000, 5000). ). In Figure 3 for two different
DP.50D
1.4
54
1.45
52
1.35
55
1.1
7500
5000
10000
2500
7500
5009
10000
step
(a) 0 = 1.51. E 3.51.
(b) 0 20.0. E = 0.19. Full plot in Appendix F3
Figure 3: CIFAR-10. 4% public data. Test accuracy / loss vs. training steps. Averaged over 3 runs.
Empirical Evaluation on EMNIST: EMNIST (ByMerge split) consists of 697,932 training images and 16.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 [ for a = 0.41 and 1.89, corresponding to privacy E = 25.80 and 0.48 at = 10 6 we report the test
loss and accuracy for K- 500, and for the two baselines. We see similar trend as with CIFAR-10 10.
cos500
DR-50D warm
cold
co0509
-0-50D warm
0.575
$7.0
0.65
86.5
1ext ccuuniy
0.50
86.0
0.525
0.475
84.5
0.50
0.450
84.0
0.45
20000
40000
00000
20000
40000
60000
20000
40000
00000
20000
40000
60000
step
step
step
step
(a) o = 0.11.
= 25.80.
(b) a = 1.89.
0.48.
Figure EMNIST. 4% public data. Test accuracy / loss vs. training steps. Averaged over 3 runs.

---

Under review as a conference paper at ICLR 2022
5 ETHICS AND REPRODUCIBILITY
This work focuses on improving the privacy/utilityy trade-offs for model training with sen- sitivity 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 on standard benchmark data publicly available data sets, and do not have any ethical concerns.
Ethics:
Our experiments are either on synthetic data sets, on standard publicly available data sets. We have provided full details (including hyperparameter choices) for the experimental setup to reproduce the results the paper. We will make the code for our experiments public as soon as possible. Additionally, we have detailed proof' for all our theoretical results in the appendix.
Reproducibility:
REFERENCES
Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS' 16), pp. 308 318, 2016.
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. Efficient full-matrix adaptive regularization. In International Conference on Machine Learning, pp. 102-110. PMLR, 2019.
Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. arXiv preprint
11519, 2019.
Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference Machine Learning, pp. 383- 392. PMLR, 2021.
Brendan Avent, Aleksandra Korolova, David Zeber, Torgeir Hovden, and Benjamin Livshits. (BLENDER): ; Enabling local search with a hybrid differential privacy model. In 26th (USENIX) Security Symposium ({USENIX) Security 17), 2017.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithmss and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 464 473, 2014.
Raef Bassily, Om Thakkar, and Abhradeep Thakurta. Model-agnostic private learning. In NeurlPS, 2018a.
Raef Bassily, Abhradeep Guha Thakurta, and Om Dipakbhai Thakkar. Model-agnostic private learn- ing. Advances in Neural Information Processing Systems, 2018b.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pp- 11279-11288 2019.
Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu. Private query release assisted by public data. In Hal Daumé III and Aarti Singh (eds.), Pro- ceedings of the 37th International Conference on Machine Learning, volume 119 of Proceed- ings of Machine Learning Research, pp. 695-703 PMLR, 13-18 Jul 2020a. URL https: //proceedings.. ml htt.igg.............emme wwtpppesssseeeeeeeeeeeeee
ly20a .html.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gra- dient descent on nonsmooth convex losses. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (cds.), Advances in Neural Information Processing Systems, volume 33, pp. 4381 13911. Curran Associates, Inc., 2020b. BRLnhttps: htttps::/pooceeiinnnen .nw.:eeiddiinsnnnnunsse..s .ewrrps...... cc/ paper /ttp://222/////2222222 7 4 712a weeaaaadddeeeeee 13teeee33ddc993a Taca
pdf.
Raef Bassily. Shay Moran, and Anupama Nandi. Learning from mixtures of private and public populations, arXiv preprint 2xXxv:0008.0033 2020c.
10

---

Under review as a conference paper at ICLR 2022
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(Mar): 2011.
Gregory Cohen, Saced Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. 2017 International Joint Conference on Neural Networks (IJCNN), 2017.
doi: 10.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Cynthia Dwork and Vitaly Feldman. Privacy-preserving prediction. In Conference On Learning
Theory, pp. 1693-1702. PMLR, 2018.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pp. 265-284, 2006. URL http: //dx doi org/ 10. 1007 / 11 681 17
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018
Guy Gur-Ari, Daniel A. Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. CoRR, abs/1812.00454, 2018. http://///axx: wwwpa/wwwwwgg/b////12..000
Elad Hazan. Introduction online convex optimization. arXiv preprint arXiv:1909.05207.222 2019.
Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. Dimension independence in unconstrained private ERM via adaptive preconditioning. CoRR, Abs/2008.06550, 2020. URL
https::/arxxv> org/ abs/ 2008 ..00088000 06570
Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces. In COLT, 2021a.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. ICML, 2021b.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009.
Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Zhiwei Steven Wu. Leverag- ing public data for practical private query release. arXiv preprint arXiv:2102.08598 2021.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL BtLhttps: //openreview. wwtp://eeeee...eeeeeeeeeee.meeee
Chris Merriman. Microsoft reminds privacy-connerned windows 10 beta testers that they're vol- unteers. The Inquirer: http:://ww:t http::://wwwwww.ttt.t..........
// /www. www.ttteeinuuee.e....mm htt.eeereeeetttt/eee www.wttwwww...eeeeeeeoee htt.:/errr.ee/2733... 2014. URL http:
Anupama Nandi and Raef Bassily. Privately answering classification queries in the agnostic pac
model. In Aryeh Kontorovich and Gergely Neu (eds.), Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pp. 603-703. PMLR, 08 Feb-11 Feb 2020. URL httpp::/pppppeepgggg.......se mmr. /asss//w17//andaa
html
A. Nemirovsky and D. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley & Sons, New York, 1983.
11

---

Under review as a conference paper at ICLR 2022
Nicolas Papernot, Martin Abadi, Ulfar Erlingsson, lan Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. arXiv preprint arXiv:1610.005755. 2016.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Ülfar Er- lingsson. Scalable private learning with pate. arXiv preprint arXiv:/802 08908, 2018.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Ülfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. arXiv preprint 1rXiv:2007.44191, 2020.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE Globul Conference Signal and Information Processing, pp. 245-242228 248. IEEE, 2013.
Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimen- sionality in unconstrained private glms. In Arindam Banerjee and Kenji Fukumizu (eds.), Pro- ceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2638 2646. PMLR, 13-15 Apr 2021. URL https::/proceecingg// mllr pptess//130ssono2a....... html
Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. arXiv preprint 1415577 2014.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference Learning Representations, 2020.
Di Wang. Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revis- ited: Faster and more general. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL
hew.reiiinnnnneeeniseeee.e..e cc/
Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Pri- vate sgd with gradient subspace identification. In ICLR, 2020.
12

---

Under review as a conference paper at ICLR 2022
A
NOTATION REFERENCE
We recall here the notation used throughout the paper:
A strong convexity parameter
b
Noise added to gradients for privacy
By
The Bregman divergence induced by v
C
The constraint set
A single sample
D pub: D
priv
The public and private data sets respectively
D
The universe of samples
6,0
The privacy parameters
")
The learning rate/step size
g
A (batch) gradient
GQ
The Gaussian width of Q
pup priv
The (per-example) public and private loss functions respectively
L
The Lipschitz constant of E ppriv
L
The empirical (private) loss on dataset D, i.e. L(0; D) Do EEED E(0;d)
7pub; Aprii
The number of public and private samples respectively
The dimensionality of the optimization problem
The empirical public loss, i.c. (0) Me Ede
((O; d); also the mirror map
Q
A set such that V is I-strongly convex with respect to -
T
The number of iterations in the optmization algorithm
A solution to the optimization problem
A bound on the variance of the public gradients
B MISSING BACKGROUND
Mirror Maps: A mirror map is a differentiable function V R' + E that is strictly convex. Since V/ strictly convex and differentiable, V RR - R2 provides a bijection from R2 to itself. One can view 0 as lying in a primal space and (V) as lying in dual space. In turn, we could now consider optimizing over the value (0) in the dual space instead of 0 primal space. Mirror descent does exactly that, performing gradient descent in the dual space by computing the gradient gi = vl(O,) (where 0r 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 0 Mirror descent is essentially motivated as minimizing a (linearized) loss plus a Bregman divergence (induced by V) the regularizer (Nemirovsky & Yudin 1983). More formally, similar to proximal gradient descent, mirror descent is equivalent to taking the gradient ge and performing the update 0.41 = arg mingec (gr, 0) + B (0, 0t)] where Bx 02) (0, & (02) (02) 0, 02) the Bregman divergence generated by V. Note that, if (0) ||0] I2, then the Bregman divergence is simply B& (0,, 02) = 110 0 and mirror descent is equivalent to the usual gradient descent.
Gaussian Width: Given a bounded set Q C Rdd, the Gaussian width of Q, Go. is measure of how isorropic the set is. Gq is defined as 1g-,1,,1, max (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 max ||x||| 1. If Q is just the unit balball, the "most isotropic" set satisfying this condition, then we have Go vp: in particular, since every set Q satisfying max ||ز|| = 1 is contained in the 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 = (l). More generally, for any ellipsoid centered at the origin whose axes have radii 0 < r: S 1, S i p. we have that the Gaussian width of this ellipsoid is / V'' r3- As other examples, the Gaussian width of the ball of radius I is roughly log p. and the Gaussian width of the loo ball of radius 1/ /pp is roughly vp.
13

---

Under review as a conference paper at ICLR 2022
C
MISSING PROOFS FROM SECTION 3
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. (014), we have:
B8"
[[[((priv]] ((00)
-
00-0 o o 1Q1))
r/T'
Let 0 in particular be the minimizer satisfying Assumption 3.1
By a-strong convexity, we have:
By ,0'00'0''0)00000000 00) = -00000000000000000) (0(O)) (V)())) (0" - 00) S
20
Plugging this into Eq. (2) and noting that any we sample is 1-strongly convex with respect to || Qq get:
E (
B[C(Opriv] C((*) -
20TT
We will show that without loss of generality,
assume ( = 0 Edvr [ (0*
(0" d)]
Once we have this assumption, Assumption 3.I completes the proof.
The assumption follows since by convexity of C we have
V ( Go 50 (E V VV ( 0" - 0o) S
Then for any choice of Y and C where either 0g or 8" is on the boundary of C, suppose we extend C infinitesmally along the line fθu + c(8- 0)|c E R} (i.e., take 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",00, fo. defined as the minimizers in C, move apart from each other along this line and turn by strong convexity the quantity ([V)((0)= (0)))) cannot decrease. This implies that for any
fixed bpub and т, the quantity (1*) (0))) is maximized for choice of C such that (0,) and Ed [uppu ( 0.
Proof of Lemma 3.3 By convexity, for all E C we have L(0: > L(0); (VL(0 8*). Note that by optimality 0 and convexity, for all 0 we have VEa=T[VE((P)) d)) 0r)
0. In turn, by the Cauchy-Schwarz inequality can conclude that L(0"; D) minsec L(O: D) always upper bounded by |C||2 [[VL(0": Eder [V((0" (((#""d)] :d)lll- By I--Lipcchtzzess of each e(0; d) have:
E D [|V[L(8;; Ed (e(0;;))] S
Vn
Which completes the proof.
Proof of Theorem 3.6
Let b, be the noise added for privacy. Without noise, mirror descent would
set l" to be such that:
7g. (V"(0") (V.)).
Similarly, given the noisy gradient g: + by, mirror descent would set Ô to be such that:
-g( + b.) (V( (V.)).
14

---

Under review as a conference paper at ICLR 2022
We then have:
n/b V
Since we assume the Hessian of v defined everywhere, we have that (V V(6(8")
22 - 0*) for some & on the line between and 0" In turn, we have:
8- = VV2 ~- -b,
-y
The norm x of b, sampled from (0, 121 has the chi distribution, i.c. pdf proportional to (1/0))9-e-(0/09% In particular, this gives the following standard tail bound:
Pr[| |r[ > (1+ cDFoo I
So with probability at least 1 - p/2p we have the event & that |lb:ll2 is at most (1 c) /po. Conditioned on this event, we have that Ó, and thus is in E, i.e. the lower bounds w; apply to (0). Since conditioning on & only decreases the expectation of ( 0", v)), we have:
E
(l 0", v)ll
Pr[s] = r/E ((())((0) -1 De. V)
Pr(E]
S sylE
v.v }bb, v)[(
Pr[E] S 1/ 1 <<>
viv. bb, v\
= E
ag
v:)i
Wl:
W0
nE
N (as/ta331
N(0. Σ
a (1//wx))))
2
no
Σ
it
When & does not happen, we have (0) 2 everywhere. So we have:
E (l 0", o)1l Pr[ Pr|-E] ny
[[<(V [(((=~(()))) b, o)
Pr[-E]
<n - (1 - e -00p/2
To determine E [b, v)Il-E], note that the distribution of (b,, v) conditioned on -E is equivalent to the distribution of the first coordinate b, conditioned on -E. We can sample by by first sampling its norm |/bill2 conditioned -E, and then sampling point the sphere with radius | (no conditioning is required here). The expected absolute value any coordinate (b,); given [bbll, can be bounded as:
Bl[ S [[(())]] = |bb /Vp.
The inequality is Jensen's inequality, and the equality uses the fact that the coordinates by on the sphere are identically distributed, and so we have:
p E (b:) =E
Σ (b)) = -bbll
We now just need to bound the expectation of |byl given that least Since the distribution
of ||bellg/ /a has pdf proportional to - e 22 this expectation is o times:
littw xpC 02
r((p + / c)p/2)
1ilto) (ap0)/pp--e- 2p-16-2212
15

---

Under review as a conference paper at ICLR 2022
Where I is the gamma function and P is the regularized gamma function. Analytically,
verify that 1((++1/22 2 1. So we get:
T(p/2) $ vp/2 for all 2 1, and (1-P0(pt//2(1++0///p S 3(1 + c)² for all (1 (1-P0//2(240////2)
3(1 c)² E B:lle -
Vpo
2
Putting all together, we get:
m0 0r, 00)1)1118))) Pr[-E] sn -n.-
1
3(1 + c)²
2
Now applying the law of total expectation gives the theorem statement.
D EXAMPLES OF STOCHASTIC CONVEX OPTIMIZATION PROBLEMS
In this section, we consider two canonical stochastic convex optimization problems and the associ- ated quantity Go. to help understand the bound Theorem 3.5 In both cases we specify the public loss; previously mentioned, natural choice is to take the private loss to be the clipped version of the public loss to ensure Lipschitzness holds.
3.5
Mean Estimation: Suppose we assume we know the true covariance matrix Σ in the mean estima- tion problem for data drawn from multivariate Gaussian. Then mean estimation equivalent to minimizing loss function 2n >, (z; - 0) -x; -o0=-0), 0), where x; is the ith sample point, and 0 is our estimated mean. The Hessian is --1 By rescaling, wlog assume the maximum eigenvalue of 2 is Now, the smallest set Q such that the public loss function is I-strongly convex with respect the Q-norm is the ellipsoid centered at the origin whose axes are in the directions of the eigenvectors of E, and whose length in the direction of the eigenvector e; the corresponding eigenvalue A, The Gaussian width of Q is thus v V X In particular, e.g. Σ only has few large eigenvalues (i.e., the data only has variance in 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 proportional to | y where is the (public) feature matrix, y are the dependent variables, and 0 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 > 1/X;, where X; 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 the public data.
E ADDITIONAL DETAILS FOR THE EXPERIMENT ON LINEAR REGRESSION
Note that the exact optimum on the public data can be computed exactly as 0cub = (X 1xT 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 the same everywhere.
For numerical stability, 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 step in PDA-DPMD: has maximum eigenvalue of one. This ensures that the Hessian were a multiple of the identity matrix, SP-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.
16

---

Under review as a conference paper at ICLR 2022
F ADDITIONAL DETAILS ON REAL-WORLD EXPERIMENTS
F.1 FIRST-ORDER APPROXIMATION TO MIRROR DESCENT
In practice, the Mirror Descent (MD) step in Line E of Algorithm [ is computationally the most challenging. In the following, we provide approximation of this step in the setting where the problem is unconstrained, i.e., C = Iº and ii). the public loss w( may not be strongly convex with respect to the fornm.. This approximation makes Algorithm Deffiiient in practice.
Consider the following equivalence of Line 4 of Algorithm with (0). the public loss on Duub
replaced by (0) (0) |101|2 This follows from Hazan 2019
Lemma 5.5).
0111 f arg min DE
(g: + bi)
+ (0)
(4)
1
arg min BERP
Tli (g: + bi, 03
(0)
+
|1012
tmp
2
Y=1
1
1
arg min
Th
g: b,
V (0,),
0
+
101
(5)
DERP
tmp
2
where (5) follows from the first-order approximation (0) = (0,) (V)) 0:)-
In the experiments, we replace g: + b; + 1-7, (O,) with og + b:) (1 - (O:)). where ag (0, 1]. This reparamertization helps with more effective hyperparameter tuning while training deep learning models. We therefore have the update rule (T)
F.2 SETUP
Network architectures: Thble model architectures for CIFAR-10, EMNIST, & WikiText-
Table 2: Model architectures for real data experiments.
(a) Model architecture for CIFAR-10 10.
Layer
Parameters
Convolution x2
32 filters of x 3, strides
Max-Pooling
2 x 2, stride 2
Convolution x2
64 filters of x 3, strides
Max-Pooling
2 x 2, stride 2
Convolution x2
128 filters of 3 x 3, strides
Max-Pooling
2, stride 2
Fully connected
128 units
Softmax
(b) Model architecture for EMNIST.
(c) Model architecture for WikiText-2.
Layer
Parameters
Layer
Parameters
Convolution
16 filters of strides
Input
8000
Convolution
32 filters of 4 x 4, strides
Fully connected
120
Fully connected
32 units
LSTM x2
120 hidden units 8000
Softmax
Fully connected
Softmax
We keep the clipping norm be 1. One small difference with the stan- dard 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
Hyperparameter Tuning:
17

---

Under review as a conference paper at ICLR 2022
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 and K that controls the decaying of ag For the learning rate, we consider a grid (1, 5) x 10' for different is such that the optimal learning rate does appear 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 of Figure
we plot the complete version of Figure? 2 and in Figure 6 we show the complete version
co0100
DR-5GD warm
00550
warm 5.5
5.6
5.5
5.7
3.5
3.4
5.5
5.4
3.3
1000
2000
3000
1200
2000
3000
0
1000
2000
3000
1000
2000
3000
3t60
step
step
Step
(a) = 0.5
(b) 1.08
Figure 5: Full plot for Figure
WikiText-2, 4% public data.
50
2.25
30
1.75
130
10
L0000
2500
7500
2:00
2:00
(a) σ 20.0.
Figure 6: Full plot of Figure
3
CIFAR-10. 4% public data. Test accuracy / loss vs. training steps.
Averaged over 3 runs.
F.4 WIKITEXT-2 WITH WIKITEXT-103 PUBLIC DATA
We compare with the SoTA (Asi et al. 202I) which uses WikiText- 103 as public data. Specifically, consider their "LargeAux" setting under 1.0 and 3.0. Since the implementation for al. (2021) is not public 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 s) 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 2 Finally, randomly sample 48, 187764 sequences, in order match the "LargeAux" setting where the public dataset is 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 (ss 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.
18

---

Under review as a conference paper at ICLR 2022
Algorithm
e = 3.0
= 1.0
Asi et al.
2021
DP-SGD (cold)
5,4819
5.6623
Asi et
2021
(LargeAux)
5.4324
5.5254
Our DP-SGD (cold)
5,4030
5,5956
Our DP-SGD (warm)
5.3646
5.5141
DP-503 cold
DP-0P
DP-500 cold
5.5
5.9
5.8
3.5
5.6
5.7
57
5.6
5.6
5.5
1000
2000
3000
4000
1000
2000
3000
4000
1000
2000
3000
1000
0.83,
3.0.
(b)
1.49,
1.0.
Figure 7: WikiText-2, WikiText- 103 as public data.
19


Reviews:
[{"review_id": "buEz9MpzsSP", "reviewer": "Reviewer_GaSe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a beautiful paper! It is well written, easy to follow, covers the literature very well. The results are nice and for me and the approach very natural. It is an easy accept. \n\nI have few comments about the paper though. Since the paper works in the public-private data setting, it would be nice to know (even theoretically) the comparison between how much public data is used by previous work and we have access to equivalent data, what is the performance of the current submission. Likewise, if we have a given utility to aim for, what is the difference between the number of public data samples in the current submission vs previous works. This would put the work in a very precise light as to whether it is improving the state-of-the-art or not.  \n\nThe paper mentions in the appendix that they compare SoTA with Asi et al. and they made a best effort to match their experiment set up. Asi et al. is a published work in ICML 2021 and I am surprised by the claim of the authors that the code is not publicly available -- given that ICML requires code submission in the supplementary material. If it is indeed so, I would suggest the authors to reach out to the authors of Asi et al. to get their code because the hyperparameters used in this submission can be very different from what Asi et al. did and hence the claim may or may not be true. \n\nOne question I have to the authors is also with regards to some other works that came out in different geometry (Bassily et al. (COLT 21), Asi, Feldman, Koren, and Talwar ICML 21 (AFKT to differentiate from Asi et al. mentioned in this paper), and Kulkarni et al. (https://arxiv.org/abs/2103.15352). Granted they do not consider public-private data setting, at least to my memory, AFKT do consider mirror descent and study in any \\ell_p space, I think it would be interesting to see the comparison of their work with this work. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "The approach in the paper is very natural and I think the algorithm would be very easy to deploy in large-scale system. The proof is very simple and elegant, which I think is another big bonus. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "W6zxc8HqFaM", "reviewer": "Reviewer_cMgL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. This paper proposes a new idea to use public data implicitly by using the public data loss as the mirror map in DP mirror descent.\n2. The empirical results of this paper on real world datasets seem to beat current baselines.\n\nQuestions/Clarifications:\n\n1. In my opinion, this paper needs better writing. At many places, mathematical notation is either used but not defined explicitly or sometimes not consistent. A short notation section, would make its easier to read. I will point out a few places where I found it particularly confusing.\n\n    a. I couldn't find the definition of $||\\cdot||_Q$, although it maybe standard, its better to explicitly define it to clear any confusion.\n    b. In lemma 3.3, how is $\\ell(\\theta;D)$ defined? It doesn't parse with the definition of $\\ell$ in the first line.\n    c. Usually $\\mathcal{L}$ denotes the population loss and $\\hat{\\mathcal{L}}$ denotes the empirical loss, this notation is overloaded and causes confusion\n\n\n2. The way to bound the excess population risk seems non-standard. If I understand correctly, first the difference of empirical loss of the estimate and the population optimum is bounded, lemma 3.3 is supposed to relate the population optimum to the sample (empirical) optimum, and then Lemma 3.4 is used to relate the excess population risk and excess empirical loss. Is there some intuition as to why this path was chosen? Why can one not directly either give an algorithm with population loss bound or give an excess empirical loss bound and add the generalization error?\n\n3. One of the biggest causes of concern for me is the Assumption 3.1, it assumes that some minimizer of the private loss is also the (unique) minimizer of the public loss. Can the authors give a real world example where the two losses are not the same but this holds?\n\n4. Overall, the paper lacks toy examples which would help understand the theory better and clear doubts that arise when reading assumptions. Some simple toy examples could be linear regression, logistic regression, LASSO, etc. I'd be curious to see what are the choices of private and public loss for these cases, what is the Gaussian width and what does the guarantee look like for these values?\n\n5. Since the minimizers of the public loss and one of the minimizers of the private loss is the same, one trivial baseline to compare against is doing non-private training using only public data. It seems the setting here is that of public data being a constant but small fraction of the private data. What is the comparison of errors for this setting?\n\n6. In the proof of Theorem 3.2, if $\\nabla \\Phi(\\theta_0) = 0$, since $\\Phi$ is the public loss, which is strongly convex, this would imply $\\theta_0$ needs to be the empirical public loss minimizer? It would be better if a formal argument is made for this.", "summary_of_the_paper": "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.", "summary_of_the_review": "There are some issues with the writing and some questions regarding the validity of assumptions and the validity the claim of dimension independence in usual settings, as detailed in the main review. Thus my score of 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "UIwS-wmVh4J", "reviewer": "Reviewer_mr6n", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The authors use public data as the mirror map to provide improved bounds compared with the SOTA. This idea is quite interesting and may be used to other problems. \n2. They further show that their algorithm has a natural \"noise stability\" property.\n3. Although DP Mirror Descent has been studied before, they were no experimental result. This paper provide some experimental results. \n\nWeakness: \n1. Compared with the classical case (\"Private empirical risk minimization beyond the\nworst case: The effect of the constraint set geometry\") The improvement on the upper bound is limited if there is not enough data. \n\n2. To achieve the upper bound, the running time needs to be $O(n^3)$, which is lower than the SOTA $O(n^{1.5})$  [1]. \n\n3. The paper did not compared with the SOTA (\"Private empirical risk minimization beyond the\nworst case: The effect of the constraint set geometry\") in experiments. I think this is necessary as this is the most close method, instead of DP-SGD. \n\nMoreover, the authors left the reference [1], which also studied the problem. \n[1]Wang, Di, Minwei Ye, and Jinhui Xu. \"Differentially private empirical risk minimization revisited: Faster and more general.\" arXiv preprint arXiv:1802.05251 (2018).", "summary_of_the_paper": "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.", "summary_of_the_review": "As I mentioned, due to high time complexity (which is impractical), lack of comparison with SOTA in experiments and limited improvement on the upper bound. I tend to reject the paper. \n--------\nAfter the rebuttal, the reviewer solved mots of my concerns instead of the time complexity. So I raise the score to 5. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new algorithm for private ERM, when given access to public data, with a dimension-independent risk guarantee if  (A) the public and private datasets are of the same distribution, (B) public dataset size exceeds the dimensionality (or, rather, the squared Gaussian width of an appropriate set), and (C) the public and private loss functions share a minimizer (and the gradients at the shared minimizer must satisfy some variance bounds). The algorithm uses the public data as the Bregman mirror map within private mirror descent (where Gaussian noise is added to the gradients), thus implicitly affecting the geometry, as opposed to explicitly learning the geometry as done in earlier works.

One reviewer was very positive, but two hovered around the borderline and expressed some reservations about the theory and experiments. Regarding the experiments, they did not compare to the ICML'21 paper by Asi et al --- however the authors of that paper have (surprisingly) still not released their code, so I think this is forgivable. Since the paper was on the borderline, I read it myself, with a focus on the theoretical aspects. I find myself agreeing with the second reviewer that the assumptions are strong, and their justification is weak and unrealistic. 

Regardless of whether the paper, is accepted or not, I strongly recommend the authors to add condition (C) to their abstract (just the part about the shared minimizer) --- currently the abstract mentions two of the above but not the critical third one. I think (A) is already a strong assumption --- their justification that some users opt-in to reveal their data does not justify this, because the opt-in will not be random (if the opt-in depends on covariates like gender/age/..., the datasets will not be identically distributed). On top of that, (C) is also a strong assumption --- indeed usually the loss functions would be different (for eg, the private one would be clipped, and clipping will rarely preserve the population minimizer, as well as regularized) --- their justification that for a linear model with symmetric noise, clipping does not change the minimizer may be true (though not proved), but we would never expect the linear model to be true in practice even if we employ it as a working model. Last, assumption (B) restricts its use in many common high-dimensional data problems. Overall, I am pressed into a corner to find situations in which all three assumptions would be true.

Nevertheless, supposing that these assumptions hold, the algorithm is indeed clean, and the empirics appear reasonable. Overall, the paper remains on the borderline. Whether accepted or rejected, I expect the authors to do a much better job of carefully justifying their assumptions, with realistic and not far-fetched examples (as suggested by the second reviewer).
Decision: Reject