Regression with Label Differential Privacy
Authors: Badih Ghazi
Pritish Kamath
Ravi Kumar
Ethan Leeman
Pasin Manurangsi
Avinash Varadarajan
Chiyuan Zhang
Venue: ICLR 2023 poster (2023)
Keywords: label differential privacy
regression

Abstract: We study the task of training regression models with the guarantee of _label_ differential privacy (DP). Based on a global prior distribution of label values, which could be obtained privately, we derive a label DP randomization mechanism that is optimal under a given regression loss function. We prove that the optimal mechanism takes the form of a "randomized response on bins", and propose an efficient algorithm for finding the optimal bin values. We carry out a thorough experimental evaluation on several datasets demonstrating the efficacy of our algorithm.

REGRESSION WITH LABEL DIFFERENTIAL PRIVACY
Badih Ghazi
Pritish Kamath
Ravi Kumar
Ethan Leeman
Pasin Manurangsi
Avinash Varadarajan
Chiyuan Zhang
Google
ABSTRACT
We study the task of training regression models with the guarantee of label dif- ferential privacy (DP). Based on a global prior distribution on label values, which could be obtained privately, we derive a label DP randomization mechanism that is optimal under a given regression loss function. We prove that the optimal mech- anism takes the form of "randomized response on bins", and propose an efficient algorithm for finding the optimal bin values. We carry out thorough experimen- tal evaluation on several datasets demonstrating the efficacy of our algorithm.
INTRODUCTION
In recent years, differential privacy (DP, Dwork et al., 2006a;b) has emerged as a popular notion of user privacy in machine learning (ML). On high level, it guarantees that the output model weights remain statistically indistinguishable when any single training example is arbitrarily modified. Nu- merous DP training algorithms have been proposed, with open-source libraries tightly integrated in popular ML frameworks such as TensorFlow Privacy (Radebaugh & Erlingsson, 2019) and Py Torch Opacus (Yousefpour et al., 2021).
In the context of supervised ML, a training example consists of input features and a target label. While many existing research works focus on protecting both features and labels (e.g., Abadi et al. (2016)), there are also some important scenarios where the input features are already known to the adversary, and thus protecting the privacy of the features is not needed. A canonical example arises from computational advertising where the features are known to one website (a publisher), whereas the conversion events, i.e., the labels, are known to another website (the advertiser). Thus, from the first website's 's perspective, only the labels can be treated as unknown and private. This motivates the study of label DP algorithms, where the statistical indistinguishabiiity is required only when the label of single example is modified.? The study of this model goes back least to the work of Chaudhuri & Hsu (2011). Recently, several works including (Ghazi et al., 2021at Malek Esmaeili al., 2021) studied label DP deep learning algorithms for classification objectives.
Our Contributions. In this work, we study label DP for regression tasks. We provide new algorithm that, given a global prior distribution (which, unknown, could be estimated privately), derives label DP mechanism that is optimal under a given objective loss function. We provide an explicit characterization of the optimal mechanism for a broad family of objective functions including the most commonly used regression losses such the Poisson log loss, the mean square error, and the mean absolute error.
More specifically, show that the optimal mechanism belongs class of randomized response on bins (Algorithm I). We show this by writing the optimization problem as a linear program (LP), and characterizing its optimum. With this characterization mind, it suffices for us compute the
Authors in alphahetical order. Email: (badih. ghazi, ravi.k53) @gmail @.mmail.com, {pritishk, ethanleeman,
pasin, avaradar, chiyuan @google com
A similar use case in mobile advertising, where websites replaced hy apps.
We note that this label DP setting is particularly timely and relevant for ad attribution and conversion measurement given the deprecation of third-party cookies by several hrowsers and platforms (Wilander, 2020; Wood, 2019; Schuh, 2020).

---

Step
M6y p .... yy) &DDP
Step
Labels Party Yp .... X,
Features Party
Trained e-LabelDP model
X1. A
Figure I: Learning with feature-oblivious label DP.
optimal mechanism among the class of randomized response on bins. We then provide an efficient algorithm for this task, based on dynamic programming (Algorithm 2).
In practice, a prior distribution on the labels is not always available. This leads to our two-step algorithm (Algorithm 3) where first use portion of the privacy budget to build an approximate histogram of the labels, and then feed this approximate histogram as a prior into the optimization algorithm in the second step: this step would use the remaining privacy budget. We show that as the number of samples grows, this two-step algorithm yields an expected loss (between the privatized label and the raw label) which is arbitrarily close to the expected loss of the optimal local DP mechanism. (We give a quantitative bound on the convergence rate.)
Our two-step algorithm can be naturally deployed in the two-party learning setting where each ex- ample is vertically partitioned with one party holding the features and the other party holding the (sensitive) labels. The algorithm is in fact one-way, requiring single message to be communicated from the labels party to the features party, and we require that this one-way communication satisfies (label) DP. We refer to this setting, which is depicted in Figure I, as feature-oblivioss label DP.
We evaluate our algorithm on three datasets: the 1940 US Census IPUMS dataset, the Criteo Spon- sored Search Conversion dataset, and proprietary app install ads dataset from a commercial mobile app store. We compare our algorithm to several baselines, and demonstrate that it achieves higher utility across all test privacy budgets, with significantly lower test errors for the high privacy regime. For example, for privacy budget 0.5, comparing to the best baseline methods, the test MSE for our algorithm is ~ 1.5x smaller on the Criteo and US Census datasets, and the relative test error is 5x smaller on the app ads dataset.
Organization. In Section 2, recall some basics of DP and learning theory, and define the feature-oblivious label DP setting in which our algorithm can be implemented. Our label DP algo- rithm for regression objectives presented in Section 3. Our experimental evaluation and results are described in Section 4. A brief overview of related work appears in Section 5. We conclude with some interesting future directions in Section 6. Most proofs are deferred to the Appendix (along with additional experimental details and background material).
2 PRELIMINARIES
We consider the standard setting of supervised learning, where have set of examples of the form (x,y) y) E X' x y, drawn from some unknown distribution 'D and we wish to learn a predictor fo (parameterized by 0) to minimize L(fe) := () E (f y). for some loss function é R x y + Rzo: we will consider the case where y C R. Some common loss functions include the zero- one loss la.1 (ū. y) = [ f w]. the logistic loss Eiog u) := log(1+e Sv) for binary classification, and the squared loss lxg (ū: y) = (ū-y)² the absolute-vale loss (abs(ū) y) = jr-yl. the Poisson log loss (r.i(ū.)) v) 1 y log (1)) for regression. This paper focuses the regression setting.
However, we wish to perform this learning with differential privacy (DP). We start by recalling the definition of DP. which can be applied any notion of adjacent pairs of datasets. For an overview of DP, we refer the reader to the book of Dwork & Roth (2014).
Definition (DP; Dwork et al. (2006b)). Let e be a positive real number. A randomized algorithm A taking input a dataset said be e-differentially private (denoted e- 3-DP) if for any two adjacent datasets X and X', and any subset S of outputs of A, we have Pr(A(X) E S] < e Pr(A(X')) E S].
In supervised learning applications, the input to a DP algorithm is the training dataset (i.c., a set of labeled examples) and the output is the description of predictor (e.g., the weights of the trained
2

---

model). Typically, two datasets are considered adjacent if they differ on single training example; this notion protects both the features and the label of any single example. As discussed in Section 1, in certain situations, protecting the features is either unnecessary or impossible, which motivates the study of label DP that we define next.
Definition 2 (Label DP; Chaudhuri & Hsu (2011)). An algorithm A taking as input training dataset said to be e-label differentially private (denoted as e-LabelDP) it is s-DP when two input datasets are considered adjacent if they differ on the label of single training example.
We next define an important special case of training with label DP, which commonly arises in prac- tice. The setting could be viewed as a special case of vertical federated learning, where each training example is divided across different parties the beginning of the training process; see, e.g., the sur- vey of Kairouz et al. (2021) and the references therein. We consider the special case where we only allow a single round of communication from the first party who holds all the labels, to the second party, who holds all the features, and who then trains the ML model and outputs it. We refer to this setting (depicted in Figure 1) as feature-oblivion without having to look at the features (but with the ability to look at the labels from all users); we next give the formal definition.
label DP since the label DP property guaranteed
Definition 3 (Feature-Obllviouss Label DP). Consider the two-party setting where the "features party" holds as input sequence (s:) of all feature vectors (across all the users), and the "labels party" holds as input sequence (y:)== of the corresponding labels. The labels party sends single message M (y1,.... Un) to the features party; this message can be randomized using the in- ternal randomness of the labels party. Based on its input and on this incoming message, the features party then trains an ML model that it outputs. We say that this output is feature- caluur--bllivoos e-LabelDP if the message (y ........ Un) ) is E E-DP with respect to the adjacency relation where a single yi can differ across the two datasets.
We stress the practical applicability of the setting described in Definition 3. The labels party could be an advertiser who observes the purchase data of the users, and wants enable a publisher (the features party) to train a model predicting the likelihood of a purchase (on the advertiser) being driven by the showing of certain type of ad (on the publisher). The advertiser would also want to limit the leakage of sensitive information to the publisher. From practical standpoint, the simplest option for the advertiser is to send a single privatized message the publisher who can then train a model using the features at its disposal. This is exactly the fcature-oblivious label DP setting.
3 LABEL DP LEARNING ALGORITHM
A common template for learning with label DP is to: (i) compute noisy labels using a local DP mechanism M. (ii) use a learning algorithm on the dataset with noisy labels. All of the baseline algorithms that we consider follow this template, through different ways of generating noisy labels, such as, (a) randomized response (for categorical labels), (b) (continuous/diicrette)) Laplace mech- anism, (c) (continuous/discrett)) staircase mechanism, etc. (for formal definitions of these mecha- nisms, see Appendix D). Intuitively, such a learning algorithm will be most effective when the noisy label mostly agrees with the true label.
Suppose the loss function l satisfies the triangle inequality, namely that E(j.v) < ((ū.v) + ((..0) for all y, 0. y. Then we have that
E (z.0)D
((fo(z).v) S
E B-P j~M(g)
((D.V)
+
E (a. g~M(s)
{ffoz))
(1)
where, for ease of notation, we use P to denote the marginal on y for (r, y) ~ D. The learning algorithm, in part (ii) of the template above, aims to minimize the second term in the RHS of (I). Thus, it is natural to choose a mechanism M, in part (i) of the template, to minimize the first term in the RHS of 31).3 Ghazi et al. (2021a) studied this question for the case of 0-1 loss and showed that randomized response
top k labels with the highest prior masses (for some k) is optimal. Their characterization was limited to this classification loss. In this work, we develop a characterization for large class of regression loss functions.
'Noe that the first term in the RHS of (1) is constant, independent of the number of training samples. Therefore, this upper bound is not vanishing in the number of samples, and hence this inequality can he quite loose.
3

---

Algorithm RR-on-Bins..
Algorithm Compute optimal @ for RR-on-Binss"
Parameters: Φ y - 5 (for label set
Input: Distribution P over y S R, privacy param.
O, loss function E IR? R20-
Y and output set )). privacy parameter 2 O.
Output: Output set ) C R and $ y y
Input: label y E V.
y',...,yf <- elements of y in increasing order
Output: 9 )
Initialize Ab][[]]
for all i, (0, (k) k}
fo {1...., k} do
return a sample ù ~ Y, where the random variable Y is distributed as
[ < mingeR Eyey Py e lvvll" w/.l.. A|o +
i = (v) otherwise.
for E {I...., k.....,k.... k} do
Pr|Y úl
for j (1, (1...... 1) do
-
Abilb t minugrei Ari - 1] + Lir 1
for each Ø E E.
return Φ, correspond. to mingel 2-1+e A [
3.1 RANDOMIZED RESPONSE ON BINS: AN OPTIMAL MECHANISM
We propose a new mechanism for generating noisy labels that minimizes the first term in the RHS of (1). Namely, we define randomized response on bins (RR-on-Bins") which a randomized algorithm parameterized by scalar & > O and a non-decreasing function 4 y - ý that maps the label set y S I to an output set V S IR. This algorithm is simple: perform e-randomized response on (y), randomizing over V) see Algorithm I for a formal definition. Any & we consider will be non-decreasing unless otherwise stated, and so we often omit mentioning explicitly.
An important parameter in RR-on-Bins is the mapping and the output set y. We choose + with the goal of minimizing E E y). First we show, under some basic assumptions about L, that for any given distribution P over labels y, there exists a non-decreasing map & such that M AR-on-Bins? minimizes Ey--P.gMMM)) E(g. y). Since is non-decreasing, follows that p is an interval* of y, for all E D. Exploiting this property, we give an efficient algorithm for computing the optimal Φ
(g)
To state our results formally, we use L(M; P) to denote Ey--P.s-M(g) {(), v). the first term in the RHS of (1). Our results hold under the following natural assumption; note that the standard loss functions such as squared loss, absolute-value loss, and Poisson log loss satisfy Assumption 4.
Assumption 4. Loss function E R x R + Rzo is such that
For all y E R, () is continuous.
For all E RR, ((G. y) is decreasing in 9 when 1 S and increasing in I when 9 2 For all g E TR, ((g.y) y) is decreasing in y when y S 9 and increasing y when y g.
We can now state our main result:
Theorem 5. For any loss function R:Rx R R2o satisfying Assumption 4, all finitely supported
distributions P over y S R. there is an output set y C IR. and a non-decreasing map 4 y - )) such that
L(RR-on-Bins PP = inf L(M;P),
M
where the infimum is over all E-DP mechanisms M.
Proof Sketch. This proof is done two stages. First, we handle the case where y is restricted to be a subset of O where O is a finite subset of R. Under this restriction, the optimal mechanism. M that minimizes L(M; P) can be computed as the solution to an LP. Since an optimal solution to an
An interval of y is subset of the form (a, bj n.,, for some a, b R, consisting of consecutive elements on y in sorted order.
4

---

Algorithm 3 Labels Party's Randomizer Labelirrreaeannddddmeeee.....
Privacy parameters E2 0. Input: Labels y1...., Yn E V.
Parameters:
Output: 91....., In E V
P' 4- M (v)....... Vn)
Ø'.3" +- Result of running Algorithm 2 with distribution P' and privacy parameter 62
for i E [r] do
4' return (U1...., Dn)
0 < ER-on-Binss, (vs)
LP can always be found at the vertices of the constraint polytope, study properties of the vertices of the said polytope and show that the minimizer amongst its vertices necessarily takes the form of RR-on-Bins.. To handle the case of general V, we first note that due to Assumption 4, it suffices to consider ) C [y/inn Ymax] (where Vmiin = minyey y and Mmax maxyey v). Next, we consider sequence of increasingly finer discretizations of [Jhinn )max], and show that RR-on-Bins, arbitrarily close to the optimal [(M; P) when restricting Y to be subset of the discretized set. But observe that any & induces partition of Y into intervals. Since there are only finitely many partitions of Y into intervals, it follows that in fact RR-on-Bins" can exactly achieve the optimal L(M; P). The full proof is deferred Appendix
come
Given Theorem 5, it suffices to focus on RR-on-Bins, mechanisms and optimize over the choice of 4. We give an efficient dynamic programming-bann algorithm for the latter in Algorithm The main idea is as follows. We can breakdown the representation of & into two parts (i) partition P+ = S2... ... of y into intervals". such that & is constant over each S,, and (ii) the values y that (b-) takes over interval S,. Let setty.. ...... y yy....,. be elements of Y in increasing order. Our dynamic program has a state A [i], which is (proportional to) the optimal mechanism if we restrict the input Sj.
to only (y'...., y²) and consider partitioning into j intervals .,...., To compute A(]] we try all possibilities for Sy. Recall that S, must be an interval, i.e., S, = "y"+!....,1" for some < i. This breaks the problem into two parts: computing optimal RR-on-Bins for { y"} partitions and solving for the optimal output label for Sy. The answer the first part simply A[rilj 1). whereas the second part can be written as a univariate optimization problem (denoted by [[]] in Algorithm 2). When is convex (in the first argument), this optimization problem is convex and can thus be solved efficiently. Furthermore, for squared loss, absolute-vale loss, and Poisson log loss, this problem can be solved amortized O(1) time, resulting in a total running time of O(k2) for the entire dynamic programming algorithm. The full description is presented in Algorithm 2 the complete analyses of its correctness and running time are deferred to Appendix B.
for j
3.2 ESTIMATING THE PRIOR PRIVATELY
In the previous subsection, we assumed that the distribution P of labels is known beforehand. This might not be the case in all practical scenarios. Below we present an algorithm that first privately approximates the distribution P and work with this approximation instead. We then analyze how using such an approximate prior affects the performance of the algorithm.
To formalize this, let denote by MMLap the s-DP Laplace mechanism for approximating the prior. Given n samples drawn from P, MMLap constructs histogram over y and adds Laplace noise with scale 2/e to each entry, followed by clipping (to ensure that entries are non-negative) and normalization. A formal description of M!!ap can be found in Algorithm 4 in the Appendix.
For convenience, we assume that St, S2.... are sorted in increasing order. "We remark that the corresponding Φ. on the last line can be efficiently computed by record- ing the minimizer for each A[]][a] and [.]]][), and going hackward starting from i = lf and j arg min J-14er [[k][d].
5

---

0.20
5.20
0.305
0025
0.300
5,500
4091
24461
200
220
30
(a) RR-on-Bins
(b) Laplace Mechanism
Figure 2: Illustration of the training label randomization mechanism under privacy budget & = In this case, RR-on-Bins maps the labels to bins chosen for optimal MSE via Algorithm 2. The 2D density plot contours are generated in log scale. The legends show the MSE between the original labels and the e-DP randomized labels.
Our mechanism for the unknown prior case descriesrri in Algorithm 3-is simple: We split the privacy budget into E2 run the s -Dp Laplace mechanism to get an approximate prior distribution P' and the optimal RR-on-Bins for privacy parameter 62 to randomize the labels. It is not hard to see that the algorithm (E1 + 42) (Full proof deferred to the Appendix.)
Theorem 6. LabefRandomizer.... (51 -2)
Let us now discuss the performance of the above algorithm in comparison to the case where the prior P known, under the assumption that yı....., Yo are sampled i.id. from P. We show in the following theorem that the difference between the expected population loss in the two cases converges to zero as the number of samples n + co, provided that y is finite:
Theorem 7. Let E
R + Rz0 be any loss function satisfyyng Assumption 4. Furthermore, assume that l(.. v) < B for some parameter B for all y. ÿ E y. For any distribution P on Y, E > and any sufficiently large N, there is choice of E1, E2 > 0 such that E1 + E2 E and
[<RRR-on-Bins 4' Pi] inf L(M; 00 VDVV))
E VI Viroo P' S
where Pt S0 are as in LabelRandomiierr..e and the infimun is over all s-DP mechanisms M.
We remark that the above bound is achieved by setting E / indeed, we need assume that n is sufficiently large that E < E. The high-level idea of the proof is to first use a known utility bound for Laplace mechanism Diakonikolas et (2015) to show that P, P' are close. Then, we argue that the optimal RR-on- -ins is robust, in the sense that small changes in the prior (from P to P') and privacy parameter (from E to #2) do not affect the resulting population loss too much.
EXPERIMENTAL EVALUATION
We evaluate the RR-on-Binn mechanism on three datasets, and compare with the Laplace mecha- nism (Dwork et al., 2006b), the staircase mechanism (Geng & Viswanath, 2014) and the exponential mechanism (MeSherry & Talwar, 2007). Note the Laplace mechanism and the staircase mechanism both have discrete and continuous variant. For real-valued labels (the Criteo Sponsored Search Conversion dataset), we use the continuous variant, and for integer-valued valued labels (the US Census dataset and the App Ads Conversion Count dataset), use the discrete variant. All of these algo- label DP setting of Figure 1. Detailed model and training configurations can be found in Appendix E.
rithms can be implemented in the

---

Privacy Budget
MSE (Mechanism)
MSE (Generalization)
Laplace Mochanism
RR-on-Bing Bins
Laplace Mechanism
RR-on-Bins
0.05
60 746.98 46.31
11 31433.84
+ 9.07
812.52 0122.56440 139.35
11 339.71
36.45
0.1
59 033.0000000 06 1: 51.31
11325553
9.25
23 93933.23 1: 172.43
11 328.04
04.0441:0 36.34
0.3
52 756.01
56.64
11210.48
9.06
20 901.83
149.47
186.20
36.10
0.5
47 253.12
57.12
10977.09
0177009 8.85
18 19/11.30000
111.82
10 00901.33 33 36.54
0.8
40223313 48.66
10
9.77
15 428.75
91.32
10256.37
37.39
1.0
36 226.54
45.05
9976.86
1.8.1.8.22 8.21
13 788.51 75.71
9 9744.08
37.59
1.5
28 170.93
39.45
8
7.04
10 608.53 52.31
8406.88
- 36.57
2.0
22 219.20
28.04
7260.05 + 10.55
892
291.93 31.03
3.0
14411.77 20.26
4
11.15
6770.3 22.86
5777.50 11:00:3300 31.75
4.0
53 17.27
2631.36 4.41
5704 02 28.
7799.61
25.01
6.0
570.57 10.30
709.71 2 6.18
1 1955.21 26.75
3371.66 68 25.31
8.0
3 232 22 6.54
176.47 1: 2.12
668
20.34
333. 12 31.94
0.00 0.00
0.00 1 0.00
322.21
28.31
4'319
29.27
Table 1: MSE on the Criteo dataset. The first column block (Mechanism) measures the error in- troduced by the DP randomization mechanisms the training labels. The second column block (Generalization) measures the test error of the models trained on the corresponding private labels.
4.1 CRITEO SPONSORED SEARCH CONVERSION
The Criteo Sponsored Search Conversion Log Dataset (Tallis & Yadav, 2018) contains logs obtained from Criteo Predictive Search (CPS). Each data point describes an action performed by user (click on a product related advertisement), with additional information consisting of conversion (product was bought) within 30-day window and that could be attributed to the action. We formulate (feature-oblivious) label DP problem to predict the revenue (in E) obtained when a conversion takes place (the goleeAmoounInEuus traffic data, with total of 15, 995, 634 examples. We remove examples where no conversion hap- pened (SalesAmountInEuro is -)). resulting in dataset of 1, 732, 721 examples. The conversion value goes up to 62, 453.. We clip the conversion value at 400E, which corresponds to the 95th percentile of the value distribution.
attribute). This dataset represents sample of 90 days of Criteo live
In Figure 2, we visualize an example of how RR-on-Bins randomizes those labels, and compare with the Laplace mechanism, which is canonical DP mechanism for scalars. In this case (and for E = 3). RR-on-Bins chooses 3 bins at around 50, 100, and 250 and maps the sensitive labels to those bins with Algorithm The joint distribution of the sensitive labels and randomized labels maintains an overall concentration along the diagonal. On the other hand, the joint distribution for the Laplace mechanism is generally spread out. Table 1 quantitatively compares the two mechanisms across different privacy budgets. The first block (Mechanism) shows the MSE between the sensitive training labels and the private labels generated by the two mechanisms, respectively. We observe that RR-on-Bing Bins leads to significantly smaller MSE than the Laplace mechanism for the same label DP guarantee. Furthermore, as shown in the second block of Table 1 (Generalization) the reduced noise in the training labels leads to lower test errors.
Figure 3 compares with two additional baselines: the exponential mechanism, and the staircase mechanism. For both the "Mechanism" errors and "Generalization" errors, RR-on- Bins consistently outperforms other methods for both low- and high-s regimes.
4.2 US CENSUS
The 1940 US Census dataset has been made publicly available for research since 2012, and has 131, 903, 909 rows. This data is commonly used in the DP literature (e.g.. Wang et al. (2019); Cao et al. (2021); Ghazi et al. (2021b)). In this paper, we set up label DP problem by learning to predict the duration for which the respondent worked during the previous year (the SKOKO field, measured in number of weeks). Figure 4a shows that RR-on- -n-Bins outperforms the baseline mechanisms across wide range of privacy budgets.
7

---

1e4
1e4
Staircase Exponential
Laplace
2.5
Laplace Staircase
-5
Mean Squared Error
RR-on-Birr
Mean Squared Error
2,0
Exponential
Bins
4
1.5
2
1.0
0
0.5
0.8
2 Privacy Budget
0. 0.0501
0.8
tn
Privacy Budget
(a) Mcchanism
(b) Generalization
Figure 3: MSE on the Criteo dataset: (a) error introduced by DP randomization mechanisms on the training labels and (b) test error of the models trained on the corresponding private labels.
450
Laplace
Staircase
60
Staircase
Lap lace
Mean Squared Error
400
PRR-on- Ni--on--ins
Exponential
50
Relative Error
350
40
300
30
250
20
200
10
150
0.058:1 9.5
Privacy Budget
Privacy Budget
(a) US Census
(b) App Ads
Figure 4: Test performance across different privacy budgets. (a) MSE on the US Census dataset. (b) Relative performance on the App Ads Conversion Count dataset. The relative error is calculated with respect to the non-private baseline, i.e. (E- Eveascins)/ / Eraseline
4.3 APP ADS CONVERSION COUNT PREDICTION
Finally, we evaluate our algorithm on an app install ads prediction dataset from a commercial mobile app store. The examples in this dataset are ad clicks and each label counts post-click events (aka conversions) occurring in the app after the user installs it. For example, if a user installs ride share app after clicking the corresponding ad, the label could be the total number of rides that the user purchases in a given time window after the installation. We note that ad prediction tasks/datasets of similar nature have been previously used for evaluation (Badanidiyuru et al., 2021).
Figure 4b shows the performance on this dataset. Consistent with the results observed on the other datasets, RR-on-Bins outperforms other mechanisms across all the privacy budget values.
In summary, by first estimating a prior distribution (privately), RR-on-Bins significantly reduces label noise compared to other label DP mechanisms, especially in the high-privacy (i.e., intermediate to small E) regime. This leads to significantly better test performance for the regression networks trained on these less noisy labels. For example, for 0.5, comparing to the best baseline methods, the test MSE for RR-on-Bim is ~ 1.5x smaller on the Criteo and US Census datasets, and the relative test error is 5x smaller on the App Ads dataset.
8

---

5 RELATED WORK
There has been large body of work on learning with DP. Various theoretical and practical set- tings have been studied including empirical risk minimization (Chaudhuri et al., 2011), optimization (Song et al., 2013), regression analysis (Zhang et al., 2012), and deep learning (Abadi et al., 2016). The vast majority of the prior works studied the setting where both the features and the labels are deemed sensitive and hence ought to be protected.
Chaudhuri & Hsu (2011) and Beimel et al. (2016) studied the sample complexity of learning with label DP for classification tasks. Wang & Xu (2019) studied label DP for sparse linear regression in the local DP setting. Ghazi al. (2021a) provided procedure for training deep neural classifiers with label DP. For the classification loss, they formulate an LP and derive an explicit solution, which they refer as RRTop-A: Our work could be viewed an analog of theirs for regression tasks. Malek Esmaeili et al. (2021) used the PATE framework of Papernot et al. (2017; 2018) to propose a new label DP training method. We note that this, as well as related work on using unsupervised and semi-supervised learning to improve label DP algorithms (Esfandiari et al., 2022; Tang et al., 2022), do not apply to the feature-oblivious label DP setting.
A variant of two-party learning (with "features party" and a "labels party") was recently studied by Li et al. (2021). who considered the interactive setting where the two parties can engage a protocol with an arbitrary number of rounds (with the same application to computational advertising described in Section as a motivation). By contrast, we considered in this paper the one-way communication setting (from Figure 1), which is arguably more practical and easier to deploy.
Kairouz et al. (2016) study optimal local DP algorithms under a given utility function and prior. For number of utility functions, they show that optimal mechanisms belong to class of staircase mechanisms. Staircase mechanisms are much more general than randomized response on bins. In that regard, our work shows that particular subset of staircase mechanisms is optimal for regression tasks. In particular, while we give an efficient dynamic programming algorithm for optimizing over randomized response on bins, optimal staircase mechanism. (In particular, straightforward algorithm takes (0))) time.)
not aware of any efficient algorithm that can compute an
6 CONCLUSIONS AND FUTURE DIRECTIONS
In this work we propose a new label DP mechanism for regression. The resulting training algorithm can be implemented in the Teature-oblivious label DP setting. We provide theoretical results shed- ding light on the operation and guarantees of the algorithm. We also evaluate it on three datasets, demonstrating that it achieves higher accuracy compared to several non-trivial, natural approaches.
Our work raises many questions for future exploration. First, in our evaluation, we set the objective function optimized using the LP be the same the loss function used during training; different ways of setting the LP objective in relation to the training loss are worth exploring. Second, our nois- ing mechanism typically introduces bias; mitigating it, say by adding unbiasedness constraints into the LP, is interesting direction. Third, it might also be useful to investigate de-noising techniques that can be applied as a post-processing step on top of our label DP mechanism; e.g., the method proposed in Tang al. (2022) for computer vision tasks, and the ALIBI method (Malek Esmaeili et al., 2021) 1) for classification tasks, which is based on Bayesian inference.
We believe that due to its simplicity and practical appeal, the setting of learning with feature- oblivious label DP merits further study, from both a theoretical and an empirical standpoint.
Finally, we leave the question of obtaining better "feature-aware" label DP regression algorithms for a future investigation.
ACKNOWLEDGMENTS
We thank Peter Kairouz and Sewoong Oh for many useful discussions, and Eu-Jin Goh, Sam Ieong, Christina Ilvento, Andrew Tomkins, and the anonymous reviewers for their comments.

