Optimal Unbiased Randomizers for Regression with Label Differential Privacy
Authors: Ashwinkumar Badanidiyuru
Badih Ghazi
Pritish Kamath
Ravi Kumar
Ethan Jacob Leeman
Pasin Manurangsi
Avinash V Varadarajan
Chiyuan Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: label differential privacy
TL;DR: We give improved algorithms for training regression models with label differential privacy.

Abstract: We propose a new family of label randomizers for  training _regression_ models under the constraint of label differential privacy (DP). In particular, we leverage the trade-offs between bias and variance to construct better label randomizers depending on a privately estimated prior distribution over the labels. We demonstrate that these randomizers achieve state-of-the-art privacy-utility trade-offs on several datasets, highlighting the importance of reducing bias when training neural networks with label DP. We also provide theoretical results shedding light on the structural properties of the optimal unbiased randomizers.

Optimal Unbiased Randomizers for Regression with Label Differential Privacy
Ashwinkumar Badanidiyuru
Badih Ghazi Google Research
Pritish Kamath
Ravi Kumar
Google Mountain View,
Google Research
Google Research
Mountain View, CA
Mountain View,
Mountain View. CA
Ethan Leeman
Pasin Manurangsi
Avinash V Varadarajan
Chiyuan Zhang Google Research Mountain View, CA
Google Cambridge, MA
Google Research
Google Mountain View, CA
Bangkok, Thailand
Abstract
We propose new family of label randomizers for training regression models under the constraint of label differential privacy (DP). In particular, we leverage the trade- offs between bias and variance construct better label randomizers depending a privately estimated prior distribution over the labels. We demonstrate that these randomizers achieve state-of-the-art privacy-utility trade-offs on several datasets, highlighting the importance of reducing bias when training neural networks with label DP. We also provide theoretical results shedding light on the structural properties of the optimal unbiased randomizers.
Introduction
Differential privacy (DP) [DMNS06] has gained significant importance in recent years as a mathemat- ically sound metric for rigorously quantifying the potential disclosure of personal user information through ML models [ACG-16, 16, RE19, TM20J. DP guarantees that the model generated by the training process remains statistically indistinguishable, even if the data contributed by any individual user to the training dataset is modified arbitrarily.
In certain scenarios, the training features of specific example are already accessible to potential adversaries, while only the training label is considered sensitive. For instance, within the context of digital advertising, it is typical to train conversion models that aim to prediet whether user, who interacts with an advertisement on a publisher's ' website, will ultimately make a purchase of the advertised item the advertiser's 's website. The conversion label, which indicates whether the user completed the purchase or not, is not initially known to the publisher website and is considered sensitive information that spans multiple websites.' This particular setting, referred label DP, was initially studied in the work [CH11]. Subsequently, has garnered attention in various recent works, such [GGK+32 21, MEMP+ 21, EMSV22J
For regression objectives (such as the squared loss and the Poisson log loss), the state-of-the-art given by the prior work of [GKK+2]] +33. Their algorithm works in the so-called features-oblivious setting (Figure 1), which consists of a features party that has access to all the features, and a labels party that has access all the labels. The labels party applies mechanism that is DP with respect to the labels in order to produce the message M (-) that it sends to the features party, who then uses the
'Given the announcement of various web browsers and mobile platforms regarding the deprecation of third-party cookies, which were previously employed to track user behavior across different websites, the need for training models that protect the privacy of labels has become inereasingly important. Fas well as in proposals for industry-wide web and mobile standards [Har23].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

M(yI.... Uw) 6-DP
Labels Party (y....., yn
Features Party
Trained e-LabelDP model
(21,..., Fnf
Figure I: Feature-obliviour label DP model training studied in
features along with the incoming message order to train the model (which as a consequence would also satisfy label DP). It proceeds by using part of the privacy budget in order to estimate prior over the labels, and then constructs a randomizer optimizing the "noisy label loss" (see Definition 4) with respect to this prior.
In this work, we introduce novel mechanism with bias- bias-limiting constraints, motivated by the theory of bias-variance trade-offs. We show that while these constraints lead to significantly higher noisy label loss, the models trained on the privatized labels performs surprisingly well, achieving the state-of-the-art utility-privacy trade-off on multiple real world datasets.
provides some background definitions related to (label-)DP and learning. In Section 3, we present the new label DP randomizers obtained by imposing unbiasedness constraints. Section 4 provides an experimental evaluation demonstrating that our method achieves state-of-the-art privacy-utility trade-offss across multiple datasets. We provide some related work in Section 5. We conclude with some future directions in Section 6. All missing proofs along with additional related work, as well as details on the experimental evaluation are provided in the Appendix.
Organization. Section 2
2 Preliminaries
Let D be an unknown distribution on X' x V. We consider the regression setting where y C R; let P denote the marginal distribution of D on V. In supervised learning, we have set {(x y) of examples drawn from D. The goal is to learn a predictor fo to minimize the expected loss LD(ff) == ((,D)> (z), y), for some loss function & R loss functions used in regression tasks are the Poisson log loss P (ū. v y log(ū) and the squared loss keg (ū. y) := ( y)².
TR. Some commonly-use -used
We recall the definition of DP; for more background, see the book of Dwork and Roth [DR14].
Definition (DP: [DMNS06]). Let e R>0- randomized algorithm AA is said to be e-differentially private (denoted e-DP) if for any two "adjacent" input datasets X and X', and any measurable subset S of outputs of AA, it holds that Pr[A(X) E S] S e Pr[A(X') E S].
In the context of supervised learning, an algorithm produces a model as its output, while the labeled training set serves as the input. Two inputs are considered "adjacent" if they differ on a single training example. This concept of adjacency is intended safeguard both the features and the label of any individual example. However, in certain scenarios, protecting the features may either be unnecessary or infeasible, and the focus is solely on protecting the labels. This leads to the following definition:
Definition (Label DP; [CHI IJ). A randomized training algorithm AA is said to be e-label differen- tially private (denoted e-LabelDP) if it is s-DP when two input datasets are "adjacent" if they differ on the label of a single training example.
We recall the notion of feature-oblivious label DP (GKK++33). In this scenario, there are two parties: the features party and the labels party. The features party has the sequence (x.) of all feature vectors across the n users: the labels party has the sequence (w:)²= of the corresponding labels. The labels party sends single (possibly randomized) message M (w yn to the features party.
Based on its input and the received message, the features party generates an ML model as its output.
Definition& 3 (Feaviue-Obliviouss Label DP [GKK+ In the above scenario, the output of the features party satisfies feature-oblivious e-LabelDP if the message M (y),..., yn) eDDP where two inputs are considered "adjacent" if they differ on single ys-

---

3 Label-DP Randomizers
A standard recipe for learning with label DP is to: (i) compute noisy labels using local DP randomizer M and (ii) use a learning algorithm on the dataset with noisy labels. Many of the baseline algorithms that we consider follow this recipe, through different ways of generating noisy labels, such as, (a) (continuous/discret)) Laplace mechanism, (b) (continoous/tiscrete)) staircase mechanism, etc. (see Appendix F for formal definitions). Prior work by [GKK 23] argues that intuitively such a learning algorithm will be most effective when the noisy label "mostly agrees" with the true label. This was formalized in the goal of minimizing the noisy label loss, which is the expected loss between the true label and the noisy label, for the true label drawn from a prior distribution, for some loss function l.
Definition& 4 (Noisy label loss). For a loss function g R y + R. the noisy label loss of randomizer M with respect to prior P is ((M;P) == RyyPP M(y) I v), where ý is the noisy label generated by .M on input y.
This was motivated by the triangle inequality [GKK BIKKK*2,, 23, Eq. (1)). namely,
E
((f(()).)) S
E g~p g~M((v)
(().v)
+
{(fo(z).)).
(I)
(z,g)=/
(a.N) g~M(s)
The work of [GKK+23] focused on optimizing noisy label loss: they showed that the optimal randomizer takes the form of "Randomized-Resse Responss on Bins" (see Appendix F for more details). However, if we notice carefully, the noisy label loss does not depend on the number of examples, so the RHS of (1) does not go to zero as the number of examples goes to infinity, even though we would like the excess population loss of the learnt predictor to asymptotically go to zero. In this paper, we provide an alternative insight into the goal of minimizing the noisy label loss.
For any distribution D over X' y, and any label randomizer M mapping y to 5 C R. let PM be the distribution over X' x E sampled as (ar, M(y)) for (a. y) ~ D. The Bayes optimal predictor for any distribution D over A' x ) w.r.t loss f, is predictor fō X' -> R that minimizes LD (f), which roughly corresponds to the best predictor we could hope to learn with unbounded number of samples from D. We show that, when training with loss from a broad family that includes lug and Eooi the Bayes optimal predictor is preserved after applying the label randomizer iff B[M(y)) = y holds for all E y' (i.e., the randomizer is unbiased).
Theorem 5. Suppose E is a loss function such that for all distributions P over y, the minimizer gx == minges Eywp Ei. y) exists and is given Uz = Ey--lyl (y). Then the following are equivalent:
E[M(y)] y holds for all y E Y,
For all distributions D over X x y, it holds that f = fōn.
The main observation is that (z()) = Ely x = vo] with probability 1 over Fr. and similarly. Ji (ra) E(M(y) I x rol with probability 1 over To. We defer the full proof to Appendix A, but for now we demonstrate a simple example where a predictor learned using noisy labels produced by the optimal RR-on-Bins randomizer can in fact be sub- optimal. Let X' = {a, b) and y = {0, 1, and the distribution D be defined in Table 1. The Bayes optimal predictor for D w.r.t. laq (or even Pri) is given as (a) = 0.4 and (b) = 0.7. On the other hand, the optimal M = RR-on-Bins" randomizer for = 0.5 (see Appendix F for notation), corresponds to the map (0) x 0.396 and ((1) = 2(2) x 0.720. The Bayes optimal predictor for DMM is given fö (a) 0.542 and Jb (b) 0.558. The squared loss of these predictors are given as CD(ftt) 2.625 and Lo(fō = 2.726, the latter being sub-optimal. Thus, preserving the Bayes optimal predictor is desirable property of a label randomizer, as any learning algorithm that converges to the optimal predictor can also be trained on the noisy labels and will approach the predictor for the original distribution.
0
1
2
a
0.35
0.1
0.05
b
0.25
0.15
0.1
Table I: Example D
Additionally, we can relate the property [[[(()]] = y to the unbiasedness of the gradients obtained in SGD. First, we observe that the gradient with respect to the parameters for loq and EP are affine in y. namely,
Volay = (fo(x) v) Vofa(z),
(olp)(f(()) (1 v/fa(z)) Vofo(z).
3

---

Thus, the error in the gradient estimate when using the noisy label ÿ instead of y is given as Volsg(fo(z). 0) Voleg(fo(z). (y 9) Vefo(z),
vefo(n) Volrei(fo(z).)) Vofrra(fo(x).))) = (v ú) fa(a)
Let S = ((x1111),......................, vi),..., (ro= yb0} be mini-batch of examples and let $ {(0 01), (ro, 96) be the mini-batch with noisy labels as returned by the randomizer M. Also consider the dataset with expected noisy labels $ = { ji),....
. (Tb, ]b)). where y; Eg-MMyy V, The difference between a mini-batch gradient w.r.t. noisy labels and the gradient of the population loss decomposes for leq as follows (similar decomposition holds for P
VoLg(fe) Volo(fe)
VVos(So) - VoLo(Jo) + VoLg(Jo) VoCs(()) + VoLg(Jo) - VoLg(J))
(2)
VoLs(fo) VoLD(Jo) +
E (y Eÿ) Vafa(o) + (a.))es
E (E 1) Vofo(a) (a.l)e
(a)
(6)
The term (a) is the difference between the mini-batch gradient and the population gradient, the inherent stochasticity in mini-batch SGD, which has zero bias. The terms (b) and (c) form precisely the bias-variance decomposition for the additional stochasticity in the gradient introduced by the label noise, with the term (c) having zero bias. In the case of stochastic convex optimization, is well known that with access to biased gradients, it is impossible to achieve vanishingly small excess loss; whereas, with access to gradients with zero bias and any finite variance, it possible to achieve an arbitrarily small excess loss using sufficient number of steps of stochastic gradient descent (see Appendix D for more details). Motivated by this reasoning, our approach is to use a randomizer that has the smallest variance possible while ensuring zero bias, namely the term (b) is zero
3.1 Computing Optimal Unbiased Randomizers
We consider a label randomizer that minimizes the noisy label loss, while being unbiased. Namely, we say that an a-DP randomizer M that maps the label set y C R to R is unbiased if it satisfies Eg-M(g) y = y for all input labels y E y. We use a linear programming (LP) based algorithm (Algorithm 1) to compute unbiased randomizer that minimizes the noisy label loss. In order to keep this approach computationally tractable we require that both Y and y are finite; shortly, is possible to handle general y by discretization using randomized rounding, and moreover the excess noisy label loss due to consideration
discuss
discrete Y can be bounded as well. Even though Algorithm is general, we will only consider g Lag henceforth (irrespective of the training loss E).
Algorithm 1 Computt@@ptuubbisseRanaa
Parameters:
Privacy parameter 2 0.
Input: P = (PP)yeyy prior over input labels V.
== (Mi) finite sequence of potential output labels. Output: An cDD label randomizer.
Solve the following LP variables M (MMgio)uez
EveyPy (EVED My-s albr:1)). subject to
min M
[Non-negativity]
Vy E vv i IEI:
My-s 2 0 EiEz My-r
[Normalization]
Wy EY:
[e-LabelDP]
Vi E I, Vy, o E E s.t. マデン:
Mi e -M
[Unbiasedness]
Vy yy:
Eier My-si Dj
return Label randomizer M mapping y to 5 given by Pr(M(H) Dz] My
In Figure 2, we illustrate a prior P over y = 1,2]. using the example in Table 1, and the corresponding unbiased randomizer returned by Compute@pptimiiseeRanddd.oo. (P)))) for certain

