LabelDP-Pro: Learning with Label Differential Privacy via Projections
Authors: Badih Ghazi
Yangsibo Huang
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Chiyuan Zhang
Venue: ICLR 2024 poster (2024)
Keywords: Differential Privacy
Label Differential Privacy
Projections
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We propose a family of label DP training algorithms that use projections to denoise the private gradients and achieve better utility in the high-privacy regime.

Abstract: Label differentially private (label DP) algorithms seek to preserve the privacy of the labels in a training dataset in settings where the features are known to the adversary. In this work, we study a new family of label DP training algorithms. Unlike most prior label DP algorithms that have been based on label randomization, our algorithm naturally leverages the power of the central model of DP. It interleaves gradient projection operations with private stochastic gradient descent steps in order to improve the utility of the trained model while guaranteeing the privacy of the labels. We show that such projection-based algorithms can be made practical and that they improve on the state-of-the art for label DP training in the high-privacy regime. We complement our empirical evaluation with theoretical results shedding light on the efficacy of our method through the lens of bias-variance trade-offs.

Published as a conference paper at ICLR 2024
LabelDP-Pro: LEARNING WITH LABEL DIFFERENTIAL PRIVACY VIA PROJECTIONS
Badih Ghazi Google Research
Yangsiho Huang"
Pritish Kamath
Princeton University
Google Research
Ravi Kumar Google Research
Pasin Manurangsi Google Research
Chiyuan Zhang Google Research
ABSTRACT
Label differentially private (label DP) algorithms seek to preserve the privacy of the labels in training dataset in settings where the features are known to the adversary. In this work, we study a new family of label DP training algorithms. Unlike most prior label DP algorithms that have been based on label randomization, model of DP. It interleaves gradient projection operations with private stochastic gradient descent steps in order improve the utility of the trained model while guaranteeing the privacy of the labels. We show that such projection projection-based the state-of-the-arr
algorithm naturally leverages the power of the central
algorithms can be made practical and that they improve for label DP training in the high-privacy regime. We complement our empirical evaluation with theoretical results shedding light on the efficacy of our method through the lens of birs-variance trade-offs.
DPD Gradient
INTRODUCTION
Projected Gradient
Differential privacy (DP) (Dwork et al., 2006b;a), which introduces calibrated noise into machine learning pipelines, has emerged as fundamental tool for safeguarding the privacy of user data. This formal and robust framework, governed by a privacy parameter & (see Definition 1), is widely used in private machine learning applications.
Non-Private Gradlent
Projection Subspace
Figure LabelDP-Pro denoises the DP-SGD gradient via projection. Since the signal (non-private gradient) is already in the subspace, the projection essentially reduces the additive DP-SGD noise. The green dashed (resp., blue dotted) line shows the gradient noise before (resp., after) projection.
In machine learning, the vanilla definition of DP aims protect both the features and labels of the training examples. However, this can be an overkill in settings where the sensitivity lies solely in the labels of the training examples. A notable example is in the realm of online advertising (Cheng et al., 2016; Wang et al., 2017; Guo et al., 2017: Zhou et al., 2018 18; Naumov et al., 2019; Wang et al., 2021). Here, the primary objective is to predict whether a user will perform a useful action on the advertiser website (e.g., purchase the advertised product) after interacting with an advertisement on another (the publisher's) website, a task inherently involving private and sensitive labels. This prediction is made based on features consisting of the product description associated with the displayed advertisement, which are generally considered non-private.
The notion of label differential privacy (LabelDP), introduced by Chaudhuri & Hsu (2011), I), captures such use cases by leveraging the standard definition of DP to only protect the privacy of the labels. There has been growing interest in studying label-only privacy in deep learning (e.g., Ghazi et al. (2021); Malek et al. (2021); Esfandiari et al. (2022); Tang et al. (2022)). Many of these
* Work done while interning Google Research.
WWe point out that several new privacy- APIs for ad measurement that were proposed by different web hrowsers support training ad prediction models with label DP. These include APIs from Mozilla and Meta (Thomson, 2022), Google Chrome (Nalpas & White, 2021), and Apple Safari (app).

---