---

REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, pp. 308-318, 2016.
Ashwinkumar Badanidiyuru, Andrew Evdokimov, Vinodh Krishnan, Pan Li, Wynn Vonnegut, and Jayden Wang. Handling many conversions per click in modeling delayed feedback. In AdKDD, 2021.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approxi- mate differential privacy. ToC. 12(1):1-61,201 2016.
Colin Cameron and Pravin K Trivedi. Regression Analysis of Count Data. Cambridge University Press, 2013.
Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Data poisoning attacks to local differential privacy protocols. In USENIX Security, pp. 947-964, 2021.
Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In COLT, pp. 185-186, 2011.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. JMLR, 12(3), 2011.
Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In NIPS, pp. 2566-2574, 2015.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pp. 486-503, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitiv- ity in private data analysis. In 7CC, pp. 265 284, 2006b.
Hossein Esfandiari, Vahab Mirrokni, Umar Syed, and Sergei Vassilvitskii. Label differential privacy via clustering. In AISTATS, pp. 7055-7075, 2022.
Quan Geng and Pramod Viswanath. The optimal mechanism in differential privacy. In ISIT, pp- 2371-2375, 2014.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. NeurIPS, pp.
2021a.
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. Differentially private aggregation in the shuffle model: Almost central accuracy in almost a single message. In ICML, pp. 3692-3701, 2021b.
Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally mixlitimaaimizzin pri- vacy mechanisms. SICOMP, 1166))1673-1699 2012.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. JMLR, 17:17:1 2016.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint. Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebas- tian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu
10