---

oUtDUc 233071000000
0.
prussalaty mas
mane
0.3
0.16
62-
0.1
0.00
(a)
(b)
nnus label
Input lobel
Figure 2: (a) An example prior P over y {0, 1, (b) The optimal unbiased randomizer returned
by
using fine grid for V, indicated by the probability mass
function for each input label.
fine- ine-grained choice of D It is worth noting that this randomizer is quite unlike "randomized response" or any additive noise mechanism! Additionally, the output labels are all outside [0, 2]. which is the convex hull V. We have observed the same in our experiments Section as well. One may find it surprising that these "out of domain" noisy labels in fact yield better trained models! This could be attributed to the Bayes optimal predictor for this randomizer being precisely fp. since E Myy] for all y y (Theorem 5).
There are however couple of challenges be addressed. First, it is unclear if the optimal unbiased randomizer has only finitely many labels, and even if so, what is the number of distinct output labels. Secondly, one needs to fix the choice of y before hand, and it is unclear how one can choose it in way that the I.P is feasible and moreover, the solution close to the optimal unbiased randomizer. We address these challenges as follows.
Structure optimal unbiased randomizers. Addressing the first challenge, we show that there is an optimal unbiased randomizer that has a small number of distinct output labels.
Theorem 6. For any convex loss all distributions P over I with finite support, and s > 0, there exists an s-DP unbiased randomizer M, infe-DP unbiased M (M;P) with most 2/y| output labels.
The main ideas in the proof are as follows: we use the convexity of g to show that an optimal D-D unbiased randomizer M must be of certain form; if not we can use Jensen's 's inequality to construct another randomizer M' with that form such that (MM'; P) S GMM; P). In particular, we show that the randomizer must be a staircase mechanism as defined in [KOV16] 16,, mechanism that maximally satisfies the DP constraints. This already implies that the number of output labels is at most 2 203,, We use the ordering of the labels, along with similar reductions using convexity of g. to show that the optimal e-DP unbiased randomizer further lies within a special subset of staircase mechanisms with 2| output labels. The detailed proof is provided in Appendix B.
Choosing D to ensure feasibility and good coverage. To address the second challenge, we use a finite set of output labels. We show upper bound on the excess noisy label loss due to discretization.
We use a heuristic (Algorithm 2) for setting ) to be a grid, in a way that ensures that the LP in Algorithm has feasible solution while keeping 5 small enough to be able to efficiently solve the LP. To compute the endpoints of the grid, we use an unbiased randomizer with a finite and bounded support: the eDD debiased randomized response (s-dbRR) on the set of labels, which operates by mapping the inputs to a unique set of values such that under randomized response the randomizer unbiased (see Appendix FF for definition). We choose the endpoints of our grid to be precisely the minimum and maximum among the possible outputs E-dbRR (see Algorithm for details). With those two endpoints defined, create the grid by evenly spacing output labels along this interval. The number of output labels we generate is as large as possible while maintaining that the LP solver terminates in reasonable amount of time. We show that having these endpoints suffices to ensure feasibility the LP in Algorithm 1.
Proposition 7. I contains just the smallest and largest values among the oulputs of s-dRRR, the LP in Compurt@@ttUbbiseeRRandd (P,)) is feasible.
5

---