Published as a conference paper at ICLR 2024
mechanisms rely variants of the classic randomized response algorithm (Warner, 1965). In such mechanisms, each label is randomly changed to a (potentially) different label according to a pre- defined probability distribution. The training is then conducted with the randomized labels, which ensures LabelDP.
In this paper, we focus the high-privacy regime (with a small privacy parameter e). This regime is especially important where highly sensitive data are being processed, as the privacy guarantee becomes exponentially loose with large Additionally, small is also essential for user-level privacy where the privacy budget is shared by multiple examples of each user. Therefore, small generally desired in private learning when possible. However, achieving LabelDP in the high- privacy regime presents a unique challenge. The crux of the issue lies in the fact that in the sigh-privacy regime, the signal-to-noise ratio extremely low in the privatized labels generated by randomized response. This problem is encountered by all LabelDP mechanisms that are based on randomized response and variants.
On the other hand, we notice that DP-SGD (Abadi et al., 2016), standard method for training deep networks with DP guarantees, exhibits better noise scaling in the high-privacy regime, compared to mechanisms relying on randomized response. However, DP-SGD guarantees privacy for both the features and the labels, which is overly stringent for the LabelDP setting. Therefore, to fully harness the advantage of DP-SGD's ' noise scaling, study LabelDP-Pro family of methods that tailor DP-SGD to unlock better utility in the high-privacy regime by applying projection operations.
Our main contributions summarized as follows:
We present LabelDP- -rrro to adapt DP-SGD for LabelDP settings with a projection- -based Denoiser. This Denoiser leverages the public input features in LabelDP to counteract the over- killing noise associated with full (i.e., features and labels) DP protection in DP-SGD (Section 3). We show efficient method for computing the projections via advanced autodiff (Section 3.2). Our LabelDP-Pro is the first practical method that fully utilizes the flexibility of the LabelDP definition, the central DP setting, and the approximate-DD guarantee. In contrast, all LabelDP mechanisms based on randomized response operate in the local DP setting and are restricted to offer pure-DP guarantees, resulting in poor utility in high-privacy regimes.
Through empirical evaluations on four benchmark datasets, we show that LabelDP- improves the state-of-the-an for LabelDP training in the high-privacy regime (Section 5).
We extend our investigation to user-level DP, which ensures the privacy of all examples contributed by each user, and demonstrate using a real-world dataset for which LabeIDP-Pro offers consistent improvement over previous LabelDP basclines (Section 6).
Complementing our empirical findings, we also provide theoretical analyses that justify the choice of the Denoiser and explain the observed improvements (Section 4).
2 LEARNING WITH LABEL DIFFERENTIAL PRIVACY
Let 'D be an unknown distribution on X' V. We consider the multi-class classification setting where y [K] : {1..... ., K). In supervised learning, we have training set D of n examples drawn i.i.d. from D. The goal is to learn predictor fa X' - RKK to minimize the expected loss
(D(S6) == ((x,))= (ff (zx), y). for some loss function é R x y + IR; the most common loss function for multi-class classification is the cross entropy loss [(v, y) notation, we also use ((0, (z. y)) to denote the per-example loss El {(f(()). v).
log By. With an abuse of
2.1 (LABEL) DIFFERENTIAL PRIVACY
We recall the definition of DP; for more background, see the book of Dwork & Roth (2014b). Definition (DP; Dwork et al. (2006b)), Let E R 8 E 1). A randomized algorithm A is said to be (c, diffferrrenlll private (denoted (e, 6)-DP) if for any two adjacent input datasets (differ by at most one datapoint) D and D', and any subset S of outputs of A, it holds that Pr(A(D) S & e Prr[A(D)) E S] 6
In supervised learning, a learning algorithm produces model as its output, while the labeled training set serves as its input. Two training datasets are "adjacent" if they differ on a single training example. This notion of adjacency protects the privacy of both the features and the label of any individual
2

---

Published as a conference paper at ICLR 2024
Algorithm 1:
Labe
Input: : Initial model weights 8g. a training set D of size n, learning rate Th, number of training iterations T, batch size nı, noise multiplier a, gradient norm bound C, and Denoiser, which a method for denoising gradients. Output: The trained model weights Or.
for t = 0 to do
Get mini-batch _ of n1 indices by uniform sampling from [x]] foreach i 7,0 do ge (1) t Vo, (xi4
Compute gradient // Clip gradient Aggregate and add noise // De-noise the gradient // Optimize; can also use other optimizers
foreach i 1 do (1 Uk) (1s,, wi)/ max (1, [.. (x:(a,06))22)
gr ni EEerç (3i, vi) + +N(00,
g: + Denoiser (Bc. B,, (iiee 0.41 - nr
example. However, in certain scenarios, protecting the features may be unnecessary or infeasible, and the focus solely on protecting the privacy of the labels. This leads to the following notion:
Definition 2 (LabelDP; Chaudhuri & Hsu (2011)).. A randomized training algorithm A is (s,ō)- LabelDP it is (e, 6D when two input datasets differ on the label of a single training example.
For both notions, due to the e factor, the high-privacy regime corresponds small E (e.g., & < 1).
Item-level and user-level DP In the traditional notion of DP, the goal is to protect the privacy of each training example, where is assumed that each user contributed only one training example; this is commonly known item-level or example-level privacy. However, in scenarios where a single user contributes multiple training examples, more desirable objective would be the so-called user- level privacy, which ensures the privacy of all examples contributed by user. In this case, the "adjacent" dataset would differ on all the examples from a single user. This is especially relevant in applications such online advertising and federated learning, where each user often contributes multiple examples (McMahan et al., 2017; Liu et al., 2020; Levy et al., 2021).
2.2 RANDOMIZED RESPONSE AND DP-SGD
Randomized response (RR) (Warner, 1965), which precedes the advent of DP, has been used as a standard mechanism to provide LabelDP guarantees. Let y E [K] be the ground truth label. When an observer queries the value of RR with e-LabelDP responds with a random draw ÿ E [K]. Specifically, RR returns the ground truth label with probability of cT while with the remaining probability, it returns a uniformly random element from [K]](v)-
DP-SGD was proposed in the seminal paper by Abadi et (2016), and has become the most widely adopted algorithm for privately training deep neural networks. DP-SGD works by clipping the per-example gradient and adding Gaussian noises, during each training iteration. (For a formal description, see Algorithm I with a NoOP denoiser.) DP-SGD relies the fact that only a random mini-batch of examples are processed each iteration, and uses amplification by sampling (Abadi et al., 2016; Bassily et al., 2014; Wang et al., 2018) to drive down the overall privacy cost.
3 LabelDP-Pro
K thus, As discussed above, RR-based LabelDP mechanisms flip the labels with probability .
in the high-privacy regime, incur exponentially more noise. For instance, with K 10 and 0.5, in expectation more than 84% of the training labels would be incorrect. In contrast, the scale of the Gaussian noise in DP-SGD increases only linearly with 1/e in the high-privacy regime. The suboptimal noise scaling for RR is partly because it provides more stringent local privacy guarantee, compared to the central privacy guarantee discussed here (See Appendix B for more novel approach that enjoys the flexibility
details). Inspired by this, propose LabelDP-Pro. of both central privacy (improved noise scaling) and the LabelDP (auxiliary information computed from the input features) to unlock high utility of LabelDP in the high-privacy (i.e., small e) regime.
3

---

Published as a conference paper at ICLR 2024
Table 1: A summary of denoisers for noisy gradients gt. with optional access to the model weights & and the features of the eurrent batch :(2, heza. A denoiser can also access the features of the full training set. particular, it can sample an "altemative"" batch If of re examples and have access feif. The last column indicates if the denoiser is compatible with amplification by subsampling in the privacy accounting.
Denoiser
Output
Compatible with Amp.
NoOP
g
Yes
SELFSPAN
Proj (g:) for A = span
(Vs, (ax, 1) hee melk]
No
SELFCONV
Proj (@:) for A = conv
(Ve, e(O,, (Ie i k) pereeeeeeeeeeeeee.. (E(K (Ve, (30e, 6) Keeff ME([K]
No
ALTCONV
Proj (g:) for A conv
Yes
3.1 PROJECTION-BASED GRADIENT DENOISING
Due to better noise scaling, DP-SGD could achieve better utility than classical algorithms like RR in the high-privacy LabelDP regime. However, it would be overkill as DP-SGD protects the privacy of both features and labels. In the following, we propose a framework to improve DP-SGD by using the input features, which yields a family of new algorithms that enjoys the same linear noise scaling, and outperforms DP-SGD (and RR) in the high-privacy LabelDP regime.
The main idea is that structural priors can be computed based on the input features, and utilized to denoise the noisy gradient from DP-SGD. Specifically, the framework introduces a Denoiser function, described in Algorithm (vanilla DP-SGD is thus a special case with a NoOp denoiser.). Table 1 summarizes some useful denoisers. For example, the SELFSPAN denoiser makes use of the fact that the (original unnoised) gradient lies in the span of the per-example per- class gradients oV,, {(,,, (I2, (z,, (er we(K]]- So it denoises the private gradient from DP-SGD by projecting it onto this span. Note the span can be constructed using only the features and without accessing the labels-the denoising step thus crucially exploits the LabelDP setting! As an alternative view, note that the privatized gradient in DP-SGD is the sum of the signal (the gradient) and the Gaussian noise, The SELFŠPAN projection for the signal part is a no-op because the signal is already in the span. As a result, the denoising step is essentially reducing the noise by projecting it onto a lower dimensional subspace while keeping the signal intact (Figure 1).
Taking one step further, note that the unnoised gradient is not just in the span, but also in the convex hull of the per-example per-class gradients. This observation leads to the SELFCONV denoiser, which has improved dependency on K (Table 4). Moreover, we can also independently sample an "alternative" batch I of n2 examples and project onto its gradients { o, ( (I3, )ief x<(())- again using only the public information; we call this denoiser ALTCONV. Empirically, we found that both SELFCONV and ALTCONv behave quite similarly under the same DP-SGD noise (see Table 3), but the latter has the extra benefit of being amenable to amplification by subsampling, resulting in lower privacy cost. We defer to Section 3.4 for the details the privacy accounting. Unless otherwise specified, we will use the ALTCONY denoiser in the experiments.
3.2 MEMORY-EIFICIENT PROJECTION VIA ADVANCED AUTODIFF
The denoisers (Table 1) operate by projecting the noisy gradient onto the subspace or the convex hull spanned by set of per-example per-class gradients. A naive implementation of such projection would need K2 memory to store the vertices spanning the convex hull, where d is the model size.
We next describe a memory-efficien algorithm. Let g be the privatized gradient, and G [V (x),x)))ker>> ,<([K] [M([]] be the x n dimensional matrix of the per-example per-class gradients (in the case of SELFSPAN and SELFCONV, 1 = 1 and n2 = n1). To project g onto the convex hull of the columns of G, we solve m |Ga - gl? where A is the unit simplex for ni K -dimensioonl vectors. We solve this optimization problem with projective gradient descent. Specifically, let 0k E A be an initialization of the projection coefficients, and r,PGD be the step size,
g) The projection onto the unit simplex can be computed using the methods of Wang & Carreira-Pent Periinnn (2013). We next focus on efficiently computing the boxed red part, which depends on two subroutines: u + Gu for any R and + G for any v E Rd. We note that given the special structure of G, those subroutines can be computed using advanced auto differentiation (autodiff, Baydin et al., 2018) primitives without materializing G. Indeed, define L + [e(0, (I., (E]] and observe
we iteratively update it as a++11 <- Proja (ox- - 27 G (Go,
4

---

Published as a conference paper at ICLR 2024
that G is the Jacobian of L. Then G vs the Jacobian-vector product (JVP). It turns out that JVP can be implemented via the forward mode autodiif, which cumulatively computes the results in a "forward" manner from the bottom of the neural network, and does not require a materialization of G. Similarly, the reverse mode autodiff can be used to compute the vector-Jacobian product (VJP) in Gu = (u' GT) again, VJP does not need materialize G. In fact, the reverse mode autodiff is the default algorithm for computing the gradients in most deep learning frameworks, since the propaaapoottnnnn algorithm (Rumelhart et al., 1986) is special case of it with scalar loss, We give pseudocode implementation in Appendix C.
3.3 STABLE PROJECTION VIA COEFFICIENT SMOOTHING
Due to the noise in the privatized gradient, the projection coefficients a sometimes put dominating values on an "incorrect" class. This might cause numerical instabilities in the learning dynamics due to excessively large gradient norms (Figure 2) because of the unboundedness of the cross-entropy loss, as also observed in previous work (Ghosh et al., 2017; Ma et al., 2020; Zhou et al., 2021).
In our case, we found simple smoothing-based regularization to be effective. Specifically, we create smoothed projection coefficient = λa + (1 X)33, where 33 R=nK is constant vector with each coordinate being K Kxng' representing a uniform distribution that assigns equal weights to all projection vertices. À controls the level of regularization, with smaller values indicating stronger regularization, As depicted Figure and summarized Table 2, enabling regularization (A 1) leads to more stable training process and improves utility. Typically, we find that A value of 0.75 yields the best results. Note if a is a one-hot encoded multi-class label, then this regularization is akin to the label smoothing technique (Mäller et al., 2019; I Lukasik al., 2020).
Table 2: MNIST accuracy (%) for the implementation with regularization compared to the vanilla implementation.
2-0.25
A-025
Gradient Norm
2-0 50
A-0.50
A.0.75
Verilla (1-1.0)
ngaining
Vanilla w/ Regularization
0.1
86.2
91.1
0.2
87.9
92.9
Step
Step
0.5
88.2
94.1
Figure 2: Effect of the regularization coefficient X on the gradient norm
1.0
91.3
94.3
(left) and the training loss (right). Applying regularization with À < 1 helps stabilize the training.
2.0
92.2
94.5
3.4 PRIVACY ANALYSIS
We recall the privacy analysis of DP-SGD (i.e., LabelDP-Pro with NoOP denoiser), and then show that the same analysis also holds for LabelDP-Pro with ALTCONv denoiser. The privacy analysis of DP-SGD is usually done by considering an approximation, where instead of shuffling and batch- partitioning as generally done in practice. in each iteration, batch is constructed by sampling each example independently with probability ni mi/n. This enables analyzing the privacy cost of DP-SGD via the composition of adaptively chosen Poisson subsampled Gaussian mechanisms, which uses privacy amplification by subsampling to provide lower privacy cost. It is now easy to see that applying the same approximation LabelDP- using ALTCONY denoiser simply composition of adaptively chosen Poisson subsampled Gaussian mechanisms with post-processing, hence we can apply the post-process post-processing property of DP (Dwork& & Roth, 201 4a, Proposition 2.1).
The main thing to note about the ALTCONV denoiser is that the projection step involves sampling a random subset I," from the training data to define the convex hull that the noisy gradient projected to. The analysis goes through since these are independent of the examples in the batch 1, and do not use the information about labels of examples in T Note that the same analysis does not hold when using SELFSPAN or SELFCONV denoisers the convex hull is defined by (unlabeled) examples in I and so the final projected gradient might reveal information about 1 (which examples ended up being sampled in the current batch) and breaks privacy amplification by subsampling.
Rényi Differential Privacy (RDP) accounting (Mironov, 2017) has been the most widely used approach in DP-SGD (Abadi et al., 2016). Numerical approaches for obtaining tighter estimates of privacy parameters have been studied recently using the notion of privacy loss distributions (PLD) (Meiser & Mohammadi, 2018; Sommer et al., 2019), and several algorithms have been
5

---

achieves the Published as a conference paper at ICLR 2024
Table 3: Test accuracy (%) on the MNIST dataset with different denoisers. "AMP." stands for privacy amplification via subsampling. The SELFSPAN and SELFCONV denoiser should use amplification, and the corresponding columns are shown (in gray) only reference purposes.
DP-SGD NoOP w/ AMP.
Project onto span
Project onto convex hull
SELFSPAN wio AMP.
SELFSza w/ AMP.
ALTCONy w/ AMP.
SELFCONY wio AMP.
SELPCONY w/ AMP.
0.1
85.6
64.5
86.1
91.1
65.9
91.3
0.2
87.9
73.8
88.2
92.9
75.6
93.3
90.9
81.8
91.5
94.1
83.8
94.2
92.8
84.8
92.9
91.3
86.1
94.3
2.0
93.8
87.4
93.6
95.4
88.2
95.6
Table 4: Additional excess error due to privacy for PGD using stochastic gradient oracles.
Method
Additional excess error due to privacy
LabelDP-Pro: NoOP
RC
dda
V
LabelDP-Pro: SELFSPAN
RC
Kann
o o (RC
Sit V [og((Ku)]
LabelDP-Pro: SELFCONV
Vaa t Vlog(Kng)
LabelDP-Pro: ALTCONY
RC
RR-Debiased (p -
K
RC
(T
studied for the same (Koskela et al., 2020; Gopi et al., 2021; Ghazi al., 2022; Doroshenko et al., 2022). In particular, we use the privacy accounting implementation Google's DP Library (2020).
4 BOUNDS FOR CONVEX EMPIRICAL RISK MINIMIZATION
We now present our theoretical motivation that underlies the method presented in Algorithm 1 and the denoisers presented in Table 1. We examine this through case study of stochastic convex optimization. Consider the goal of minimizing a conver objective [(w) for to E K., for some convex set IC with diameter R using stochastic gradient oracle that, given w, returns stochastic estimate ((w) of g(w) = ((w). The loss is said to be C-Lipschitz if ([g(())))) [nw))l2 S C. for all w. We say that the gradient oracle has bias a and variance 2 ī(w) g(w) + e(w) such that [e(w)ll2 S a and IE (e(w) I e e(w) 1 < w² holds for all w. Additionally, we say that the gradient oracle has expected squared norm of C2 if (()()))) E for all w. The projected gradient descent (PGD) with step size y is defined as iteratively performing W <- (w, - ng(w,)) where Projxc the projection onto K. Let w" be minimizer of L(w)) The expected excess loss be bounded as shown below following the standard analysis of PGD (see, e.g., Hazan (2022)); we include a proof for completeness in Appendix E.
Lemma 3. For a convex loss function L. and a gradient oracle with bias a and expected squared R
norm Č PGD over a convex sel K. C R& with diameter R and step size = CVT
following expected excess risk bound for the average iterate WT := ET we
RC + aR.
E C (wr) -((w")
Note that C-Lipschitz and the gradient oracle has variance w², then C S (C a)² + w² although it is possible to get an improved upper bound on Ö for some oracles we consider.
Now consider the problem of minimizing the empirical loss. Namely, let é: Rd x x [KK] - R be C-Lipschitz loss function, and let L(w) = Eve(n) ((w; Wt). Observe that the true gradient at w is given as ((x) Eiejn) Vwl(ur; F4, V:), and each method discussed in this paper provides a stochastic gradient oracle the empirical loss L. In particular, we diseuss LabelDP-PP using various denoisers as well as the debiased randomized response for this theoretical case study.
We can apply Lemma to bound the excess error of PGD using the stochastic gradient oracles arising out of each method. Table 4 provides upper bounds the excess error for each method; derive these formally Appendix E. The most technical part is to bound the expected squared norm of the error in the stochastic gradient oracle with the ALTCONV denoiser, as shown below, which in particular implies a bound on both the bias and the variance the oracle.

---

Published as a conference paper at ICLR 2024
Lemma 4. Let 10, IP C [n]] be random subsets of size n1, n2 respectively. Let denote the noisy gradient estimate from Ic namely, 9 = Ligre V Vwl(ur Ti Vi) + e f e NO0 <cc I). Let A = conv ((V (un, (e),))) (N(KK) denote the convex body on which we project. Then, over the choice of 1 IP, and e, we have
E (rojA 91l S 0 02
R2
R2
We now interpret the bounds in Table 4, and compare it against the accuracy bounds in Table 3. The rate of SELFSPAN gets rid of the dependence on dimension d; however, it comes at a price that privacy amplification by subsampling is no longer applicable, due to which the noise multiplier na larger than σg. This is indeed limiting, and if we instead use og instead, SELFSPAN denoiser ends up better than DP-SGD. The rate of SELFCONV improves upon the rate of SELFSPAN, but again suffers from the same limitation that privacy amplification by subsampling is not applicable. Finally, ALTCCONV achieves error that is slightly larger than SELFCONV when using the same noise multiplier (which can be see by comparing against SELFCONV when we use the noise multiplier using privacy amplification), but since ALTCONV benefits from privacy amplification by subsampling, it overall ends up being better than SELFCONV.
Note that the bounds in Table hold only for convex loss functions. Moreover, they are upper bounds on the excess error. For instance, while the bound in Lemma 3 is tight in the worst case, better rates might be achievable under additional assumptions on the loss function. Despite these limitations, we see in Table 4 that the excess error bounds align well with the experimental findings.
EVALUATION WITH ITEM-LEVEL PRIVACY
In this section, we evaluate the performance of LabelDP-Pro and compare it with baseline approaches for item-level privacy. We detail the experimental setup in Section 5.1 and present the main results in Section 5.2. We then demonstrate that LabelDP-Pro can be combined with self-supervised learning to unlock even higher utility (Section 5.3).
5.1 EXPERIMENTAL SETUP
We compare our LabelDP-Pro four benchmark datasets commonly used in LabelDP learning evaluations: MNIST (LeCun et al., 1998), KMNIST (Clanuwat et al., 2018), FashionMNIST (Xiao al., 2017), and CIFAR-10 100 (Krizhevsky et al., 2009); against four established LabelDP baselines:
Randomized Response (RR) (Warner, 1965): Method that randomly flips the label ( Section 2.2).
RR with Debiased Loss (RR-Debiased): RR extension with unbiased loss function for training. Label Privacy Multi-Stage Training (LP--MTT) (Ghazi et al., 2021): LP-MST trains the model disjoint partitions of the dataset in different stages. Specifically, compare against LP-2ST, a specific configuration with two training stages.
Additive Laplace with Iterative Bayesian Inference (ALIBI) (Malek al., 2021): A soft RR mechanism that directly adds Laplace noises to one-hot encodings of training labels.
We also report the performance for DP-SGD as a reference, since our approach is built upon it. See Appendix D for more details on the experiments.
5.2
MAIN RESULTS
As presented in Table 5, across both the MNIST and CIFAR-10 benchmarks, LabelDP-PP -ro consistently surpasses baseline LabelDP mechanisms when ε < 1.0. Notably, the performance gap widens as ε decreases. For instance, when = 0.2, previous baselines all achieve accuracy levels close to random guessing, while LabeIDP-Pro maintains non-trivial accuracy at 92.9% on MNIST and 30.8% on CIFAR- 10. These results demonstrate the effectiveness of LabelDP-Pro in preserving utility, and they echo the theoretical analyses in Section 4. There also appears to be a threshold ex such that when & e*, LabelDP-PP Pro outperforms RR, but when > e*. RR exhibit superior performance. In Appendix D.4, we show how the number of classes (K) and the probability for catastrophic failure (8) affect e".
Compared to DP-SGD, LabelDP-Pro also consistently exhibits superior performance, underscoring the effectiveness of our Denoiser. Notably, this performance gap tends be more pronounced when
7

---

Published as conference paper at ICLR 2024
Table 5: Test accuracy on (a) MNIST-10 and (b) and CIFAR-I0, for different E's. The best result for each is boldfaced. We report the utility differences between LabelDP-Pro and the best baseline among RR, RR-Debiased LP-2ST. ALIBI (Ansselne)), and between LabelDP-Pre and DP-SGD (ADP.SCD). LabeIDP-Pro outperforms baseline methods the
regime.
Privacy Budget (8)
Baseline LabelDP Methods RR-DEBIASED LP-2ST ALIBI
LabelDP- (Ours)
DP-SGD
RR
Acc.
Roseline
ApP.SGD
(a) MNIST-10
0.01
6.5
10.8
9.0
10.3
65.3
68.2
57.4
2.9
0.1
7.3
10.9
10.0
9.7
85.6
91.1
80.2
5.5
0.2
8.1
10.9
10.0
9.7
87.9
92.9
82.0
5.0
0.5
10.4
11.0
10.0
82.5
90.9
94.1
83.1
3.2
1.0
51.3
50.6
83.3
94.1
92.8
94.3
11.0
1.5
2.0
96.7
96.8
96.8
96.6
93.8
95.4
1.4
1.6
(b) CIFAR-10
0.05
10.0
10.0
10.0
9.9
10.1
16.0
6.0 f
5.9
0.1
10.0
10.0
10.0
9.9
24.6
27.0
17.0
2.4 1
0.2
10.0
10.0
10.0
17.9
29.8
30.8
12.9
1.0
0.5
10.0
10.0
35.8
34.4
36.9
40.2
5.8
3.3
1.0
17.0
10.0
60.9
51.3
43.5
44.8
16.1
1.3
Table 6: Test accuracy (%) on CIFAR-10 using Wide-ResNer18 with SclfSL. The PATE-FM results (also using Wide-ResNet18 but with SemiSL) are from Table 1 of Malck al. (2021). The best result for cach e boldfaced. We report the utility differences between LabelDP-Pre and the best baseline among RR, RR- Debiased, RRWithPrior, PATE-FM (Buueiiee,, and between LabelDP-Pre and DP-SGD (ADF-SGD). Despite PATE-FM's stronger SemiSL pipeline (95.5% non-private accuracy, compared outperforms PATE-FM in the high-privan privacy regime.
90.9%). LabelDP-Pro
Baseline LabelDP Methods
LabelDP Pro (Ours)
DP-SGD
RR
RR-Debiased RRWithPrior
PATE-FM
Acc.
Basellne
ApP-SGD
0.01
2.7
24.6
71.8
74.4
43.1 f
f
0.02
3.4
2.1
50.4
81.6
82.4
32.0 f
f
0.05
3.5
2.7
70.8
85.1
85.5
14.7 1
f
0.18
4.7
3.1
76.8
73.4
86.4
86.6
9.8 f
0.2 f
0.29
5.1
3.7
76.8
86.9
87.0
87.2
0.3 f
0.2 f
0.5
6.0
9.8
78.1
87.1
87.4
9.3 1
0.3 f
1.6
88.1
88.0
83.1
93.7
87.2
87.7
6.5
0.5 1
dealing with smaller E's which can be potentially attributed to the fact that when E is relatively large, the noise introduced by DP-SGD is already minimal, leaving limited room for improvement by our Denoiser. We also observe similar results on other datasets (see Appendix D.4).
5.3 LEVERAGING SELF-SUUPERVSEDD LEARNING WITH LabelDP
Since the features are public LabelDP, we can use self-supervised learning (SelfSL) techniques (Chen al., 2020a;b; Grill et al., 2020; He al., 2020: Caron et al., 2021; Xie al., 2022) to obtain high-quality representations to further the utility of LabelDP Ghazi et al. (2021). These representations can learned solely from the input features without requiring labels; later, they can be fed into the private supervised training pipelines alongside the corresponding labels.
We demonstrate this approach by evaluating LabelDP-Pre with SelfSL on CIFAR-10. Specifically, we pre-train Ride-ResNNt18 (He et al., 2016) as a representation extractor with unlabeled CIFAR- 10 images using the SimCLR algorithm (Chen al., 2020a). We then train classifiers on the extracted representations using various LabelDP mechanisms, including RR, RR-Debiased, RRWithPrior (Ghazi al., 2021)?, DP-SGD, and LabelDP-Pro. See Appendix D.2 for more details.
We additionally include PATE-FM (Malek al., 2021). state-of-the-art semi-supervised learning (SemiSL) based method, comparison. is noteworthy that PATE-FM benefits from a more powerful SemiSL pipeline, with non-privee non-private accuracy of 95.5% compared to SelfSL pipeline's 's
PRRWithPtior subroutine the LP-MST method, where randomized labels are sampled with access to label priors to improve accuracy. When implementing this in the context SelfSL, we follow the procedure detailed in Ghazi et al. (2021, Section 5.2): we cluster training examples based on the SelfSL model representations, and then query label histograms for each group using the discrete Laplace mechanism to obtain lahel priors. The budget spared for the histogram query can he found in Appendix D.
8

---

Published as a conference paper at ICLR 2024
Table 7: Test AUC of RR, DP-SGD, and LabelDP-Pre on the Critco data, with a different number of examples contributed per user (k) and privacy budget (c). The best results for cach (e, k) combination boldfaced.
k DP-SGD
k 5
k 10
RR
LabelDP-Pro
DP-SGD
LabeIDP-Pro
DP-5GD
LabelDP-Pro
0.1
0.562
0.686
0.780
0.537
0.668
0.768
0.544
0.652
0.751
0.2
0.594
0.707
0.786
0.549
0.693
0.771
0.555
0.680
0.766
0.5
0.652
0.719
0.787
0.587
0.714
0.776
0.575
0.704
0.766
1.0
0.710
0.724
0.789
0.638
0.722
0.777
0.605
0.712
0.768
2.0
0.761
0.731
0.791
0.704
0.728
0.778
0.652
0.720
0.769
5.0
0.804
0.741
0.793
0.761
0.739
0.781
0.718
0.733
0.773
0.823
0.824
0.821
non-private accuracy of 90.9%. As shown in Table 6, LabelDP-Pro consistently outperforms all previous LabelDP baselines for ε I 0.5. Remarkably, even when PATE-FM utilizes a stronger SemiSL pipeline, achieving higher non-private accuracy than our SelfSL pipeline, LabelDP-Pro still outperforms it at e = 0.18 and s = 0.29. We note that while LabeIDP-Pro is a generic LabelDP algorithm, both the SelfSL-based approach and PATE-FM (SemiSL-based) heavily rely on powerful visual priors that can be derived from randomly augmented images alone. It is unclear how to generalize other domains where there are no powerful input data augmentations. Therefore, while it is possible to plug LabelDP-Pro into a SemiSL. pipeline as well by only privatizing (and denoising) the supervised loss gradients, we leave the evaluation of this complicated setup for future work.
EVALUATION WITH USER-LEVEL PRIVACY
We finally evaluate LabelDP-Pro with user-level privacy, which protects a user's entire contribution the model instead of guaranteeing privacy for individual items. User-level DP offers more stringent but realistic protection against adversaries, especially in advertising applications.
Dataset and model We use the Criteo Attribution Modeling for Bidding dataset (Diemert Eustache, Meynet Julien et al., 2017), which comprises 30-day sample of live traffic data from Criteo, a company that provides online display advertisements. Each example in the dataset corresponds to banner impression shown to user, and whether it resulted in conversion attributed to Criteo. The dataset retains user identifiers, and each user may contribute to multiple examples. We randomly select 200, 000 users and gather their data create the training dataset, and disjoint set of 50, 000 users for evaluation. For the training data, we cap the maximum number of examples any one user contribute to be k where vary l in {2, 5, 10]4. In cases where user contributes fewer than 1 examples, we use random re-sampling to augment their contributions to k examples. We train attribution model (Appendix D.3) with cross-entropy loss and report the AUC. We use group privacy (see e.g. Vadhan, 2017) for randomized responses. For DP-SGD and LabelDP-Pro we compute per-user gradients and use them replace the per-example gradients used in traditional item-level DP-SGD. This inherently offers privacy guarantees at the user level (Kairouz et al., 2021a; Xu et al., 2023).
Results We report the performance of LabelDP-Pro. RR, and DP-SGDS. As shown in Table 7, LabelDP-Pro consistently exhibits superior utility compared to RR when e < 5, across various numbers of examples per user (k)) As h increases, the performance gap between RR and LabelDP-Pro becomes more pronounced. This widening gap can be attributed to the fact that user-level DP guarantee of () translates into an item-level DP guarantee of (e/k, 8 o/ke*) by group privacy (e.g., Vadhan (2017)). So as k increases, the corresponding item-level privacy budget decreases, which further accentuates the advantage of LabelDP- Prro over RR as shown in Section 5.
CONCLUSIONS AND FUTURE WORK
We studied LabelDP-Pro, a family of label DP training algorithms that interleaves gradient projection steps with DP-SGD to improve the utility of the trained model. Our empirical study, encompassing item-level and user-level privacy, demonstrates that such projection- based algorithms improve the state-of-the-art utility in the high-privacy regime. We further support our empirical findings with theoretical analyses based on bias-variance trade-offs. An important direction is to
httpps: /ab criteo www.croc/icioo www.raatttiiatrrae poodelingg-ae *The distribution of the number of examples contributed by each user is shown in Figure 5 (Appendix D.4). 'ee do not include methods based SemiSI. SelfSL. in our analysis, because it is not clear how to effectively adapt those algorithms designed for image classification data to the domain of online advertising.

---

Published as a conference paper at ICLR 2024
explore more efficient denoisers. Currently, the memory-efficient approach demands approximately 200 iterations to reach convergence, presenting a computation bottleneck within the overall training process. In addition,
aspire investigate the potential of LabelDP-Pro in the context of regression tasks Ghazi et al. (2023), thereby expanding its applicability beyond the scope of the classification tasks that study.
10

---

Published as a conference paper at ICLR 2024
REFERENCES
A proposal for privacy preserving ad attribution measurement using Prio-like architecture. https: //gi www.tth.coo... wtt.:cttt//pcccccctttttc
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangging Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg. Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL ht / //www. tensorflow org/.
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, pp. 308-318, 2016.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In FOCS, pp. 464-473, 2014.
Atilim Gunes Baydin, Barak Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic diffcrentiation in machine learning: survey, JMLR, 18:1-43, 2018.
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//gi //github..o com/ gooom//oole/jax.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In ICCV, pp. 9650- 9660, 2021.
Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In COLT, pp. 155-186, 2011.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In ICML, pp. 1597-1607, 2020a.
Ting Chen, Simon Korbblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self- supervised models are strong semi-supervised learners. In NeurlPS, pp. 22243-22255, 2020b.
Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. Wide & deep learning for recommender systems. In 1st Workshop on Deep Learning for Recommender Systems, 2016.
Tarin Clanuwat, Mikel Bober- Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical Japanese literature. arXiv preprint arXiv: 1812.01718, 2018.
Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geambasu, Matthew Jagielski, Yangsibo Huang, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, al. Challenges towards the next frontier in privacy. arXiv preprint 23Xx:23344006229 2023.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204.13650, 2022.
Carson Denison, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi. Krishna Giri Narra, Amer Sinha, Avinash Varadarajan, and Chiyuan Zhang. Private ad modeling with DP-SGD. In AdKDD, 2023.
Diemert Eustache, Meynet Julien, Pierre Galland, and Damien Lefortier. Attribution modeling increases efficiency of bidding in display advertising. In AdKDD, 2017.
11

---

Published as a conference paper at ICLR 2024
Friedrich Dörmann, Osvald Frisk, Lars Nørvang Andersen, and Christian Fischer Pedersen. Not all noise is accounted equally: How differentially private learning benefits from large sampling rates. In MLSP, 2021.
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. PoPETS, 2022.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor Comput. Sci., 9(3-4)221 1-407, 2014a.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014b.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pp. 486-503, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pp. 265-284, 2006b.
Hossein Esfandiari, Vahab Mirrokni, Umar Syed, and Sergei Vassilvitskii. Label differential privacy via clustering. In AISTATS, pp. 7055-7075, 2022.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. In NeurIPS, pp- 27131-27145, 2021.
Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Faster privacy accounting via evolving discretization. In ICML, pp. 7470-7483, 2022.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan, and Chiyuan Zhang. Regression with label differential privacy. In ICLR, 2023.
Aritra Ghosh, Himanshu Kumar, and P Shanti Sastry. Robust loss functions under label noise for deep neural networks. In AAAI, 2017.
Google's DP Library. DP Accounting Library. differential wttllpppatttee//aaaiaiiia wttpaaann/n///pppppppapaa accounting. 2020.
https: http::://gituub.com/////
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In NeurlPS, pp. 11631-11642, 2021.
Ban--Batienn Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Beraaro Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent A new approach to self-supervised learning. In NeurIPS, pp- 21271-21284, 2020.
Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. DeepFM: a factorization- machine based neural network for CTR prediction. arXiv preprint arXiv:1703.04247. 2017. 2017.
Elad Hazan. Introduction to Online Convex Optimization. MIT Press, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pp. 9729 2020.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. ICML, 2021a.
Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. Fast dimension independent private adagrad on publicly estimated subspaces. In COLT, 2021b.
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. In AISTATS, pp. 2560-2566 2020.
12

---

Published as a conference paper at ICLR 2024
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Master's 's thesis, Department of Computer Science, University of Toronto, 2009.
Alexey Kurakin, Steve Chien, Shuang Song, Roxana Geambasu, Andreas Terzis, and Abhradeep Thakurta. Toward training at ImageNet scale with differential privacy. arXiv preprint vrXiv:2201.12325 2022.
Yann LcCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322 1998.
Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. NeurIPS, 04112466-12779 2021.
Xuechen Li, Florian Tramer, Perey Liang, and Tatsunori Hashimoto. Large language models can be
strong differentially private learners. In ICLR, 2022.
Yuhan Liu, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Michael Riley. Learning discrete distributions: user vs item-level privacy. In NeurlPS, pp. 20965-20976. 2020.
Michal Lukasik, Srinadh Bhojanapalli.. Aditya Menon, and Sanjiv Kumar. Does label smoothing mitigate label noise? In ICMI., pp. 6458, 2020.
Xingjun Ma, Hanxun Huang, Yisen Wang, Simone Romano, Sarah Erfani, and James Bailey. Normalized loss functions for deep learning with noisy labels. In ICML, pp. 6543-6553, 2020.
Mani Malek, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramèr. Antipodes of label differential privacy: PATE and ALIBI. In NewrlPS, pp. 6934 6945, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficeent learning of deep networks from decentralized data. In AISTATS, pp- 1273-1282, 2017.
Sebastian Meiser and Esfandiar Mohammadi. Tight budget? Tight bounds r-rold approximate differential privacy. In CCS, pp. 247-264, 2018.
Ilya Mironov. Rényi differential privacy. In CSF, pp. 263-275, 2017.
Rafael Müller, Simon Komblithh and Geoffrey E Hinton. When does label smoothing help? In NeurlPS, 2019.
Maud Nalpas and Alexandra White. Attribution Reporting, May 2021. https://developer.
chrome. www.///o//oooeecccc/ccceeeeecooe eee/e///oooe/ aatprppiiiiyyaaadorrrrrtrrrrrtoo
Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang. Narayanan Sundaraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G Azzolini, et al. Deep learning recommendation model for personalization and recommendation systems.
arXiv preprint arXiv:1906.00000 2019.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. In ICLR, 2018.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. In AAAI, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In NeurlPS, pp. 8024 8035, 2019.
Sofya Raskhodnikova, Adam Smith, Homin K Lee, Kobbi Nissim, and Shiva Prasad Kasiviswanathan. What can we learn privately. In FOCS, pp. 531-540, 2008.
David E Rumelhart, Geoffrey Hinton, and Ronald J Williams. Learning representations by back- propagating errors. Nature, 323(6088) 1986.
13

---

Published as a conference paper at ICLR 2024
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying superviiee learning with consistency and confidence. In NeurlPS, pp. 596-608, 2020.
David M Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. PoPETS, 2019.
Xinyu Tang, Milad Nasr, Saeed Mahloujifar, Virat Shejwalkar, Liwei Song, Amir Houmansadr, and Prateek Mittal. Machine learning with differentially private labels: Mechanisms and frameworks. PoPETS, 4:332-350, 2022.
Martin Thomson. Privacy Preserving Attribution for Advertising, February 2022. https://blog
mozilla. wwtp://gg/////o///eeeeeee//eae/a http:///www.aaaaaaaaaarrreeeeeee peeeserving-attiibutiooo
Florian Tramer and Dan Bonch. Differentially private learning needs better features (or much more data). In ICLR, 2021.
Salil Vadhan. The Complexity of Difserential Privacy. Springer, 2017.
Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep & cross network for ad click predictions. In ADKDD, 2017.
Ruoxi Wang, Rakesh Shivanna, Derek Cheng, Sagar Jain, Dong Lin, Lichan Hong, and Ed Chi. DCN V2: Improved deep & cross network and practical lessons for web-scale learning to rank systems. In The Web Conference, 2021.
Weiran Wang and Miguel A Carreira- Perpinán. Projection onto the probability simplex: An efficient algorithm with simple proof, and an application. arXiv preprint arXiv: /309. 1541, 2013.
Yu- Ku-Xiang Wang, Borja Balle, and Shiva Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. arXiv preprint arXiv: 00087, 2018.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. JASA, 60(309):63-69, 1965.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
Zhenda Xie, Zheng Zhang. Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu. Simmim: A simple framework for masked image modeling. In CVPR, pp. 9653-9663, 2022.
Zheng Xu, Maxwell Collins, Yuxiao Wang, Liviu Panait, Sewoong Oh, Sean Augenstein, Ting Liu, Florian Schroff, and H Brendan McMahan. Learning to generate image embeddings with user- level differential privacy. In CVPR, 2023.
Da Yu, Huishuai Zhang, Wei Chen, and Tie- Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. ICLR, 2021.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. In ICLR, 2022.
Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In KDD, 2018.
Xiong Zhou, Xianming Liu, Junjun Jiang, Xin Gao, and Xiangyang Ji. Asymmetric loss functions for learning with noisy labels. In ICML, pp.
2021.
14

---

Published as a conference paper at ICLR 2024
A RELATED WORK
Differential privacy (DP, Dwork al., 2006b;a) is a widely adopted notion that could formally bound the privacy leakage of individual user information while still allowing for the analysis of population-level patterns. When it comes training deep neural networks with DP guarantees, the go-to algorithm is DP-SGD, as introduced in the seminal work by Abadi et al. (2016). This algorithm operates by clipping the contributions of gradients on per-example basis and injecting noise into the average gradient updates during each iteration of SGD.
Although several techniques have been proposed to enhance the utility of DP-SGD for specific
downstream applications (Papernot et al.. 2021: Li et al., 2022: Dörmann et al., 2021; Tramer & Bonch, 2021: Kurakin et al., 2022; Yu al., 2022; De et al.. 2022; Denison al., 2023; Cummings et al., 2023), our work primarily focuses on utilizing the standard DP-SGD framework for the purpose of generalization. We anticipate that the utility improvements demonstrated in our work can be transferred to modern techniques.
The concept of label DP was initially introduced by Chaudhuri & Hsu (2011), who established lower bounds on the sample complexity of private PAC learners. More recently, there has been growing interest in leveraging label-only privacy in the context of deep learning. The first work by Ghazi et al. (2021), which introduced Label Privacy Multi-Stare Stage Training (LP-MST), an approach for training deep neural classifiers while ensuring label DP. LP-MST operates by dividing the dataset into disjoint partitions across various stages of training. Notably, the soft output of the model from the previous stage serves as a prior, which then used to improve the accuracy of the label randomizer in subsequent stages. In Appendix F.2, they presented theoretical analysis of an algorithm referred to as LP-Normal-SGD, which involves projecting noisy gradients onto subspace to improve noise scaling. This algorithm is captured by our LabelDP-Pry family. However, to the best of our knowledge, this algorithm has not been developed into a practical one.
Malek al. (2021) introduced the idea that additive Laplace noise, combined with Bayesian inference, better aligns with the demands of learning tasks. Their contributions include the development of soft RR algorithm called ALIBI and a more intricate framework named PATE- FM. PATE-FM combines the FixMatch semi-supervised learning algorithm (Sohn et al., 2020) with the PATE private learning framework (Papernot et al., 2018). Notably, their PATE-FM framework achieves state-of-the-art utility in image classification tasks. While the benefits of integrating unsupervised learning and semi-supervised techniques into the context of label DP have also been recognized by other studies, such as those conducted by Esfandiari et al. (2022); Tang et al. (2022), it is unclear if these approaches are immediately applicable to settings like online advertisement. This is primarily due to the ambiguity surrounding what constitutes effective unsupervised feature extractor in such settings.
We also note that few previous work has explored DP-SGD with gradient projection. Yu et al. (2021) proposed Gradient Embedding Perturbation (GEP), which firstly projects individual private gradient into non-sensitive low-dimensional anchor subspace, and then perturbs the low-dimensional embedding and the residual gradient separately according to the privacy budget. However, Yu al. (2021) requires a public dataset compute their gradient subspace; while such data is possible for image classification tasks, it is typically not available for recommendation tasks, which is one of the major applications of LabelDP. Kairouz et al. (2021b) introduced a projection step to maintain the trajectory of the descent algorithm within the gradients' subspace. While this theoretically suggests faster convergence rates, empirical studies are not presented in the original work, making it challenging to establish direct comparison.
B CENTRAL DP AND LOCAL DP
Recall the definition of (c, 8)-DP in Definition 1. This notion is usually referred to as the central DP when compared to an alternative notion of local DP defined below:
Definition 5 (LocalDP: Ruskhodnikova et al. (2008)). Let Rz0. 8 E J0, 1). A randomized
algorithu R is said to be (e, LoccalD if for any two data points z, z, and any subset of outputs R, it holds that Pr( E S] < e Pr(R(=') S)+ + 6.
15

---

Published as a conference paper at ICLR 2024
In central DP, A acts trusted central server which has direct access the dataset of sensitive examples and outputs (aggregated and) privatized results. On the other hand, LocalDP assumes that no central server be trusted, and randomized mechanism R runs locally by directly randomizing each individual data point. Since the outputs of R already provide DP guarantees, they can be sent to any (potentially malicious) central server for subsequent data analysis.
LocalDP can provide privacy protection even when the trusted central server is compromised. However, the stringent guarantee usually requires a LocalDP algorithm inject extremely high noise, severely compromising the utility of data analysis, especially in the high-privacy regime. On the other hand, in central DP, the randomized mechanism A takes in an entire dataset D, which allows it to compute a distributional property of D without noise. By randomizing only the aggregated outcome, a central mechanism could better maintain the utility of distributional data analysis while still protecting the privacy of individual data points. In the context of machine learning, typical example of LocalDP mechanism is the randomized response (RR) for LabelDP, and typical example of central DP mechanism is DP-SGD.
C MEMORY-EFFICIENT PROJECTION VIA JACOBIAN VECTOR PRODUCT
We described memory-efficient algorithm to compute the gradient projection in Section 3.2 using advanced autodiff primitives. While autodiff has been widely used in various domains such as atmospheric sciences and computational fluid dynamics, in most deep learning applications, only a special case of the reverse mode autodiff is used compute the batch gradients. But as we discussed, the advanced autodiff primitives can be extremely useful to construct efficient gradient projection algorithms. We skip the details of how such primitives are realized and refer the curious readers to survey by Baydin learning frameworks such as Py ToTchh (Paszke et al., 2019), Tensorflow (Abadi et al., 2015), and JAX (Bradbury et al., 2018) are all starting provide interfaces such primitives facilitate such advanced usage.
al. (2018) and the references therein. Fortunately, modern deep
In the following we present pseudocode implementation of the two subroutines Gu for any E "2" and v + G v for any v E R that are required to compute G (Go, g). The pseudocode is written using the JAX functional style APIs, but also be implemented using the corresponding APIs in PyTorch or Tensorflow.
def G_u(f, theta, x, u): " """Computes G * using VJP (grad).
Args:
f: the neural network function that maps inputs to logits given the model weights.
theta: the neural network model weights.
x: the (unlabeled) inputs.
u: an array of shape (n2, K).
Returns:
The sum of per-example per-class gradients weighted by u, which is a nested array of the same structure as standard gradients.
def weighted (ostedetsss(ttet) logits f(theta, x)
return - sum(u * log_softmax(lggits, axis=-1))
return jax. gwad(wweighee__los)) (thet))) (theta)
def G_ G_trranspos__(C theta, x, v): """Compute GTT using JVP.
16

---

Published as a conference paper at ICLR 2024
Args:
given the model weights. f: the neural network function that maps inputs to logits
theta: the model weights.
X: the (unlabeled) inputs.
V: nested array of the same structure as the gradients.
Returns:
An array of the shape (n2, K), where each entry is the inner product each per-example per-class gradient with v.
def saw_loss(theta) logits = f(theta, x)
return - -log_ sof softmax(logits, axis=-1)
results jax.jappxa............ jvp(raw_loss, (params,), (v,))
return results
D EXPERIMENTAL DETAILS AND MORE RESULTS
D.1 BASELINE ALGORITHMS
RR-Debiased: RR-Debiased (originally proposed by Ghazi al. (2021) and was referred as LP-RR-SGD) is an extension of RR that uses unbiased loss for training. To elaborate, let us consider the multi-class classification setting where the input space is X' and the label space {I...., K}. Given a training dataset D E X x y and loss function é R x y + R. our objective is to train model f : R learn the mapping from X' to )
[K]
When using RR for training, each example (x, produces a randomized label ý: Specifically, with a probability of p : - D is set to randomly drawn value from [K], and with probability 1 - p. & is set equal to y. However, the loss ((f(r),) 9) introduces bias in estimating the true loss:
undergoes a randomization process that
[[(((()) = (1 - p) {(f(x).))
Σ ((S(c),) E(S(z).))
RE[K
To address this bias, RR-De ER-Debiased uses the following unbiased loss function (f(2).))) 8l(()) 9) {(f(z), 0) $ Emejk] (()()),
1-p
We direct the readers to Appendix F. of Ghazi et al. (2021) for more details of this method.
LP-2ST: Label Privacy Multi-Stage Training (LP-MST, Ghazi et al., 2021) trains the model on disjoint partitions of the dataset in different stages. Specifically, our evaluation adopts LP-2ST, specific configuration of LP-MST that employs two training stages, which is the primary setup evaluated in Ghazi et al. (2021). We use 40% of the data for the first stage and 60% for the second.
D.2 EXPERIMENTAL DETAILS
parrae-prrsesers We search for the best hyper-parametts settings for each evaluated approach. For each set of hyper-parameters, we launch three independent runs with different random seeds. The final results are derived by averaging the accuracy results across these three runs, selecting the configuration that yields the highest performance. Table provides the search space of hyper- also search for hyper-
parameters for results presented in the main paper. For LabelDP-Pro parameters of the memory-efficiem projection, including its learning rate in {0.01, 0.02, 0.05), training step in (100, 200, 500), and the label smoothing coefficient À in 70.7, 0.75, 0.8, 0.85).
17

---

Published as a conference paper at ICLR 2024
Table 8: hryper-araamter for experimental results presented in the main paper.
Clipping norm
Optimizer
Learning rate
# Epochs
Batch size
(DP:SGD & LabelDP Pro)
Table
SGD
{0.01, 0.1, 0.2)
{2, 5, 10)
(1024)
{1.0, 2.0,5.0 [1.0. 2.0, 5.0)
Table 5.b
SGD
(0.01, 0.01, 0.2, {0.1, 1.0)
{50, 100]
[1024]
Table 6
SGD
(1,2,5, 10, 20)
{1024)
[1.0, 2.0,
Table 7
RMSprop
(l--4, 1c-3)
(10, 20, 50)
{256, 1024, 4096)
(1.0, 2.0,
Self-supervised learning For the self-supervised learning (SelfSL) experiments presented in Section 5.3, we pretrain the ResNet-18 (He et al., 2016) model on the CIFAR-10 dataset for 1, 000 epochs using SimCLR (Chen et al., 2020a). We use the Adam optimizer with a learning rate of 1 x 10 (weight decay set 10-6) 9), and batch size of 1, 024. The pretraining takes around 26 hours on a single NVIDIA A100 GPU, with the pretraining loss trajectory presented in Figure 3.
10
7.0
Train loss
6.6
6.4
6.2
200
400
600
800
1000
Pretraining epoch
Figure Pretraining loss SenSSL with SimCLR (Chen al., 2020a) on CIFAR-10.
For our comparison with RRWithPrior (Ghazi et al., 2021), we need to split the privacy budget for querying the prior and for training the model. The allocation of the budget for the prior across different & values presented in Table 9.
Table 9: Budget for querying the prior in RRWithPrior for results in Table 6.
Budget for prior querying
0.01
0.005
0.02
0.01
0.05
0.02
0.18
0.05
0.29
0.05
0.5
0.1
1.6
0.1
D.3 MODEL ARCHITECTURE
Table 10 provides the models used for item-level evaluation in Section 5.
For the experiments in user-level evaluation (Section 6), our feature set comprises total of eleven features, including ten categorical features and one numerical feature. The categorical features are: campaign, unique identifier for the campaign, and cat[1-9], nine contextual features associated to the display. The numerical feature cost, the price paid by Criteo for this display. Our goal to predict the last-touch attribution, namely whether the final click on an impression leads to conversion. Specifically, we firstly collect a subset of data where the impression has been clicked; then create new label named Boolean AND of the original conversion label and (click pos = click nb-1). We then build model predict last touch attribution conversion based the features.
which is defined the
18

---

Published as a conference paper at ICLR 2024
Table 10: Model architectures for item-level evaluation in Section 5.
(a) Model architecture for MNIST, FashionMNIST, and KMNIST
Layer
Parameters
Convl
channels: 1, out channels: 16, kernel size: 3, activation: ReLU
AvgPool
kernel size: 2, stride: 2
Conv2
channels: 16, out channels: 16, kernel size: 3, activation: ReL.U
AvgPool
kernel size: 2, stride: 2
FCI
out features: 16, activation: ReLU
FC2
out features: 10
(b) Model architecture for CIFAR-10
Layer
Parameters
Conv1
in channels: 3, out channels: 32, kernel size: 3, activation: ReLU
MaxPool
kernel size: 2, stride:
Dropout
ratio: 0.2
Conv2
in channels: out channels: 64, kernel size: 3, activation: ReLU kernel size: 2, stride:
MaxPool
Dropout
ratio: 0.2
Conv3
in channels: 64, out channels: 128, kernel size: 3, activation: ReLU kernel size: 2, stride: 2 ratio: 0.2
MaxPool
Dropout
FCI
out features: 80, activation: ReLU
Dropout
ratio: 0.2
FC2
features: 10
D.4 MORE RESULTS
Running time We provide the single-epoch training time for baseline methods and our LabelDP-Pro in Table 11, all implemented in JAX, utiliziig fixed batch size n2 1024. For our method, we run 200 steps to solve the projection coefficients (see Section 3.2). Note that we have excluded the ALIBI method from our comparisons. This is because our experiments for ALIBI are based on the official ALIBI implementation PyTorchh, making direct runtime comparisons inappropriate. However, as presented in Table of Tang et al. (2022), ALIBI should have similar running time to LP-MST.
Table 11: Single-epoch training time (scconds) for different tasks. Results for MNIST, CIFAR-10, 10, and CIFAR- 10 10-SelfSL are reported on single NVIDIA Tesla-P100 GPU, while results for Critco Attribution are reported on single NVIDIA A100 GPU.
Task
RR
RR-debiased LP-2ST
DP-SGD LabeIDP-Pro
MNIST (Table 5)
2.40
88.34
331.30
44.52
59.93
CIFAR-10 (Table 5)
34.00
169.67
141.61
128.50
493.34
CIFAR-1O-SeLISL (Table 6)
3.35
50.89
17.93
20.07
Criteo Attribution (Table 7), =
17.52
205.67
315.69
As shown, despite the iterative steps to solve the projection coefficient, LabelDP-Pro only incurs 1.11x 3.84x computation overhead compared to DP-SGD. This is because we jax. 1ax. fori_loop() compilation, resulting in significant speedup gains. We also observe that the overhead is typically smaller for tasks with small models (e.g., MNIST-IO and CIFAR- 10-SeIS,),,,, potentially due to faster JVP because of lower weight dimension d.
JAX primitive that ensures the loops are compatible with just-in-time
Intersection point As demonstrated in Table 5, there appears be threshold g* such that when & S e", LabelDP-Pro outperforms LabelDDPPProoonpefffoms RR, but when e > e*, RR exhibit superior performance. Table 12
andis
19

---

Published as a conference paper at ICLR 2024
demonstrates how the intersection point s* varies with the number of classes (K) and the probability of catastrophic failure (6).
that the additional excess error due to privacy Table 4 decays / KKje. On the other hand, the same for VE (ignoring dependence on other
Our theoretical case study also demonstrates this phenomenon. When ef > K,
LabelDP-Pro with ALTCONV denoiser decays ~ log" log..20 (K)/ ( parameters). Thus, for fixed K, we expect RR-Debiased to outperform LabelDP-Pre for large enough &.
Number of classes (K): We find that the larger the number of classes, the larger E" becomes. This can be also be seen in our theoretical case study in Table 4, since the intersection point of
/ increases with increasing K. v KK/e and log 0.25 log /
Privacy parameter (6): Since LabelDP-Pro is an approximate-DP mechanism, we also explore the impact of varying ó, which represents the probability of catastrophic failure, on e*. find that when is smaller, E* decreases. Indeed, the reduced tolerance for failure cases necessitates the injection more noise into DP-SGD, ultimately leading to reduced utility in LabelDP-Pro.
Table 12:
The intersection section point e* under different number of classes (i.e., K) and probability for catastrophic failure (i.e., 6).
(a)
vs
(b) 8* v
K
g*
1.0 1.1
1/n
1.3 1.4
1.1 ~ 1,2
1/m
1.2 ~ 1.3
10
1.2 1.3
1/n
1.0 ~ 1.1
Item-level privacy Table 13 presents results CIFAR-10 with larger range of Table 14 and Table present results on the KMNIST (Clanuwat et al., 2018) and FashionMNIST (Xiao et al., 2017) datasets. These results align with the findings presented in Table 5 of the main paper: observe consistent improvements achieved by LabelDP-Pro over LabelDP in high-privacy settings, well
DP-SGD.
Test accuracy of LabelDP, DP-SGD, and LabelDP-Pro the CIFAR-1O dataset, for different e's. The best result each is boldfaced. LabeiDP-Pro outperforms baseline LabelDP methods the high- privacy (i.e., small E) regime.
Table 13:
Baseline LabelDP Methods
Privacy Budget (s)
DP-SGD
LabelDP- P-Pro
RR
RR-DEBIASED
LP-2ST
ALIBI
0.05
10.0
10.0
10.0
9.9
10.0
16.0
0.1
10.0
10.0
10.0
9.9
24.6
27.0
10.0
17.9
29.8
30.8
0.5
10.0
10.0
35.8
34.4
36.9
40.2
1.0
17.0
10.0
60.9
51.3
43.5
44.8
2,0
77.6
58.8
63.8
64.2
51.4
52.0
5.0
80.4
80.2
81.7
82.3
59.5
59.8
10.0
81.5
81.8
83.5
83.5
63.6
63.7
Table 14: Test accuracy of LabelDP, DP-SGD, and LabelDP- -ro on the FashionMNIST dataset, for different e's. The best result for each is boldfaced. LabelDP-PP outperforms baseline LabelDP methods in the high-pri brivacr (i.e., small e) regime.
Baseline LabelDP Methods
Privacy Budget (e)
DP-SGD
LabelDP-Pro
RR
RR-DEBIASED
LP-2ST
ALIBI
0.01
13.9
10.0
10.0
9.9
59.1
63.0
0.1
15.7
10.0
10.0
10.7
73.4
75.7
0.2
19.8
10.1
10.0
10.7
75.6
77.9
44.8
69.2
79.7
79.8
1.0
75.7
73.9
76.5
81.5
81.7
2.0
84.6
85.0
84.8
82.3
82.3
82.4
20

---

Published as a conference paper at ICLR 2024
Table 15: Test accuracy of LabelDP, DP-SGD, and LabelDP-Pre the KMNIST dataset, for different e's. The best result for each is boldfaced. LabelDP-Pro outperforms baseline LabelDP methods high- privacy (ie.. small E) regime.
Baseline LabelDP Methods
Privacy Budget (e)
DP-SGD
LabelDP-Pre
RR
RR-DEB DEBIASED
LP-2ST
ALIBI
0.01
7.6
10.0
10.0
10.0
40.6
43.4
0.1
8.2
10.0
10.0
10.8
61.1
62. 1
10.0
10.9
64.8
67.4
0.5
10.0
10.1
12.2
49.7
68.7
72.4
1.0
31.1
28.9
55.1
69.8
72.8
74.5
2.0
82.4
81.8
83.2
82.8
75
76.3
RR results in SelSL We notice that when
1.6, combining RR with SelfSL results in
surprisingly low accuracy (see Table 6), even worse than the performance of random guessing. To investigate the reason, we visualize the confusion matrices on test data for the initialized model, and for trained models with RR with initialization, the predictions are biased towards a few labels such as 'I', '5', '6', '7', suggesting that the representations from SelfSI. are probably not very balanced. With the randomly initialized weights, on average the prediction accuracy is around 10% as expected. However, we observe that after training, for 0.1, the model is severely confused by the strong noises in the training labels. maintains a strong bias to predict '1', '6' and '7', but only when the true labels are not '1', '6', or '7', respectively. As result, the accuracy is even lower than random guessing (10%). In contrast, when e is set to a larger value (say, 1.6) which returns the true label with higher probability, the model's prediction aligns better with the ground truth label.
0.1 and & = 1.6 in Figure 4. We observed that at
Initialization
Epsilon:
Epsilon:
12C
VIDI
315
95
14
379
322
71
209
2
19
100
322
16
83
148
176
220
20
36
400
4E
107
26
20
383
333
5
9
014
24
05
Thue label
16
100
115
TrUe labul
39
221
3
3
15
335
392
2
500
ARUC bbbe
54
37
P1R
22
505
51
24
300
400
301
200
300
200
200
100
-0
label
Predicted
Predicted
Figure 4: Confusion matrices computed on test data for the randomly initialized model (left), and for trained models with RR using = 0.1 (middle) and Æ = 1.6 (right). When is small, the model is highly biased towards predicting unseen example '1', '6', and '7'.
User-level privacy Figure 5 presents the distribution of the number of examples contributed per user in the Criteo Attribution dataset.
Number of users having K examples
10a
10a
Number of users
10a
10a
10a
10a
10a
200
400 Number of examples user (K)
600
800
Figure 5: Examples per the Criteo Attribution dataset.
21

---

Published as a conference paper at ICLR 2024
E PROOFS FOR THEORETICAL CASE STUDY (SECTION 4)
E. EXCESS ERROR IN STOCHASTIC CONVEX OPTIMIZATION
For completeness, we prove Lemma 3, restated below for convenience. standard analysis of projected gradient descent (see, e.g.. Hazan (2022)).
The proof follows from
Lemma 3. For convex loss function L, and a gradient oracle with bias a and expected squared norm C² PGD over a convex S R with diameter R and step size dl TVT achieves the following expected excess risk bound for the average iterate wr == -r-1 wt
RC VT
([C() ((ww") S + aR.
(1)
Proof. Suppose we have gradient oracle with bias a and expected squared norm Č Let 9: ([(w) denote the true gradient, and let 9i denote the stochastic gradient received at step Let
et = St 9: be the error in the stochastic gradient. We have that || E e S and E |gr C2.
Recall that PGD operates by computing w/+11 <- Projx n/tt). We have
((w;) L(w")
(gt, Wi w*)
(et, wi w") + (g., w")
(er, w. w" + (11::, WP ==²)
(er, Wi w 0') + 21 (I/w, - w" 1/2 + 17 19 - ||w, - 7/9r w" ((3)
(er, Wi w") + 27
L (Ilw, w" 1/ + 1/² 11 1 || w 112)
(e,, wi- - w²) + aاا@ + 2n (Il - w l| | w 11))
where the second inequality is due to the fact that w.+1 is projection of we n9: onto I. and un E KC, and hence ||up,-1 - ur" S lun, n9: ur"
Averaging over = .,..., T 1 and using Jensen's 's inequality we have for ur = + T'1 w. that ((wr) [(w")
1 1 7 Σ ((w,) - L(w")
s T llwo w= 112
E (er, we w²)
R²
19
Et= (e,, w, w²)
TT
Taking expectation on both sides and using the convexity of L, we have
R²
0
T-1
B[[(wr) - [(w")] 5
E [(e,, wi w''l
2T
2
T
t=
R2
1
R Beele
2n/
T
1=0
R²
C
+ +aR
TT
RC
R ÖUT
aR
for 1l
VT
E.2 ERROR BOUNDS OF STOCHASTIC GRADIENT ORACLES
We analyze the enror introduced by various stochastic gradient oracles thereby using Lemma 3 to obtain excess rates for projected gradient descent. First, we observe that just sampling a mini-batch l already introduces some variance in the stochastic gradients, which can be bounded as follows for C-Lipschitz losses.
22

---

Published as a conference paper at ICLR 2024
We use the following notation in this section. Let g [(w) LiEin) V Vwl(w; Vc). For
randomly sampled mini-batch le S [n] with [ = 71, let g = Ligjo V (w; 9i).
Lemma 6, Over the choice of a random subset 1 C [x] with |G| = n1 it holds that
Eg -9
and
E [ 2ll S
Proof. The first part holds by the linearity of expectation. To show the second part, let v; = V Vol(w; y4) g- We have that EiE(n] 8 0. Hence for indices i, sampled without
replacement from [n]]. it holds that [(v w,)] < 0, since E/oy/o,] = uu,(n 1). Hence we have
E | -l1ø] = E
1 Eigra
EiEro E
1 |2 + +
Bi w,حl
<
C²
We now analyze the excess error introduced by stochastic gradient oracles considered Table 4, and explicitly focus the additional excess that introduced due to privacy. In order to do so, we note that the non-private mini-batch gradient averages have variance n, the PGD with this oracle achieves an excess error bound of RC
C due to which
(2)
VT
The instantiations of LabelDP-Pro operate by obtaining a noisy gradient estimate gg¹ + for aPce I), and then potentially projecting it. The addition excess error incurred due to NO, Tu
privacy can deduced by subtracting (2) from the error bound.
NoOP (same as DP-SGD). The vanilla DP-SGD algorithm performs PGD using stochastic gradient with zero bias (i.e., 0) and variance w² C do'c" where recall that d is the dimension of the parameter The first term of the variance comes from Lemma 6 and the second term is due to the addition of noise. Using Lemma 3 and subtracting (2), this implies that the additional excess error bound due to privacy is
O
RC VT
daa Von
SELFSPAN. Recall that this stochastic gradient oracle returns & = Proja(ğ) where A span (fV (I;,k) he Since g' A, we have that غ = (e)) This span has dimension most Kn1, which can be much smaller than d. Hence, this stochastic gradient oracle has zero bias and variance 2 C² Knja²C² Using Lemma and subtracting (2), this
implies an additional excess error bound due to privacy of O RC VKo).
Thus, we have reduced the Vd/n1 term in excess enror rate VK. However, this comes price! Unlike DP-SGD, cannot leverage amplification by subsampling because the (unlabeled) examples were used to define the span on which the noisy gradient was projected. Thus, the noise multiplier a required for the same privacy guarantee (roughly /n/nj times) larger, due to which this bound is incomparable to the bound of DP-SGD.
SELFCONV. Recall that this stochastic gradient oracle returns á = (r)j where = conv ((V l(w, (Ie, 1i) ()) We show the following.
Lemma 7. Let 1G S [n] be random subset of size ny. Let ğ denote the noisy gradient estimate from TG, namely, 9 = "n Eiero Vwl(w,; I4, yb) + e for e ~ N(0, d'c" I). Let A conv (VV,elur, (xi, (e) denote the convex body on which we project. Then,
23

---

Published as a conference paper at ICLR 2024
the choice of I and e, we have
E (
S 0
C²
o /oog Kni) via
Proof. Let 2 = Proja (g). Since A is a convex set, we have (2 15--0 n, 9) S 0, for all E A. By definition, we have that g' E A and hence setting v = g and rearranging, we arrive at
g g²) (2, E)
maxf/ (0, UE
(since & E A) max (wwl(w; Ki), e) : iE B2, R E [K])
oC (og((Km)))
Thus,
E -
O
V/n
which follows by observing that Wwl(w; k)ll I C and using the standard bound on the Gaussian mean width of convex hull of a finite set. Thus, by the triangle inequality and using Lemma 6, we have that
E [| [
< 2E |1la
gll + + 8'1
C
o0 Voge (on(
v
Thus it follows that the SELFCONV stochastic gradient oracle has bias and error most
o 0 Vsj
vo (lo((Kn)) fni
Moreover the expected square gradient norm C s C (since
all vectors the convex hull have norm at most C). Using Lemma and subtracting (2), this
implies an additional excess error bound due to privacy of
o RC'
/a (log(Kmn)
VPI
Vn1
But in SELFSPAN, we cannot leverage amplification by subsampling and the noise multiplier here is (again, roughly / /n/n1 times) larger compared to DP-SGD. However, we have non-zero bias, and hence a non-vanishing (in ?') term.
ALTCONV. Recall that this stochastic gradient oracle returns z = (r) where A conv (VV wel (2i, 1:) kr) We show Lemma 4 restated below for convenience.
Lemma 4. Let 10, IP S [n]] be random subsets of size n1, n2 respectively. Let denote the noisy gradient estimate from 1G namely, ğ = no Eigro Vwe(w, Tis Vi) + e for e NO0 d²c². I). Let denote the convex body on which we project. Then, over
A = conv ((V.)) E (zi,
the choice of G IP, and e, we have
E [1] ( -913] S 0 C2.
(ce.
( 12
a (ogoog(K
n2
/ni
Proof. Let 9 92 denote the gradient estimates from G 1 respectively. Formally,
9 = ni Eiero Vwe(w: F4, Vi),
g² na Eier Vwl(w;
Let = Proj (g). Since A is convex set, we have:
(ž - v, & - g) S 0,
for all A.
By definition, we have that g² E A and hence setting w 92 and rearranging, we arrive at
(z 92, 2 -- g²) < (ž,e)
S max (0, e) : u A (since & E A)
maxfl (V 2 2), e) : Bz, [K]]
a02 1oo2/on (og((nn))
Thus,
E [
-2, -0-)] < o
24

---

Published as a conference paper at ICLR 2024
which follows by observing that V I;, K)ll Σ C and using the standard bound on Gaussian mean width of convex hull of a finite set. Thus, we have that
E. [|
9
8'1l2
s E - 9 12 +
--
E |ll 22 - g²)
oC* Vooslog(KMn Kn))
vun
where the last step uses Lemma 6. Thus, we have by the triangle inequality that
I 2E
|||
g g + llg g3ا2و S o
C²
1
/log(ng)) Kng)
Moreover the expected squared gradient norm 8 norm at most C). Using Lemma and subtracting (2), this implies an additional excess error bound due to privacy of
< C (since all vectors in the convex hull have
o O RC
(++++
vo (log((mg))
While we again have non-zero bias, and hence a non-vanishing term (in 7), we can leverage amplification by subsampling!
RR-Debiased. Recall from Appendix D.I, that RR-Debiased uses gradient oracle that first samples E [n)], and using p = e samples random label Ú: as
p(K-1)
if D 91
PríM y)
if U: + Vi-
K
and then returns the stochastic gradient
V Vw E < Fi, 01) - K EnE(K] V m Zi, xw;
g
1-2
For ease notation, let gz.y == V ww x, y). is easy to see (also shown in Ghazi et al. (2021)), that this stochastic gradient has zero bias (i.e., E[g] g). Moreover, the variance of the stochastic gradient introduced by the randomized response for any fixed (Ii, y:) is given as
E [l]@- Incvel
E
I0..8:
P
Σ
I8. (1 - p)
2
K
KE[K]
(1 p kc) 11pp- (1- k )g En I2.
E
(1 p)2
[ Σ
N' # [1 -i k) -k Exeeet Ix., - (1 p & kg
p
C
(1 p)
Note that Ghazi et al. (2021) also establish bound on the variance, however, they state an approximate version that is only applicable when = & 1: whereas, the above bound holds for all In fact, their version follows from the bound above, since for < 1, Re 1 and p Rz KK and thus the bound becomes 02 p k/e and p and hence the bound is O(C² K/e*).
On the other hand, when e > K, we can approximate
Finally, when using mini-batch 1 with प = 71, the variance due to randomized response reduces by factor of 1/n,, and hence using Lemma 3 and subtracting (2), this implies additional excess error bound due to privacy of
RC VI
v
[1-plymn
25


Reviews:
[{"review_id": "cC8j02bhK3", "reviewer": "Reviewer_3Pz1", "summary": "This work considers training under label differential privacy by projecting the DP-SGD gradient onto a gradient subspace that only depends on the features. Experiments show that the algorithm works well in the high privacy regime ($\\varepsilon <1$). Theoretical analysis proves convergence in the stochastic convex optimization setting.", "questions": "1. Could you explain why the proposed algorithm underperforms the best baseline by a large margin when training from scratch for $\\varepsilon \\ge 1$? \n2. When using pre-trained weights from SSL, the result for $\\varepsilon > 1$ is much better. Maybe this is due to a more accurate gradient subspace after SSL pretraining?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea to project the noisy gradient of DP-SGD onto a smaller subspace is simple and intuitive. \n2. The authors also address practical issues of memory efficiency and stability when calculating projections, which makes the algorithm more practical.\n3. The experiment result is encouraging for the high privacy regime ($\\varepsilon < 1$)\n4. The algorithm has theoretical support which shows that dimension-independent convergence rate can be achieved under stochastic convex optimization.", "weaknesses": "1. The user-level private algorithm only leverages group privacy, which is extremely sub-optimal even in the simple problem of mean estimation. A good user-level private algorithm should go beyond the simple application of group privacy.\n2. For $\\varepsilon \\ge 1$ in Tables 5 and 6, the proposed algorithm underperforms the best baseline by a large margin. In practice, it is still reasonable to use $\\varepsilon < 5$, so it would be better if the algorithm could also perform well for moderate level of privacy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bvihbn9p79", "reviewer": "Reviewer_Taxi", "summary": "Paper proposes to use DP-SGD (private features and labels) in a label-only DP setting. It then proposes a way to de-noise DPSGD noisy gradients by projecting them to a convex hull build out of gradients derived only from the features (calculating gradients per existing label class). \n\nPaper then shows how this de-noising process can be made compatible with privacy amplification by subsampling that is fundamental to utility-privacy trade off in DPSGD.", "questions": "I would like to see results of the proposed algorithm for epsilons between 1 and 10 too (for a fairer comparison and decision making for interested users). \n\nI would like to see an empirical epsilon study (like the one referenced by authors, e.g. Malek et al. 2021)\n\nI would like to see studies on CIFAR-100 (along with comparison with SOTA)", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Paper proposes a novel gradient denoising method in label-only private settings. The proposed algorithm outperforms SOTA in high privacy regime on small public datasets like MNIST and CIFAR-10.", "weaknesses": "The main issue with applied DP is that production use cases really crave performances close to non-private regimes. Label private settings are very important for ads and marketing use cases and accuracy is of utmost value in these settings. Developers will prefer a medium privacy regime with very close to non-private utility compared to a highly private regime with very low utility. \nFrom the paper results, trends suggest that the proposed algorithm gets inferior to SOTA as epsilon starts to pass 1 which I think is the most important hurdle in using the proposed algorithm in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "khjD5m2sV7", "reviewer": "Reviewer_zF53", "summary": "This paper studies the algorithm design for label differential privacy (label-DP), where the labels in the dataset are private and the features are public. Previous label-DP algorithms are in the framework of random label flipping. This paper proposes a novel algorithm which utilizes the framework of DP-SGD. By the empirical evaluation, the proposed algorithm has the advantage over previous algorithms in the high-privacy regime.", "questions": "Please check the details in \"Weaknesses\" above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The clarity is great. The arguments are well-explained and the structure is good.\n2. The proposed algorithm is novel. It is different from previous algorithms which are in the framework of label random flipping. It instead utilizes the DP-SGD framework.\n3. It derives the theoretical utility-privacy trade-off for DP convex optimization and compares this trade-off among different versions of their algorithm.\n4. The proposed methods and baselines are evaluated on both the image benchmark and the Criteo dataset.", "weaknesses": "Both the proposed method and baseline numbers in the experiment can be potentially better. As they might be underestimated, the current comparison could be inaccurate, which is the main evaluation to illustrate the advantage of the proposed algorithm.\n- The pure DP-SGD can be much better, which can potentially bring benefits for the proposed algorithm. For example, De et al., 2022 empirically show that DP-SGD can achieve 56.8% accuracy on CIFAR10 when $\\varepsilon=1.0$, while the number reported in the paper is only 43.5%.\n- ALIBI's accuracy on CIFAR-10 is reported as 51.3 when $\\varepsilon=1.0$ in Table 5 in the paper, while in the original paper (Malek et al. (2021)) ALIBI achieves 71% when $\\varepsilon=1.0$.\n- When leveraging self-supervised learning with LabelDP, PATE-FM doesn't utilize the SelfSL on CIFAR-10, which seems a little unfair. It is reasonable to at least utilize a pretrained feature extractor as an initialization instead of random initialization when training teachers in PATE-FM. In this way, PATE-FM leveraging SelfSL is expected to have better accuracy.\n\nMoreover, DP-SGD with gradient projection actually has been investigated for a while [1, 2] and not introduced in the paper. Although I still agree with the novelty of the proposed method given that all previous labelDP algorithms are based on label flipping, it might be worthwhile to see the difference and comparison between the proposed method and the methods in the literature.\n\n[1] Yu, Da, et al. \"Do not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning.\" International Conference on Learning Representations. 2020.\n\n[2] Kairouz, Peter, et al. \"Fast dimension independent private adagrad on publicly estimated subspaces.\" arXiv preprint arXiv:2008.06570 (2020).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zKYs4kXYo5", "reviewer": "Reviewer_NHnW", "summary": "This paper introduces a cute idea -- leveraging the feature vectors (which are non-private under label DP) to construct a prior, which helps to reduce the noise required for label DP. To this end, this paper considers label-DP in the central model rather than the previous local model. Some theoretical results and experimental results are provided.", "questions": "I think this paper introduces some nice ideas and I also enjoyed reading this paper. \n\nI have some clarification questions so as to ensure I did not miss something. \n\n1. [Regarding the subtlety of privacy analysis of SELFSPAN]. If I understand it correctly, the problem is that even though the additional projection step does not touch sensitive data (labels) in this case, one cannot directly use post-processing. This is because the projection will leak the index of the sampling result, which then impacts the privacy amplification by subsampling in the original DP-SGD. Due to this, when using SELFSPAN, one cannot enjoy the gain/benefit of subsampling. On the other hand, since it does not touch labels, one can still use post-processing over the **non-subsampling** version of DP-SGD?\n\n2. [Regarding the improvement over DP-SGD] It seems to me that the main gain over DP-SGD is the improvement over dimension d? It might be better to give more discussions on Table 4, as there are different choices of \\sigma. Being more specific or using more particular values will be better I think. \n\n3. [Confusion about the section name] For Section 4, the authors use SCO, which gives readers the impression that the goal is somehow the population excess loss. However, it turns out the authors are actually analyzing ERM. It might be better to replace the section name.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of leveraging feature vectors to boost the performance under the label DP is cute.\n2. A good balance between theory and experimental results, which is a good fit for ICLR.", "weaknesses": "I think the comparisons in the theoretical part need to be clear, i.e., what's the exact gain of the proposed method?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)