---

Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Oscar Li, Jiankai Sun, Xin Yang, Weihao Gao, Hongyi Zhang, Junyuan Xie, Virginia Smith, and Chong Wang. Label leakage and protection in two-party split learning. In ICLR, 2021.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In ICLR, 2017.
Mani Malek Esmaeili, Nya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramer. Antipodes of label differential privacy: PATE and ALIBI. NeurIPS, 34:6934-600 6945, 2021.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pp. 94- 103, 2007.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. ICLR, 2017.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Er- lingsson. Scalable private learning with PATE. In ICLR, 2018
Carey Radebaugh and Ulfar Erlingsson. Introducing TensorFlow Privacy: Learning with Differential Privacy for Training Data, March 2019. blog. tensor org.
Justin Schuh. Building more private web: A path towards making third https://blog.cht http:///log..chomimmm. wwt.:umwogg////e org/2020/011
party cookies obsolete, January 2020.
towards html.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In GlobalSIP, pp. 245-24222 208,248.44 2013.
Marcelo Tallis and Pranjul Yadav. Reacting to variations in product demand: An application for conversion rate (CR) prediction in sponsored search. In IEEE BigData, pp. 1856-1864, 2018
Xinyu Tang, Milad Nasr, Saced Mahloujifar, Virat Shejwalkar, Liwei Song, Amir Houmansadr, and Prateek Mittal. Machine learning with differentially private labels: Mechanisms and frameworks. PoPETS, 4:332-350, 2022.
Di Wang and Jinhui Xu. On sparse linear regression in the local differential privacy model. In JCMI., pp. 6628-6637, 2019.
Tianhao Wang, Bolin Ding, Jingren Zhou, Cheng Hong, Zhicong Huang, Ninghui Li, and Somesh Jha. Answering multi-dimmensoonll analytical queries under local differential privacy. In SIGMOD, pp. 176, 2019.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. JASA, 60(309):63-69, 1965.
John Wilander. Full Third-Party Cookie Blocking and More, March 2020. https://webkit.orrg blog/10218/ful1-ca0 thilddthii--iie httpr///fuul-ttiir--rat-------e cookie- wwweeeebooooiiionoeeeeeeeeee and-more/.
Marissa Wood. Today's Firefox Blocks Third-Party Tracking Cookies and Cryptomin-
ing by Default, September 2019. https://blog.moziil www.i/lla..rgg////rrrtttt/s////s and-
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv:2109.122990 2021.
Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winslett. Functional mechanism: regression analysis under differential privacy. VLDB, 5(11):1364-1) 1375, 2012.
11