Algorithm 2 FeasibleOutputSet,
Parameters: Privacy parameter 2 O.
Input: Set of input labels V. Positive integer 2 representing size of output [)]- Output: Set of output values Y that guarantee feasibility of LP in Algorithm 1.
L + |-] - 1) min()/) EyEr /(=--1) -
U <- (ef + |3]| 1) max())) (axx)))-xpe) Eper /(6f -1)
A + (U- Ln/(nnnn -
return y (1,L+
We defer the proof to Appendix F; the main idea is that these endpoints create an interval that contains the interval one would obtain from the debiased randomized response on the two label set of the minimum label and maximum label. Because the V we choose has labels less than this minimum and larger than this maximum, all labels in between be generated by interpolation.
Additionally, we show that using the randomizer optimized on the grid 5i gives bounded excess noisy label loss compared to optimizing over a continuous set of labels for Lipschitz loss functions.
Lemma 8. Let M be the optimal unbiased randomizer with y = [I.U], and let Ma be the optimal unbiased randomizer with y {L, A G(Ma:P) - G(M; KA.
A, U. If ((. v) is K K-Lipschitz in g, then
In the case of ( y) (Ú - 2 we have (U L). Therefore, as the grid gets finer, the excess noisy label loss of MA obtained from over the noisy label loss of M scales linearly in the discretization parameter A. We present the proof in Appendix
For large values, we experimentally observe that the optimal unbiased randomizer appears to approach c-dbRR. For small values, we also experimentally observe that the optimal unbiased randomizer appears to be supported on the labels of the debiased randomized response on the two label set of the minimum label and the maximum label. This justifies our choice of endpoints for grid.
Splitting budget between prior and label. So far, we have assumed a known prior P over input labels V. However, this is typically not the case, and so we use the standard Laplace mechanism to privately estimate the prior. Given n samples drawn from P. MMap constructs histogram over y and adds Laplace noise with scale 2/s to each entry, followed by clipping (to non-negative) and normal-
Algorithm 3 Labe@Randomizerr..cr
Privacy parameters E1 2 0. Input: Labels yı, ......... Un V...
Parameters:
Output: Ú1...., ... E V
P' - MLrP (yn...., yn)
D FeasibleOutputtet,, (2)
ensure that entries ization. For completeness, we include a formal description of M! in Appendix C.
M < ComputeOOtUnniasedRRnn,, (P',
for ė [n] do
0 t M(}. return (Ú1....,
Our randomizer for the unknown prior case, de- scribed in Algorithm 3, thus operates by splitting privacy budget into E E2, using MLap to get an approximate prior distribution P', and using (P', to randomize the labels. It follows
the randomizer returned by ComputeOptUnbiasedeee that the entire algorithm is (81 + DD..
Handling continuous y. While focused the of finite sets V, the approach be extended to the case where ) is continuous set, say y = [T. U]. In this case, we can first choose finite discrete subset 5 C y' that contains both L and U, e.g., = (L, A, ... U). and then apply unbiased randomized rounding (-) to all labels before applying any mechanism M.
Namely, for any label y E [L, UJ such that y1 < y S y2 for yı, 1/2 being consecutive elements of } Æーール and y2 with probability μー#1 This ensures カ2-31
URR 5 (v) returns drawn as V1 with probability セュ-3リ
that E g y and hence, for any unbiased mechanism M that acts inputs in V, it holds for all

---

0313
Bhra Bis
5000
Lupacs
E550
Cippad Lagaos Noduaisn
Optiaal Uebiaso
030
100
6002
Z000
Randambbrr
120
122
0
32C
306
300
+00 3. 002
300
03 0001
300
3.0
4.00
00
300
200
400 00
021
Oriinal
Figure 3: Illustration of various eDD label randomizers for & = 4. The 2D density plot contours are generated in log scale using Gaussian kernel density estimates. The legends show the MSE between the original labels and the s-DP randomized labels.
y E y that [[M(URRS (v))) = (5)
y. Furthermore, as the gap between consecutive points of y decreases, the variance introduced by URRy also decreases.
4 Experimental Evaluation
We evaluate our randomizer on three datasets, and compare with the Laplace mechanism [DMNS06], the additive staircase mechanism [GV14], and the IR-on-Bins method [GKK*23], The Laplace mechanism and the additive staircase mechanism both have a discrete and a continuous variant. Following [GKK+22] +33,, we use the continuous variants for real-valued labels (the Criteo Sponsored Search Conversion dataset), and the discrete variants for integer-valued labels (the US Census dataset and the App Ads Conversion Count dataset). Note that in the experiments from [GKK+ (OCK+23) 23], the noised labels from both the Laplace mechanism and the additive staircase mechanism were clipped to be in the valid label value range, as for small E's, the magnitude of the noised labels could be orders of magnitudes larger than the original label values, potentially causing numerical instability in model training. However, our study, we found that with more careful hyperparameter tuning and early stopping (see Appendix G). the learning could be stabilized for sufficiently small values (c.g., & 2 0.3) that is practically useful in ML, and in this case, the unclipped (therefore also unbiased) version of both the Laplace and the additive staircase mechanisms outperform their clipped counterpart. For reference, we present the results for both clipped and unclipped variants for those two mechanisms. We note that all of these mechanisms can be implemented in the feature-oblivious label DP setting (Figure 1). More details on model and training configurations are presented in Appendix G.
4.1
Criteo Sponsored Search Conversion
The Critco Sponsored Search Conversion Log Dataset [TY18] is a collection of 15, 995, 634 data points derived from sample of 90-day logs of live traffic from Criteo Predictive Search (CPS). Each example contains information of an user action (e.g., a click on an advertisement) and a subsequent conversion (purchase of the related product) within 30-day attribution window. We use the setup of feature-oblivious label DP to predict the revenue in E (i.e., the SalesAmountIInErr field in the dataset) of a conversion. We apply the following preprocessing steps: filtering out examples with SalesAmount InEuro being- 1, and clipping the labels at the 95th percentile of the value distribution (400C).
In Figure 3, we visualize an example of the various label randomizers. For E = 4, the optimal RR-on-Bins randomizer maps the input values to one of four distinct values. On the other hand, for the optimal unbiased randomizer, the joint distribution of the sensitive labels and randomized labels maintains an overall concentration along the diagonal. The joint distribution for the Laplace mechanism is quite spread out.
In Figure 4, we compare the noisy label loss on the training set and the mean squared error on the test set for all the randomizers considered. For each randomizer, the label randomization and training was run with 10 independent random seeds, and the plots show the average and standard deviation bars. For RR-on-Bine and the optimal unbiased randomizer, we use e 0.017 for privately estimating the prior using MLLa,, and #2 E1 for randomizing the label, following the guidance in Appendix C.
7

---

Lepice
Statean 12
10
307
107
Squred Shee
30020
40020
30000
3000
20000
4020
<psaon
0.5
0.5
0.5
25
459 Ton 0.5
0.5
2.5
1.5
(a) Noisy Label Loss
(b) Test Loss
Figure 4: Comparison of different label DP randomizers on the Criteo Search dataset: (a) shows the mean squared error between the original labels and the privatized labels the training set from each randomizer; (b) shows the mean squared error between the model predictions and the groundtruth labels the test set. The solid line indicates the non-private baseline.
Lapioss
Leplace
Lasace
3W10P
II.
142
Erer
140
138
Mom
134
apsilon
(a) US Census
(b) App Ads
Figure 5: Comparison of different label DP randomizers: (a) shows the mean squared error of the prediction on the US Census test set. The solid line indicates the non non-private baseline. (b) shows the relative Poisson loss (i.e., (I. T,*) with respect to the non-private baseline Poisson loss I
find that the optimal unbiased randomizer (Algorithm 3) achieves smallest test mean squared еrror across a wide range of values. It is interesting to note that the unbiased randomizers (Laplace and additive staircase mechanisms and optimal unbiased randomizer) vastly outperform the biased randomizers (clipped versions of Laplace and additive staircase mechanisms well as the RR-on-Bins) in terms of test loss, even though the noisy label loss is an order magnitude larger for the unbiased randomizers.
4.2 US Census
The 1940 US Census dataset is widely used in the evaluation of data analysis with DP /WDZ+19 CJG21, GKM+21J. This digitally released dataset in 2012 contains 131, 903, 909 examples. We follow the task studied in [GKK+23] and evaluate label DP algorithms by learning to predict the number of weeks each respondent worked during the previous year (the WKSWORK1 field).
In Figure 5a we compare the mean squared error the test set for all the randomizers considered. For each randomizer, the label randomization and training was run with independent random seeds, and the plots show the average and standard deviation bars. For RR-on- -ins and the optimal unbiased randomizer, we use E = 0.002 for privately estimating the prior using Mlap, and E2 = E E1 for randomizing the label, following the guidance in Appendix C. We find that the optimal unbiased randomizer achieves the smallest test mean squared error across a wide range of & values.

---

4.3 App Ads Conversion Count
We also evaluate on conversion count prediction dataset collected from a commercial mobile app store. Each example in this dataset corresponds to an ad click and the task is to predict the number of post-click conversion events in the app after user installs the app within a certain time window.
In Figure 5b we compare the relative Poisson loss on the test set for all the randomizers considered. For each randomizer, the label randomization and training For the optimal unbiased randomizer, Laplace and additive staircase mechanisms, at low E's we experience blowup in the training loss during training. The plot show the average and standard deviation bars, at the time of lowest training loss, right before blowup. We see that for all e's, all of the unbiased randomizers vastly outperform the others, including RR-on-Bins. Among the unbiased randomizers (optimal unbiased randomizer, Laplace and additive staircase mechanisms), the optimal unbiased randomizer performs the best at all e's. One caveat is that for the smaller E's, one can see the standard error increase. We hypothesize this is not an inherent feature of the randomizers but due to the blow up of the model training, reducing the training length and adding additional variance to the error, behavior that seems specific to the AppAds dataset.
run with 6 independent random seeds.
5 Related Work
DP learning has been the subject of considerable research spanning different settings that include empirical risk minimization [CMS11], PAC learning [BLM20], training neural networks [ACG+ 16), online learning [JKT12], and regression [Wan18]. For the label DP setting, [CH11, BNS16] studied the sample complexity of classification, while [WX19] studied sparse linear regression in the local DP model [EGS03, KLN+ 11]. For training deep neural networks with label DP. [GGK 22] studied the classification setting and gave a multi-stage training procedure where the priors on the labels in the previous stage are used to define an LP that is optimized to find the randomization mechanism for the next stage. For the classification loss, they characterized the optimal solution as the so-calll co-called RRTop-k. By contrast, the work of [GKK [23 showed that for regression objectives the optimal solution to the LP is an RR-nn-Bins solution. A crucial insight in our work is that the addition of an unbiasedness constraint to the I.P leads to solutions that (i) are not RR-on-Bins solutions, (ii) can have substantially higher variance than RR-on-Bins, and (iii) nevertheless have a much lower train and test error due to the reduction in bias.
Kairouz et al. [KOV16] defined a family of staircase mechanisms and showed they are optimal among local DP algorithms for minimizing an objective function given a prior. We extend the notion of staircase mechanisms to include real-valued labels that affect the optimization function. The structural properties that we prove (Theorem 6) utilize the ordering of the labels and the unbiasedness condition, which we show is critical for training neural networks for regression with label DP and high accuracy. Moreover, their work shows the presence of staircase mechanisms in the context of optimizing mutual information and Kl.-diveeeeece objectives, whereas we show their presence in the context of regression.
two-party learning setting with one features party and one labels party was recently studied in the work of [1] They focus on the interactive setting, which is arguably less practical than the (non-interactive) feature-oblivious setting studied in [GKK+23] that we also consider.
We also note that the label DP mechanism of [MEMP 211, which builds the PATE framework [PAE+ 17, PSM* + 18], and the works of [EMSV22, TNM 22], which leverage unsupervised and semi-supervised learning algorithms, cannot be implemented in the feature-oblivion DP-SGD algorithm of [ACG* 16), which protects both the features and the label of each training example and which has been applied to different domains including computer vision [DBH+22] and language models [YNB+22 22] also cannot implemented in the feature-oblivious label DP setting. The same is also true for label DP algorithms for logistic regression [GR21] that are based on linear queries (where the features are assumed to be known and non-sensitive, and the lincarity is with respect the labels).
setting. The
Over the past decade, there has been a significant body of research on DP ML (e.g., [CMSII, ZZX 12, SCS13J). In particular, DP regression has been the focus of several prior papers including [ZZX- 12, KST12, Wan18, SÁZLI8, AMS+

---

The label DP setting has also been studied in several papers including [CHI1, BNS16, WX19, GGK 21, MEMP*21 21, YSMN21, EMSV22, BMS22, GKK 23]. The Randomized Response (RR) mechanism [War65], basic form of label DP, was introduced several decades ago and is widely studied/used.
Conclusion
In this work, we show that using unbiased E-DP label randomizers lead to better trained models, and in particular, choosing the label randomizer that minimizes the noisy label squared loss seems to perform the best in terms of test performance, by empirically demonstrating this three datasets. We also provide theoretical results shedding light on the structure of these randomizers, as well as why they might lead to better trained models.
Discussion. While we focused entirely on e-DP ("pure-DP"), for our specific approach, does not seem that relaxing (e, 6)-DP ("approximate-DDP)) will be beneficial. For the first stage of estimating the histogram privately, one could potentially use an approximate-DD mechanism, but we believe that is unlikely change the prior significantly. For the second stage of randomizing labels, it is known that approximate-DD may not be helpful in the local model [BNS18].
In this work, we use hyperparameter tuning to choose the best architecture, which in general has additional privacy costs, and how to tune hyperparameters privately and efficiently is an active research topic [PS22, SSS23J. Consequently. it is common in the private ML literature separate the question private hyperparameter tuning and private training. and focus on comparing the privacy- utility trade-off under optimal hyperparameters, e.g., [MEMP+ 21, HLY + 23, KCS.20 22, DBH 22].
We also follow this convention.
Limitations and future work. While LPs somewhat efficient, it would be desirable to have more efficient algorithm for computing the optimal unbiased randomizer. The RR-on-Binn randomizer introduced in [GKK+22 23] has important advantage that one does need construct the set of potential output labels y before hand, and in fact, there is simple dynamic programming algorithm to compute the optimal randomizer along with the output labels. Moreover, the RR-on-Bins family of randomizers has a clean structure. Understanding more structural properties of the optimal unbiased randomizers, and designing better algorithms for computing them, would be an interesting future direction to pursue.
To further improve the benefit of this optimal prior- based unbiased label randomizer, it might be possible to first partition the input examples into groups of "related examples", purely using the input features and compute the optimal unbiased randomizer for each group, by privately estimating the prior over labels for each group. This could lead to better test performance, as the randomizer can adapt to the different priors across these groups, unlike the "static" label randomizers such as Laplace and additive staircase mechanisms. For example, such an approach was used in the setting image classification using self-supervised learning in [GGK +21]
As shown in (2), there is hias-variance trade-off when it comes choosing label randomizer. While Ai-on-Binss minimizes the noisy label loss (corresponding to the variance), the method in work minimizes the bias (in fact, making it zero), at the cost of greatly increasing the variance. However, it might be possible in some settings that allowing a small amount of bias might greatly reduce the variance, thereby improving performance. This might be especially relevant when is very small. This could be done for example by adding a regularizer to reduce the bias, without enforcing hard unbiased constraints, as currently done Algorithm We leave this investigation future work.
10

---

References
[ACG+16 16]
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. CCS, pages 308-318, 2016.
[AMS*22] 22]
Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression. PETS, 2: 2:184-204, 2022.
[BLM20]
Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In FOCS, 2020.
[BMS22]
Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. Differentially private learning with margin guarantees. In NeurIPS, 2022.
[BNS16]
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. ToC, 12(1):1-61 2016.
[BNS18]
Mark Bun, Jelani Nelson, and Uri Stemmer. Heavy hitters and the structure of local privacy. In PODS. pages 435 045,447,220 2018.
[CH11]
Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In COLT, pages 155-186, 2011.
[CJG21]
Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. Data poisoning attacks to local differential privacy protocols. In USENIX Security, pages 947-964, 2021.
[CMS11]
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. JMLR, 12(3), 2011.
[DBH+22]
Soham De, Leonard Berrada, Jamie Hayes, Samuel L. Smith, and Borja Balle. Un- locking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
[DHSI5]
Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning structured discrete distributions. NIPS, pages 2566-2574, 2015.
[DMNS06]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
[DR14]
Cynthia Dwork and Aaron Roth. The algorithmic foundations differential privacy. Foundations and Trends@ in Theoretical Computer Science, 933-4):211-477 2014.
[EGS03]
Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. PODS, pages 21 1-222, 2003.
[EMSV22] Hossein Esfandiari, Vahab Mirrokni, Umar Syed, and Sergei Vassilvitskii. Label differential privacy via clustering. In AISTATS, pages 7055-7075, 2022.
[GGK+21] Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. NeurIPS, pages 27131-27145, 2021.
[GKK+23] Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan, and Chiyuan Zhang. Regression with label differential privacy. In ICLR. 2023.
[GKM*21] Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. Differ- entially private aggregation in the shuffle model: Almost central accuracy in almost single message. In ICML, pages 3692-3701, 2021.
[GR21]
Alexandre Gilotte and David Rohde. Learning logistic model from aggregated data. AdKDD Workshop, 2021.
[GV14]
Quan Geng and Pramod Viswanath. The optimal mechanism in differential privacy. In ISTT, pages 2371 1 1-2375, 2014.
[Har23]
Charlie Harrison. Consider randomizee-ressoosslliik privacy mechanism, April 2023. github. www.cattgcocoe//o/./c.o indi soddiviiull- /ntd//aaaaaalddtatttaaaa/////aaa
(Haz22]
Elad Hazan. Introduction to Online Convex Optimization. MIT Press, 2022.
[HLY+23]
Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. Exploring the limits of differentially private deep learning with group-wiss wise clipping. In ICLR, 2023.
11

---

[JKT12]
Prateck Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In COLT, pages 24:1-24:34, 2012.
[KCS*2] Alexey Kurakin, Steve Chien, Shuang Song, Roxana Geambasu, Andreas Terzis, and Abhradeep Thakurta. Toward training at imagenet scale with differential privacy. CoRR, abs/2201.123225 2022.
[K] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can learn privately? SIAM J. Comput. 40(3):793-826, 2011.
[KOV16]
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. JMLR, 17:17:1-17:51, 2016.
[KST12]
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In COLT, pages 25.1-25.40, 2012.
[LSY+21] 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.
[MEMP*21] Mani Malek Esmacili, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramer. Antipodes of label differential privacy: PATE and ALIBI. NeurIPS, 34:6934-6945, 2021.
[PAE+17]
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In ICLR, 2017.
[PS22]
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with Rényi differential privacy. ICLR, 2022.
[PSM* 18]
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. ICLR, 2018.
[RE19]
Carey Radebaugh and Ulfar Erlingsson. Introducing TensorFlow Privacy: Learning with Differential Privacy for Training Data, March 2019, blog. tensorflow org.
[SÁZL18]
Michael Thomas Smith, Mauricio A. Alvarez, Max Zwiessele, and Neil Lawrence. Differentially private regression with Gaussian processes. AISTATS, 2018.
[SCS13]
Shuang Song, Kamalika Chaudhuri, and Anand Sarwate. Stochastic gradient descent with differentially private updates. In GlobalSIP, pages 245-248, 2013.
[SSS23]
Tom Sander, Pierre Stock, and Alexandre Sablayrolles. TAN without burn: Scaling laws of DP-SGD. In ICML, pages 29937-29949, 2023.
[TM20]
Davide Testuggine and Ilya Mironov. Py Torch Differential Privacy Series Part 1: DP-SGD Algorithm Explained, August 2020. medium. com.
[TNM+22] Xinyu Tang, Milad Nasr, Saeed Mahloujifar, Virat Shejwalkar, Liwei Song, Amir Houmansadr, and Prateek Mittal. Machine learning with differentially private labels: Mechanisms and frameworks. PETS, 4:332-350, 2022.
[TY18)
Marcelo Tallis and Pranjul Yadav. Reacting to variations in product demand: An application for conversion rate (CR) prediction in sponsored search. In IEFE BigData, pages 1856-1864, 2018
[Wan18]
Yu-X fu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In UAI, pages 93-103, 2018.
[War65]
Stanley L Warner. Randomized response: survey technique for eliminating evasive answer bias. JASA, 60(309):63 69, 1965.
[WDZ+ 19]
Tianhao Wang, Bolin Ding, Jingren Zhou, Cheng Hong, Zhicong Huang, Ninghui Li. and Somesh Jha. Answering multi- calti-dimensionall analytical queries under local differential privacy. In SIGMOD, pages 159-176, 2019.
[WX19]
Di Wang and Jinhui Xu. On sparse linear regression the local differential privacy model. In ICML, pages 6628-6637 2019.
12

---

(YNB*22)
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, al. Differentially private fine-tuning of language models. In ICLR, 2022.
[YSMN21]
Sen Yuan, Milan Shen, llya Mironov, and Anderson Nascimento. Label private deep learning training based on secure multiparty computation and differential privacy. In NeurIPS Workshop Privacy in Machine Learning, 2021.
[ZX 12]
Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winslett. Functional mechanism: regression analysis under differential privacy, VLDB, 13:413344113777 2012.
13

---

A Bayes Optimal Predictor Using Noisy Labels
We prove Theorem 5, restated below for convenience.
Theorem 5. Suppose & is loss function such that for all distributions P over y, the minimizer g. = mingeR Eypp E(G, y) exists and is given as d- = (p)) Then the following are equivalent:
E[M(y)] y holds for all y E y. For all distributions over x y, it holds that f = f.
Proof. If M is unbiased, then Bg) = EEer 2 Pr[M(y) = 5l for all input labels y E y. We have the following equalities (we restrict ourselves to the case of finite y and V, but the proof generalizes easily to measurable sets y and )):
E gmM(ly)
19 x rol
Σ VEY
Pr y, zol Priyy x mol
(x,3)~
Σ VERIEE
Pr(ů v) Pr(y I x = aod
(t.' feature obliviousness)
Σ VEY
Pr(y x = =xool- Σ
Pr ul
BE>
Σ JEY
Pr(yl x = vol.2
(:: unbiasedness)
E g- (>)))))
[y x== sol:
showing that the Bayes optimal predictors equal at all values To-
Conversely, suppose we have a y E y' such that Eg-M(s)) [9] * y'. Then take any distribution D for which there is some To with Pr(y = = mo] = Then clearly Ey--( xo] = y/-
However, E Big-MM)) 1 x zul Eg-Mor + y'. Hence the Bayes optimal predictors differ at To.
B Structural Properties of Optimal Unbiased Randomizers
We prove Theorem 6, restated below for convenience. We use the following assumption about the label loss g. which in particular, is satisfied by laq that primarily use.
Assumption 9. The loss R x R + IR is such that for all it holds that g(و v) is convex in and minimized at ÿ = y for all y.
Theorem 6. For any convex loss g, all distributions P over R. with finite support, and there
exists an c-DP unbiased randomizer My. E inff-DD unbiaved Ar G (M:P) with at most 2 output labels.
We recall the definition of signature matrix from 23). Consider any feasible solution M == (My= of the LP in Algorithm 1. Note that for reasons that will be clear shortly, we do not require the D. values to be distinct, and will assume without loss of generality that 9s S. 9; for all i < E Z. Let yinin min, My-vi and let pmaax = max,, My Note that if M encodes an e-DP randomizer, it holds that p.max < -p.ppp
Definition 10 (Signature matrix). For any s-DP randomizer encoded by M, the corresponding signature matrix entry S (y, i) for all y y and i I is defined
0
if My =
U
if M pmmax e. min
SM(
L
if My-ii pinin e = p max
S
otherwise.
14

---

We show that for any E-DP unbiased randomizer M there exists another e-DP unbiased random- izer M, which satisfies certain nice properties, while increasing the noisy label loss.
Claim 11. Suppose [>] 2 2. For any e-DP unbiased randomizer M mapping to a finite set of output labels, there exists an E- E-DP unbiased randomizer M with output label sequence y = (ūi)ez,
encoded by (My-ssyys such that the following hold:
g(MP; P) 2 G(M; P).
Each column of SM consists of only U's and L's, with at least one and one L.
With row indices in y sorted in increasing order from top bottom, every non-zero column of SM matches the regular expression L'U+L'. For each i I, let 4 11(1) and 22 be the smallest and the largest y respectively for which (y U.
For all < i' it holds that (1( S (1()') and (2((1) - P2(('). with at least one of the inequalities being strict.
Before we prove Claim 11, we prove Theorem 6 using it.
Proof of Theorem 6. If [3]] 1, then it is immediate that the optimal unbiased randomizer simply returns the unique value in y with probability 1. If [>] 2 2, then for any optimal unbiased randomizer ( we can apply Claim 11 to get another optimal unbiased randomizer M that satisfies the stated conditions. Let I&o C I be the subsequence of all outputs for which My * 0 (for all y). The sequence (L) (i), P2())) ordered in increasing order of E I is strictly increasing in the partial order y )r that is, at least one of Φ2 (1) or P2(1) strictly increases from one i to next. It is easy to see that this can happen at most | times, thereby concluding that [Z S 2
To prove Claim 11, we perform several transformations to the given e-DP randomizer ( which is say encoded by (0) (M (My-))a aas for some D = (Di)izz, such that the randomizer obtained in each step satisfies (r) (y) E (((+)) for all y E y and G(M P) 2 ((M(+)))
Combining columns with identical signatures. For convenience let k == Vl. Let by be the k-dimensional binary vector corresponding to the binary representation of for j - 2* 1. A matrix g(k) (1, ( (2x(2* is called Staircase Pattern Matrix [KOV16] if the jth column of ((k) is
s(()) = (e -16, + L, for E {l,...,27 2 2}. For example,
1
e
e
5(3)
1
1
e
1
e
1
Since () is e-DP, we have that each column of M()), namely (M fiyyyy is conic combination of the columns of 5(h).
Claim 12. Let ())) be an s-DP randomizer, mapping y to finite subset )'() of Then there exists an e- e-DP randomizer M() mapping Y to 501 C R encoded by (M (Mg- such that:
S(M@) < (U:
P)) for any convex loss g. ( = [[M (y)lu),
DJ S 2
The vector (M,-r)lees) is positive multiple of a staircase column, with the staircase column being unique for each ÿ 51)).
The proof idea of combining columns of staircase type to potentially decrease loss was shown in [KOV16].
Proof. By EDD constraint, the columns of (0) lie in the cone made by convex combinations the
rays (c,c-ef efIl>il where e 2 0. Because positive multiples of the staircase columns are specifically these rays, except the ray [c)l which already the convex hull, this column of (1 a convex combination of positive multiples of the staircase columns.
15

---

Let Ug be the columns of ( indexed by )Xo) which by the above can be written as:
2 Σ j=1
& 5
0/
Define for each j:
Egero 8 c
C
and
C
DE
Define M() as being supported only at Új with the vector of probabilities being C³ C¹. 5 We now prove M()) has all the desired properties.
(Defines Mechanism):
2
2
Σ
C
(K)
Σ
5 S
- T
$EY0
(Does increase loss): This follows by Jensen's inequality and the linearity of expectation:
24-2 Σ
((M())))
E(s yEY
(5)
( (o((,, (00 ((M
DEY
(Expectation does not change): Because M( is unbiased:
Σ ú 0g = (y)
AEjo
We have
2* -2
Úi C$ -5 = (v)
j=1
showing that M1) is unbiased.
(Bounded by 2 and multiple of unique staircase columns): This is clear by construction. 17
While the finite case is easier to read, the above proof can be done also when the range of M is TR and vg is a vector absolutely continuous probability distributions. The only change is that sums over ÿ E (x(0) become integrals. The projections of Uy onto the staircase columns are continuous maps. Lastly, because a continuous function that is bounded by a function I is itself in I all the integrals become well-defined and finite. Therefore, our theorem regarding the structure of the optimal unbiased c-DP mechanism does not depend on a finiteness condition.
Each row matches the pattern L*U+L". We now use the ordering of the input and output labels as real numbers to make further deductions.
Claim 13, Suppose |}] 2 2. For any sDD randomizer (1)) obtained via Claim 12, there exists an e- c-DP randomizer (2)) mapping y to y c TR encoded by M == (Mg-s))yey.se such that:
((M@); P) < (M P) any convex loss g. ELM@ (v) EIMO) w).
Every now of SM matches the regular expression L*U
Proof. The only way a row of Sy does not match the regular expression L*U+L* is if (i) there is no present, or (ii) if there an L between an two U's. It is easy see that (i) is not possible because Eg My-- = 1 for all y E y, and if one row has no U's, this would imply no row has any U's, which not possible by the uniqueness of the columns if [}]| 2, and we know such an M exists.
16

---

If (ii) is true, then we can construct .M as follows. For any and i1 < 02 < is such that Saon (y. Man (v. 0s) U and S (y. 022 L. consider perturbation (for a small enough
> 0), where we set
M(2)
M y-th (Us y2) --rūr
M22)
y-422 + (V3 y1 y1)"
9-022
M (2) My (y2 y1)m
This choice ensures that ((2) remains an unbiased randomizer. By Jensen's inequality, due to convexity of g, it holds that ((M P) < ((M()) P). We can keep repeating these steps, in addition Claim 12 if necessary, till we arrive M such that each row of S matches the regular expression L*U+L".
Set of U's in any row cannot be subset of the set of U's in another, and are "moving forward
Claim 14. For an e-DP unbiased randomizer (2)) obtained via Claim 13, let T(y) S E be defined as Tςy)= == i0 (y. 0) = U}. Then, all # y', it holds that T(y) o T(y)), and moreover if y y', then min Tgy) min Tyy) and max T (y) max Taxx((r (gy).
Proof. Tt) C T(y",, then it holds that My S Mg M with the inequality being strict for some y. Thus, we have Eg My-+g Eg My- 1, which is contradiction.
Given that both Tyy) and T(y') are contiguous subsets of V, it follows that one of following holds:
min T(y) min T(y') and max T(y) max T(y'),
b min TVy) > min T(y') and max T(y) > max T(y').
However, if < y/, the latter is not possible because in that case, we would have y' = Mije (V') M (v) y. which is contradiction.
Putting together the claims. Finally, we put together Claims 12 to 14 prove Claim 11.
Proof of Claim 1I. Given any c-D unbiased randomizer M, we apply Claims 12 and 13 to obtain the s-DP unbiased randomizer M which satisfies the conditions in Claim 14. Consider the signature matrix SM corresponding to (2)2, with the row indices sorted in increasing order of V.
a column has a signature with an L between two U's, this would contradict Claim 14, since the U's only "move forward".
Additionally, for the signatures of column ý1 < f2, the first U of column و22 cannot come before the first U of column D1. as this would also contradict the claim of the U's moving forward. Similarly, the last U of column ÿi cannot come after the last U column do- Finally, the columns must be unique, since each column is unique staircase matrix vector. Thus, each column of SM matches the regular expression L*U+L*.
C Optimal Unbiased Randomizers with Approximate Prior
We elaborate on the approach of splitting privacy budget for estimating the prior and for generating noisy labels as described Section 3.
To privately estimate the prior, we use the Laplace mechanism. The Laplace distribution with scale parameter b, denoted by Lap(b). is the distribution supported on R whose probability density function 1 exp(-lxl/00 The Laplace mechanism is presented in Algorithm 4.
is 26
It is well-known (c.g.. [DMNS06]) that this mechanism satisfies sDP. It is also well-known that this yields an approximation of the true distribution up to small total variation distance (e.g.. [DHS15)).
In [GKK + 23], it is argued that the best choice of (E1, E2) that minimizes the excess noisy label loss achieved by randomizer computed in Algorithm 3 over the optimal unbiased randomizer computed using the true prior and privacy parameter e, given as E = Vk/n.. (We follow the same budget splitting method in our experiments))
17

---

Algorithm 4 Laplace Mechanism for Estimating Probability Distribution Mlap.
Parameters: Privacy parameter 2 0. Labels yI...., EV.
Input:
Output: A probability distribution pa over
for y E 3 do
hy f- number of i such that y/: h. f- max(hy Lap(2/E), 03
return Distribution P' over y such that p/, = Evcr
D Excess Loss of SGD with Biased Gradient Oracles
Consider a convex objective [(-) over RD,, for which we have a gradient oracle, that given w, returns stochastic estimate g (w) of VL(w). We say that the gradient oracle has bias and variance o² if g(w) = VL(w) + ((w) such that [E((W) < a and E [[((w) - E ((=)] I a² holds for all w. When optimizing over convex set K. C RDD projected GD with step size y is defined as iteratively performing W+++1 +- [w - Tgg[w) (e)) )), where x (-) is the projection onto K. We recall the following guarantee the expected excess loss using standard analysis (see (Haz22]).
Lemma 1S. For a L-Lipschitz loss function, and a gradient oracle with bias and variance o², achieves
projected GD over a K. with diameter with step size rj
Vi(L+a+to3y"
E [ ( ET wi)] L(w*) S
RL VT
2a 1
22 aR.
L
L
In particular, if O. get
E c ( E wi)] - -((w") I
1+ 1 vT
RL
The dependence on the bias is essentially tight, for any first order method. Consider the loss function L(w) foo defined over the domain K. = Rt. However, if the gradient oracle is allowed to have a bias of magnitude a, it is impossible using any first order algorithm to distinguish between the gradients of L and that of L' C'(w) := daw. Note that both and L' are L-Lipschitz
for 2 faa While is minimized w 0, L' is minimized w R. For any w E K., min(C(w) [(0), (w) [R)) 2 aR..
Thus, with access to gradients with bias it is impossible for any first order method to achieve an excess loss that is smaller than M(RR), whereas, with access to gradients with zero bias and variance x², it is possible to achieve an arbitrarily small excess loss using sufficient number of steps of SGD.
E
Noisy Label Loss Bound from Discretization
Here we prove Lemma 8, restated below for convenience.
Lemma 8. Let M be the optimal unbiased randomizer with y U). and let Ma be the optimal unbiased randomizer with y = {L, A.. A, If g(0. y) is K K-Lipschitz in g, then G(MA:P) < G(M:P) KA.
Proof. Given any unbiased mechanism M, we construct mechanism M,, supported on y L LL, A,..., U - A, U) by applying "unbiased randomized rounding" URR to the output of M, My(y) = y (My))).
For any 0 [L.U] U] such that أ $ ÿ returns 8/ drawn as タi with probability
02 for 91 92 being consecutive elements of Dr, URRy. (v) fa= and ÿ2 with probability 9-th 92-91
Observe that
E|URRy, (i)] 9 and JURRy.() Ø1 < A with probability 1.
18

---

Thus, we have that [[M+(v)] = E|URR (M(x) B[M(U)] = and hence Ma is also unbiased. Moreover,
G(MuiP)
E yop 5f My)
(g .))
E
[o(ilvvv]
y-p
g~M(())
o gr~URRgr(0))
(g(0,9) + KW ا1 G)M:
w gr~((v) o 3'~URR3((B)
where the last line follows from K-Lipschitzness g. Since MA is the optimal unbiased randomizer with output labels ) we have that ((Ma: & G(M,) P) - ((M:P) + KA.
F DP Mechanisms Definitions
In this section, we recall the definition of various DP notions that we use throughout the paper. Definition 16 (Global Sensitivity). Let f be function taking input dataset and returning as output vector Rd Then, the global sensitivity A(f) (f) of defined as the maximum, over all pairs (X, X') of adjacent datasets, of (1][()--((() f(X')l1
The (discrete) Laplace distribution with scale parameter > is denoted by DLap(b). Its probability mass function is given by p(y) x exp(-lyl/b) for any y E Z.
Definition 17 (Discrete Laplace Mechanism). Let f be function taking as input dataset X and returning as output a vector in zd The discrete Laplace mechanism applied on imput X returns f(X) + (Yi...., Ya) where each Y; is sampled i.id. from DLap(A(f)/s) The output of the mechanism is s-DP.
Next, recall that the (continuous) Laplace distribution Lap(b) with scale parameter b > 0 has probability density function given by h(y) x exp(-lul/b) for any y E
Definition 18 (Continuous Laplace Mechanism, (DMNS06)). Let f be function taking input dataset X and returning as output a vector in Rdd The continuous Laplace mechanism applied to f
on input X returns f(X) (Yi...., Ya) where each Y, is sampled i.idd from Lap(A(f)/e). The output of the mechanism is s-DP.
We next define the discrete and continuous versions of the staircase mechanism [GV14]. Definition 19 (Discrete Staircase Distribution). Fix A > 2. The discrete staircase distribution is parameterized by an integer I r & A and has probability mass function given by:
((rr)
for 0 < <
e a(r)
for S i < A
(i)
(3)
e kr kA)
for Aλ < < (Is + 1)4 and & e N
pr(-i) for <
where
1 1-1
a(r) =:= 2r 2b(4
r) b)
Let / be a function taking as input dataset and returning as output scalar in The discrete staircase mechanism applied to on input X returns f(X) + where Y is sampled from the discrete staircase distribution given in (3).
Definition 20 (Continuous Staircase Distribution). The continuous staircase distribution parame- terized by y E (0, 1) and has probability density function given by:
a(>) aa(r)
for 7A))
for [yA, A)
hx)
(4)
e ke 1 kD)
for æ E [KA, (k + 1)4) and E
(-x) for < O,
19

---

where
a(7)
Let be function taking input dataset X and returning output scalar in R. The continuous staircase mechanism applied to ʃ on input X returns f(X) - Y where Y is sampled from the continuous staircase distribution given in (4).
Definition 21 (Randomized Response, [War65]). Let ε 2 O, and g be a positive integer. The randomized response mechanism with parameters e and (denoted by RR takes input y {L....,g} and returns 9 ~ Y, where the random variable is distributed as:
for -= y otherwise.
Priý = ū] =
(5)
The output of RRe.g is s-DP
Definition 22 (Randomized Response on Bins, [GKK+23J) Let O, for map + > D RR-on-Bins, is defined as the mechanism that input y samples Y, where the random variable Y is distributed
if (
Pr(y = 5]
otherwise.
Definition 23 (Debiased Randomized Response). For O, the e-debiased randomized response (E-dbRR) operates by performing randomized response on (I(U))yEy. where
( (eee + 11y EvEyy' w)) /(E-
namely, the mechanism on input y samples Ý, where the random variable Y is distributed as if ÿ = (v)
Pr[r =
otherwise.
Finally, we prove Proposition restated below for convenience.
Proposition I contains just the smallest and largest values among the outputs of e-dbRR, the LP in Compuute@ptUubisseRRanddd. (P,Y) feasible.
Proof. Let min()') and = max()). The smallest and largest values among the outputs of e-dbRR are given as
O = (eF + | - 1) 3/0 - EvEyy) /e - 1),
Ú1 = (ef + | - 1) y1 - ΣnEy /6 - 1).
Consider the mechanism M such that for any input E y it holds that
{
80
w.p.
$1 y
M(x)
01 w.p.
8 80
Note M is unbiased, namely [[M(y)] y for all y V. We show
max, Pr[M(y) dul miny Pr[M(y) dol
Pr[M(y0) tol
Pr(M(11) 50]
(er + D/ - 1) 91 EyEy 1-ayy-a (ee 1)yo
(er | - 11) 91 -E 1/ (ee 1)y1
Eytw (v1 y) + (y1 Vo)
< e
Eyto (11 y) (11 yo)
where the last step follows because E mn (v1 - v) 2 0 and for b, c >> 0 it holds that (a + ()/(a+ c) < b/c. Similarly, it holds that max, Pr Pr(M(y) / min, Pr[M(y) タıl < ef
0
20

---

G Additional Details of Experiments
All our experiments were performed using NVidia P100 GPUs.
G.1 Hyperparameter Details
Criteo Sponsored Search Conversion. We use neural network that takes as input concatenation of floating point features, well categorical features using embedding table of dimension four for each. The neural network had two hidden layers of dimensions 64 and 32 respectively. The training was performed on random 80% of the dataset using RMSProp algorithm using the squared loss objective, with learning rate of 10 fz-regularization of 10 batch size of 1, 024 for 50 epochs. The remaining 20% of the dataset was used report the test loss.
This architecture choice was chosen by performing a hyperparameter search over various choices, and this choice seemed to give the best results for all the randomizers considered.
US Census. We use neural network that takes as imput concatenation of floating point features, well as categorical features using embedding table of dimension eight for each. The neural network had two hidden layers dimensions 128 and 64 respectively. The training was performed random 80% of the dataset using RMSProp algorithm using the squared loss objective, with (z-regularization of 10-4, batch size of 8, 192. A varying learning rate in {10-2, 10-3, 10-4 and varying number of epochs in (50, 200) were used, and the best test loss was reported for training with each randomizer. The remaining 20% of the dataset was used to report the test loss.
G.2 Early Stopping
In training on the AppAds dataset, found that the training would often be unstable, with the training loss blowing up after several steps, especially for smaller values of e, which corresponded to faster blow up. We used early stopping, keeping track of intermediate states, to select the best model that minimizes the training loss, and used this to report the test loss.
G.3 Complexity of Computing the Mechanisms
Even though the wall clock time for computing the optimal unbiased randomizer using an LP solver significantly larger than that computing the optimal RR-on-Bins randomizer (for which there is highly efficient dynamic programming algorithm [GKK+23]], this is still orders of magnitude smaller than that of ML model training. We note that while the noisy label loss decreases as in Algorithm 2 is made smaller, this causes the computational cost of solving the LP to increase. This trade-off is demonstrated in the following table, which shows the running time the LP for the unbiased randomizer, the noisy label loss and the final test loss, for different mesh sizes (parameter in Algorithm 2) for ε = 1 on the US Census dataset we study (prediction number of weeks worked in , 52
Computing mechanism wall-clock time (sees)
Mechanism
Mesh size
Noisy label loss
Test loss
RR-on-Bins
n/a
0.154
79.71 1288.21
172.44
Opt. Unbiased
52
2.38
134.44
Opt. Unbiased
416
17.1
1275.22
134.43
Opt. Unbiased
1664
161
1274.71
134.43
The test loss is quite similar for various mesh sizes, even though the noisy label loss does improve slightly with finer discretization. This suggests that the unbiasedness was key to the improvements over RR-on-Bi OR-on-Bins and the discretization of the output set does not hurt performance as much.
The computation time increases considerably when the number of input labels is large, e.g., in the Criteo Search Sponsored Conversion Logs dataset, where there were 401 input labels {O...., 400).
21


Reviews:
[{"review_id": "u0teDL5PT1", "reviewer": "Reviewer_Vhiv", "summary": "This paper proposes a new family of DP label randomizers for regression models. They show that these randomizers improve the MSE of the training set at the expense of the noisy label loss, indicating an alternate bias-variance tradeoff to other similar works. ", "questions": "Overall, I think the paper is well-written and has enough experiments to validate its conjectures. The novelty of the paper is in its theoretical results and improved guarantees.\n\nSome points/comments that could be improved are: \n$\\hat{y}$, the noisy label, is never defined in Section 3? \nThe end of Section 3, particularly the observations for $\\epsilon$ are a bit unwieldy to read -- this would probably be better presented with a table or figure\nWhy is the computational complexity not compared between the unbiased and biased randomizers? This would help understand what tradeoffs of this method are\nIt would be nice to see an analysis of why the method works better on one dataset versus the other\nIn Section 4.3, it is mentioned that for smaller $\\epsilon$’s one can see the standard error increase -- is this only true for these types of algorithms or simpler models as well?\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The strength of this paper is the theoretical and empirical evidence of the randomizer. It is evident that it outperforms the unbiased randomizers by significant margins in the test error, but this comes at the cost of the noisy label loss. ", "weaknesses": "However, it would have been helpful to include what this tradeoff means practically and its implications. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and useful suggestions. We will add the definition of $\\hat{y}$ and incorporate other suggested changes in a future revision. \n\n> Trade-off between noisy label loss and test loss\n\nOur main goal in the paper is to minimize the final test loss. The noisy label is only an intermediate metric of interest. Note that the noisy label loss decomposes as bias and variance. The main observation of this paper is that _reducing the bias, even at the cost of blowing up the variance (by orders of magnitude) is beneficial for the end goal of minimizing the test loss_. This seems to be consistent with our experiments, where for mechanisms without bias (unclipped Laplace & staircase mechanisms, and our optimal unbiased randomizer), we find that reducing the variance corresponds to reducing the test loss as well.\n\n> Computational complexity\n\n(Same response as to Reviewer oAvy) While both the optimal biased and optimal unbiased randomizers can each be written as a solution to an LP, the solution to the former has a special structure that admits a dynamic programming algorithm (RR-on-Bins from prior work).  However, no similar property seems to hold for the solution to the latter; hence explicitly solving the LP is the only available option now. Fortunately, even though solving the LP can be expensive, it is a “one-time” computation in our setting; and the training time typically largely dominates the time taken to solve the LP. In addition, the LP also has a “knob”, namely mesh size, that can be used to tradeoff the LP computation and the utility of the unbiased algorithm.\n\nThe following Table shows the running time of the LP for the unbiased randomizer, the noisy label loss and the final test loss, for different mesh sizes (parameter $n$ in Algorithm 2) for $\\varepsilon = 1$ on the US Census dataset we study (prediction of number of weeks worked in $\\{1, \\ldots, 52\\}$). We note the following:\n* Even though the wall clock time for computing the optimal unbiased randomizer is significantly larger than that of the optimal biased one, this is still orders of magnitude smaller than the ML model training.\n* The test loss is quite similar for various mesh sizes, even though the noisy label loss does improve slightly with finer discretization. This suggests that the unbiasedness was key to the improvements over RR-on-Bins and the discretization of the output set does not affect performance as much.\n\n| **Mechanism** | **Mesh size** | **Computing mechanism wall-clock time** | **Noisy label loss** | **Test loss** |\n|---|---|---|---|---|\n| RR-on-Bins | n/a | 0.154 s | 79.71 | 172.44 |\n| Optimal Unbiased Randomizer | 52 | 2.38 s | 1288.21 | 134.44 |\n| Optimal Unbiased Randomizer | 416 | 17.1 s | 1275.22 | 134.43 |\n| Optimal Unbiased Randomizer | 1664 | 161 s | 1274.71 | 134.43 |\n\n> In Section 4.3, it is mentioned that for smaller $\\varepsilon$’s one can see the standard error increase -- is this only true for these types of algorithms or simpler models as well?\n\nWe conjecture that this might be data dependent (e.g., specific to the AppAds dataset).  Note that the increase in standard error bars is evident even for other unbiased mechanisms such as Laplace and Staircase mechanisms as well.\n"}, {"review_id": "WSoete74GT", "reviewer": "Reviewer_DWLv", "summary": "The paper studies the regression problems under label differential privacy (DP). It proposes a novel randomizer that generates high-quality DP labels which can be used to train a regressor. The proposed randomized mechanism is sound and the experiments on various benchmark datasets and different privacy budgets demonstrated the improvements over the baselines. \n\nOverall I think the contribution of the paper is significant, but the proposed mechanism seems to be limited to the case where the labels are discrete (not continuous). Based on that I recommend a weak accept for this paper. ", "questions": "Can the authors explain more why the proposed mechanism is better than the optimal stair-case mechanism for example if we look at Figure 4.a , especially even when epsilon is large? I used the staircase mechanism before and this turned out to be better than many baseline mechanisms when epsilon is large enough.\n", "limitations": "The paper  discusses clearly the limitations of their proposed mechanism compared to the baselines in the Conclusion section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The contribution is significant and the idea is novel. The paper proposes a novel randomized mechanism that can generate unbiased DP labels which helps to train an unbiased regressor. \n\n2. The paper conducts extensive experiments on different benchmark datasets and different epsilon and shows that a noticeable reduction of mean squared error  when using the proposed mechanism over the previous works. \n\n", "weaknesses": "1. The paper focuses on optimal mechanism for epsilon-DP and this topic is pretty studied in some previous work such as  the stair-case mechanism. It would be great if there is any discussion about extension to (epsilon, delta)-DP. \n\n2. The settings are limited to the discrete (but not continuous) choice of labels which only applies for ordinal regression.\n\n3. The authors did not attach the codes so it might be hard to reproduce the experiments. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoughtful comments and questions. We include below the responses to the questions.\n\n> Comparison of “optimal unbiased randomizers” to the staircase mechanism.\n\nIndeed, the staircase mechanism was introduced as the optimal noise mechanism minimizing the _worst case error_, namely the error for any true value, and moreover the domain of the true value is unbounded, namely all of $\\mathbb{R}$. Our optimization problem is different in that we are optimizing for the _average_ squared loss between the noisy and true labels and we assume that our domain is bounded. Note that the staircase mechanism is usually applied in the central model of DP, where the noise is added to an aggregate value (which can be unbounded, but has bounded sensitivity), whereas, in our setting, we are applying the staircase mechanism in the local model of DP.\n\n> It would be great if there is any discussion about extension to (epsilon, delta)-DP.\n\nFor our specific approach, it does not seem that relaxing to $(\\varepsilon, \\delta)$-DP will be beneficial. For the first stage of estimating the histogram privately, one could potentially use an approximate- DP mechanism, but we believe that is not likely to change the prior significantly. For the second stage of randomizing labels, it is known that approximate-DP may not be helpful in the local model [1]. Thank you for raising this question; we will add a discussion about this in the Conclusions section.\n\n> The settings are limited to the discrete (but not continuous) choice of labels which only applies for ordinal regression.\n\nWe can apply our techniques even to the continuous case by discretizing the domain (such as in the experiments with the Criteo Sponsored Search Conversion Log Dataset, where the `SalesAmountInEuro` field was an arbitrary floating point number). There is indeed some utility loss due to the discretization, but it should not be significant, as it can be upper bounded in terms of Lipschitz constant of the loss and the width of the discretization interval. Moreover, the rounding can be done in a randomized manner that preserves the expectation (e.g., 0.3 rounds to 1 w.p. 0.3 and to 0 w.p. 0.7), so the final noisy label as a result of rounding and applying the randomizer is unbiased. (Please see the Lemmas in response to Reviewer YHYY for a similar argument about discretization of the output labels.)\n\n**References**\\\n[1] Bun, Nelson, Stemmer. Heavy Hitters and the Structure of Local Privacy, PODS 2018."}, {"review_id": "zBVO2wI1QX", "reviewer": "Reviewer_YHYY", "summary": "This paper proposes a differentially private algorithm for regression problems. The algorithm protects the privacy of the labels (\"label DP\"), in contrast to the entire example. The canonical application of this is digital advertising, where the label might be transaction data from a separate website. Furthermore, the algorithm operates in what [GKK+23] term the \"feature-oblivious\" model, where a private algorithm, operating solely on the labels, sends a message to the \"features party,\" who then uses these together to learn a model.\n\n[GKK+23] studied a label randomizer that aims to minimize the difference between the true and noisy labels. This work studies a unbiased randomizers. In addition to experiments, the paper provides some theoretical evidence that unbiased estimators, even if they have high variance, may be superior.\n\nThe private algorithm (which, again, only has access to the labels) proceeds in two steps. First, it uses a private histogram to estimate a prior over the labels. It then solves a linear program, the output of which is our label randomizer. The LP minimizes the expected difference between the true and noisy labels, subject to privacy, unbiasedness, and normalization constraints.\n\nAn important technical question is the randomizer's output space. Let $\\mathcal{Y}\\subseteq \\mathbb{R}$ be the label space and $\\hat{\\mathcal{Y}}\\subseteq \\mathbb{R}$ the set of possible outputs of the randomizer. The solution to the LP has $|\\mathcal{Y}|\\times|\\hat{\\mathcal{Y}}|$ entries, representing a probability distribution over $\\hat{\\mathcal{Y}}$ for each entry in $\\mathcal{Y}$. Thus it is clear that this approach demands both sets be finite (and of modest size, to solve the LP). What is less clear, due to the unbiasedness constraint, is what $\\hat{\\mathcal{Y}}$ should be. Note that if $\\min \\mathcal{Y} =0 $ and $\\hat{\\mathcal{Y}}=\\mathcal{Y}$, then unbiasedness demands we map $0\\to 0$ with probability 1, violating privacy. Thus the endpoints of $\\hat{\\mathcal{Y}}$ must exceed those of $\\mathcal{Y}$. The authors set the endpoints of $\\hat{\\mathcal{Y}}$ so that (provably) the LP is feasible. They \"fill in\" the rest of $\\hat{\\mathcal{Y}}$ with a grid, as finely spaced as their computational constraints allow.\n\nFor a fixed $\\hat{\\mathcal{Y}}$ and prior on $\\mathcal{Y}$, the LP finds the unbiased private randomizer with the lowest expected difference (or loss) in labels. Experiments demonstrate improvements over prior work on three data sets.\n\nI noticed that parts of the submission (introducing the label DP recipe, describing data sets, and reviewing related work) had substantial overlap with text from GKK+23. After discussion with my chair, I have not used this information in my evaluation of the paper.", "questions": "Is there evidence (even informal) that this discretization approach is close to optimal? For instance, can we rule out that the LP's objective is highly sensitive to the choice of endpoints (in the regime considered)?\n\nCan you briefly sketch out what you feel are the key innovations beyond GKK+23?\n\nEstimating the prior requires some privacy budget for each bin. Do you expect that, as $|\\mathcal{Y}|$ grows, another approach will perform better than yours?", "limitations": "The algorithm operates in the feature-oblivious model; other label-DP algorithms might perform better in different settings.\n\nThe algorithm assumes prior knowledge of $\\mathcal{Y}$; it is not always clear where this information comes from.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "Without unbiasedness constraints, GKK+23 find the best randomizer is of a form they call \"RR-on-Bins.\" The authors nicely sum up their core innovation: \"the addition of an unbiasedness constraint to the linear program leads to solutions to the LP that (i) are not RR-on-Bins solutions, (ii) can have substantially higher variance than RR-on-Bins, and (iii) nevertheless have a much lower train and test error due to the reduction in bias.\" This is a clear observation that allows them to move past prior work.\n\nI buy that this is a practical problem, that the feature-oblivious model is useful.\n\nTheir approach does seem to significantly improve on that of GKK+23 on the data sets they tested. Their experimental results are complemented by their formal claims (Theorem 6 and Proposition 7) about the output label space of randomizers.\n\nWith minor exceptions, I found the presentation very clear throughout.", "weaknesses": "In light of the work of GKK+23, this paper has limited novelty. Originality is also a serious weakness: GKK+23 point out that \"our noising mechanism typically introduces a bias; mitigating it, say by adding unbiasedness constraints into the LP, is an interesting direction.\"\n\nThe title says the work finds \"optimal\" unbiased randomizers, but that optimality only holds once the choice of output space is selected. Theorem 6 (there is an optimal unbiased randomizer with at most $2|\\mathcal{Y}|$ labels) and Proposition 7 (selecting endpoints to ensure feasibility) are good steps, but do not get us all the way there. As far as I can tell, it remains possible that some other scheme generates better unbiased randomizers, at least for some priors.\n\nThe paper's focus is on feature-oblivious algorithms, but I would have liked to see a comparison with other label-DP algorithms that solve this problem. How much are we giving up by moving to feature-oblivious?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoughtful comments and questions. We include below the responses to the questions.\n\n> key innovations beyond GKK+23\n\nGKK+23 proposed an optimal (biased) randomizer (RR-on-Bins). While an unbiased mechanism was mentioned as a future direction in GKK+23, it was not clear how to realize this in practice. The key innovations of our paper beyond GKK+23 include a formulation and theoretical justification of an unbiased randomizer, a practical algorithm based on a heuristic discretization approach to the LP, a systematic evaluation with optimal hyperparameters and empirical results that substantially outperform the previous state-of-the-art.\n\n> discretization approach is close to optimal?\n\nThank you for the important question. Firstly, Theorem 6 implies the output set is finite and hence some boundary exists. The way we constructed the heuristic for choosing the boundary points for the output set was by experimenting with various strategies, first ensuring feasibility of the LP, and then expanding it and stopping when we start seeing diminishing returns on the LP objective. We also empirically observe that the final mechanism is supported on values that are away from the boundaries we consider, so it seems likely that expanding the boundaries further does not change the optimal solution.\n\nThe mesh size controls a trade-off between computation time for solving the LP and the value of noisy label loss. We note that it is possible to bound the optimality gap due to discretization in terms of Lipschitz constant of the loss and width of the mesh discretization interval (see Lemmas towards the end of this rebuttal). In practice however, (see the table in response to Reviewer Vhiv), we find that a smaller mesh size is already able to recover good test loss, especially for small $\\varepsilon$ values, even though a finer discretization reduces the noisy label loss by a small amount.\n\nWe leave it to future work for a more principled method to compute the optimal unbiased randomizer. In practice, we find this heuristic to be sufficient for extracting utility out of these unbiased randomizers. We will add more discussion on this in the revision.\n\n> Estimating the prior requires some privacy budget for each bin ... as |Y| grows, another approach will perform better than yours?\n\nNote that, in estimating the prior, the amount of noise added to each bin is sampled from $\\mathrm{Lap}(2/\\varepsilon_1)$, since changing one label can modify the counts for only two bins (reducing one and increasing the other). Thus, we do not need a privacy budget for each bin.\n\n> feature-oblivious algorithms ... comparison with other label-DP algorithms that solve this problem. How much are we giving up by moving to feature-oblivious?\n\nThanks for the suggestion! While there are feature-aware LabelDP algorithms for classification problems, we are not aware of any existing feature-aware LabelDP algorithms for regression problems. In this paper, we focus on feature-oblivious algorithms for simplicity. But we note feature-awareness is an orthogonal component that can be easily added by extending our algorithm to use feature-aware priors instead of a global prior. One natural approach mentioned in the Conclusion section is to cluster the  input features and build separate priors for each cluster. With this extension, the utility of our algorithm could potentially be improved -- but the trade-off between utility gain and implementation complexity will be heavily task and data dependent. We leave a systematic study to the future work.\n\n---\n\n**Lemma:** Let $M$ be the optimal unbiased randomizer with output labels bounded in $[A, B]$. Let $M_d$ be the optimal unbiased mechanism with output labels in $\\{A, A+d, A+2d, …, B-d, B\\}$. Suppose for all input labels $x$, output labels $y \\in [A, B]$ and $c \\in [-d, d]$ such that $y+c \\in [A,B]$ and $|\\ell(x, y) - \\ell(x, y+c)| < C_d$. Then the noisy label loss $\\mathcal{G}(M_d; \\mathcal{P}) \\leq \\mathcal{G}(M; \\mathcal{P}) + C_d$.\n\n_Proof._ From $M$, we construct an unbiased mechanism supported on $\\{A, A+d, A+2d, …, B-d, B\\}$ by a postprocessing step called ‘unbiased rounding’. For an output label $k \\in [A+nd, A+(n+1)d]$, any time we see $k$ as an output of $M$, we instead emit the value $A+nd$ with probability $(k - (A+nd)) / d$, and emit $A+n(d+1)$ with probability $(A+(n+1)d - k) / d$. This post processing step is unbiased, and therefore preserves the mechanism being unbiased. It is clearly supported on $\\{A, A+d, A+2d, …, B-d, B\\}$. Lastly, because $|\\ell(x, y) - \\ell(x, y+c)| < C_d$, unbiased rounding at the output value $k$ increases the noisy label loss at most by $\\Pr(output=k)*C_d$. Summing over all possible output labels $k$, we get $\\mathcal{G}(M_u; \\mathcal{P}) \\leq \\mathcal{G}(M; \\mathcal{P}) + C_d$ where $M_u$ is the mechanism created by performing unbiased rounding on $M$. Since $M_d$ is the optimal mechanism over a set that includes $M_u$, we get $\\mathcal{G}(M_d; \\mathcal{P}) - \\mathcal{G}(M; \\mathcal{P}) < C_d$.\n\n**Lemma:** Suppose $\\ell(x,y)$ is $K$-Lipschitz for $x,y \\in [A, B]$. Then $C_d < Kd$ in the lemma above.\n\n_Proof._ By the $K$-Lipschitzness of $\\ell$, $|\\ell(x, y) - \\ell(x, y+c)| < K|c|$, and $c \\in [-d, d]$, giving the lemma.\n\nNote that for the case of $\\ell(x,y) = \\frac{1}{2} (x-y)^2$, $\\ell$ is $(B-A)$-Lipschitz. These two lemmas taken together show that as $d$ goes to $0$, that is, the mesh gets finer, the noisy label loss of the unbiased mechanism obtained from the LP approaches the optimal noisy label loss, and gives a bound on the excess loss in terms of $d$.\n"}, {"review_id": "ptPGJ6PCuN", "reviewer": "Reviewer_oAvy", "summary": "This paper investigates the bias of the state-of-the-art label-differential privacy (label-DP) mechanism proposed by Ghazi et al. (2023) and proposes bias-corrected randomizers achieved through minimizing of a constrained linear programming approach. The proposed label-DP mechanisms demonstrate lower mean squared errors empirically by carefully tuning the hyperparameters in deep learning.", "questions": "See the weakness part.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The main result of this paper is intriguing and original. The paper provides a compelling example illustrating the bias present in the state-of-the-art label-DP mechanism and proposes a new mechanism to address this bias. Additionally, the authors thoroughly investigate the empirical performance of the proposed algorithm and show that it outperforms the state-of-the-art.\n\n2. This paper is well-written. The authors effectively communicate their contributions and main findings in a clear and concise manner. Furthermore, the organization of the paper is well-structured.", "weaknesses": "1. The proposed algorithm introduces extra computational cost. In order to obtain the unbiased randomizer, a constrained linear programming (LP) problem needs to be solved, which introduces extra computational cost. Although the authors demonstrate the feasibility of the LP, the term \"feasible\" left me uncertain, and it would be more informative to explicitly state the computational complexity involved.\n\n 2. The authors should consider the potential privacy implications of hyperparameter tuning. In the experimental section, they mention the careful tuning of hyperparameters. However, if the validation set used for this tuning procedure is not label DP, there is a risk of privacy leakage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoughtful comments and questions. We include below the responses to the questions.\n\n> Computational cost and “feasibility”\n\nFirstly, we clarify that “a linear program (LP) is feasible” (e.g. in Prop. 7) means that the feasible set, a.k.a. the solution space of the LP is non-empty. This is important to show because otherwise, the method is not guaranteed to return a valid $\\varepsilon$-DP mechanism.\n\n(Same response as to Reviewer Vhiv) While both the optimal biased and optimal unbiased randomizers can each be written as a solution to an LP, the solution to the former has a special structure that admits a dynamic programming algorithm (RR-on-Bins from prior work).  However, no similar property seems to hold for the solution to the latter; hence explicitly solving the LP is the only available option now. Fortunately, even though solving the LP can be expensive, it is a “one-time” computation in our setting; the training time typically largely dominates the time taken to solve the LP. In addition, the LP also has a “knob”, namely mesh size, that can be used to tradeoff the LP computation and the utility of the unbiased algorithm.\n\nThe following Table shows the running time of the LP for the unbiased randomizer, the noisy label loss and the final test loss, for different mesh sizes (parameter $n$ in Algorithm 2) for $\\varepsilon = 1$ on the US Census dataset we study (prediction of number of weeks worked in $\\{1, \\ldots, 52\\}$). We note the following:\n* Even though the wall clock time for computing the optimal unbiased randomizer is significantly larger than that of the optimal biased one, this is still orders of magnitude smaller than the ML model training.\n* The test loss is quite similar for various mesh sizes, even though the noisy label loss does improve slightly with finer discretization. This suggests that the unbiasedness was key to the improvements over RR-on-Bins and the discretization of the output set does not affect performance as much.\n\n| **Mechanism** | **Mesh size** | **Computing mechanism wall-clock time** | **Noisy label loss** | **Test loss** |\n|---|---|---|---|---|\n| RR-on-Bins | n/a | 0.154 s | 79.71 | 172.44 |\n| Optimal Unbiased Randomizer | 52 | 2.38 s | 1288.21 | 134.44 |\n| Optimal Unbiased Randomizer | 416 | 17.1 s | 1275.22 | 134.43 |\n| Optimal Unbiased Randomizer | 1664 | 161 s | 1274.71 | 134.43 |\n\n> Privacy implications of hyperparameter tuning\n\nWe thank the reviewer for raising this important point. Indeed, hyperparameter tuning in general has additional privacy costs, and how to tune hyperparameters privately and efficiently is an active research topic [1, 2]. Consequently, it is common in the private ML literature to separate the question of private hyperparameter tuning and private training, and focus on comparing the privacy-utility trade-off under optimal hyperparameters [e.g., 3, 4, 5, 6]. In this paper, we follow this convention.\n\n**References:**\\\n[1] Nicolas Papernot and Thomas Steinke.  Hyperparameter tuning with Renyi differential privacy, 2021.\\\n[2] Sander, Tom, Pierre Stock, and Alexandre Sablayrolles. Tan without a burn: Scaling laws of DP-SGD, 2023.\\\n[3] Malek, Mani, et al. Antipodes of label differential privacy: PATE and ALIBI, 2021.\\\n[4] He, J., Li, X., Yu, D., Zhang, H., Kulkarni, J., Lee, Y. T., Backurs, A., Yu, N., & Bian, J. Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping, 2022.\\\n[5] Kurakin, A., Song, S., Chien, S., Geambasu, R., Terzis, A., & Thakurta, A. Toward Training at ImageNet Scale with Differential Privacy, 2022.\\\n[6] De, S., Berrada, L., Hayes, J., Smith, S. L., & Balle, B. Unlocking High-Accuracy Differentially Private Image Classification through Scale, 2022.\n"}]

Author rebuttal:

Meta-review: The authors were unanimous in identifying the merits of this paper, and its fit for publication at NeurIPS. 

One of the reviewers identified several passages in the paper that were nearly identical to the arxiv version of GKK+23, which was published at ICLR. Before publication, the authors MUST do an editing pass to remove any copied text to avoid plagiarism.
Decision: Accept (poster)