---

A OPTIMALITY OF RR-on-Bins"
In this section, we prove Theorem We prove this in two stages. First we consider the case where P has finite support and y is constrained be a subset of pre-specified finite O _ R. Next, we consider the case where Y is allowed to an arbitrary subset of R, and thus, the output distribution of the mechanism on any input y can be an arbitrary probability measure over R.
Stage I: Finitely supported P. C O, strictly increasing/deeressingg,
Theorem 8. Let P be a distribution over with finite support, O a finite subset of R, and R x R 12 be such that
For all y E IR, E(G, v) is strictly decreasing in ÿ when ÿ S y and strictly increasing in ÿ when ÿ 2 y.
For all i E IR, f(J, v) is strictly decreasing in y when S y and strictly increasing in when y 1 D.
Then for all 8 > O, there exists $ y + such that
L(RR-on-Bins"; inl L)M; M
where inf is over all c-DP mechanisms M with inputs in y and outputs in O.
The proof of Theorem is inspired by the proof of Theorem 3.1 of Ghosh et al. (2012). Namely, describe the problem of minimizing LMM; P) as a linear program (LP). We arrange the variables of the LP into matrix and associate any solution the LP signature matrix, which represents when constraints of the LP are met with equality. Then we make several observations of the signature matrix for any optimal solution, which eventually leads the proof of the theorem.
Proof of Theorem 8. Without loss of generality, we may assume that y = supp(P) P) and therefore is finite.
When D is restricted to be a subset of O, the optimal mechanism M which minimizes L(M; P)
E.y-P.ss {(ū, y), is encoded in the solution of the following LP, with | variables My-r
Pr[M(y) = ú] indexed by (y, 9) E y x O. Namely, the first two constraints enforce that (My a valid probability distribution and the third constraint enforces the c-DP constraint.
ΣPn Py yEy
Σ My-r - ((5,8)
min M
subject to
Vy E V, :
My 2 0,
(2)
Ay E/:
Σ My-1 =1 DEO
Vÿ E O, V.. E ",リ
My S e -M
Corresponding to any feasible solution = SM. First, let p ming My-r and let pl max max, My-rj Note that, from the constraints follows that ymax < ef mmin.
we associate a |/ [0| signature matrix
Definition 9 (Signature matrix). For any feasible M for the LP in (2), the signature entry SM (v. 0) for all y E y and ÿ E O is defined as
0
if My- =
if My-+8 = max = E p
SM (M
L
if My-1 P.J - p) max
5
otherwise.
12

---

1.5
2.5
3.5
4.5
1.5
2.5
3.5
4.5
1
0
1/2
1/4
1/4
1
0
U
S
2
1/2
1/4
1/4
2
3
0
1/1
1/1
7/2
3
0
L
5
4
0
1/3
1/3
1/3
4
0
5
5
S
5
1/3
1/3
1/3
M
SM
Figure 5: Example of signature matrix for e 1/2 for (1,2,3,4.5) and O {1.5, 3.5,
We visualize SM as a matrix with rows corresponding to y's and columns corresponding to j's, both ordered in increasing order (see Figure 5).
If . is an RR-on-Bins, mechanism for some + y O, then it is easy to see that the cor- responding signature matrix satisfies some simple properties (given in Claim 10 below). Interest- ingly, establish converse, thereby characterizing the signature of matrices M that correspond to RR-on-Bins, mechanism for some 4 O.
Claim 10. M corresponds to an RR-on-Bins, mechanism for some non-decreasing + y - D (for y O) and only if either
(1) One column consists entirely of S. while all other columns are entirely 0; let V ( ÿ. where corresponds to the unique column,
or all of the following hold:
(2a) Each column in SM either entirely O, or entirely consisting of U's and L's, with at least one
U and one L.
(2b) Each row contains single U entry, with all other entries being either or for each y, we denote this unique column index of U by T (ty).
(2c) For all y < sf holds that (yy S (t)))
In each case, it holds that Φb V
Proof of Claim 10. Suppose M corresponds to RR-on-Bins," for some non-decreasing T. If tb is constant, then condition (1) holds, since all columns corresponding to ý range($) in SM all O, whereas, the only remaining column consists of all S. If & is not constant, then My-r = e <l(
[ 11). and hence its signature Sa is such that S (v. D) is U if ÿ. and casy to verify that all three conditions hold: is entirely 0 if and only if ÿ range 4) and entirely consisting of U's and L's otherwise with at least one corresponding to y such that (vy) = ÿ and at least one corresponding to y such that (g)) has a unique U corresponding to y V (y) = ( and (2c) For < y it holds that (v) S (1)) since & is non-decreasing.
9 E range(D) () {y))) and otherwise.
(2a) column corresponding
(since + is non-constant), (2b) Each row corresponding
To establish the converse, suppose we have that Sa satisfies condition (1). Then we immediately get that M corresponds RR-on-Bins for the constant map v. Next, suppose SM satisfies all three conditions (2c). Immediately, we have that M is given as
min e P p
if SM (v. 9) U
My =
SM (v. 9) =
0
if SAr (v. = 0.
Let Y correspond to the set of non-zero columns of SM. Since each row of M corresponds probability distribution, have for each y that EgrED p (e ( 11pp 1 by considering
13

---

the row corresponding to any y v (0). Thus, we get that p is the same for all values in }) and in particular, P. oz -1 and thus, we get that the corresponding M is uniquely given by
if S ú) = U if Sur 0) = L
My-1-
++
if MM (y. 0) =
which clearly corresponds RR-on-Bins," for k (y)) We have that v, and hence o, is non-decreasing from condition (2c). This completes the proof of Claim 10.
Thus, to show optimality of RR-on- it suffices to show that there exists minimizer M of the LP (2), such that Sy satisfies the conditions Claim 10.
It is well known that an optimal solution to any LP can be found at the vertices of the constraint polytope and that for I.P with n variables, vertices must meet n linearly independent constraints. We use this to find a submatrix of SM, which will determine M in its entirety.
If M is feasible point, then each column of SM is either entirely O, or entirely consisting of S, U, and L. This is necessary since if My-ra O, then 0 S My - S e My 0. Let k denote the number non-zero columns of S
Lemma 11.
Suppose M is verlex of the LP (2) with k non-zero columns of Sas. If 2 2, then M has a x k submatrix (k) with all distinct rows, consisting of only U's and L's.
Proof. M is a vertex if and only if there are | | many linearly independent constraints that tight. We count the number of tight constraints just from Sw and note some instances of dependence give lower bound on the number of linearly independent constraints.
1. | constraints, given by E3 My are always tight.
2. For a zero column of SM corresponding to y. each My-si 2 is tight corresponding to each E y. These correspond to |}]] ([O) - k) constraints.
3. For non-zero column of Sas corresponding to g. let Cg(U) denote the number of U entries in column ÿ and similarly, define (L) and C5(S) analogously. For each pair
y1, 1/2 such that Sas (y1, ú) L and SM (32, ú) U, we have tight constraint My - S ef M, 1/2 - However, these constraints are not linearly independent. In fact, there are only D Cy)S) many linearly independent constraints among these.
(₂)
C,))+
4. Another instance where the constraints might be dependent is if two rows of SM. corre- sponding to say 8/1 and y/. are identical and do not contain any S's. In this instance, the two equations of Eg My.-+g independent. The DP inequality conditions imply that all the coordinates are equal between the two rows, which imply a dependence relation between those and the two conditions.
and the inequalities given by the Os, U's, and L's are not
Counting these all up, we have a lower bound on the number of linearly independent constraints. This must be at least DVI (O). Let (# of duplicate rows not containing S) be the difference between the number of all rows not containing and the number of distinct rows not containing S. Thus, we get
CC((S) of duplicate rows not containing S) 2 11-11))
Rearranging,
| Σ Cg(S)) (# of duplicate rows not containing S) 2 k.
and because
Σ Cg(S) (# rows containing S),
14

---

conclude
| - (# rows containing S) - (# of duplicate rows not containing S) 2
Hence, there are at least k rows, which are all distinct and contain only 0's, U's, and L's. Narrowing our scope to just the k non-zero columns, we get k x k sub-matrix M(K) that contains only U's and L's. This concludes the proof of Lemma 11.
So far, we did not use any information about the objective. Next we use the properties of the loss function & to show that if M is an optimal solution to the LP, any submatrix provided by Lemma 11 can only be of one form, the matrix with U's along the diagonal and L's everywhere else:
Lemma 12. Suppose M is an optimal vertex solution to the LP with k 2 2 non-zero columns. Then any k x k submatrix (k) given by Lemma 11 has U's along the diagonal and L's otherwise.
Proof. Firstly, in each row of M the U's are consecutive. Suppose for any and ÿ1 < ú2 < ÿs. it holds that Sa (y. 91) = (y, ûs) U, whereas SM (y, 92) is either L or This implies that ((i, y). ((33.))) < E(92.)) y), since otherwise, it is possible to reduce My-r. (resp. M + $a)) and increase My-raz thereby further reducing the objective, without violating any constraints. But this is a contradiction to the assumption of l in Theorem 8, since ((: cannot increase from ý1 to d2 and then decrease from 32 to ÿ3.
Secondly, SM cannot contain the following 2 x 2 matrix, where yı < 1/2 and ÿ1 Ø2:
91
02
3/1
U
1/2
Since M is optimal, we get that E(g1, 81) > E(02. V1), and from the assumption on é it follows that
d1 < y1 (since otherwise, 31 S 81 < d2 which would imply E(i,, V1) < E(i2, V1)). Similarly, we
have that E(02. y2) > E(11.22) and y2 ÿ2. However, since 91 < 11 < y/2 < f2. we have that (iiz, v1) > E(02, U2) and U2) > ((1, which gives rise to a contradiction:
f(11. v1)
> f(02, v1)
E(22, 822
E(11, U2)
((1, 81).
In particular, this claim of not containing the above 2 x 2 matrix applies to (
Lastly, every row of M (k) has at least one U. Suppose for contradiction that the row y in Sy does not contain single U. Then it has all L's and O's. Any column that contains L must contain U in SMS So necessarily there is a row y' in SM containing a U. Now, y containing only L's and O's implies that E3 My-ri Eg My which is a contradiction of the constraints of the LP.
Since the rows of this k x l sub-matrix (() are all distinct, and it does not contain any 2 x 2 submatrix as above, the only possible signature is where all the diagonal signature entries are U and the rest are L. Let E [k] be the index of the first index U for the ith row and similarly e E [k] be the last index of U. Because the U's are continuous, 8; and e; determine the signature of the Cj. then Σy My-+ < ES My--r where
row. If 8; = 8, for i * j. then e; ej- Else if y corresponds to row i and y' corresponds to j which is a contradiction. Similarly for e; > ej. The same argument can be made if e; ej. then s; $5- The rows of (*) are distinct, so this implies that 8; F 8j, 6 & éj for i * j. The observation about the 2 x 2 matrix shows that if < 8; 8j and e; S Gj- So the 8; and 6; are both l distinct ordered sequences of [k:). The only such sequence is s; = e, i, implying (k) is a diagonal matrix of this form. This completes the proof of Lemma 12.
We now have the necessary observations to prove Theorem 8. Let M be an optimal vertex solution to the LP 2. That is C(M; P) inf M L(M; P). If M has non-zero column, then Sas has one column entirely of S and the rest O. By Claim 10, M corresponds to RR-on-Bins, mechanism. If
15

---

M has & 2 2 non-zero columns, then by Lemma 12, SM has k x & submatrix M with U along the diagonal and L otherwise. We show this completely determines Sas in the form described by Claim 10(2a-2c).
Note that SM for any vertex M has at most one per row. S (v. 31) and (y (22) are both equal to S for 1/1 # y2, then it is possible write M convex combination of two other feasible points given as M + 1yM' and M ryM' for small enough where My + 92) = -y - 01 = and M' + 1'') 0 for all other v' Intuitively this corresponds to moving mass My-ri from My My in a way that does not violate any of the constraints. But M is vertex so it cannot be the convex combination of two feasible points.
But moreover, Sa for an optimal vertex solution has exactly one U per row and the rest L's and 0's. Suppose the row corresponding to y has Sy (y, 9) either L or S and the rest of the entries either L or O. From the observations above of the submatrix M(k),, there exists a row y/ such that S (v', D) U. Then, we have Σg My-- < Eg My- 1, which contradicts feasibility. Similarly, if a row of SM contains U and an S (or multiple U's), then we would have Σ3 M Eg My-e-
This allows us define V y O be the unique such that SMr 0) U. Note that V is non-decreasing from the observation earlier that SM cannot contain the 2 signature above. This completely characterizes SM as the form described by Claim 10(2a-2e), completing the proof of Theorem 8.
We use a continuity argument show that Theorem 8 holds in the case where the loss function ((j y) is decreasing/ / increasing instead of strictly decreasing increasing.
Corollary 13. Let P be a distribution over R with finite support, O finite subset of E. and
R x R
R20 is such that
For all y RR f(j, v) is decreasing in when ğ S y and increasing when y. For all E R, ((.3)) y) is decreasing in when S 0 and increasing in when 2 g.
.
Then for all > 0, there exists 4 y O such that CARR-nn-Bins"" P)
inf L(M; P).
M
where inf M is over all s-DP mechanisms M with inputs in y and outputs in O.
Proof. Let V correspond to the set of solutions M that are vertices of the LP. Let W C V correspond to the set of vertex solutions that are RR-on-Bins. A rephrasing of Theorem is that the minimum loss over mechanisms in V is equal to the minimum loss over mechanisms in W.
For > 0, define (ū. y) = E(ÿ. y) + ly - 5 Note that E, satisfies the conditions of Theorem 8. For any fixed mechanism M, the loss continuous 17
lim
Σ Py
Σ BEO
My ((.
Σ Ps DE
E My-s ((G. v)
VED
GEO
The minimum of finitely many continuous functions is continuous. In particular
lim min Σp
Pv
Σ BEO
My (0(
min Σn Pv MEV
Σ JEO
My-0 E(D.v)
7 MEV yEy
yEy'
and similarly
lim min n 7 MEW
Σ Py
Σ
My- ((.
min NEW
Σ
Py
Σ
My E(O v)
yE
JEO
DEy
JEO
but the LHS of both equations are equal by Theorem 8, so
min
Σ
Ps
Σ
My-i E(G.u)
min NEW yEy
Σ Py
Σ
My E(G.,v) v)
MEV
VEY
BEO
BEO
completing our proof.
16

---

Stage II: Finitely supported P and y C R. We now prove Theorem 5. Let Umin and Ymax denote the minimum and maximum values in V. respectively. We will first show that
inf inf L(RR-on-Bins"" P) PCR4YYY
inf L(M; P). M
(3)
where the infimum on the RHS is over all s-DP mechanisms M. Since RR-on-Bins, an e-DP mechanism, we have
inf C(MPP) S inf inf L(RR-on-Bins"; P). oc
(4)
M
To show the converse, let y be any parameter. There must exist E-DP mechanism M' : R such that
L(Mi inf L(M: P) + 7/2.
(5)
M
Let O S Ummiu Vmax be defined as follows:
For each y E y, let ay minge (maee) {(g. v) and by maXge (Jmmnn [mmax]] E(g. v). Let
T = [4 ay)/7l-
Let oye be the finite set containing the maximal and minimal element of {ū { y)
=
ay + (by - ay)} if the set is non-empty. Otherwise, let it be the empty set.
Let O, = U - Oy
Finally, let O Uney Og,
Naturally, O is finite. Finally, let MM be the mechanism that first runs M to get and then outputs the element in O closest ÿ. By post-processing DP, M remains e-DP. Furthermore, is not hard to see that by the construction of O and by Assumption 4, we have
[(M"; P) < L(M'; P) + 7/2.
(6)
Finally, since range(M") O is finite, the proof in Stage implies that
inf inf L(RR-on-Bins," c P) < L(M"; P). yço v.
(7)
Combining (5), (6), and (7), we can conclude that
inf inf L(RR-on-Bins," P) inf L(M; L(M;P)+ PCR o:y-v
(8)
M
Since (8) holds for any 7 0, combining with (4), conclude that (3) holds.
Next, will show that there exists Y and x- y + yr such that L(RR-on-Bins, :P) inf inf C(RR-on-Bins": P). VCR wy-+
(9)
Combining this with (3) completes the proof.
For any Φ y + R. let Po denote the partition on y induced by Φ-1, Note that the RHS of (9) can be written as
inf inf L(RR-on-Bins"; P) min inf JCROY-
C(RR-on-Bins" P),
(10)
Y.y-
YCR
where the minimum is over all partitions of
For fixed partition P P of V L(RR-on-Bins"" P) simply be written
e [
Σ
+ | - ((ii u)
Py
e
S,EP
vEy
17

---

(from Assumption 14) where it is the output corresponding to the part S₁ in the partition.
atlloc3s) Notice that the function Di + (Evey Py 20 24 (( w)) is continuous. Furthermore, it is ob- vious that increases once it becomes further from [8/mn Ymax] Thus, the minimum must be achieved at some point 0f E [ymins Mmax] As result, by defining Ø such that (s,,,) 07 this also achieves the minimum for inf +.y+3 ((RR-on-Bins"" P). Therefore, plugging this back into
yCR
(10), we can conclude that the minimum of inf DÇR inf ..yーン ((RR-on-Bins," P) must be achieved by some y", Φ" This completes our proof of Theorem 5.
A.1 EXTENSION TO ARBITRARY (INFINTELY-SUPPORTED) P AND y C..
We show that Theorem 5 can be extended to hold even for anfinitel--suppotee distributions P over bounded interval, but under additional assumption that the loss & is Lipschitz over the said interval.
Assumption 14. For specified bounded interval (umin Fmaxl, loss function & [ymin Fmaxl x WMmin ymax]] + R22 is such that both E(-,3) 3) and E(is :) are L-Lipschitz
Theorem 15. For all Ymin: Vnax E TR. loss functions E: R x R - Rzn satisfying Assumptions and 14, and all distributions P over y S [ymin: Umax], there is finite oulput set y C. R and non-decreasing map T y + 5 such that
: P)) = inf L(M:P),
M
where the infinum is over all E-DP mechanisms M.
We break down the proof into series lemmas. First we show that the infimum reached by the infimumm of GR-on-Bins mechanisms:
Lemma 16. Under the assumptions of Theorem 15, it holds that
inf PCR.
L(RR-on-Bins"" P) inf L(M;P). M
4-
Proof. To prove the lemma, suffices to show that for any g E N, there exists choice of ÿ C R and & y + such that C(RR-on-Bin) BBns P) I inf L(M; P) + where ? = L Mmav Umin
Consider a discretization of y given as
Mmuin + in L 0
Let : + 5 be the map that rounds any element of ) to the closes element of V. Note that ly p(y) < (2T.)) for all y y. Consider the distribution P over ) given by the "rounding process", which samples y P and returns p(y). Note that there is natural coupling between P and P such that ly - Ø S 7/(2)) holds with probability 1. From Theorem 5, we have that there exists a finite ) C R and non-decreasing map क. ÿ + such that &h L(RR-on-Bins" P) inf P)
(11)
M
where M is an c-DP mechanism mapping 5 to D: We can extend क to + y - D given as (vy) == d(p())) It is easy to see that since & is non-decreasing, & is also non-decreasing. From Assumption 14, follows that
L(RR-on- Bins,: P)
E E(RR-on-Bins (v).
y-P
y-P E ((RR-on-Bins (p(y)).v)
y>P < E. (RRR-on-Bins" ((lu)),(u)) + 7/2
C(RR-on-Bins P) 7/22.
(12)
18

---

Similarly, for any E-DP mechanism M mapping y to D, construct an E-DP mechanism M mapping Y y where M() is sampled as M(y) for y P()()==-- Note that sampling 5 P and returning Plo(v)= is equivalent to sampling P. Thus, we have
L(M;P) = E ((M(O).))
g-P
E (((()))
w-P
S E. (M)(())) +7/2 gop
(from Assumption 14)
L(M;P) + 7/2.
(13)
Thus, combining (11), (12), and (13), we get
L(RR-on-Bins"; ; P) L +. P) 7/2
inf ((M; P) +2/2
S inf iIM P) + M
Next we show that the infimum of RR-on-Bins is reached by considering the RR-on-Bins with finitely many bins. Towards this end, let RR-on-Bins", denote the set of all RR-on-Bins, mech- anisms where & Y + ÿ with [ n.
Lemma 17. Suppose f(G. v) integrable over y for any Then for all 0, it holds that lim inf MERR-on-Bins"
L(M; P) >
inf MERR-on-Bins!
((M:))
Interestingly, Lemma 17 does not require any assumption about the distribution P or aside from integrability. For example, P can be an unbounded distribution.
Remark:
Proof. Let
/ v)d.))
=
inf MERR on Bins
C(M:P) inf ØeR
This is precisely inf inf MERR Bins; L(M; P), where the ÿ is selecting the single bin output Note that a does not depend on E.
For any > 1, consider RR-on-Bins,, where & : y + 5 for í = tūr.... InJ. Then we can bound the loss from below:
e + e + (((())))) dP(v)
L(RR-on-Bins." P)
ex +n n-1 ((D.V))
c + ((Ut.)) dP(u)
E(ūr. u(PP.))
e +
n
e + a
+ n -1 a.
In particular, inf MERR L(M:P) - which implies that
lim
inf
L(M; P) 2 a.
==00 MERR-on-Blins
19

---

Corollary 18. Suppose E(g. y) is integrable over y for any ÿ. Then for all >> 0, there exists such that
inf MERR-on-Bins"
L(MPP) = inf inf -oRRRon-Biiny
((M; P).
Proof. For any n, let an inf MERRo--B--s P) From Lemma 17, have that limn-+oo On 2 a1 If inf, = 01, then the corollary is true for 1. Else, if inf, On = a' < 01, then there exists ng > 0 such that for all > ng. it holds that an (a1 + a//22. Thus, inf, On minngng On which implies that the infimum is realized for some finite n.
Finally, we show that the infimum over RR-on-Bins" is also achievable, completing the proof of Theorem 15.
Lemma 19. Suppose is bounded within the interval ymin Mmax] Suppose é: R IR + Rz0 satisfies Assumptions and 14, then for any n >> there is an output set D C with | n and a non-decreasing map & : - y such that
C(RR-on-Bins"; P) P)
inf MERR-on-Bins"
C(M;
Proof. Because of the increasing / decreasing nature of we can restrict the output of + to be in the range [ymin: Vmax]- Given an output range fūi..... Gn the RR-on-Bins, mechanism that minimizes C(RR-on-Bing P) satisfies
( arg min Ejjc, y)
So consider CRRR-RR-Binss P) function of (fi.....9,
2n) [ymin: Vmax
We claim that L(RR-on-Bins"" P) is continuous with respect these inputs {91,... 8n }. Indeed ......,,,,, by the Lipschitz continuity, a change in -ii,..., 2n] to 17,... V%1 where [0; 7/l < 6 for some 6 > 0 results in change in C L(RR-on-Bins." P) bounded by L8. Therefore C(RR-on-Bins, P) continuous function of (Ji,...,dhe Un) over compact set [ymin Umux]" and hence it attains its infimum. This infimum defines & that satisfies the lemma.
B ANALYSIS OF DYNAMIC PROGRAMMING ALGORITHM FOR FINDING OPTIMAL RR-on-Bins
Below we give correctness and running time analysis of Algorithm 2.
Correctness Proof.
We will prove the following statement by strong induction on i:
min
Σ Σ Pv llves| -(D(SS))),
(14)
RR
SEP y
iPl-j
where the minimum across all {v- ..... v' such that, for each á e range (4), - ()) is an interval and that [Po. = j where the intervals are SI...., Sy (in increasing order).
Before we prove the above statement, note that it implies that A/m|[d] (d 1 e²)
min - --lldd C(RR-on-Bins" P). Thus, the last line of the algorithm ensures that we output the optimal RR-on-Bins as desired.
We will now prove (14) via strong induction on i.
Base Case. For 0 (and thus j 0), the statement obviously true.
20

---

Inductive Step. Now, suppose that the statement is true for all O.....t 1 for some E N. We will show that it is also true for i = t. To see this, we may rewrite the RHS term (for i = t) as
min
Σ SEPo NEy
Σ Py (vES] e (()(S).))
2: iPol=j
R
Pg el (((((S).))
min 0srct T:(1" ""." PPo
min
JR
SEP& DEy
(y"
JEP&
Σ
Σ
By elIvES) (((4(5),))
min uSrc!
min 0:(3" w..l H-R SEPs vey
iPo=jj-1
Σ vEy
pv "lvelv''' "'ll== E(0,8) 3)
min
8=0((~"1 (..)
A[r] 1] 05t<t
min
L(r 1][(].
where the third inequality follows from the inductive hypothesis and the definition of L[r + []({- The last expression is exactly how A[t][}] is computed in our algorithm. Thus, (14) holds for =
Running Time Analysis. It clear that, apart from the computation of +1]b],, the remainder of the algorithm runs in time O(k2). Therefore, the total running time is O(k2 where I' denotes the running time for solving the problem mingeR Evey Py elIvely", ">'l== f(ğ, y)- When the loss function é is convex, this problem is univariate convex optimization problem and can be solved in polynomial time. We can even speed this up further. In fact, for the three main losses we consider (squared loss, Poisson log loss, and absolute-value loss) this problem can be solved in amortized constant time, as detailed below. Therefore, for these three losses, the total running time of the dynamic programming algorithm is only (kk)).
Squared Loss.
In this case, the minimizer is simply
Eney Py ellvelr w
arg min
Σ Py elIvele" w'lle leg(D. Evey Py ell will =: Vr. yEY
jER
Therefore, to compute Gr it suffices to keep the values Evey Py e Ivvev"" w'll and Evey Py elvVE>>" w']]== We can start with r = and as we increase i, these quantities can be updated in constant time.
Note also that
min Σ jER vey
Py e [iveee"w'tlee (0. y)
Σ wEY
HoEly wfke 32² -2
Py e ellvelo"'''le w) Fr.s + (Hr.)) PEy
Σ
Therefore, to compute the minimum value, we additionally keep Eyey ellvElo" <llvel"ww/llse which again can be updated in constant time for each
Poisson Log Loss.
The minimizer is exactly the same as in the squared loss, i.e.
Σ Py Aue w']l Epoi 4) = Evey Py IevEv"
arg min
EyEr Py el "ee =: Dr
VER
BEY
21

---

Therefore, using the same method as above, compute 9" in amortized constant time. The minimum is the simply
min yER
Σ
Py
Llvele" Epoa(ú: y)
yEY
ENs
Σ
el Alveel".>') log(ūt;)),
Ps
NEY
DEy
this also be computed in constant time with the quantities that have recorded.
Absolute- Value Loss.
To describe the minimizer, we define weighted version of median. Let {(w1, a1 a1)................... (w,,a,)) be a set of tuples such that Wi,..., Wi E R>0 and aI,..., E R with _ ... S ar. The weighted median of {[w) ai),..., (w, a. denoted by wimed(((w)) ai),.................... (w;, (;))
is equal to the minimum value a" such that Σ jE(U] Wy 2 (EjE(a w2)/2. 2. It is not hard to see 0,Sa"
that
- Nyelly wfll (aba( wmed (1(D)) Alvelo .w) }ey)))
arg min VER
Σ Py yEy
Notice also that we must have V. y. For fixed (and varying i), the algorithm is now as follows: first compute pr and also compute
Σ DEY V.S.
elvlev w'Ile
Who
Pv
and
Whi = Σ
Pv . c w')l
VEY 1>ン
For i= - +....,.,. initialize Ur Vr and update Who or whi (corresponding to the weight change from Py, e of y:). We then perform updates reach the correct value of ir, That is, if Who Whis then move to the next larger value in V; if Who Pot.: then move the next smaller value in y Otherwise, stop and keep the current 07..- To understand the running time of this subroutine, note that the initial running time for computing or,- and W)o Whi is (k)) Furthermore, each update for Dr, takes O(1) time. Finally, observe that if we ever move Di, decrease again. As result, in total across all
"." .y'Il== Whis
larger value, it must be that y/ gf. After this i, g will never
+ 1, ....,, k. the total number of updates can be at most 2k. Thus, the total running time for fixed (k)) Summing up across [k). we can conclude that the total running time of the entire dynamic programming algorithm is O(k2).
C RR-on-Bins WITH APPROXIMATE PRIOR
Recall from Section 3.2 that, when the prior is unknown, we split the budget into 1 E2, use the E DP Laplace mechanism to approximate the prior and then run the RR-on-Bins with privacy parame- ter The remainder of this section gives omitted details and proofs from Section 3.2. Throughout this section, we use to denote |}|| (the size of the input label set).
C.I LAPLACE MECHANISM AND ITS GUARANTEES
We start by recalling the Laplace mechanism for estimating distribution. Recall that the Laplace distribution with scale parameter b, denoted by Lap(b), is the distribution supported on IR whose probability density function is 2/2 cxp(- - The Laplace mechanism is presented in Algorithm 4.
is well wnol- (c.g., Dwork et al. (2006b)) that this mechanism satisfies e-DP. Its utility guarantee, which we will use in the analysis of LabelRandomizer, is also well-known:
22

---

Algorithm Laplace Mechanism for Estimating Probability Distribution MM
Parameters: Privacy parameter 2
Input:
Labels yi...., e
Output: A probability distribution P' over
for y E y do
hy number of i such that y/s
Ny f- max(hy + Lap(2/s), 0}
" return Distribution P' over y such that ply = Evey Kg
Theorem 20 (e.g., Diakonikolas et al. (2015)). For any distribution P on Y, n E N, and > 0, we
have
k
E Vir.BaNPP p' P'r ( (vi....))))
|| PIl1
0
En
C.2
PROOF OF THEOREM 6
Theorem 6. LabelRandomizer...a is (E1 D2)-DP.
Proof of Theorem 6. The Laplace mechanism is E1-DP; by post-processing property of DP, 4' is also DDP For fixed Φ', since RR-on-Bins", Eg-DP and applied only once on each label, the parallel composition theorem ensures that (J1,..., Un) is e2-DP. Finally, applying the basic composition theorem, we can conelude that the entire algorithm (e1 + 82)-DP.
C.3 PROOF OF THEOREM 7
Theorem 7. Let E R + Rz0 be any loss function satisfying Assumption 4. Furthermore, assume that {(), y) for some parameter B for all y, 1 Y. For any distribution P Y, e > O, and any sufficiently large E N, there is choice of $1, 82 > 0 such that $ + &2 = and
C(RR-on Bins 4' 02 P)] L(M; P) SO VDDI/)
Mirooll p' v0' S
M
where P P', "', S0 are as in LabelRandomizerr..ce and the infimum is over all s-DP mechanisms M.
Proof of Theorem 7. From Theorem 20, we have
(1 Eim
||'' P|h 50
D P'NMMtaRDD)
23

---

Recall from Theorem 5 that there exists + y D such that L(RR-on-Bins P) infM L(M; P). Consider instead the Bi--n-Binng, mechanism. We have
inf [(M; P) L(RR-on-Bins"; " P) M
[C(RR-on-Bins_" P) L(RR-on- Bins
- Σ Py B.
e
e²2
Σ
c + (
1 -1
e D1
e + -1 e + 130 -1
VEY
(E)({*())
2(15) 1)(e -E
B. (ef + [] ee +111 -)
2B. (1 -((
2B(e - 82)
2Bar.
Recall that RR-on-Bins, is Ep- optimal mechanism for prior Pl. That is, we have
L(RR-on-Bins" '' P s L(RRR-n--inns", P!).
Finally, we also have
LC(RR-on-Bing 4 P) L(RR-on--Bns P')l 1C(RR-on-Bins P) C(RR-on-Bins, gg
B |P Pll
P') S B P -Phh
Combining the above five inequalities, we arrive at
[(RR-on-Bins P)] - inf ((M;:)
B
61 +
9 MoooMe PP pe o S
Ein
Setting E1 Vk/n then yields the desired bound".
D DP MECHANISMS DEFINITIONS
In this section, we recall the definition of various DP notions that we use throughout the paper. Definition 21 (Global Sensitivity). Let f be function taking input dataset and returning as output a vector in Rdd Then, the global sensitivity (()) of f is defined as the maximum, over all pairs (X, X') of adjacent datasets, of [X) - f(X'Ili-
The (discrete) Laplace distribution with scale parameter b 0 is denoted by DLap(b). Its probabil- ity mass function given by p(y) x exp(-lyl/b) for any y E
Definition 22 (Discrete Laplace Mechanism). Let f be function taking as input dataset X and returning output a vector in zd The discrete Laplace mechanism applied to on input X returns S(X) + (Y....,, Ya) where each Y; sampled i.i.d. from DLap(A(f)/e)) The output of mechanism is s-DP.
Next, recall that the (continuous) Laplace distribution Lap(b) with scale parameter b > 0 has prob- ability density function given by h(y) xx exp(-lul/b) for any y E
Definition 23 (Continuous Laplace Mechanism, Dwork al. (2006b)). Let f be function taking as input dataset X and returning as output vector in d The continuous Laplace mechanism applied f on input X returns f(X) (Y....., Ya) where each Y, sampled i.i.d. from (f)(A)))/E). The output of the mechanism is c-DP.
Note that this requires k/e² for the setting of 52 E1 he valid.
24

---

We next define the discrete and continuous versions of the staircase mechanism (Geng & Viswanath, 2014).
Definition 24 (Discrete Staircase Distribution). Fix A 2 2. The discrete staircase distribution is parameterized by an integer 1 $ S A and has probability mass function given by:
a(rr)
for 0 < <i<r, for Si A
e F((r)
pr
(15)
e kr pr (i- kD)
for Kλ S < (k: + 1)A and & e E
Pr -r( for < O,
where
1-
a(r) = 2r + 2b(A r) - (1-b)
Let f be function taking as input dataset X and returning output scalar in E. The discrete staircase mechanism applied to f on input X returns +(X++Y where Y is sampled from the discrete staircase distribution given in (15).
Definition 25 (Continuous Staircase Distribution). The continuous staircase distribution is param- eterized by E (0, 1) and has probability density function given by:
(a())
for æ E [0, 74) for x E } A)
e a(r)
hx)x)= =
(16)
e ke h,y kA)
for [K (k 1)A) and & e N
hy(-x) for O,
where
a(7) =:=
Let f be function taking input dataset X and returning output scalar in R. The continuous staircase mechanism applied to f on input X returns f(X) + Y where Y is sampled from the continuous staircase distribution given in (16).
Definition 26 (Exponential Mechanism, McSherry & Talwar (2007)). Let q(-,-) be scoring fune- tion such that q(X,r) r) is a real number equal to the score to be assigned to output when the input dataset is X. The exponential mechanism returns sample from the distribution that puts mass x exp(=q(X,r) on each possible output r. It is (2=A(q))-DD) where A(g) is defined as the maxi- mum global sensitivity of q(.r) over all possible values of
Definition 27 (Randomized Response, Warner (1965)). Let с 2 and q be a positive integer. The randomized response mechanism with parameters and K (denoted by RRc.g) takes as input y E {1....,K] K} and returns a random sample ğ drawn from the following probability distribution:
for 1 = otherwise.
Pr(ū = 5)
(17)
The output of RRe.g is c-D..
E ADDITIONAL EXPERIMENT DETAILS
We evaluate the proposed RR-on-Bins mechanism on three datasets, and compare with the Laplace mechanism (Dwork al., 2006b), the staircase mechanism (Geng & Viswanath, 2014) and the expo- nential mechanism (McSherry & Talwar, 2007). For real valued labels (the Criteo Sponsored Search Conversion dataset), we use the continuous Laplace mechanism (Definition 23) and the continuous staircase mechanism (Definition 25), and for integer valued labels (the US Census dataset and the App Ads Conversion Count dataset), we use the discrete Laplace mechanism (Definition 22) and the discrete staircase mechanism (Definition 24).
25

---

E.1 CRITEO SPONSORED SEARCH CONVERSION
The Criteo Sponsored Search Conversion dataset is publicly available from https://ailabb
criteo. com/criteo- wetrrssreeedeaacc---ooooeeee log---o---ttsset/ To predict the conversion value (SalesAmountInEur)), we use the following attributes as inputs:
Numerical attributes: fime_dellyyffor_covvrrssi @b_clicks_lweek product_price.
Categorical attributes: product__ge-_gruup device device_type, audience_ __d,, product_gendee product_cattegoy..7 product_country,
product_brand, product_categune product_id, product_title, par tner _nn, user_id.
All categorical features this dataset have been hashed. We build vocabulary for each feature by counting all the unique values. All the values with less than 5 occurrences are mapped to a single out-of-vocabulary item.
We randomly partition the dataset into 80%-20% train-test splits. For each evaluation configuration, we report the mean and std over 10 random runs. In each run, the dataset also partitioned with a different random seed.
Our deep neural network consists of a feature extraction module and 3 fully connected layers. Specifically, each categorical attribute is mapped to 8-dimensional feature vector using the pre- built vocabulary for each attribute. The mapped feature vectors are concatenated together with the numerical attributes form feature vector. Then fully connected layers with the output dimen- sion 128, 64, and I are used to map the feature vector to the output prediction. The ReLU activation applied after each fully connected layer, except for the output layer.
We train the model by minimizing the mean squared error (MSH) with 1,2 regularization 10-1, using the RMSProp optimizer. We use learning rate 0.001 with cosine decay (Loshchilov & Hutter, 2017), batch size 8 8192, and train for 50 epochs. Those hyperparameters are chosen based on setup with minor label noise (generated via Laplace mechanism for 6). and then fixed throughout all runs.
For the RR-on-Bins mechanism, we use the recommended E / />i// in Theorem private prior, and with the remaining privacy budget. optimize the mean squared loss via dynamic programming. When running Algorithm 2, would be quite expensive to use y as the set of all unique (real valued) training labels. So we simply discretize the labels by rounding them down to integer values, and use y = (0, ,, 400J. The integer labels are then mapped via Algorithm I.
query
E.2 US CENSUS
The 1940 US Census can be downloaded from https://wwe archives. httpivves.go//reeeaeeeeee gov/reesearch/census 1940. We predict the time that the respondent worked during the previous year (the WKSWORK1 field, measured in number of weeks), based on the following input fields: the gender (SEX), the age (AGE), the marital status (MARST), the number of children ever born to each woman (CHBORN), the school attendance (SCHOOL), the employment status (EMPSTAT), the primary occupation (OCC), and the type of industry in which the person performed an occupation (IND). We only 50,582,693 examples with non-zero WKSWORK1 field, and randomly partition the dataset into 80%/20% train/test splits. For each evaluation configuration, dataset is also partitioned with a different random seed.
report the mean and std over 10 random runs. In each run, the
Our deep neural network consists of a feature extraction module and 3 fully connected layers. The feature extraction module can be described via the following pseudocode, where the vocabulary size chosen according to the value range of each field in the 1940 US Census documentation, and the embedding dimension for all categorical features are fixed at 8
Features = Concat
1),
AGE 30.0. 0,
Embedding(vocaa_sizee-))) (MARTT 1),
[mmeeddigg(voabbsszzee11101100 - 1),
Embedding hwwpr//oooobbbbbeeeee(MMM.
26

---

Embeedingg(vocab_size-- mmbeedding(vocab_sszee--ee
})
The features vectors are mapped to the output via fully connected layers with the output dimension 128, 64, and 1. The ReLU activation is applied after each fully connected layer, except for the output layer.
We train the model by minimizing the MSE with L2 regularization 10-4, using the RMSProp opti- mizer. We use learning rate 0.001 with cosine decay (Loshchilov Hutter, 2017), batch size 8192, and train for 200 epochs. For the RR-on-Bine mechanism, we use the recommended E v /2//nn in Theorem 7 to query a private prior, and with the remaining privacy budget, optimize the mean squared loss via dynamic programming.
E.3 APP ADS CONVERSION COUNT PREDICTION
The app install ads prediction dataset is collected from commercial mobile app store. The examples in this dataset are ad clicks, and each label counts post-click events (aka conversions) happening in the app after the user installs the app.
The neural network models used here is similar to the models used in other experiments: embedding layers are used map categorical input attributes to dense feature vectors, and then the concatenated feature vectors are passed through several fully connected layers to generate the prediction. We use the Adam optimizer (Kingma & Ba, 2015) and the Poisson regression loss (Cameron & Trivedi, 2013) for training. For the RR-on-Bim mechanism, we use the recommended E1 = V/>'// /n in Theorem 7 to query private prior, and with the remaining privacy budget, optimize the mean squared error via dynamic programming. Following the convention in event count prediction in ads prediction problems, we train the loss with the Poisson log loss. We report the relative Poisson log loss on the test set with respect to the non- non-private baseline.
F LABEL CLIPPING
The Laplace mechanism and staircase mechanism we compared in this paper could both push the randomized labels out of the original label value ranges. This issue is especially severe for small e's, as the range of randomized labels could be orders of magnitude wider than the original label value range. Since the original label value range is known (required for deciding the noise scale of each DP mechanism), we could post process the randomized labels by clipping to this range.
We compare the effects of clipping for both Laplace mechanism and staircase mechanism the Criteo dataset Figure 6. In both case, this simple mitigation helps reduce the error significantly. especially for smaller epsilons. So in all the experiments of this paper, we always apply clipping to the randomized labels.
Figure 6 also shows the exponential mechanism (McSherry & Talwar, 2007), which is equivalent to restricting the Laplace noises to the values that would not push the randomized labels out of the original value range. In our case, we implement via rejection sampling on the standard Laplace mechanism. This algorithm avoid the boundary artifacts of clipping, but to guarantee the same level of privacy, the noise needs scale with 2/e, instead of 1/2 as in the vanilla Laplace mechanism. As result, while it could be helpful in the low epsilon regime, in moderate to high regime, it is noticeably worse than all other methods, including the vanilla Laplace mechanism due to the 2x noise scaling with I/e.
G COMPARISON WITH RRWithPrior
In this paper, we extended the formulation of Ghazi al. (2021a) from classification to regres- sion losses. Here we provide a brief comparison between our algorithm (RR-on-Bins) and the RRWithPrior algorithm from Ghazi et al. (2021a) the US Census dataset. Instead of using multi- stage training, we fit RRWi thPrior in our obbluio-olliviuus label DP framework, and use the same privately queried global prior the input to both RR-on-Bins and RRWi thPrior. For RRWi thPrior,
27

---

10a
10
10a
10a
50K
30K
Lap lace tw/o cipl
mean squared error
40K
25K
Stairrase
Experential
30K
15K
20K
10K
0.050.1
0.050.1
0.8
epsilon
epsilon
(a) Mechanism
(b) Generalization
Figure 6: MSE on the Criteo dataset, with or without postprocess clipping. (a) measures the error introduced by each DP randomization mechanism on the training labels. (b) measures the test error of the models trained on the corresponding private labels.
MSE (Mechanism)
MSE (Generalization)
Privacy Budget
RRWi thPrior
RR-on-Bins
RRWi thPrior
RR-on-Bins
0.5
274.11
179.88
273.97
183.28
1.0
274.11
159.49
273.97
172.64
2.0
274.11
107.89
273.97
152.03
4.0
138.00
36.43
145.89
136.59
8.0
11.58
2.54
134.26
134.35
0C
0..0
01.00
134.27
134.27
Table MSE the US Census dataset, comparing RR-on-Bins with RRWithPrior. The first block (Mechanism) measures the eиrоr introduced by the DP randomization mechanisms on the training labels. The second block (Generalization) measures the test error the models trained on the corresponding private labels. Note RRWi thPrior was designed for classification loss (Ghazi et al., 2021a), here we just ignore the numerical similarity metric and treat each integer label separate category.
we simply treat each of the integer label values in US Census as an independent category during the randomization stage. Once the private labels are obtained, the training stage is identical for both algorithms. The results are shown in Table 2. Note the results are for reference purposes, as this is a fair comparison. Because RRWi thPrior was designed for classification problems (Ghazi al., 2021a), which ignore the similarity metrics between different labels, while RR-on-Binn takes that into account.
28


Reviews:
[{"review_id": "tGBrpuz-jQ2", "reviewer": "Reviewer_deEc", "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": "", "summary_of_the_paper": "This paper studies the regression task with label differential privacy. It proposes a label flipping mechanism with the guarantee of $(\\varepsilon, \\delta)$-label DP and further proves that it is the optimal label-DP mechanism which achieves the minimum expected loss between the original label and the flipped label. Finally it evaluates the proposed label DP mechanism and classical Laplace Mechanism on three different datasets. The result shows the efficacy of the proposed mechanism.", "summary_of_the_review": "Given that the algorithm is novel and proved to be optimal in a general setting, I give the score of 8.", "strength_and_weaknesses": "**Strength**\n1. The writing of this paper is very clear.\n2. This paper proposes a novel label-DP algorithm and proves its optimality w.r.t. the expected loss between the original label and the flipped labels.\n3. The experiments are conducted on the real world datasets and the results are convincible.\n\n**Weaknesses**\n1. As stated, the proposed label-DP mechanism is optimal w.r.t. the first term in the RHS of Equation (1). However, the mechanism will also influence the minimum of the second term, which is the bayes optimal error to predict $\\hat{y}$ from $x$. Think of this simplified setting: when $y$ is deterministic given $x$, the bayes optimal error is equivalent to the variance of $\\hat{y}$ condition on $y$. By considering this additional variance, it is potential to come up with a better label-DP mechanism w.r.t. the entire RHS of Equation (1).\n2. Is it possible that the number of optimal bins is smaller than the number of different labels?", "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": "jzewTLFC6x", "reviewer": "Reviewer_dKhp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "summary_of_the_paper": "Paper proposes regression with label differential privacy and introduces randomized response on bins as a new mechanism to induce differential privacy on labels.", "summary_of_the_review": "paper is easy to follow and has the potential for a net positive impact.", "strength_and_weaknesses": "Proposed method is interesting and of practical use where one might want label differential privacy. Empirical evaluation shows that the proposed method performs better than other common DP methods such as Laplace, Exponential, and staircase. \n\nPaper is clearly written and is easy to follow. Assuming the proofs go through (I did not check them in detail), I think the paper will make positive contribution to the DP community. My only question is that there should be some discussion on why it is not compared against other label-DP methods such as [1].\n\n[1] Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., & Zhang, C. (2021). Deep learning with label differential privacy. Advances in Neural Information Processing Systems, 34, 27131-27145.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": {}}, {"review_id": "jVxHQ8rDi6", "reviewer": "Reviewer_hzx9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This paper provides an optimal label randomization mechanism that ensures local differential privacy given the prior distribution of labels. For a known loss function, the proposed mechanism is optimal. If the prior is unknown, this paper proposes to use the private histogram to estimate the prior. In this case, the gap between the proposed method and the optimal mechanism is proved to be O(\\sqrt{|Y|/n}), where $|Y|$ is the cardinality of the label domain. Compared to prior work Ghazi et al. (2021a), the proposed mechanism works for general regression losses. This paper also empirically compares the label loss of the proposed method with some baselines on real data. ", "summary_of_the_review": "This paper provides an optimal mechanism for privatizing the labels that minimize the loss between noisy labels and true labels. The proposed method is a strict generalization of 0/1 loss appeared in Ghazi et al. (2021a). Theoretically, this paper shows the optimality of the proposed mechanism. Empirically, the authors demonstrate the effectiveness through extensive experiments.", "strength_and_weaknesses": "Strengths: 1. This paper is clearly written. Also, it provides extensive experiments on real data.\n\nLimitations: 1. In the practical setting, the label party is typically able to see the public feature data.\n2. In practice,  the overall generalization error is usually more concerning. I was wondering if there is any way to also consider the second term in Eq. (1) like in Ghazi et al. (2021a)?\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bysoHy-Iy8", "reviewer": "Reviewer_Qh4U", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The authors study the task of training regression models with the guarantee of label differential privacy (DP). Based on a global prior distribution on label values, which could be obtained privately, they derive a label DP randomization mechanism that is optimal under a given regression loss function.", "summary_of_the_review": "It is an interesting problem. \n\nThere are some typos, authors should read the draft once more before submission.", "strength_and_weaknesses": "Strength: The authors try to extend the method and results of labeled DP solving classification problem to regression. The problem is good.\nWeaknesses: They map the response (maybe in a continuous region (interval)) to finite possible values. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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:

Decision: Accept: poster