Bit-aware Randomized Response for Local Differential Privacy in Federated Learning
Authors: Phung Lai
Hai Phan
Li Xiong
Khang Tran
My Thai
Tong Sun
Franck Dernoncourt
Jiuxiang Gu
Nikolaos Barmpalios
Rajiv Jain
Venue: ICLR 2022 Submitted (2022)
Keywords: local differential privacy
federated learning
bit-aware

Abstract: In this paper, we develop BitRand, a bit-aware randomized response algorithm, to preserve local differential privacy (LDP) in federated learning (FL). We encode embedded features extracted from clients' local data into binary encoding bits, in which different bits have different impacts on the embedded features. Based upon that, we randomize all the bits to preserve LDP with three key advantages: (1) Bit-aware: Bits with a more substantial influence on the model utility have smaller randomization probabilities, and vice-versa, under the same privacy protection; (2) Dimension-elastic: Increasing the dimensions of embedded features, gradients, model outcomes, and training rounds marginally affect the randomization probabilities of binary encoding bits under the same privacy protection; and (3) LDP protection is achieved for both embedded features and labels with tight privacy loss and expected error bounds ensuring high model utility. Extensive theoretical and experimental results show that our BitRand significantly outperforms various baseline approaches in text and image classification.

Under review as a conference paper at ICLR 2022
BIT-AWARE RANDOMIZED RESPONSE FOR LOCAL DIF- FERENTIAL PRIVACY IN FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we develop BitRand, bit-aware randomized response algorithm, to preserve local differential privacy (LDP) federated learning (FL). We encode embedded features extracted from clients' local data into binary encoding bits, in which different bits have different impacts on the embedded features. Based upon that, we randomize all the bits to preserve LDP with three key advantages: (1) Bit-aware: Bits with a more substantial influence on the model utility have smaller randomization probabilities, and vice-versat under the same privacy protection; (2) Dimension-elastic: Increasing the dimensions of embedded features, gradients, model outcomes, and training rounds marginally affect the randomization proba- bilities of binary encoding bits under the same privacy protection; and (3) LDP protection is achieved for both embedded features and labels with tight privacy loss and expected error bounds ensuring high model utility. Extensive theoretical and experimental results show that our BitRand significantly outperforms various baseline approaches in text and image classification.
INTRODUCTION
Recent data privacy and security regulations (GDPR 2018 Regulation 2018
Cybersecurity Law
2016) pose major challenges in collecting and using personally ly sensitive data in different places for machine learning (ML) applications. Federated Learning (FL) (McMahan et al.) 2017 Kairouz et al.) 2019) is promising way to address these challenges, enabling clients to jointly train ML models by sharing and aggregating gradients computed from clients' local data through coordinating server for model updates. However, recent attacks (Zhu et al., 2019) Y. et al.) [021]] Zhao et al. (020aa) have shown that clients' training samples, each which includes an input ir and a ground-truu label ya can be extracted from the shared gradients. These attacks underscore the implicit privacy risk in FL.
Our main goal to provide a strong guarantee that the shared gradients protect the privacy of clients' local data without undue sacrifice in model utility. Local differential privacy (LDP) has emerged as crucial component in various FL applications (Yang et al. 2019; Kairouz et al. 2019). To achieve our goal, we focus on preserving LDP in cross-device FL, i.e., in which clients jointly train an FL model (Kairouz et al. 2019).
In cross-device FL. existing LDP -reeeeeeegi approaches can be categorized into three lines: Clients (1) add noise into local gradients derived from their local training samples, e.g., using Gaussian mechanism (Abadi al. 2016), protect membership information the training sample level with
DP guarantees (Zheng et al. 2021 Dong et al.) 2019: Malekzadeh et al.) 2021 Geyer et al., 2017]
Huang et al., (2020). (2) add noise local gradients using Randomized Response (RR) mechanisms
to protect the values of the local gradients with LDP guarantees (Sun et al. 2021 Liu et al. 2020
Zhao et al., 20206 Wang et al., 2019a), and (3) add noise into each training sample, e.g., embedded
features and labels, using RR mechanisms to protect the value of each training sample with LDP
guarantees (Arachchige et al., 2019 Lyu et al., (020a), then the clients use -DP-presereed training samples to derive local gradients. For all three approaches, in each training round, clients send DP or L.Pe-preeereed local gradients to the coordinating server for model updates, which will be sent back to the clients for the next training round.
In this paper, we focus on protecting clients" training data at the value level with LDP guarantees. Existing RR mechanisms to preserve LDP in FL suffer from the curse of privacy composition, in which excessive privacy budgets are consumed proportionally to the large dimensions of input or embedded features (Arachchige et al., 2019). gradients (Zhao et al.) 2020b; Wang al. 2019a), and training rounds (Zhao et al. 2020b Wang et al.] 2019a), causing loose privacy protection or inferior model accuracy (Wagh et al. 2021

---

Under review as a conference paper at ICLR 2022
Addressing the curse of privacy composition is non-trivial. Existing approaches, such as anonymizers
(assumed to be trusted), i.e., shuffler (Erlingsson et al. 2019 Sun et al. 2021 L. et al. 2020 Wang
et al. 2019b] Cheu et al.. 2019; Balle et al. (2019)
anonymity approaches (c.g.. faking source IP. VPN, Proxy, etc. (Sun et al. 2 Cormode et al. 2018), and dimension reduction (Liu et al. 2020)
Zhao et al., 2020b] [Shin et 2018 Xu et al. al.12009 mitigate the problem but also have limitations.
In the real world, it is possible that the anonymizers can either be compromised or collude with the
coordinating server to extract sensitive information from observing LDP-preserved local gradients (Erlingsson et al. 2019). Meanwhile, applying RR mechanisms on reduced sets of embedded features or gradients using dimension reduction techniques can work well with lightweight models, such as logistic regression and SVM (Liu et al. 2020 Zhao et al. 2020b; [aang et al. 2019a). However, it challenging for these techniques to achieve good model utility under tight LDP guarantees given complex models and tasks, such as DNNs, since the dimensions of reduced embedded features, gradients, and training rounds still need to be sufficiently large (Zhao et al. 2020b; Liu et al. 2020).
Hence, the curse of privacy composition in preserving LDP by applying RR mechanisms in FL remains a largely open problem. Orthogonal to this, preserving LDP to protect ground-truth labels Y/ in FL has not been well-studied. Two known approaches for centralized training are 1) injecting Laplace noise into the labels (Phan et al. (2020) and 2) applying RR mechanisms on the labels to achieve DP at the label level (Ghazi et al. 2021). However, centralized training in Ghazi al. (2021) has not been designed for FL with LDP guarantees since they require centralized and trusted databases. The model utility in Phan et al. (2020) notably affected by the number of model outcomes.
Key Contributions. To mitigate the curse of privacy composition and optimize the trade-off between privacy and model utility, our paper is structured around the following contributions:
1) We propose BitRand, which is a combination of a novel bil-aware f-RR mechanism and label-RR mechanism, to preserve LDP at both levels of embedded features and labels in FL. In f-RR, we encode embedded features (extracted from x) into binary-bit bit string. which will be adaptively randomized such that bits with a more substantial impact on model utility will have smaller randomization probabilities and vice-versa under the same privacy budget. To preserve LDP on Yz. we develop generalized randomization, in which the probability of randomizing label ye from one to another class is a function of the number of model outcomes C. By doing that, we can optimize the trade-off' between model utility and privacy loss with significantly tighter expected error bounds.
2) By incorporating sensitivities of binary encoding bits into a generalized privacy loss bound, show that increasing the dimensions of embedded features r. encoding bits I, and model outcomes C marginally affect the randomization probabilities in BitRand under the same privacy budget. This dimension-elasiie property is crucial to evade the curse of privacy composition by retaining a high value of data transmitted correctly through our randomization given large dimensions of r, L, and C. 3) These bit-aware and dimension- -laastic properties allow us to work with complex models and tasks with formal LDP guarantees for training samples (æ. Uz.) while retaining high model utility. Extensive theoretical analysis and experimental results conducted on fundamental FL tasks, i.e., text and image classification, using benchmark datasets and our collected Security and Exchange Commission financial contract dataset show that our BitRand significantly outperforms variety of baseline approaches in terms of model utility under the same privacy budget.
BACKGROUND
prreerreng mechanisms (Erlingsson et al. 2014 Duchi et al., 2018 Wang et al. 2017 Acharya al. 2019]] Bassily & Smith 2015) generally build on the ideas of randomized response (Waner 1965), which was initially introduced to allow survey respondents to provide their correct inputs while maintaining their confidentiality. c-LDP is presented as follows:
Definition 1. e-LDP. A randomized algorithm M fulfills e-IDP,, if for any two inputs x and x', and for all possible outputs O E Range(M), we have: Pr[M(z)= = O) S e Pr[M(x') = O), where e is privacy budget and [ange(M) denotes every possible output of the algorithm M.
The privacy budget controls the amount by which the distributions induced by inputs x and x' may differ. A smaller c enforces a stronger privacy guarantee. We revisit RR mechanisms for LDP preservation in Appendix A Our approach is binary encoding mncddng-bbsee approach, similar to (Arachchige et al. 2019||yu et al. 2020a). since has the potential to overcome the curse of privacy composition. In binary encoding, is converted into an (-bit vector consisting of 1 sign bit, bits for the integer part, and 1-m-1 1 bits for the fraction part (Figure II. as follows:
Vi E [0, 1] : 04- = 22 -- [x]]] mod?
(I)
2

---

Under review as a conference paper at ICLR 2022
Each bit in is randomized by applying RR mechanism, e.g.. (Erlingsson et al. 2014; Bassily & Smith 2015 Wang et al. (017)) 7 to generate perturbed 7-bit vector v', which preserves LDP. However, in our theoretical reassessment directly applying RR mechanisms on binary encoded vectors as in existing mechanisms. i.c.. LATENT (Arachchige et al., 2019) and OME (Lyu et al. 2020a), consumes huge privacy budgets since each binary encoding bit cannot be treated as a bit in hash. Each binary encoding bit has a different sensitivity, i.e., A; = 2m for the integer and fraction parts or A 2 I for the sign bit (Lemmall D. compared with a bit B; in a hash, i.e., vB; Ap. 1. Our mechanism does not suffer from this problem, thanks to our bit-aware randomization binary encoding (Theorem) 2
Integer
Fraction
201-1
20-- go--2
2
2
2nd
Higheet
(Appendices[[
Integer
Integgr
Figure 1: Binary encoding.
3 BITRAND ALGORITHM
Coord Server (henest but curious
Let us now present our FL setting, threat model, and BitRand algorithm (FigureZande and Alg. [ Appendix B). and privacy guaran- tees. Then, we will show that our algorithm is dimension-elastic and the ability to opti- Figure 2: Federated Learning with BitRand Algorithm.
Froh soltactor
P-FR
Training prosel
Devviture g"*1
book dama
Tmode 271)
givs
mize the randomization probabilities with expected error bounds in our theoretical analysis.
Federated Learning Given N clients, each client u E [L, NJ has a set of training samples D {(x, [o)] where x E Rd is the input features, and its associated ground-truth label ye E 2 is one-hot encoded with C' categorical model outcomes -. Mr,C) J. and nh is the number of training samples. In a pre- pre-processsig step, each client u extracts r numerical embedded features from I, denoted ez2 by using pre-trained model frre, In practice, fore could be trained on large-scale and publicly available datasets without introducing any extra privacy cost to the clients' local data (He et al., 2 Devlin et al. 2018). N clients jointly train the model f IR"" RC by minimizing a loss function (ex),, Ma) on their local training samples in D', that penalizes mismatching between the prediction (ex) and the ground-truth label Yn. given the model's parameters O. In each training round I, each client u receives the most updated model parameters O from the coordinating server and then computes local gradients Vb. (vs.B.))D Vo, ((((e)) Nw) /Tn, which are sent to the coordinating server for aggregating and model updating: 0.+1 0: - T/c Σne(I,N) /
Threat Model. The coordinating server strictly follows the training procedure but curious about the training data D.. This is a practical threat model in the real world since service providers always aim at providing the best services the clients (Haeberlen al. 2011 Truex et al. 2019 Lyu et al., 2020b). Given the observed gradients V the coordinating server can extract the clients' data {ez, Mn. by using recently developed attacks (Carlini et al. 2020 Fredrikson et al., 2015). In a defense-free environment, {ez. 3x. can be used to infer the sensitive training data D2 ((x, Va)],., using the pre-trained model fare, since f = ex (Song & Raghunathan 2020 This poses a severe privacy risk to the sensitive data Da.
BitRand Algorithm. To protect the sensitive training data D,, against the threat model, in our algorithm, we preserve LDP on both embedded features eg and labels yz-
Each of the embedded features in e, is encoded into I binary bits following Fq. Binary encoded features are concatenated together into vector Ur consisting of rl binary bits to represent the embedded features eg (Alg. [ line 16). Each bit i E 10, 1] in ea is randomized by our f-RR mechanism (Alg. line 17) with bit-aware term 1%l optimizing randomization probabilities:
px + a exp( a exp( ex) [x = + exep
if e (i)
(f-RR mechanism) We (0, P(v.() = 1)
(2)
if U2 00
where (i) E {0, 13 is the value of Ug at the bit i, v/ the perturbed vector created by randomizing
all the bits in Uz, ex is privacy budget, and is a parameter bounded in Theorem 2 From Eq. 2
we also have that P( (i) 0) = - px if (1) = 1, and ((v = 0) = 1 qx oz (i) We use the bit-aware term 1% to indicate the location of bit i, which is associated with the sensitivity
of the bit at that location, in its l-bit binary encoded vector among rl concatenated binary bits.
3

---

Under review as a conference paper at ICLR 2022
2021 Zhao ct al. 2020b Wang et al. 2019a; Liu et al. 2020; Arachchige et al. 2019 Lyu et al. 2020a) is the
One of the key differences between mechanism and existing works (Sun et al.
bit-aware randomization probabilities. By introducing the bit-aware term 270t we are able to: I) Derive significantly tighter privacy loss and expected error bounds compared with existing approaches (Sections 4 and and 2) Adaptively control the randomization probabilities across bits, such that bits with a stronger influence on the model utility, e.g., sign bits and integer bits, have smaller randomization probubilities qx, and vice-versa (Section[5) (5). These advantages are crucial to evade the curse of privacy composition enabling to work with complex tasks and models (Section 6).
In addition, inspired by the LabelDP (Ghazi et al. 2021), we randomize Us using the following label-RR mechanism (Alg. line 18):
py = exp(3)
if Uo = Uv
1 ex)((())
(label-RR mechanism)
P(v'= = Mo) =
(3)
qr +1+ exp()() 11 if To # Uns Us E
where Ds is one-hot encoded, and .3 is a parameter bounded in Theorem 3 under a privacy budget ey,
Randomizing the label ys provides complete LDP protection to each local training sample (ens Uz). All the perturbed training samples (e'2 Vir) are included in a local dataset D', which will be used to train the model fo R' - RC, i.c., e = E(e') where E-) is a decoding function, (Alg. lines 20-22). The training will never access the original data D.. All other operations remain the same with our aforementioned FL setting.
4 PRIVACY GUARANTEES OF BITRAND
In this section, we focus on bounding formal privacy loss of BitRand for input and label protection. To achieve our goal, we need to bound and Eqs.
2 and such that our algorithm preserves LDP for each training sample (z, Mnr) E D,, given (v'z, 1/) D', Note that the decoding ez = E(e') does not incur any extra privacy risk following the post-processing property (Dwork & Roth 2014). Given Ug and U2 can be different at any bit, for the LDP condition to hold, the ratio of two probabilities P(J-RR(v))=e) needs to be bounded by exp(Ex) with U2+ Rangeef-RR).
P[F-RR F2) mPs)
Given a feature a, i.e., one of the r features, let us first consider a bit in the encoding vector uia- Intuitively, when we apply our f-RR only on the bit i in Ua (i.e., all the other bits remain the same), denoted as f-RR(tu. (va. i). the l--sesittivity of the bit is 1. This is because, given two neighboring vectors vo and Vali that differs only at the bit i, we have that Vi E Uo. arg max., f (V. i) f-RR(V.je. i)]l = 1. However, the coordinating server can infer the decoded features (ff-RR( instead of just the intermediate result f-RR(e.). Thus, we need to quantify the L iy-sensitivity of single encoding bit E Un to determine just how accurately we can return the decoded features E(f-RR((a)) through our randomization f-RR applied on Va- Following (Dwork & Roth 2014), the sensitivity A, of a bit can be quatified as follows:
Definition 2. Bit l--snsiitivi,,, Given two neighboring vectors Va and Vali that differs only bit i, the sensitivity Ai captures the magnitude by which the bit i can change the decoding function E(f-RR(-) in the worst case, as follows:
Vi [0, 1]:
max max - E(F-RR(va)))
vo
Based on Eq. 4 sensitivities A, of all the bits in u2 are bounded in the following lemma.
Lemma 1. The 4 i-sensitiviiy of a single binary encoding bit is bounded as follows:
2
if is sign bit
[0, - : = 2 if i is an integerffraction bit
(5)
All the proofs are in Appendix. Unlike existing RR mechanisms, we incorporate the lisensiitvvtty A; into the privacy loss bound of f-RR by ensuring that the privacy loss in randomizing a bit i is bounded by the privacy loss in the embedded feature space. By doing so, we can derive tighter privacy loss bounds as discussed next.
Given A, there always exists a Laplace noise injected into the feature a, i.e., i) E(v.)
Lap( A,/6), to achieve GDP in the embedded feature space (Dwork & Roth 2014). In other ((((e))-
words, P(M(e..))=)) I exp( A.
and 2 E RM) To ensure that the privacy loss
)(M
4

---

Under review as a conference paper at ICLR 2022
in randomizing the bit i bounded by the privacy loss in the embedded feature space is to find in Eq.
such that: P))-)R(ea.))=1))) S exp( (=1((vs)=_(vv:s))) However, randomizing a binary encoding
Plf-RR(vaj.:))m))
A;
bit given C4 and Vals results in a smaller 1 -iiittaece (ff-RR(R (Uay 2)) E(f-RR(v, is i)) compared with E(va)= :(aa since [E(f-RR("a: 1)) E(f-RR(uott 1)) - [E(v,) - E() Thus, can derive a tighter bound by replacing (E(v,) EveNp)) with ( (ff- i)) (ff-RR(Vaa) E)
Given (i) is the bit i in Ca. we have
P(S-RR(Ve === vs) P(f-RR(U.. (u 1) =z) ((F-RR((a)(()) vo))
P( (1)) (i))
P(ua(j) = vz(i))
II
P(Na)(()) (2)
P(A-R((V(()== (i)
C(E(F-RR(V,,)) 1)) E(f C(f-RR((M.)s O)
((F-RR(Va):()) v.) exp(
(6)
A
However, finding a closed-form solution of a for the tight privacy bound in Eq. is non-trivial, since (n. m
is intractable. To address this, we consider two cases: (1) P(FRR((P, = (i) 2 1 below, and (2)
0 < P( ST-- P. (0)== can change the decoding function E.) in the worst case, we have |E(F-RR( E(F-RR( ..] 2 1.
(f, (1)
in Appendix Since AS captures the magnitude by which the bit i
A.
As result, have
P(SRRR (1) v=(i)) P(f-RR( U. (()) = (i)) P(f-RR(C.) = U. (i)
P(J-RR(e e. (i) = vi)
S exp(e))
(7)
Eq. enables quantify generalized privacy loss bound of RR mechanism, in which different
bits have different sensitivities by randomizing all the bits in Us independently in Theorem ||
Theorem 1. Generalized privacy loss bound. The privacy loss for randomizing binary encoding
vector Uz is bounded as follows:
P(f-RR(Vz) = vx) P(f-RR(T=) e.)
rl-1
(2 (1) (1)) (1) u ((ff-R(U (P v (1)
$ II i=D
exp(
6))
(8)
2
Now, enforce the condition Er'o & cx ensure that the total privacy budget will be bounded by cx. Based upon that, we derive a closed-form solution showing that there always exists an upper bound of a so that v' preserves cx-LDP given Ug in Theorem 2 (Alg. 1 line 17).
Theorem 2. Va
ex+rl < V El=0 N o%1y the f-RR mechanism satisfies cx-LDP:
P(J-RR(==)==) 6x, where Ux and U. be different at any bit, and E Range((-RR).. P(T-RRU))=8)
Regarding to the ground-truti label yz. given a privacy budget cy, we show that there always exists an upper bound of B so that y'a preserves -LDP given ye-
Theorem 3. v3 B < cy - In(C 1), the label-RU -RR mechanism (Alg. ! line 18) satisfies ey -LDP: P(label-RRe )= < exp(ey), given any distinct labels yo and Uz. and (lange(label-RR)
P(label-RX(g. )= [
From Theorems 2 and 3 our BitRand preserves LLD for the vector va and eDP for label Wz. The gradients Vb, preserve (ex, <y >-LDP in any training rounds for any training samples (z, yo) E D., and for all clients E [I; since, Vu, t: Vk, are computed from the randomized training samples (V/g, v2))n, without accessing any further information from {(x, U2) In.
5 PRIVACY AND UTILITY TRADE-OFF
As shown Theorem [ we can derive a tighter pri- vacy loss bound. Therefore, we focus on understand- ing how BitRand can address the privacy-utility trade- off in comparison with existing approaches by theo- retically studying: (1) the utility of f f-RR regarding the expected error bound (Theorem 4. and (2) the trade-off between privacy budget and randomization probabilities. All statistical tests are 2-tail t-tests.
"Tone cutputs
20.2.n
Lag uglaco
ti warre
comneed ATTKT
comeated ONE
10
Pr vacy budget
Figure 3: Expected error bound comparison for an embedded feature a with r = 1, 000, [= 10, and m 5.
Expected Error Bounds, We analyze the data utility through expected error, denoted as E.. measuring the
5

---

Under review as a conference paper at ICLR 2022
expected change of each embedded feature after applying f-RR: &. = BIE(f-RR(v.) E(ca)) The smaller expected error is, the better data unility the randomization mechanism achieves. The expected error Éa is bounded by Iie 9xi A.
Theorem 4. The f-RR expected error bound is quantified by Ea = (E)E()) - E(va) =
EiE 1) 9xi A..
Theorem 4 can be directly applied to quantify the expected error bounds of f-RR without the bit-
aware term 1%1/ll corrected LATENT (Appendix[]. [.. and corrected OME (Appendix (]. Regarding
existing mechanisms applied on the embedded feature a, including Duchi mechanism (DM) (Duchi
let al. 2013), Piecewise mechanism (PM) (Wang et al., 2019a), Hybrid mechanism (HM) (Wang al. 2019a). Suboptimal mechanism (PM-SUB) (Zhao et al.) 2020b), Gaussian and Laplace (Dwork & Roth 22014), we derive a general form of expected error bounds Ça for these mechanisms as:
Sa
1/r EeE[1.r] [M(a) al where M is an Ex-LDP preserving mechanism, since lim M al = 1/rr -.e(I.))) [M(a)- - a/.
M(a)
Figure 3 iillustrates the expected error bound of each algorithm as a function ex. It is obvious that f-RR has significantly tighter expected error bounds compared with baseline approaches under wide range of privacy budgets given reasonable large numbers of embedded features and encoding bits (p = 0.02); thus indicating that our mechanism achieves better data utility compared with the baselines. The improvement of our f-RR over existing mechanisms is larger when 6x increases.
To profoundly study the data utility, take a depth look into bit-level analysis by relaxing Theorem into (1) an expected error bound & = qxi x A, for each bit i E [0, / 1]. and (2) an average top-k (Appendix K show that, at the bit-level, f-R achieves smaller values of & for most important bits, especially the sign bit and integer bits, and comparable E, for least important bits, i.e., fraction bits. The gap between f-RR and the baselines are significantly larger given the Êtop- We obtain smaller values of Étop-k for all k E [0, - 1]. under tight privacy budget cx 0.1. Importantly, when increasing privacy budget ex (Figures 1 Tb,c). the gap between f-RR and the baselines is larger. In fact, the expected error bounds in f-R is reduced while the expected error bounds in the baselines are remained the same.
expected error bound Etop- 1/k Σ = ε.. Yk E [0, 1]. Figure
Privacy budget and randomization probabilities trade-off. Compared with existing RR mech- anisms (Lyu et al. 2020a Arachchige et al. 2019; Sun al.) 2021: Zhao et al., 2020b Duchi & Rogers 2019 Wang et al. 2019a] Liu et al. 2020), in our algorithm, bits with a stronger influence on the model utility, e.g., sign bits and integer bits, have smaller randomization probabilities 9x, and vere-versa. This is because we consider the influence of each bit i through the term 1%! in modeling the randomization probabilities qx (and px). This unique property of our algorithm enables us to better optimize the trade-off between privacy loss and model utility.
To demonstrate this, we examine the behavior of qx across bi- nary encoding bits under wide range of cx E {0.1, 1,2), given reasonable values of r and I, i.e., uresfann 12 Appendix KJ. Our mechanism achieves smaller randomization probability qx than the corrected LATENT in all cases (p = 3.7e 9). especially more significant bits, such as sign bits and integer bits. The gap is more prominent when ex increases. This observation is less obvious when comparing our mechanism with the corrected OME, given uneven randomiza- tion probability across bits in the corrected OME. To better show the comparison, we draw average top-k measure curve: Yk E [0,1-1]: Hopp- = 1/k Σi= 4s where q. is the bit i's qx- to evaluate the average qx across bits. The smaller Qrop-k the better the randomization probability qx is. Given a tight privacy budget ex = 0.1, our mechanism and the corrected OME have a similar Topp-k However, when <x increases, i.e., Cx E 2). our mechanism achieves significantly smaller values of Stop-k than the corrected OME (p- = 5.1c - 3).
0.5
1, 000 and / 10 (Fig-
0.4
0.3
corrected LATENT
0.2
AAR
0.1
correctied CME (2 XRR (1)
Ugn 2012" 2' 2 2' 2
Figure 4: Randomization proba-
bility qx and (top given 7 10, =1, 1000 and <x = 1.
DIMENSION-ELASTE
ANALYSIS
In existing RR mechanisms, the curse of privacy composition is rooted in the privacy composition
across bits and features r (Duchi et al. 2013) Lyu et al.) [2020a] AAachhhhie et al. 2019), gradients
Vd, (Zhao et al. 2020b: Wang et al. 201 9a), and training rounds 7 (Zhao al. 2020b Wang et al.)

---

Under review as a conference paper at ICLR 2022
2019a). Thus, increasing the dimensions of I, r. V and eitherr significantly increases the privacy budget (i.e., resulting in loose privacy protection) Wang et (019|]000]]] 2017) or notably affects the randomization probabilities (i.c., the value transmitted correctly through the randomization becomes
smaller resulting in poor utility (Wang et al. 2016a)) (Lyu et al. 2020a Arachchige et al.) 2019).
In Theorem 1 the privacy composition across bits and features is unavoidable. However, the values of embedded features transmitted correctly through our randomization mechanism is minimally affected when increasing the dimensions of r. Vë. T, and C' under the same ex and ey. That enable us to evade the curse of privacy composition when working with complex models and tasks under rigorous LDP protection. To shed light into this property, we conduct a theoretical analysis to examine: (1) How the dimensions of r, L, gradients Vg. and training rounds T'' impact the privacy budget ex and the randomization probabilities qx and px (= 1 - gx); and (2) How the number of model outcomes C' impacts the privacy budget cy and the randomization probabilities qy and py: We select the upper bounds of a vex (2) Elzo exp(2xx {)) and 3 = cy In(C 1) (Theorems
in our analysis.
Dimensions of gradients Vë, and training rounds T. In Bi- (Rand, the clients only use the perturbed samples (v',, 3/4 ) train their local models without accessing any further information from
0.6
Sign bit
Highest Integer
0.5
Lamgst futwow ki
Highest F Fraction bit
(ar, y=). Thus, the privacy budgets cx and cy are independent of the dimension of gradients Vä, and the training rounds T, i.e. following the post-processing property in DP (Dwork & Roth 2014). Also, the size of V8 and T do not affect the random-
4x
0.4
Lowast fraction we
ization probabilities, since V ee and T are not used to model qx. Px. gy, and py as in Eqs. and
0.1
10
10
10' 10*
Figure 5: Randomization proba-
Dimensions of embedded features r' and encoding bits 1. Varying the dimensions of and does not affect the privacy budget Cx E R since there always exists an a for Theorem[] to hold. However, it is necessary to understand the influence of varying r and on the privacy-utility trade-off. We theoretically analyze the impacts of r and I on the randomization probabilities qx and Px. given fixed values of ex- A model is expected to achieve higher model utility given smaller values of 9x (higher values of px) under the same privacy budget. We examine qx and px in the following experiments: (i) Fixing I, then varying r; and (ii) Fixing r, then varying
bility qx a function of with fixed = 10 and Ex = 1.
Figures 5 and 13 (Appendix K illustrate qx as function of r, under E (5. 20, 100, 1, F and cx E f0.1, 1.2). Varying r does not affect the randomization probability qx (and px) for all the bits in uy. To explain this, we take a deeper look into the a's bound, which is the only factor affecting Qx and px. Given fixed ex and 4, Di=1 exp(2ex is a constant, denoted C. So, we have a = / (ex + +()/(2+C)= = V + +1C((C) 2 vI/(2C), since ex z 0.0 in practice. Thus, with fixed 6x and I, 9x and Px are r-elastic, given approximately is constant v1/(2C).
066
Sign bit
Highest Integer bit
0.5
dosueee Intage bit
Highest Fraction bit
Lowest Fraction
0.4
0.3
0.2
0.1
10
20
100
1000
Figure 6: Randomization proba-
Now, we fix = 1, 000, which is a decent number of embedded features, and show qx as function of I under wide range of r E [10, 10, 000] and éx E 1.2) (Figures 6 and [4] Appendix K). Given tight privacy budget 6x 0.1, varying I does not affect the randomization probability qx. i.e., m = [1/2] in our analysis covering most values of embedded features in practice.
bility qx as a function of / with fixed = 1, 000 and ex = 1.
However, with higher values of ex E [1.0, 2.0). using more encoding bits/ / lowers qx for most important bits, i.e., sign and integer bits; while increasing qx for least important bits, i.e., fraction bits. When I is large enough (I 2 20), the randomization probability qx l-elastic since the impact of l becomes marginal to all the bits. This is also true for Px.
Number of model outcomes C. Similar to Ex, from Eq. and Theorem 3. the privacy budget Ey is not directly affected by the number of model outcomes C, since VC, ex: 3/ for Theorem to hold. However, C' may impact the trade-off between privacy and model utility by affecting the randomization probabilities qy and py- 7
that, when C' is sufficiently large, i.e., C 100, the randomization probability qy is C-elastic since the impact of C on ạy is marginal given wide range of the privacy budget ey. This is also true for py, When Ey increases, the randomization probability ςy becomes smaller (py becomes larger). This is a reasonable observation.
7

---

Under review as a conference paper at ICLR 2022
Thanks to the bit-aware and dimension-elann properties, our BitRand can achieve high data utility, especially under tight privacy budgets and expected error bounds.
10-4
c
7 EXPERIMENTAL RESULTS
2
We have conducted an extensive experiment on benchmark datasets under two fundamental FL tasks, text and image classi- fication, to shed light on understanding 1) the interplay among privacy budget and model utility in BitRand, 2) the effectiveness of the dimension-elastic and bit-aware properties on model utility, and 3) different settings of applying RR to preserve LDP.
10-2-
10
1,000
2:000
Figure 7: Randomization proba-
Baseline Approaches. We consider variety of LDP-preservingg
bility qy with varying ey and C.
mechanisms as baseline approaches: (1) Binary encoding ap- proaches, including the corrected LATENT (Arachchige al.
(019) and the corrected OME (Lyu
et al. 2020a) (Appendices) | and D: (2) LDP-FL (Sun et al. 2021;; (3) Duchi mechanism (DM)
(Duchi al. 2013); (4) Piecewise mechanism (PM) (Wang et al. 2019a); ; (5) Hybrid mechanism
(HM) (Wang et al. 2019a); (6) Threc-Outpun
mechanism (Zhao et al. 2020b (7) Suboptimal
mechanism (PM-SUB) B) (Zhao et al., 2020b); and (8) Label-Laplace (Phan et al. 2020). Each base-
line approach is applied to randomize (when applicable): (i) Embedded features eg; (ii) Gradients
Vă, and (iii) Gradients Vë, with a recent anonymizer (Sun et al. 2021) to reduce the privacy budget consumption. In addition, Label-Laplace is used as a baseline to protect the ground-truth labels y/. Note that, in our experiment, we use the upper bound of 3 resulting in the same randomizing probabilities as in LabelDP. Therefore, we do not include LabelDP in comparison. More details about the difference of label-RR and LabelDP are in Appendix G These settings are widely accepted to preserve LDP in FL; thus, offering comprehensive view of preserving LDP in FL. Note that LATENT, OME, and BitRand can only be applied on embedded features e,; while LDP-FL can only be applied on gradients Vž, with and without the anonymizer (Sun et al. 2021). We include the Noiseless FL. model trained on the original data D., to show upper-bounds and a Random guess model understanding model utility better.
Datasets, Metrics, and Model Configuration. The complete details of the datasets, metrics, and model configuration are in Appendix L We carried out our experiments on two textual datasets and two image datasets, including the AG dataset (Gulli et al. 2012). our collected Security and Exchange Commission (SEC) financial contract dataset, the large-scale celebFaces attributes (CelebA) dataset (Liu et al. 2015), and the Federated Extended MNIST (FEMNIST) dataset (Caldas et al.) 2018). We use the test accuracy and the test area under the curve (AUC) as evaluation metrics. Models with higher values of test accuracy and AUC are better. We use the BERT-Base (Uncased) pre-trained model (ber: Devlin et al., 2018) to extract embedded features in the AG and SEC datasets. In the CelebA and FEMNIST datasets, we use the ResNet-18 pre-trained model (img; He et al. 2016). For text and image classification tasks, we use two fully connected layers on top of embedded features, each of which consists of 1, 500 hidden neurons and uses ReLU activation function.
Evaluation Results. Comprehensive results show that BitRand offers stronger privacy protection with higher model utility, compared with all baseline approaches, discussed next.
LDP-preserve preseervsnn approaches applied on the embedded features Cg.. Baseline approaches do not work well when they are applied on embedded features eu (Figures [5]and [9 Table 3 Appendix [[) In SEC, AG, and FEMNIST datasets, BitRand achieves the highest model utility compared with the best baseline approach, which is the corrected OME, under tight privacy budget ex = 1. In terms of accuracy and AUC values, BitRand (cy = oo) achieves an improvement of 46.03% and 38.51% 51% in the AG dataset (p- 2.7e - 22), 13.69% and 73.79% in the SEC dataset (p- 4.1e-122 and 21.62% and 13.42% in the FEMNIST dataset (p = 5.6e 11) respectively. In the CelebA dataset (Table BitRand outperforms the best baseline approach, i.e., PM-SUB, with an average improvement of 1. .66% across all 40 attributes in terms of AUC measure (p = 1.2e - 2). Since the CelebA dataset is highly imbalanced, we use the AUC measure instead of the model accuracy. The gaps between BitRand and the baseline approaches are significantly wider when the privacy budget ex is larger. In addition to c = 1, with a tight privacy budget for the class labels cy E (.,2. BitRand still outperforms baseline approaches in most of cases, offering stronger privacy protection with better model utility, i.e., LDP at both embedded feature and label levels instead of only LDP on the embedded features in baseline approaches.
3 Appendix
8

---

Under review as a conference paper at ICLR 2022
100
100
100
10, Aron)
80
Thres- Arori
AUC
ALIC
SUB hrg
UP FL fog d.Acn)
60
60
60
corrected LATENT (ed)
coreetted ONE (e.]
B2fand [6] 2o
40
B2ford [6]]
2
10
E4
Ey
Ex
(a) AG
(b) FEMNIST
SEC
Figure 8: AUC values of each algorithm applied on the gradients V with the anonymizer.
The key reason is that, in the baseline approaches, the model utility is significantly affected by the size of the embedded features. Thanks to the dimension-elastic and bit-aware properties, BitRand can achieve high model accuracy and AUC values, especially under tight privacy budgets. In addition, BitRand achieves the highest improvement in the AG dataset, since is a balanced dataset compared with the highly imbalanced CelebA dataset, in which BitRand achieves the least improvement. Addressing imbalanced data in FL under DP (Huang et al. (020) is out-of-scope of our study.
LDP-preserving approaches applied on on gradients Ve, without and with the anonymizer (Sun et al., 2021). We observe the same phenomenon when baseline approaches are applied on gradients V2, without and with the anonymizer (Sun et al. (021), even though the gaps between
BitRand and baseline approaches are (marginally) smaller (Figures g] [6 20 and Tables + 5
Appendix D. Without using the anonymizer in the baseline approaches, in terms of accuracy and
AUC, compared with the best baseline approach PM-SUB, BitRand (EX = 1, Ey = 1) achieves an
improvement of 44.95% and 37. 52% in the AG dataset (p- 3.9c 20), 12.82% and 12.92% in the SEC dataset (p- = 1.3c - 11), 24.17% and 13.40% in the FEMNIST dataset (p = 4.1c - 11). When the anonymizer is applied in the baseline approaches, in terms of accuracy and AUC, compared with the best baseline approache HM, our BitRand achieves an improvement of 39.38% and 32.75% in the AG dataset (p- 1.2e- 16), 13.59% and 13.69% in the SEC dataset (p 2.1e 10), and 23. 22% and 37.02% in the FEMNIST dataset (p = 2.8e - 11). Regarding the CelebA dataset, BitRand outperforms the best baseline approaches, which are Three-outputs and HM, with improvements of 1.28% and 0.3%, in the cases of with and without the anonymizer, across all 40 attributes in terms of AUC (p- 3.1c 2). The model utility in baselines affected by the size of gradients and the training rounds (when the anonymizer is not applied) and their finite numbers of randomization outputs of the gradients (Zhao et al. 2020b). Thanks to the bit-aware and dimension-agnostic properties, BitRand can achieve high model utility under rigorous LDP protection.
LDP-preserving labels. Figures 18| 21 and Table 3 (Appendix L present the model utility of BitRand as a function of the privacy budgets ex and Ey, in which label-RR is replaced by the Label-Laplace, denoted as f-RR& & Label-Laplace. label-RR outperforms the Label-Laplace in all values of cx, cy. and datasets. Under rigorous LDP protection cy 1 given cx E [1, 10). there is an average improvement of 9.65% accuracy and 7.92% AUC in the AG dataset (7.3e- - 6), 7.84% accuracy and 7.35% AUC in the SEC dataset (1.2e 5), and 9.91 % accuracy and 10.55% AUC in the FEMNIST dataset (p- 9.8e 5), and 2.04% AUC in the CelebA dataset (p- = 1.6e- 2). The gaps are delicately smaller in the AG and SEC datasets, and substantially larger in the FEMNIST and CelebA datasets when ey is increased. Given ey = 2.5, there is an average improvement of 1.71% accuracy and 1.37% AUC the AG dataset (8.5e 2), 4.65% accuracy and 4. 4.73% AUC in the SEC dataset (6.9e - 3), and 14.43% accuracy and 12.02% AUC in the FEMNIST dataset (p = 1.9e 4), and 4.24% AUC in the CelebA dataset (p- = 2.3e - 2). The reason is that Label-Laplace injects Laplace noise across C' classes in label ye causing more noisy model outcomes compared with label-RR, in which only one of the model outcomes is selected as the result of the randomization.
CONCLUSION
In this paper, introduced bit-aware algorithm, called BitRand, providing rigorous LDP protection to both embedded features and labels in FL via binary encoding. In BitRand, the trade-off between the privacy budget consumption and randomization probabilities is dimension-elastic to the numbers of embedded features, encoding bits, gradients, model outcomes, and training rounds, enabling us to work with complex models and FL tasks. We further optimize the randomization probabilities by having smaller randomization probabilities assigned to more critical bits and vice-versa under the same privacy budgets. Theoretical analysis and extensive experiments showed that our BitRand outperforms baseline approaches in text and image classification.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Cometomyhead academic news search engine.
http::/rewseeggnne.d............
Google ai. pre-trained bert model. http:p///aattteeeeeoooaaaaaaaaae
latest/sect iotccction/eeee http://esssattttttnntnsssssaaaas
Pre-trained resnet-18 model. http:///settttaa..oooo..aaaaaaaa
Induction https:/ http://pwwwwpp....t.tta.cc.//t/t
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318- 2016.
J. Acharya, Z. Sun, and H. Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1120-1129, 2019.
M. Alvim, K. Chatzikokolakis. C. Palamidessi, and A. Pazii. Local differential privacy metric spaces: optimizing the trade-off with utility. In 2018 IEEE 3 Computer Security Foundations Symposium, pp. 262-267, 2018.
P. C. M. Arachchige, P. Bertok, I. Khalil, D. Liu, S. Camtepe, and M. Atiquzzaman, Local differential privacy for deep learning. IEEE Internet of Things Journal, 7(7):5227-5842, 2019.
B. Balle, J. Bell, A. Gascón, and K. Nissim. The privacy blanket of the shuffle model. In Annual International Cryptology Conference, pp. 638-667, 2019..
R. Bassily and A. Smith. Local, private, efficient protocols for succinct histograms. In ACM Symposium on Theory of Computing, pp. 127-135, 2015.
R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta. Practical locally private heavy hitters. arXiv preprint arXiv: /tci::/777.0444 044922, 2017.
Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protec- tion against reconstruction and its applications in private federated learning. arXiv preprins urXiv:1812..000 2018.
Robert Istvan Busa-Fekete, Umar Syed, Sergei Vassilvitskii, et al. On the pitfalls of label differential privacy. In NeurlPS 202/ Workshop LatinX in AI, 2021.
S. Caldas, S. M. K. Duddu, P. Wu, T. Li, Konečný, H. B. McMahan, V. Smith, and A. Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint: /a/p::::////0000 2018.
N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert- Voss, K. Lee, A. Roberts, T. Brown,
D. Song, U. Erlingsson, et al. Extracting training data from large language models. arXiv preprini arXiv:2012.07805, 2020.
A. Cheu, A. Smith. J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In EUROCRYPT, pp. 375-403, 2019.
G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik. EMNIST: Extending MNIST to handwritten letters. In International Joint Conference on Neural Networks, pp. 2921-2926, 2017.
G. Cormode, T. Kulkarni, and D. Srivastava. Marginal release under local differential privacy. In ACM SIGMOD, pp. 131-146, 2018.
J. Devlin, M. W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 18Xiv:1810. 04805, 2018.
J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy. arXiv preprint 190.v:9005.02338 2019.
Duchi and R.n Rogers. Lower bounds for locally private estimation via communication complexity. In COLT, pp. 1161-1191, 2019.
10

---

Under review as a conference paper at ICLR 2022
J. C. Duchi, M. I. Jordan, and M. Wainwright. Local privacy and statistical minimax rates. In IEEE Protocols for secure computations, pp. 2399438.44 2013.
J. C. Duchi, M. Jordan, and M. J. Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Asseciation, 1136521)182-220)) 2018.
C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., (13$#2211:44:1111 107, 2014. ISSN 1551-305X.
U. Erlingsson, V. Pihur, and A. Korolova. Rappor: Randomized aggregatable privacy-preservingg ordinal response. In Proceedings of the 2014 ACM SIGSAC CCS, pp. 1054-1067, 2014.
U. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In ACM-SIAM SODA, pp- 1668-2479, 2019.
G. Fanti, Pihur, and U. Erlingsson. Building a rappor with the unknown: Privacy-preserving learning of associations and data dictionaries. arXiv preprint arXiv: 1503.01214, 2015.
M. Fredrikson, Jha, and T. Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In ACM SIGSAC CCS, pp. 1.322-133,, 2015.
GDPR. The european data protection regulation. https: https://gdpr interriifoeeeee 2018.
R. C. Geyer, T. Klein, and M. Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv: 172200755 2017.
B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and C. Zhang. On deep learning with label 2021.
differential privacy. arXiv preprint
M. E. Gursoy, A. Tamersoy, S. Truex, Wei, and L.. Liu. Secure and utility- utility-aware aware data collection with condensed local differential privacy. IEEE Transactions on Dependable and Secure Computing, 2019.
A. Haeberlen, B. C. Pierce, and A. Narayan. Differential privacy under fire. In USENIX Security Symposium, volume 33, 2011.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
X. Huang, Y. Ding, 7. L.. Jiang, S. Qi, X. Wang, and Q. Liao. DP-FL: a novel differentially private federated learning framework for the unbalanced data. World Wide Web, 23(4):2552 2545, 2020.
Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, al. Advances and open problems in federated learning. arXiv preprint arXiv:19/2.04977 2019.
S. Kim, H. Shin, C. Baek, S. Kim, and J. Shin. Learning new words from keystroke data with local differential privacy. IEEE TKDE, pp. 479-491, 2018
Ruixuan L., Yang C., Hong C., Ruoyang G., and Masatoshi Y. FLAME: differentially private federated learning in the shuffle model. CORR, hass/209.00003. 2020.
R. Liu, Y. Cao, M. Yoshikawa, and H. Chen. Fedsel: Federated sgd under local differential privacy with top-k dimension selection. In International Conference on Database Systems for Advanced Applications, pp. 485-501, 2020.
Z. Liu, P. Luo, X. Wang, and X. Tang. Deep learning face attributes in the wild. In ICCV, December 2015.
L. Lyu, Y. Li, X. He, and T. Xiao. Towards differentially private text representations. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1813-1816, 2020a.
11

---

Under review as a conference paper at ICLR 2022
L. Lyu. H. Yu, and Q. Yang. Threats to federated learning: A survey, arXiv preprint arX1v:2003.02133, 2020b.
M. Malekzadeh, B. Hasircioglu, N. Mital, K. Katarya, M. E. Ozfatura, and D. Gündüüz. Dopamine: Differentially private federated learning on medical data, arXiv preprint arXiv:2101.11693, 2021.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communication--fficciii learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp. 1273-1282, 2017.
Iya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM conference on Computer and communications security, pp. 650-661, 2012.
N. H. Phan, M. Thai, H. Hu, R. Jin, T. Sun, and D. Dou. Scalable differential privacy with certified robustness in adversarial learning, In ICML, pp. 7683-7694, 2020.
Protection Regulation. General data protection regulation. Intouch, 2018
X. Ren, C. M. Yu, W. Yu, S. Yang, Yang. A. McCann, and S. Philip. Lopub: High-dimensional crowdsourced data publication with local differential privacy. IEEE Transactions Information Forensics and Security, 13(9):2151-216, 2018
H. Shin, S. Kim, J. Shin, and X. Xiao. Privacy enhanced matrix factorization for recommendation with local differential privacy, IEEE Transactions on Knowledge and Data Engineering, 30(9): 1770-1782, 2018.
C. Song and A. Raghunathan. Information leakage in embedding models. ACM SIGSAC CCS, pp. 377-390, 2020.
L. Sun, J. Qian, and X. Chen. LDP-FL: Practical private aggregation in federated learning with local differential privacy. IJCAI, 2021.
Cybersecurity Law.
Cybersecurity law of the people's republic of china. https: //en. wiiinwiiippiia www.aorrg/wwiooo
Law of the People827a
Republic_of. China 2016.
Gulli et Ag's corpus of news articles.
http://groups. wnw.innip.... .t/ wtt.duww......ttgul.///////////. news articles htmllsshmmll 2012.
corpus _ewp
Truex, N. Baracaldo, Anwar, T. Steinke, Ludwig, R. Zhang, and Y. Zhou. A hybrid approach to privacy-preserving federated learning. In Proceedingg of the 12th ACM Workshop Artificial
Intelligence and Security, pp. 1-11, 2019.
S. Wagh, X. He, A. Machanavajjhala, and P. Mittal. Dp-cryptography: marrying differential privacy and cryptography in emerging applications. Communications of the ACM, 64(2):84-93, 2021.
D. Wang and J. Xu, On sparse linear regression the local differential privacy model. ICML, pp. 6628 6637, 2019.
N. Wang, X. Xiao, Y. Yang, J. Zhao, S. C. Hui, H. Shin, J. Shin, and G. Yu. Collecting and analyzing multidimensional data with local differential privacy. In IEEE ICDE, pp. 638-649, 2019a.
S. Wang, L. Huang, P. Wang, H. Deng, H. Xu, and W. Yang. Private weighted histogram aggregation in crowdsourcing. In International Conference on Wireless Algorithms, Systems, and Applications, pp. 250-261, 2016a.
S. Wang, L. Huang, P. Wang, Y. Nie, H. Xu, W. Yang, X. Li, and C. Qiao. Mutual information optimally local private discrete distribution estimation. arXiv preprint:1601 1607.08025, 2016b.
T. Wang, J. Blocki, N. Li, S. Jha Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium, pp. 729-745, 2017.
T. Wang, B. Ding, M. Xu, Huang, C. Hong, Zhou, N. Li, and S. Jha. Improving utility and security of the shuffler-hased differential privacy. arXiv preprint arXiv: arXiv:1908 1/515, 2019b.
12

---

Under review as a conference paper at ICLR 2022
T. Wang, B. Ding. M. Xu, al. Murs: practical and robust privacy amplification with multi aulti-party differential privacy. In ACSAC, 2019c.
S. L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, 1965.
X. Xiong, S. Liu, D. Li, Wang, and Niu. Locally differentially private continuous location sharing with randomized response. International Journal of Distributed Sensor Networks, 15(8): 1550147719870379, 2019.
C. Xu, J. Ren, L. She, Y. Zhang, Z. Qin, and K. Ren. Edgesanitizer: Locally differentially private deep inference the edge for mobile data analyties. IEEE Internet of Things Journal, 6(3):5140-5151) 2019.
Hongxu Y., Arun M.. Arash V., Jose M. A., Jan K., and Pavlo M. See through gradients: Image batch recovery via gradinversion, 2021.
Q Yang, Y. Liu, T. Chen, and Y. Tong. Federated machine learning: Concept and applications. ACM Transactions Intelligent Systems and Technology, 10(2):1-19,200
B. Zhao, K. R. Mopuri, and H. Bilen. idlg: Improved deep leakage from gradients. arXiv preprint arXiv:2001.02610. 2020a.
X. Zhao, Y. Li, Y. Yuan, X. Bi, and G. Wang. Ldpart: effective location-record data publication via local differential privacy. IEEE Access, 2019.
Y. Zhao, J. Zhao, M. Yang. T. Wang, Wang, Lyu, D. Niyato, and Y. Lam. Local differential privacy based federated learning for internet of things. IEEE Internet of Things Journal, 2020b.
K. Zheng, W. Mou, and L. Wang. Collect at once, effectively: Making non-interactive locally private learning possible. ICML, pp. 4130-4139, 2017.
Q Zheng, S. Chen, Q. Long, and W. Su. Federated f-differential privacy. In International Conference on Artificial Intelligence and Statistics, volume 130, pp. 2251-2259, 2021.
L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients. In NewrIPS, volume 32, Curran As- sociates, Inc., 2019, U http:///ww......pppp....c/p////a wttpppppppppp///ceeeeepppp 60a6=3002cc1/2311122eef881111113 Papelaa--pppppppppp
13

---

Under review as a conference paper at ICLR 2022
APPENDIX
A REVISITING RANDOMIZED RESPONSE MECHANISMS FOR LDP
To preserve LDP given the client's 's input x, we can apply existing RR mechanisms (Wang al.
2016b Fanti et al. 2015: Bassily et al., 2017 Kim et al. 2018 Ren et al. 2018 Zheng et al. 201
Wang & Xu 2019 Zhao et al. 2019: Gursoy et al. [..]|2019 Alvim et al. 2018 Xiong et al. 2019).
such as unary encoding-based approaches (Wang et al. 2017, Brlingsson et al. 20144), hash based
approaches (Wang et al. 2017; Bassily& & Smith, 2015; Acharya et al. 2019; Wang et al. 2019c).
binary encoding- baasddd approaches (Arachchige al. 2019; Lyu et al. 2020a), etc. For instance. approaches such as those of Google RAPPOR (Erlinssoon et al. 2014) and OLH (Wang ct a (2017) hash the client's 's input onto bloom filter B of size i using h hash functions. Then, for each client's input x and a bit E B, RAPPOR creates a perturbed binary value B from B, with the following randomization probability:
with probability p/2
B₁
0,
with probability p/2
Bs
with probability
where p is hyper-parameter. This B' is reused as the basis for all future analysis, learning, and reports on this distinct input x. This approach achieves <x-LDP, where ex = 2h In((1 ()))). given that the sensitivity of every bit B, is AB. (Erlingsson et al. 2014).
To deal with numerical inputs, e.g., embedded features, generalized RR mechanisms such as Duchi (Duchi & Rogers 2019 Bhowmick al. 2018), Piece-wise (Wang et al. 2019a), Hybrid (Wang et al.
2019a). Three-outputs (Zhao et al. 2020b), Suboptimal (Zhao et al. 20206). LDP-FL (Sun
al. 2021). LATENT (Arachchige al. 2019). and OME (Lyu al. 2020a) can be applied.
Asymmetric version of RAPPOR (e.g., (Wang et al. 2017) designs different randomization prob-
abilities for different inputs. The technique is well-applied in the context of frequency estimation and successfully reduce the communication cost from (d) to Olog n) (d is data dimension and n the number of samples). However, simply applying the mechanism (Wang et al. 2017) does not optimize the model utility and the privacy-utility trade-off when working with machine learning or deep learning models.
Another line of work in LDP is Mironov (2012), which addresses the floating-poit arithmetic in implementation of DP applications. The inconsistency between mathematical abstraction of Laplace mechanism with sampling "uniform" floating-point numbers can be exploited to carry out privacy attacks. Floating- point arithmetic a leaky abstraction, which ubiquitous in computer systems and is difficult to argue about formally and hard to get right in applications, including all the RR mechanisms.
However, different from the asymmetric version of RAPPOR and the floating-point arithmetic, our proposed f-R mechanism focuses on mitigating the privacy-utilit trade-off. To achieve that, besides the asymmetric nature of the randomization probabilities, our designed f-RR consists of two key components: 1) The bit-aware term 8%l/l, which indicates the location of the bit in each embedded feature associated with the sensitivity of the bit that location; and 2) The adjustable but bounded o, which takes into account the correlation between privacy loss and the sensitivity of embedded features to mitigate the privacy-utility trade-off and the curse of privacy composition.
The bit-aware property refers to the bits with a more substantial influence on the model utility have smaller randomization probabilities, and vice-versa, under the same privacy protection. By incorporating sensitivities of binary encoding bits into a generalized privacy loss bound, we show that increasing the dimensions of embedded features r, encoding bits I, and model outcomes C marginally affect the randomization probabilities in BitRand under the same privacy budget. This dimension-elastie property is crucial to mitigate the curse of privacy composition by retaining a high value of data transmitted correctly through our randomization given large dimensions of 7, and C.
Besides the fRR for protecting the data, we also include the label-RR for protecting the label in our proposed BitRand mechanism, that provides a complete protection for every data sample.
14

---

Under review as a conference paper at ICLR 2022
B BITRAND ALGORITHM PSEUDO-CouD -CDE
1: Input: Privacy budget and ey, number of training iterations T. learning rate v). binary encoding parameters (1 and m)
13: At client side E [],
for each data sample (2. Dr, do
15: Extracting embedded features: ex + (2))(x)
2: At server side:
16:
Uz + BinaryEncoding ex) using Eq.
3: Initialize model g
17:
Randomizing Vx: 1/2 - f f-RR(2) Uxx with
4: Send the pre-trained model fare to clients
6x
using Eq.
5: for T do
2r 2imm #)
6: Distribute model parameter 0' each client
18: Randomizing the label y=: V/2 + label RR (3(3))
7: for each client u do
with / = ey -InC - 1) # using Eq
8: V t Client-Update(())
19:
end for
9: end for
Client- Mhent-Update(0>>
10: oc+1 0. t/e EMED,NI V
21: VE, = Dieggggen Vo, ((T(E))
end for
22: return V
Output: (ex,er)-LDDP
Algorithm 1: BitRand Algorithm in Federated Learning
C PROOF OF LEMMA 1
Proof. Without loss of generality, let us study the I f1-sensitivity of binary encoding bits of a feature's value a in ez. is obvious that f-RR Ca. i) and (-RR(vale+>) differs at the bit in the worst case. The decoded feature of f-RR(v,, Va. i) is a' = E(f-RR i)).
Let us denote bybb ... b the binary representation f-RR(v,, i) of a', where bn is the value of sign bit (i.e., 60 1 if a' >= 0 and bo 0 if a' < 0), and {b. [= is the value of integer bits and fraction bits. We have decoding function: &(J-RR (Va: i)) = (2ho- - 1) D by x 2m- This decoding function is also applicable to {(f-RR(vajs i)). Let us denote (b)) as the value of the bit in (v)ss.)) Following Eq. the 1 (1-sensitivity of the bit by is computed as follows:
If i is an integer or a fraction bit (i E [1, - 1)). we have: A, = max..
E(f-RR(va i)) - E (f-RR(UV i)) |12 max., (1bbg 10000-110 1) (Ei=1,44 by2mh 3-m2-+ -
-(2b0-
1) - ii bm 1 + (/2m-1) ||I = max., 11(2b - 1)(b: - 63)2m-'11 211 S max.. (1260
1)1[[, - 14ll120 2Th The A is maximized when by and b/g are different, and 126g 11 = 1.
Therefore, A; 2m-
If is the sign bit (i 0), have: A, max..
E(f-RR(V. 0))
(f-RR((ugis 0)) ||1= = max,, 11(bbg 1) 1) b,2m-i (256
1) Σ ;= b:2m-i1 ||1
max., (1(bbo - 226) Σ b -i -11 S max..
12b- - -26611| E!=1 b,2m-ill $111
The A; is maxi-
mized when bn and b/, are different and all {b: 1-
1. Then, A, S max 0
2 2Σ 1==1 2m- Since
2 +.... + 2 = 2 2 mat). we have: 2) a result, A, = m+1
i= 2m-1 = 2 1) < 2 As
From the aforementioned A of a feature's value in ez, is easily expanded to the entire eg. Since exr the concatenation of all / bits of values in eg, all bits with the same value of 7%! have the same 4 i--eeniitivity across rl bits. Therefore, the A; of the sign bit and the integer/ffaction bits are 2 and 2 5% respectively. Consequently, Lemma hold.
D PROOF OF THEOREM I
Let us consider a bit i belonging to feature a, i.e., one of the r features. We denote f-RR (U.. i) as vector U. with only the bit i randomized by our f-RR, i.e., all the bits different from are kept the same in o,; that is, we only protect the bit when using the notation f-R i). Given the I i-sensitivity A,, there always exists Laplace noise injected into the embedded feature a, i.e.,
15

---

Under review as a conference paper at ICLR 2022
M( 1) E(vo) + Lap( A1) to achieve e, e,-LDP in the embedded feature space (wwork & Roth 2014). In other words, P [a)]ss from Vaa only at the bit and E (M).
-) I exp( s.1E(n)) ( where Vaji is the vector that differs
A.
To ensure that the privacy loss in randomizing the bit i, we need to bound a in Eq. such that However, randomizing binary encoding bit given P()-)R((...)=es)) I exp( ( P(J-RR(aass)))))
A; Va and Vali results in a smaller (ı-distance [E(f-RR(va 2)) E[f-RR(Vale 2))] compared with [E())) - E(aaj:):: since [E(f-RR(y,, +)) - E(f-RR(uofs i))l - (E(va) - E(va(:)). Thus, we can derive tighter bound by replacing (E(vg) - E (Va|ti] with | (ff-RR(ve. i)) (aji ())l
Given (i) is the bit é in Cas we have
P(f-RR(uajis (1 Uz) = P(f-RR(VO(0) (1)) = vz()))
P(f-RR(Vo: 1) = Uz)
P(va(j) vi)
II
P(F-RR(Va/i/C = ve) x
P(val((i) = U. (i))
P(F-RR(Va(()) =i=(i)) P(F-RR((GH(() = (i) S Sexp( GLE(F-RR(U, i)) - E( ((F-RR(Va)i
(10)
A;
However, finding a closed-form solution of a for the tight privacy bound in Eq. 10 is non-trivial,
since Ej is intractable. To address this problem, we consider two cases: (1) P(/-RK( (Pa (1) 2 1
PLS-RR(E ()) =. (1)
and (2) P(f-RR(*, (t)) 1. Also, since A; captures the magnitude by which a bit can (0)
change the decoding function E() in the worst case, we have [((--R((..))) CLF-RR(Ua(.E)] 2 1.
A
In the first case, the privacy loss for a bit i can be bounded as follows:
P(f-RR(V. ( ([.-RR(V.]:. = (1) (PUJ-RR( (1) (f)
P(f-RR( o. (1)) (i))
TE Bic exp((s) (11)
Since the RR mechanism is independently applied on each bit i in U/ and on every of the features, Eq. enablee us to quantify generalized privacy loss bound of a RR mechanism, in which different bits have different sensitivities to the randomized outcome as follows.
P(f-RR(U,) = 02)
-!-1
P( (RR (1) = (i))
II
P(F-RR(T.) = v.)
P(f-RR( (22))(())) = (i))
=
< II (i)) = (1)) == (())) u. (i))
r1-1
-|-
< II k=
exp(e.) = exp(
Σ E)
1=0
(12)
In the second case, the privacy loss for bit i can be bounded as follows:
P(f-RR(V, (1) (i)) P(f-RR(u (v.) (i)) = vz (f))
(i)) vz)) I P(F-RR(va (va (i)) = (i))
(UU-RR(Va):(0) = (1))
217 HRL 217
S exp((e)
P(F-RR(va(i) = vi))
(13)
Similarly, we obtain the same result with Eq. 12 in the second case:
P(f P(f-RR(u)) = v2)
P(f-RR (v, = (i))
ri-1
P[F-RR(ZZ)(0)) = ve(
II
< II P(f-RR(U, (1)) E. (1)
P[f-RR(E.) = 0.) ==
P(f-RR((2):(0) (1))
k=0
P(f ((f- (1)) (z))=
r--
rL-1
II exp(e:) = exp( 1=0
Σ
6))
1=0
(14)
Consequently, Theorem Tholds.
16

---

Under review as a conference paper at ICLR 2022
E PROOF OF THEOREM! 2
To ensure that the privacy loss in randomizing the is bounded by the privacy loss the em- bedded space and to take into account different sensitivities of different bits (Theorem[]) [I), we need to find a in Eq. 2 to solve Eq. [2 However, solving Eq. 12 is not straightforward since the
privacy budget 6; and the actual 1 disittaece {f(f-RR(u (2,, i)) Eff-R((V2)) ())] are intractable. To address this problem, from Eq.
12 we first consider the bit in all the r embedded fea-
tures, as follows:
[I.E(1.)] P(F-RR
P(F-RR(Pa::)) (x)) S exp(Ene((.r)
(())
sale(F-RRR -
A. E(F-RR(Mass: ())I) Note that all the bits i, e.g., sign [1, consume the same privacy budget 6, with the same sensitivity A;. The term Ede( &E(-RR(Va i)) E(F-RR(Vaje i))l can be unbiasedly replaced with [E(f-RR(v) i)) - E(f-RR(%as: 1)), since lim ()E(f-RR(",: i)) - E(f-RR(vaj: i))
exp( A. EeE(L.) (E(S-RR(Va:1) i))
bits, in all the features
(JE(f-RR(Va1))
E(f-RR(Vals i))l where E is the expectation of
Euctier |E(F (R) - E(F.RR().)..))) Hence, we have that
aE(..) P(/RR(V, va) (i) = v2)) S eepp( rG x (IE(S-R((U,) ()) E(f-EEERRRRRR-- ([f--R((Vasss)))) 6)]
P PR-- (1) = vz(1))
II
A.
P(F-RR(EO(0) (1)) v0) P(S-RR(vaN(O) (1)
πI aE(1,r]
ETE BR Ii9 S exp(re:)
(15)
Note that, in our work, we consider the worst case is the case that all the bits of two neighboring vectors can be different. The expectation quantify the difference of every two extreme vectors at bit i. Then for the whole vector, it is the sum
i)) - -(f-RR(Vaa:: i)) in Eq. [5 is used to
over the expectation E(-) of all bits i, as follows: Eus(..)] [ff-RR()) i)) Eff-R (1 i)) =
r x (f RR.( i)) - (f i))l. Therefore, the expectation in Eq. 15 does not imply the average-case scenario.
The sum over the expectation E(-) of all bits i, i.e., Eme(a.) Eigo (E(F-RR(va) i))
E(S-RR("a)s) i))
Ej (/ - E(J-RR(Vo): 1)) is used bound the
privacy loss as follows:
P(f-RR(Uz) = )
II II P(f-RR(cc(1) = (i))
REC
P(f-RR( (2) U2)
((F--R((a)::(6) Us (i))
0E(1,r)
G|E(f-RR Cas i)) - E(f-RR((
S Sexp( Σ
A.
aE(1,r] 1c
(:(r x (IE(J-RR(V,,)) (va, 1)) E(J-RR(V. 1))
=exp( Σ
A
|E(0,-1]
S <ex((r Σ G)
-E(0.-1]
ri-1
P(f-RR(Ue (i) =v))
rI-1
II == P(f-RR( Un (1) U. (1)
< exp(
(16)
1=0
Now, we need to bound the generalized privacy loss by discovering closed-form solutions of a given the privacy budgets 6x (Theorem (2). In other words, we need to solve Eq. 16 for discov- ering the closed-form solution of a. To solve it. first we need to calculate E (fR( i)) E(f-RR(uz)) d))]. To be more precise, let us denote px and gxi as px and qx in Eq, 2 for particular bit i, respectively. Given the worse case of et and Unlis there are four possible cases of [E(SRRR Cn, i)) ([J-RR(Uass i))l:
If f-RR(R ( (1)) and (-R(())(())) then (8(J-RR(V,,)) 1)) E(f-RR(Va)e i)) 0.
17

---

Under review as a conference paper at ICLR 2022
If (-RR(e)(1)) 0 and f f-RR(ua)(( 0, then [ 1)) - ([ff-RRRUnnp 8))l 0.
If f-RR((( and f [ 0, then [f E(f-RR() 8))l A.- This happens with the probability ( (1)) 1, (c, 0). To compute this probability, we use marginal probability and Bayes' theorem, as follows:
((f-RR(V,()) = (,, =
=P( f. = 0, (1) ur (() = =0)
+P(F-RR( (1)) F-RR (1) (1) = U2fi(1) = 1)
- (1) 0, 1, 01) =0)
x (()) 01v, = 1, (1) =0)
x P(cc())==1uu -100) 0) x (1)))((1) 0)
+ ( (1. ())((())
0, (1)) 0, 22)1(1) =1)
x ((f-)R((s(()) (1) = 0, (1) 1)
x 0| 1) (1)))((1) =
(()) (1) =1)
x P(F-RR("H) 012)/((1) = 0) x ((u = 0)
+ PP (-RRRR (i)R( (1)) (1) =0)
x P(f-RR((s)(()) = 012))((1) = 1) x P(un):(0) = 1)
P(ug 0) P(ex((() = 1)
(17)
If (-RR(cx(1) 0 and f-RR(")):(()) = 1, then (f))) - (f = A.
This happens with the probability P(f-RR(v,.0)) = 0, (RR (1)) = 1). To compute this probability, we use marginal probability and Bayes' theorem, as follows:
0.)
1)
= (P()-R((0(0))- 0, F-R( = 1, (1) = 1, =0)
+ PP v. (i)) = 0, /RR (v (1)) = 1, vx) = 0, (el((1) = =1)
= P(e,((())()) 0) P33 P(e ((ei)i(1) =)
(18)
Consequently, the expectation EfE(fRR (Ue, 1)) E(f-E(((Re))) (RRRRRRU i))] is computed as follows:
BJE(F-RR(V=,.)) ()) E(f-RR( -E(-RRRR 1))
= (p2(P(())1()) = 0) + 12 ((u)ss())) = 11) D
+ (ott P(ea(()))))) = 0) + p3, (1) = 1) Ai
= (p3x+ + 2x.),,
(19)
From Eqs.
12
16 and 19
have that
18

---

Under review as a conference paper at ICLR 2022
P(f-RR(UZ) Uz)
P(f-RR(U,) = U2)
P(f-RR(UZ(1) (1)) vz(
RIE(T-HK(VV (E E)) 2C
P(f-RR( Un (1)) = (0))
P(f-RR(Vx(1) = (10)(1) = (0) = 01) 2,
((f-RR(va(i)) = (1) 1) (i) (1) 0)
(a2 exp(((()))) )) (2 -2
II
(20)
==
Taking the natural logarithm of two sides of Eq. 20
In P(S-RR(UZ) (1z) = Uz)
In (a² exp(2cx 1)) px
Pif-RR( U2)
1-1
r
In (a² exp(2ex
(21)
Pxi + (1-pxx))
Let us bound the summation in Eq. 21 using the following inequality:
In(a) I a 1 for a > 0
(22)
The proof Eq. 22 is as follows. Let a > 0, we define h((a) = In(a) - a + 1. We have: h'(a) = = + 1, and since ha(a) - < Va 0, get the maximal point at a = 1. We also have: lim h(a) = -00 = lima- h(a). Therefore, a = 1 is the global maximal point and than Va 0,h(a) S h(a 1) = so In(a) a+1 S Therefore, Eq. 22 does hold.
-
Note that, to simultaneously satisfy the randomization probabilities px 1+a ( ex)
and 9x = exexp 2x))
2 in Eq. 2 we need to have: (i) + a expp 1old EX) 2 and (ii)
I+a expeex((F ex
cxp(
1%1 (x) 2 O. Since exp( 1%61 ex) is always true, from (i), 2 exp( 1% cx), and from
(ii). a 0. Therefore, a 2 is necessary to satisfy the condition px 2 and qx 2 0. To apply
Eq. 22 into Eq. 21 need to have a² exp(2ex 0 + 0. As result, have that
a> 0
(23)
Applying Eq. 22 into Eq. 21 where a = a² e2exx(2ex
In P(SRR (vx) = U2)
In (a² exp(2ex
P(fRRR (T)) = U2)
px + (1 -px.)²
1=0
ra exp((ext))
(24)
Px: + (1 -pxi)2
Px + (1-pxx)
1=0
To bound the logarithm in Eq. 24 we use: P2: + +x1 -p's + (1 - (1-pxx)² (1ra0sp ( xxx)) )²+ ++
aexpp 186 (x) )² exp 1211 (xx))x))
exepp 16l ex)
{ 5 1. and p2. + (1 pxx)² > (pxctl-px.)
(In fact,
eoresp 1861 ex)
19

---

Under review as a conference paper at ICLR 2022
Va, b. a² 132 (a+b)² + (a
b)3 2
which is true). Note that, from Eq. 19 we have that
1.
[E(//RR(V. - [R(
PX. +
Applying these inequalities in Eq. 24
obtain:
In P(f-R((UZ) (22) =
ra exp(2exi)
P(f-RR U2) U2)
== Pxi
pxxi)
1=0 Xxi + (1 pxi)
2ra² exp(2ex ) rl ex
2ra² exp (xp(2ex7)
Σ
(25)
By solving Eq. 25
we have that
cx + rl
6x trl
a² S
+ la|
(26)
2r
E (xx())x))
V
2r E/D 1-1
(2x((ex()
Therefore, from Eqs. 23 and 26 we have that Va a a<as V
extrl
the f-RR
2r Di exp((xx /)"
mechanism satisfies ex -DP. Consequently, Theorem holds.
PROOF OF THROREM
Proof. We have:
max (R Pa PI Pllobei-RR (T.
exp(8
P(label-RR(
In(C - 1)) S exp(er) + 3 S In(C 1). Consequently, Theorem does hold.
G label-RR AND LABELDP COMPARISON
Although our label-RR is inspired by the randomizing probability (Eq. (Ghazi et al. 2021 in the LabelDP showcased by (Ghazi et al. 202T), there are two major differences between our label-RR and LabelDP discussed next.
(1) We combine f-RR and label-RR to completely protect a data sample. As pointed out in (Busa Fekete et al., 2021), only protecting the label as the LabelDP offers a weaker privacy protection than it appears, as the features are sufficiently predictive of the label, obscuring the label is not enough, as a classifier can still be trained on such noisy data; hence, user experiences privacy loss due to both the public release of the features and the private release of the label.
(2) The RRWithPrior algorithm that is used to guarantee LabelDDP requiring publicly available priors and the multi-stage training (L.-MMTT) illustrating RRWithPrior algorithm cannot be straightforwardly applied to federated learning. LP-MST algorithm, the dataset partitioned into subsets, then based on the prior probability to randomize the label and add the data with that randomized label to the training data. These steps are presently applied on centralized training and it has not been show how to be effectively applied in federated learning.
Using the upper bound (Theorem) results in the same randomizing probabilities between label- RR and LabelDP. For instance, in Eq.
exp(ey) py [+exp(A) 1+exp(ry In(C-I) G- (xx((y)) and
exp(2)
exp(ey -inCC-1))
qY (I 10-1exppcy)) which is equivalent to Eq. 1 (Gaazi et al. 2021 Therefore,
we did not include LabelDP (Ghazi et al. 2021) in comparison.
H PROOF OF THEOREM
Proof. We have & (v()))R((..)) E(va) = Eigoo x 0 + ax X A:)
Eie qxi A, Therefore, Theorem hold.
20

---

Under review as a conference paper at ICLR 2022
1 CORRECTED PRIVACY BUDGET BOUNDS IN LATENT (ARACHCHIGE ET AL. 2019)
In this section, we aim at providing corrected privacy budget bounds for LATENT Arachchige et al. 2019). LATENT first encodes embedded features es into rl-bit binary vector ea. Then, each bit V E [0, rl -1] is randomized by a RR mechanism (i.e., the MOUE algorithm for high sensitivities in Theorem 3.3 (Arachchige al. 2019)). denoted f-LT, follows:
Px 1+
v. = 1
Vi E 10,rl-1] - 1]: -1)
(27)
9X
1f (1) = 0
= a exp +
From Eq. 27 we also have that (tc = = 1
if (z) = 1, and (t) = =)
Ita
1 qx a expl (x)
if (z) O.
exp! +
Theorem 5. LATENT with the randomization probabilities in Eq. 27 preserves Coorrected -DP,
(1+a)(1+a Xx ))
where Coorrccted a(I+oxp( +)
Proof. Similar to the analysis in Appendix
we obtain the following inequality:
P(f-LT(U>) = v.) P(f-LT(U,,) = v.) S II
r-11
(()) vv)))) ()
I exp((xx
2= (()() = vz)
(28)
and the expectation B]E((-LT((r): E i)) is computed as follows:
E| - 1))l
(P()-L((UE,)) = 1/x(()) = 1)
x P(S-LT(EW))) 1) (1) = 0) ((vx)(()) = 0)
+ P(f-LT(E,, i) (1),(() = 0)
x P(f-LT(D 1) = (1)) = 1) x P(vz)(()) = 1))
+ +PP(L-L((VE) i) = (1) =)
x (TS-LT((Eo/s) 1) (1) = 0) x (() = =0)
+ PP(f-LT(Eer i) (1),(() 0)
x PP(f-LT(Vn) (unjs, (1) 1) (() = 1
= (pxi(1 - ((e = 0) + 4x: - P(Uzfe =1)
+1 (1-px:) ((xpxx)xxP((un((C = 0) + 11-xx))xxP(uu110 = 1)) A.
= (pxi(1 - gxa) + qxx - -xx)) A
(29)
Furthermore, we have:
pxx)) a(1 exp(
px - (xx1) + +xx
(30)
a1 + exxp( (x)
21

---

Under review as a conference paper at ICLR 2022
From Eqs.
28
30
we have that
P() Uz)
P(f-LT (x) = Uz)
xl11
P(F-LT(UE Un v=(1))
(( = vz)
1=0
(()) (1) 11 -x
(()-LT((z(()) (1) = 1)
P(f-LT(Ue))) (1) (12 = =0) (( = (1) = =0)
(XX OXITOX20 PXI)T
rl-1
II
exp(
ex exiil exill PX.. rl
(31)
2=0
Then, from Eq.
we have:
+
Corrected In I exp( (x) rl
ixi1 -x-x--x
(32)
al1 a11 exp( ())
Consequently, Theorem Sareemmm@holl holds.
From Theorem we show the proportion Ccorrected/c, as function of in Figure 9 and as function of I Figure p. Following the experiment settings LATENT (Arachchige et al. 2019). with the commonly used = 7, when changing E {10, 100, 1, 000, 10, 000} with a fixed {5, 10, 20, 100, 1, 0000 with a fixed r = 1, 000 (Figure (p) and under tight privacy budget ex = 0.1, the proportion Ecorrected/ ex moderately changes among [4.57, 4.75j. In other words, the Ecorrected is remarkably larger than Ex, for most r and values in practice. Unlike LATENT, mechanism does suffer from this problem, i.e., in BitRand, feorrected/ Cx 1, thanks to our bit-aware randomization probabilities for LDP binary encoding (Theorem
10
(Figure Da), or when changing
J CORRECTED PRIVACY BUDGET BOUNDS IN OME (YU AL..
2020A
In this section, we aim at providing corrected privacy budget bounds for OME. OME first encodes embedded features e, into an ri-bit binary vector Uz. Then, each bit i E [0, rl randomized by the following f-MEE mechanism:
Pix a ifi 2j, v. (1)
1
10, 1): (()(())
P2X 1 0
i 2j + 1, (1) =1
(33)
9x 1 (
if (1) =0
From Eq. 33 we also have that (t) = 0) PIx 14o
1 if (z) (i) = and E 2j. P(u
0) 1 P2x Itas if (1) 1 and E 2j + 1, and (()((() 0) qx 1ta exp( 1x Uy (2) =
a
ccexp( "X
Theorem 6. OME with the randomization probabilities as Eq. preserves Coorrected where
Coorrected dt
In(a) + 20. in which Q1 Ita 14 exp ( T+aexp(
exp( (x)
and Q2 1 1ta expl
1xp 1+a3.
Proof. Similar the analysis in Appendix b and Appendix obtain:
22

---

Under review as a conference paper at ICLR 2022
LATENT
4.5
LATENT
4.5
OME
4.0
10a
4.0
-109
3.5
3.5
3.0
10
3.0
Econesteal
10c
Ecorecctal
2.5
2.5
2.0
10
2.0
1.5
LATENT
1.5
LATENT
10
Ecorresteu/
1.0
10
Ecorrccted
1.0
1.0
1.0
10
100
1000
10000
10
20
100
1000
/
(i) Fixed 0.1, 10
(h) Fixed
0.1,
1, 000
Figure 9: Impacts of and ECorrected in LATENT (Arachchige et al. et al. 2020a).
2019 and OME (Ly
U2) U.)
r1-1
P(f-OME( Uz (1)) = vz) P(f-OME((Vr) Un]]((i) (i))
I eep((Ex)
P(f-OME U+2)
=
(34)
and the expectation B]E(J-OME(r.,.)) (v., E(JOMEE (U2))) i)) is computed as follows:
E/E(f-OME(vr: Up, 1)) - E(f-OME U1 1))
(pixi(1 9x.) + (1 PIXi)) QIA, if 2j (p2xi(1 9x.) + 1x P2xi)) Q24,, if 2j +
(35)
aexpl ) where Q1 = Pixx(1 (xi) + 1xx PIXi) 1ta 1+a exp( + 1+aexp! [x) 1ta"
1 oxpp (X)
and Q2 = P2xx(1 4xi) + 4x p2x1) Ita Itaexpl [ 1 1xaexp( (
From Eqs.
34 and 35
we have:
P(J-OME vz)) U&)
P(f-OME U.)) Uz)
111
P(F-OME(r,(() (1)) v2)
II
BIE(T OMEE EU af
P(f-OME (n))(()) = (i)
II
P(f-OME ( (1) = (1) 1) (1) = (10 0)
0,4,
P(F-OMB(UL) (U, (1) (1) P) (1)) 0/. 1)
SE2)
P(f-OME(2E))
1 (1) 1)P(f-OME(r = (12z(1) 0)
II
P(f-OME (OXME((x()) (vz(1)) = 110=1111 (1) 0) (i)(i) (2 1)
1E2j+1
EX
EX
a
exp(
(36)
2Q
2Q2
Then, from Eq. 36 have:
Coorrccted In (a
a2 exp(
EX
EX
rl
rl
In(a)
EX
6x
(37)
2Q
2Q2
Q
Q2
2Q
2Q2
Consequently, Theorem does hold.
23

---

Under review as a conference paper at ICLR 2022
From Theorem 6 show the proportion Ccorrected/C, <x function of in Figure 9 and function of in Figure Dp. Following the experiment settings in OME (yy et al. 2020a), with the commonly used (Figure or when changing / {5, 10, 20, 100, 1, 000) with a fixed r = 1, 0.0 (Figure 9 and under fight privacy budget c 0.1, the proportion fcorrected/ significantly changes among [4.6e + 6, 4.6e + 9]. In other words, the Ecorrected is extremely larger than ex. for most r and ( values in practice. Since compare with OME, we use 1. This value is used in OME (Lyu et al., 2020a) and generates Ccorrected/Xx 2, which offers reasonable range apply OME practice. Unlike OME, our mechanism does not suffer from this problem, i.e., in BitRand, coorrented bit-aware randomization probabilities for LDP in binary encoding (Theorem
100, when changing
{10, 100, 1, 000, 10, 000 with a fixed
10
100 causes the extreme privacy exaggeration. in our experiment, to
1, thanks to our
60
SUPPLEMENTARY THEORETICAL RESULTS
Setting for Gaussian and Laplace mechanisms.
SMSE
The Gaussian and Laplace mechanisms naturally ap- ply an addition operation, which add noise into the data or embedded features. Therefore, in our anal- ysis of expected error bound comparison for bedded feature (Figure 3). we add noise into the em- bedded feature following the Gaussian and Laplace mechanisms. The sensitivity captures the magnitude by which an embedded feature can change in the worst case. In our experiment and analysis, we use / = 10 bits in which 1 sign bit, 5 bits for the integer, and bits the fraction part. Therefore, the maximum the embedded feature can be change, ie., the sensitivity, is 2 - 2'. Note that, we multiply Σー= 2 by since when we flip the sign bit, it significantly changes the value of the embedded feature from
082
10
Figure 10: RMSE error comparison func- tion of EX-
-4
in which = Σ 2'.
RMSE error comparison in mean estimation. To investigate how our proposed approach f-RR works with statistical query, study f-RR and other baselines with mean estimation. We created a synthetic data that consists of N = 1, 000 data samples [ each of them has d = 768
dimensions. The mean estimation is calculated over each dimension (D) 1 Σ Ziy for j E [1, dl. Root mean square error (RMSE) is used to evaluate the error between the original vector and the randomized/estinatee vector. The binary-encoding ebosdigg-bbbd approaches (i.e., f-RR, corrected LATENT, and corrected OME) achieve a significantly small error compared with others. As can be seen in Figure TO, f-RR obtains the smallest error, which further shows the effectiveness of our proposed mechanism.
No 3it Beaare (E) coneeced LAFENT
correctec ONE (C)
FOR (E(
+ No bt swart +)
LAFENT
(Go
Frrt (Ew
10
10
No ahaara (2.)
comette LATENT
1
cometne ONE
3824
27
31
(8) cx
ex
(x)
Figure 11: Expected error bound as a function of Ex with fixed and
0.6
06
0.4
0.4
0.4
0/
4r
0.3
0.3
corpected
corpected corrected OME
compected
correted
corrected MR corrected OME 30me-al
ARR
FRR
0.1
corrected OME loco.al
01
corrected ONE Ioco-al
01
(asa-.)
(4
0.
2 23
2
u0
b12l
> 27
= 0.1
(b)
1.0
(0) 2.0
Figure 12: Randomization probability qx and Stop given = 10 and r = 1, 000.
24

---

Under review as a conference paper at ICLR 2022
0.6
0.6
0.6
Highest Integer
Highest Integer
Highest Integer be
0.5
Highest Fraction bit
cnaeet Inieger
0.5
Highast Raciion bR
cosnect Imogger
0.5
Highest Fraction att
Inwend integer
4v
Bo0s MH
Lowestt Fraction bh
7V
Lowest Fraction by:
9x
Lowesst Fraction at
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
(n)
5 ex 0.1
(b)
5 and ex 1.0
(c) 5 and ex 2.0
0.6
0.6
0.6
Highest Integer
Highest Integer
Hightstt integer
0.5
Inaeet Inieger
0.5
coveett lnowger a
cnwee integer
Highast Fraction bit
Highast Fraction bit
Highest Fraction at
Lowest Fraction bi
7V
Loweett Fraction bt.
Lowest Fraction at
0.3
0.3
0.3
0.2
0.2
0.
0.1
0.1
0.1
20
ex
(e)
20 and ex 1.0
20 and ex 2.0
0.6
0.6
0.6
Highest Integer
Highest Integer
highest integer
0.5
Inaeet Intwger
0.5
Intwger
0.5
mowed integer
Highast Fraction bit
Highest Fraction bi
Highest Fraction ait
4v
Lowest Fraction bi:
7V
Lowest Fraction bt:
Lowest Fraction alt
0.4
0.3
0.3
0.3
0.2
0.
0.
0.1
0.1
0.1
10
(8) / 100 and ex 0.1
(h)
100 and ex
(
100 and ex = 2.0
0.6
0.6-
0.6
gnn
Highest Integer
Highest Integer
Highest integer
0.5
Loaest Integer
0.5
Integer
0.5
Inwett integer
Highest Fraction bit
Highest Fraction bi
Highest Fraction at
4x
Lewest Fraction oi
Loweett Froction bt:
Lowest Fraction att
0.4
0.3
0.3
0.3
0.2
0.
02
0.1
0.1
0.1
10
(i) = 000 and ex = 0.1
(k) = 1, 000 and ex 1.0
()) = 1, 000 and ex 2.0
Figure 13: Randomization probability q (p = 1 - .) as a function of r with fixed and c.
25

---

Under review as a conference paper at ICLR 2022
0.6-
Si
Sign bit
0.6
Sign bit.
lighest Integer bit
liihhsst Integer bt
lighest integer be
0.5
Lonosat Indugur bit
Highest Fracfion be
0.5
Loownnd Intager bi
Highest Fraction ait
0.5
Lowaod intagerr bi:
Highest Praccion sit
Fraction
Fraction
0.4
0.4
0.4
0.2
0.2
0.2
0.1
20
200
1000
0.1
10
20
100
1000
0.1
20
100
1000
(a) r
10 and ex 0.1
(b)
10 and ex
1.0
[c) r 10 and EX = 2.0
0.6
gn
0.6
Sign
0.6
Stgn
Hignest Intoger
Highsst Intoger
Highost intagor
0.5
Highest Fraction bi
Lowest Integer att
Lowest inteper b
Highost Fraction bit
0.5
Highest Pracion st:
Lowest integer bt
9,
Lowert Tracbon bit
Lowest Fraction bit
4:
Lowest Traction st
0.4
0.3
0.3
0.3
0.2
02-
0.2
:00
1000
10
20
100
1000
20
100
1000
(d)
100 and <x 0.1
(c)
100 and 6x 1.0
(f)
100 and <x 2.0
0.6
0.6
Sign bit
0.6
Hignest
Highest bit
Highest integer
0.5
Highest Fraction
Intenge
Highest Fracton
integer
0.5
Highost Pracion
integer
0.4
Lnvest Frectoo bit
0.4
Lowest Trection
9:
0.4
Lowest trection bet
0.3
0.3
0.3
0.1
1000
(g)
U00 and 0.1
1, 000 and 1.U
(8)
000 and 2.0
0.6
gn
Sign bit
0.6
Siin bit
righest Integer bit
Hiihhest Integer be
Highest Integer be
0.5
Lowest Intager bit
Hiighted Fraetion be
0.5
Lowest Intoper bit
Hightdd fraction ait
0.5
Lowest ntoper bi:
Highes (r bit
Praction
Praction
Lomast Fraction
0.1
0.1
0.4
0.3
0.3
0.2
0.2
0.2
0.1
20
20
200
1000
0.1
5
10
20
100
1000
0.1
30
20
100
1000
() 10, 000 and ex 0.1
(k) = 10, 000 and ex = 1.0
(0 = 10, 000 and ex 2.0
Figure 14: Randomization probability 4x (px 1 - 9xx as a function of 7 with fixed r and 6.
26

---

Under review as a conference paper at ICLR 2022
L SUPPLEMENTARY EXPERIMENTAL RESULTS
Datasets and Data Processing. We carried out our experiments on two textual datasets and two image datasets, including the AG dataset (Gulli et al. 2012). our collected Security and Exchange Commission (SEC) financial contract dataset, the large-scale celebFaces attributes (CelebA) dataset
(Liu et al. 2015), and the Federated Extended MNIST (FEMNIST) dataset (Caldas et al. 2018). The AG dataset collection of news articles gathered from more than 2, 000 news sources by (Com). It is categorized into four classes: world, sport, business, and science/techollogy classes. Our SEC dataset consists of over 1, 000 contract clauses collected from contracts submitted in SEC filings] The CelebA dataset consists of more than 200, 000 celebrity images, each with 40 attributes, e.g.. attractive face, big lips, big noses, black hair, etc., which are used as binary classes. The FEMNIST dataset is built by partitioning the images in Extended MNIST (Cohen et al. (017) based on the writer of the handwritten digits and characters. For data preprocessing, we changed all words in the AG and SEC datasets to lower-case and removed punctuation marks. The breakdown of the datasets is in Table T
Table 1: Dataset breakdown.
Train
Test
Samples/client (Average)
Dataset
# classes
# samples
# samples
AG
120, 000
7, 600
43
4
SEC
1,1
134
3
2
CelebA
155, 529
19, 962
20
40 (binary)
FEMNIST
734, 033
83, 818
227
62
Model Configuration. We use the test accuracy and the test area under the curve (AUC) evaluation metrics. Models with higher values of test accuracy and AUC are better. We use the BERT-Bass (Uncased) pre-trained model (ber: Devlin al. 2018) to extract embedded features in the AG and SEC datasets. In the CelebA and FEMNIST datasets, we use the ResNet-18 pre-trained model (img) He al. 2016). Dimension of the extracted embedded features in the AG and SEC datasets is r = 768, and in the CelebA and FEMNIST datasets is = 512. For text and image classification tasks. we use two fully connected layers on top of embedded features, each of which consists of 1, 500 hidden neurons and uses a ReLU activation function. The output dimension is corresponding to the number of classes, i.e., 4, 2, 40, and 62 the AG, SEC, CelebA, and FEMNIST datasets. SGD optimizer with the learning rate is 0.01 in the AG and SEC datasets, 0.1 in the FEMNIST and CelebA datasets.
Experimental setting for anonymization (Sun et al. 2021
In LDP-FL (Sun et al., 2021), 1) they design LDP mechanism to perturb the weights at the local client, then each local client applies split and shuffle mechanism on the weights of local model and sends each weight through an anonymous mechanism the cloud. The purpose of the shuffling mechanism is to break the linkage among the model weight updates from the same clients and mix them among updates from other clients, making it harder for the cloud to combine more than one piece of updates to infer more information about any client. Therefore, the key idea of the shuffle mechanism in LDP-FL is to mitigate the privacy degradation by high data dimension and many training/query iterations. In other words, the client anonymity is preserved, and the privacy budget will not accumulate.
When comparing with LDP-FL, we maintain their mechanism' spirits of no privacy accumulation. In the submission, we consider there is no privacy accumulation over the training iterations. It is equivalent the shuffling step that breaks the linkage among the model weight updates with associated clients. We also used the same randomized response mechanism in the paper, which is Eq. (Sun et al. 2021). to perturb the weight.
In the revision, we added an experiment that do not consider the privacy accumulation over data dimension and training/query iterations. This completely follows the gist of LDP-FL. In addition.
https: / hww.////..... www. www.sscww.oo/dg.r..oo
27

---

Under review as a conference paper at ICLR 2022
the weights used for LDP-FL. without actual shuffling splitting can be considered a lossless process, therefore the results we reported here can be counted as an upper-boune bound result for LDP-FL.
As shown in Table 2 obtained the slightly higher accuracy of LDP-FL compared with f-RR on the AG dataset. The key component LDP-FL that helps to reduce the privacy accumulation issue is the shuffling mechanism. However, as pointed out in (Erlingsson et al., 2019), in the real world, is possible that the anonymizers (i.e., shuffler) can either be compromised or collude with the coordinating server to extract sensitive information. Even though there marginally lower trade-off between privacy loss and model utility compared with LDP-FL, the advantage of f-RR is that it perturbs the data only once, then used the perturbed data for training process without facing an extra privacy risk potentially caused by the compromised or colluded anonymizer.
Table 2: Results of LDP-FL. without privacy accumulation.
CX
2
5
6
9
10
LDP-FL
78.73
82.21
83.25
84.19
84.36
84.22
84.64
84.43
84.31
84.72
f-RR
72.46
79.72
81.42
79.35
81.11
79.84
79.50
80.05
81.20
82.72
Noiseless model
87.59
PM [e]
PNN-SLS [s]]
corrected LATENT
BiRand [cx] (or-
Biitadd fex 1.00
20
Besand to 5.00
BeRand tevs 10
FEMNIST
(e) SBC
dondom--- Nelseless
Figure 15: Accuracy of LDP algorithms applied the embedded features e₂ in the AG, SEC, and FEMNIST datasets.
00
50
DM PM Pog
70
AcCURICY 8
Three eutouts
correctod LATENT (6.)
20
50
BiBand le.1 1t-
Billand [e] Sn- 5.0
Privacy budget (6)
Prisary oudget Fg
Prisery budge Px
Bifland le.] la-- 10.01
Fandom Rotudees
FEMNIST
(c)
Figure 16: Accuracy of LDP algorithms applied on the gradients Vi in the AG, SEC, and FEMNIST datasets.
DM L'g anent
93
70
HM Ing, & Anon!
60
Accumcy
Accurscy
20
PHSSU Irs, Aron!
outputs log Anon)
8
6AAnc)]
corrected LATENT
20
10
Itr-=
Bitfand (eu) Itve 1.01
4
2
10
30
Biflund (nu) w.5)
Privayy
budget
Privacy sudget
Privacy busget Cy
Oitlind [eu] Ityms.l 5.21
(0)
(b) FEMNIST
SBC
(4u)
Figure 17: Accuracy of LDP algorithms applied the gradients Vi, with the anonymizer (un et al. 2021
28

---

Under review as a conference paper at ICLR 2022
100
400 Labsl-Laploce 6- 1.00
Lab Labd-Laploce 6o-
5401 Label--apooca 6 -5.0
Aecurcy
Labd-Laploce
BitRa (c) (c1-
-0
Btfandd (m5m
Btttaadd -c--
BrtRand (t>- 10.00 20.01 Random
10
Privacy budget 54
Hiiracy sudcet
Pitracy budget
(a) AG
(b) FEMNIST
(c)
300
100
80
HMt [o,]
93
80-
Uhree cete--upputs [eu]
70
70
corrected LATENT (ec
60
60-
corrected GME
30-
BtRand led to 1.6)
Bliland [al] 2.5)
40
40
40
Privnry
budget
Privacy batget
BtRond led tc 10.00
(0)
AG
(b) FEMNIST
(c) SEC
Random No salass
Figure 19: AUC values of LDP algorithms applied on the embedded features ez in the AG, SEC, and FEMNIST dataset.
PM [og]
80
Three-a-tputs [Cg]
cor corwete ATTRTT [6])
corvecte OME (ec]
50
BeRand In.
10
Beitand [e. lay 3.0)
Privacy bucgzt Cy
Pryaay oudget Cx
Privacy budget
Biitand [e.] toy 10.00
(a)
FEMNIST
SEC
Bandom Mennedecs
Figure 20: AUC values of LDP algorithms applied the gradients Vi, in the AG, SEC, and FEMNIST datasets.
100
100
90
CRR Label Laplal 0.5)
80
C&B Label-Laphne Ouy 10.0) 10)
70-
BtRaad Ier
60-
Stlinnc
10.01
50
Random
40
10
Nelseless
Mayy budggt
(a) AG
(b) FEMNIST
(c) SEC
Figure 21: AUC values of each mechanism applied on labels in the AG, SEC, and FEMNIST datasets.
29

---

Under review as a conference paper at ICLR 2022
Table 3: AUC values of each algorithm applied on ea in the CelebA dataset. Average is the average of all 40 attributes.
Attribute
Heavy Makeup
High Cheekbones
Mouth Slightly Open
Algorithm 17 with Anon]
Attractive
Male
Smillng
Lipstick
Average
Noiseless
CX = D0
78.05
85.47
76.53
92.77
72.91
79.15
88.85
68.09
$1.96
50.00
50.9
50.12
51.54
$1.77
50.63
50.17
DM
CX
32.48
50.00
51.04
30.14
31.64
52.08
30.94
50.21
ex
52.08
50.00
50.87
30.20
31.91
52.03
50.40
50.19
51.83
50.00
51.13
50.09
52.22
$1.95
50.58
50.20
<x
$1.67
50.00
50.93
50.39
52.31
51.63
50.59
50.19
52.62
50.00
50.98
50.16
52.21
52.02
50.49
50.21
=
52.33
50.00
50.56
50.13
$1.90
51.53
50.68
50.18
cx =.5
$1.99
50.61
= 10
51.86
50.00
50.56
50.09
52.26
$2.19
50.63
50.19
Three outputs
cy
$2.57
50.00
50.59
50.19
51.80
51.83
50.62
50.19
32.07
50.75
50.12
52.14
$1.66
50.60
50.18
6x = 10
31.94
50.00
50.54
50.19
$1.44
$2.30
50.38
50.17
6x
52.44
50.01
51.10
50.13
52.02
51.60
50.74
50.20
PM-SUB
$2.49
50.00
50.87
50.15
52.18
51.64
50.51
50.20
6x
31.94
30.00
30.30
30.19
52.02
52.28
50.85
50.19
cx 1,ey =1
50.00
50.81
50.00
50.03
50.00
50.00
50.00
50.12
<x 1,6y 2.5
30000
50.00
50.00
31.39
50.00
50.00
50000
50.20
f-RR and Label
ex 1,ey
31.92
50.06
30.31
31.41
30.00
50.01
50.00
50.22
cx b.cy =1
50.64
50.00
50.07
50.01
50.00
50.39
50000
50.21
ex b,ey 2.3
50.00
50.00
50.00
Laplace
b.ey =5
51.87
52.40
50.00
50.00
50.00
50.00
50.00
50.21
ex = c0 =1
$1.70
50.00
50.00
50.00
50.00
51.03
50.00
50.12
c0 2.5
30.01
50.12
50.00
50.00
50.00
50.05
51.12
50.16
fx
10 =
30.00
50.00
50.00
30.13
50.01
50.00
50.00
50.21
<x
1,ry
59.8
60.65
56.7
64.57
54.56
56.44
64.93
51 86
6x 1,ey =1
34,52
55.03
53.37
36.99
52.63
53.34
57.43
50.91
ex
1,ey
1,ey =
59.98
60.15
56.28
63.67
54.14
56.91
63.38
51.77
tx = 5.6y
67.15
71.81
60.65
77.91
58.16
61.82
76.15
$4.99
BitRand
=1
58.04
59.87
54.24
62.99
54,05
55.67
62.35
$1.82
<x 5,4y 2.5
64.61
67.70
58.78
73.56
56.2
60.04
72.09
53.50
<x
67.51
71.41
60.94
77.96
37.82
61.37
76.11
54,82
6x = 10,6y 0c
75.09
81.96
70.14
90.22
65.26
71.76
86.68
63.31
10,
60.33
10 = 2.5
71.35
76.69
66.88
84,48
62.74
68.33
81.32
58.16
6x = 10, 10, =
74.45
82.28
69.23
89.88
64.81
71.47
86.38
62.25
30

---

Under review as a conference paper at ICLR 2022
Table 4: AUC values of each algorithm applied on the gradients Vo, with the anonymizer (Sun et al.
2021 in the CelebA dataset.
Mouth Slightly Open
Attribute
Heavy Makeup
Ligh Cheekhones
Algorithm 17 9 with Anon]
Attractive
Male
Smiling
Lipstick
Average
Noiseless
ex
79.15
43.44
55.86
49.63
65.42
48.86
43.33
60.50
49.85
DM
<x
46.94
44.25
49.00
49.68
49.97
51.73
59.24
51.00
38.60
40.81
51.87
64.81
49.55
49.05
48.58
50.25
=
47.48
62.64
53.94
49.60
50.88
49.07
$2.04
50.81
43.30
10
56.85
45.04
52.46
48.42
50.15
49.16
49.81
50.30
rx
49.61
63.99
52.06
47.27
$1.90
48.43
38.25
50.05
HM
<x
53.39
42.84
47,26
59.54
53.23
55.21
67.67
31.54
ex 10
44.02
68.26
$1.07
34.43
50.17
49.91
44.04
50.42
Three
<x =
54.71
43.89
55.70
55.37
48.46
54.93
43.11
49.99
35.45
65.80
50.13
42.53
50.21
45.62
50.36
51.54 54
outputs
cx 10
48.53
46.76
50.03
31.96
33.64
49.37
31.48
cx m
50.35
49.02
PM-SUR
47.62
43.88
50.86
5482
51.76
53.90
46.81
51.79
6x
40.82
74.82
49.80 86
55.00
54.19
52.39
45.04
41.51
33.03
49.01
49.40
33.76
LDP-FL
= 5
30.35
33.27
$1.99
56.76
49.71
50.02
56.31
51.74
6x
47.74
48.50
1, =1
50.00
50.81
50.00
50.03
50.00
50.00
50.00
50.12
<x 1,
50.00
50.00
f-RR and
1,ey =0
51.92
50.06
50.31
51.41
50.00
50.01
50.00
50.22
ex = 5,ey =1
50.64
50.00
50.07
50.01
50.00
50.39
50.00
50.21
cx =x= 2.5
30.00
50.23
50.00
49.99
50.00
50:00
50000
50.10
5x b.6y m
31.87
32.40
50.00
50.00
50.00
50.00
50000
30.21
Laplace
31.03
50000
50.12
= 10 2.5
50.01
50.12
50.00
50.00
50.00
50.05
51.12
50.16
fx 10.ey
50.13
50.01
50.00
50.00
1,6y
39.8
60.65
56.7
64.57
54.56
56.44
64.33
$1 86
ex 1,6y
54.52
53.37
56.99
52.63
53.34
57.43
50.91
1.ey 2.5
59.08
58.20
55.36
62.02
54.29
55.86
61.91
51.52
<x 1,cy =
3938
60.13
56.28
63.67
54,14
56.91
63.88
$1.77
fx b.ry
67.15
71.11
60.65
77.9
58.16
61.82
76:15
54.99
BitRand
ex b.ey =
38.04
39.87
$4.24
62.99
54.05
55.67
62.35
51.82
cx b,ey
56.2
60.04
b.ey =
67.51
71.41
60.94
77.96
37.82
61.37
76.11
$4.82
ex 10,ey
75.09
81.96
70.14
90.22
65.26
71.76
86.68
63.31
=1
61.87
64.88
59.04
68.82
56.8
60.33
67.20
53.84
(x 1y = 2.5
71.33
16.69
66.88
84.48
62.74
68.33
81.52
58.16
10,
74.45
82.28
69.23
89 388
64.81
71.47
86.38
62.25
31

---

Under review as a conference paper at ICLR 2022
Table 5: AUC values of each algorithm applied on Vo. in the CelebA dataset. Average is the average of all 40 attributes.
Attribute
Heavy Makeup
High Cheekbones
Mouth Slightly Open
Algorithm 17 with Anon]
Attractive
Male
Smillng
Lipstick
Average
Noiseless
CX = D0
78.05
85.47
76.53
92.77
72.91
79.15
88.85
68.09
$7.96
29.57
46.45
61.43
50.58
50.9
47.61
47.96
DM
CX
39.83
39.72
31.01
53.36
31.13
49.97
32.64
48.62
Ex
56.33
44.01
50.05
35.19
49.8
52.05
30.79
50.00
51.87
39.38
49.3
73.24
49.41
48.9
52.99
49.66
<x
48.42
40.86
46.84
72.35
50.55
49.52
47.68
50.66
49.02
36.59
49:03
59.12
50.39
50.46
53.36
49.22
=
46.31
33.84
$2.46
42.45
48.33
50.98
48.23
50.41
cx = 10
48.04
53.3
49.65
52.23
35.33
50.82
47.69
47.19
50.33
Three outputs
cy =
45.91
63.71
50.16
61.60
51.35
45.39
61.21
50.58
55.22
47.60
46.30
58.41
50.39
6x = 10
35.03
60.51
49.85
60.69
47.70
43.97
$4.05
49.88
6x =
61.56
63.02
46.78
38.77
52.23
50.38
48.60
48.90
PM-SUB
58.59
57.14
48.93
31.43
50.54
53.93
51.75
47.93
Cx
63.09
33.82
47.10
33.13
49.70
51.11
59.87
49.61
cx 1,ey =1
50.00
50.81
50.00
50.03
50.00
50.00
50.00
50.12
<x 1,6y 2.5
30.00
50.00
50.00
31.39
50.00
50.00
50000
50.20
f-RR and Label
ex 1,ey
31.92
30.06
30.31
31.41
30.00
50.01
50.00
30.22
cx b.cy =1
50.64
50.00
50.07
50.01
50.00
50.39
50000
50.21
ex b,ey 2.3
50.00
50.00
50.00
Laplace
b.ey =5
51.87
52.40
50.00
50.00
50.00
50.00
50.00
50.21
ex = c0 =1
$1.70
50.00
50.00
50.00
50.00
51.03
50.00
50.12
cy 2.5
30.01
50.12
50.00
50.00
50.00
50.05
51.12
50.16
fx
10 =
30.00
50.00
50.00
30.13
50.01
50.00
50.00
50.21
<x
1,ry
59.8
60.65
56.7
64.57
54.56
56.44
64.93
51 86
6x 1,ey =1
34,52
55.03
53.37
36.99
52.63
53.34
57.43
50.91
ex
1,ey
1,ey =
59.98
60.15
56.28
63.67
54.14
56.91
63.38
51.77
tx = 5.6y
67.15
71.81
60.65
77.91
58.16
61.82
76.15
$4.99
BitRand
=1
58.04
59.87
54.24
62.99
54,05
55.67
62.35
$1.82
<x 5,4y 2.5
64.61
67.70
58.78
73.56
56.2
60.04
72.09
53.50
<x
67.51
71.41
60.94
77.96
37.82
61.37
76.11
54,82
6x = 10,6y 0c
75.09
81.96
70.14
90.22
65.26
71.76
86.68
63.31
10,
60.33
10 = 2.5
71.35
76.69
66.88
84,48
62.74
68.33
81.32
58.16
6x = 10, 10, =
74.45
82.28
69.23
89.88
64.81
71.47
86.38
62.25
32


Reviews:
[{"review_id": "enpXEjtkxej", "reviewer": "Reviewer_UqE3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of this paper is to introduce a bit-aware randomization technique. That is a randomized response algorithm that flips a bit based on its position in the binary representation of the scalar (or naturally extend to a vector). I found the paper a bit hard to read because of clutter and too many notional changes. I have some clarifying questions from the authors:\n\n1. What is the notation $i$%$\\ell$ used in the definition of the bit-aware term? It needs to be defined more explicitly. \n\n2. Is the decoding function $\\mathcal E$ the averaging of the gradient? I would rather have the author clearly state that in the first 8 pages than point to the lines in the algorithm. I do not understand why the authors call it a decoding function to begin with. Decoding is a specific technical term in coding theory. \n\n3. What is $f^\\theta$? There is no such notation in the Algorithm. Is it a function taken from a set of functions parameterized by the model?\n\n4. After equation (6), why is the ratio of the probabilities the worst case?\n\n5. How does equation (6) happen? Why can you decompose the probability like that? If we change the binary vector by adding $1$, more than one coordinate gets affected; hence, the probability of seeing a bit in different coordinates is dependent. Am I missing something here? The same form of independence is claimed in the guarantee of Theorem 7. \n\n6. Am I correct in understanding that $\\epsilon_X$ is the privacy budget in the embedded space?\n\n7. Coming to the proof of Theorem 2, we have $\\mathbb E[ \\cdot]$ in equation (13). This does not make sense in any practical setting. This pretty much means that the privacy bound is in the average case, which is weird!! From what I see, the end result would be some kind of average-case DP, which has its own pitfalls! Can the author clarify this?\n\n8. What is the notion of neighboring dataset? It is very essential to know that before I can make a reasonable comparison with the previous work. \n\n9. Randomized response does not give an unbiased estimate. On the other hand, to do SGD, we need unbiased estimate of the gradient while ensuring that the variance is bounded. So, I feel there should be some form of bias correction, which is not in this paper. ", "summary_of_the_paper": "The paper tries to address the question whether we can have different noise scale for different bits for a high dimensional vector and still preserves privacy. They propose a method to do that. ", "summary_of_the_review": "There are a lot of clarifying question that I do not understand in this paper. \n\nThe authors have answered most of the clarification questions I had during the author's response phase. I still feel the paper is cluttered and not ready for ICLR and at maximum is a borderline accept mainly due to the strength of the problem studied. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Sn3t12Idnaz", "reviewer": "Reviewer_Sanq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+ The paper provides a simple but useful trick of tweaking the bit randomization probabilities based on the bit-index that results in \"dimension-elastic\" privacy/utility gains. \n+ The paper is in general well written and easy to follow. \n+ The comparison with prior research is very comprehensive along with strong experimental evaluation.\n\nComments.\n1. I am a bit confused as to why is the privacy analysis is performed w.rt the encoding/decoding $\\mathcal{E}$ instead of just $f-RR$.As  mentioned, the sensitivity of $f-RR$ is lower - 1 and since $\\mathcal{E}$ is applied to the output of f-RR,  by post-processing guarantee, LDP would still hold. Is the reason for choosing to analysis for $\\mathcal{E}(f-RR)$ the fact that the gradient computations require the decoding process and hence, this results in better utility by directly analysing w.r.t to $\\mathcal{E}$?\n2. Could the authors provide some details about motivation/purpose of the embedding step? Is it a smarter approach for dimensionality reduction or the embedded features carry some intrinsic meaning? Also, how integral is the embedding step to the proposed scheme - would the privacy/utility gains hold true if Alg.1 is applied directly on the input $x$? \n3. How is the proposed different label-RR scheme different from the RR techniques showcased by Ghazi et al. 2021? Also , why is the evaluation baseline  Label-Laplace instead of Ghazi et al.?\n4. Why is the sign bit valued at 2^{m+1} and not 2^m (since the MSB integer bit is 2^{m-1})? Also, is there any specific reason why the sign bit is assigned the highest weightage?\n5. Why is $\\epsilon_i$ intractable (just below Eq. 6)? Is it not a user defined privacy parameter whose value is an input to the algo?\n6.  Is not $|\\mathcal{E}(f-RR(v_a,i)-\\mathcal{E}(f-RR(v_{a|i},i)|$ randomized (since f-RR is)? How does this imply $|\\mathcal{E}(f-RR(v_a,i)-\\mathcal{E}(f-RR(v_{a|i},i)| < |f-RR(v_a,i)-f-RR(v_{a|i},i)|$?\n7. I could not understand why $P(f-RR(v_{a}(i)=v_z(i)))/P(f-RR(v_{a|i}(i))=v_z(i)) )\\geq 1$ is the worst case?\n8. I could not understand how is the anonymization work by Sun et a.l applied in the evaluation - exactly what is being compared against?\n9. Anonymization (shufflers) can be also implemented by cryptographic techniques such as mixed nets. Additionally, most of the work on shuffling DP provide amplification results that can work with using the same randomization mechanism for all. So I would suggest toning down the relevant sentences in Page 2. ", "summary_of_the_paper": "The paper proposes a randomized-response algorithm that takes into the bit indices and prioritises higher order bits. As a result, the utility is higher than other competitive algorithms. Additionally, the analysis allows the bit randomization probabilities not to be affected too much by the dimension of the data.", "summary_of_the_review": "Overall, the paper provides an effective technique for improved utility for RR. However, I have a few confusions regarding the solution setting (see comments above). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GPRjPo-BMk", "reviewer": "Reviewer_S5g9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nPros:\n\nI think the idea seems natural and as far as I see the LDP mechanism that takes into account the signifigance of the digit in the noise variance of the randomiser has not been considered before (good discussion of related literature).\n\nThe paper is well written and all the math that I checked seems correct.\n\n\nCons: \n\nI find the paper a bit difficult to read, everything seems to be discussed on a very low level. That is of course not a deficit per se, but a bit more higher level view on the problem would help, I think.\n\nExample: It is totally possible I missed something, but it is unclear to me, why do you only consider the LDP mechanism for the embedding and then observe the error in the decoded representation (that mathcal(E) representing the decoder) ? I mean, if the gist of the paper is that bit-aware LDP randomiser, why not to also have utility comparisons for that (more) directly ?\n\nI think the presentation could be improved. Examples:\nIn Section 5, Figure 3: This figure is not referred to anywhere, nor are the labels of the figure. You mean that you measure the expected error of the decoded features so that f-RR is replaced by Gaussian mechanism etc.?\nIn Figure 3, what is the sensitivity for the Gaussian mechanism, for example? sqrt(r) ?\nAnd for the Laplace mechanism? How do you use the Gaussian mechanism for the binary r-vector?\n\nOther:\n\n-The figures are quite small and thus a bit hard to read. \n-Would it be clearer if Fig. 7 had logarithmic y-axis?\n-When talking about bit-wise DP, I think it would be good to mention also the paper \nMironov, Ilya. On significance of the least significant bits for differential privacy. In: Proceedings of the 2012 ACM conference on Computer and communications security. 2012. p. 650-661.\n\nEDIT: I think the paper has its merits and the bit-wise mechanism is an interesting approach, however I think the paper is not yet mature for publication in ICLR. Some of my concerns regarding the presentation (e.g. why is only the privatisation of the embedded representation studied) seem to be shared also by other reviewers. Thus, I have decided to keep my score. ", "summary_of_the_paper": "The importance of rigorously taking care of privacy leakage in a DP algorithm on the bit level is well-know, see e.g.\n\nMironov, Ilya. On significance of the least significant bits for differential privacy. In: Proceedings of the 2012 ACM conference on Computer and communications security. 2012. p. 650-661.\n\nThis paper considers locally differentially private (LDP) mechanisms for binary representations of floating point numbers. The technique seems like a natural thing to do: the individual bits are flipped with a probability that scales with their importance.\n", "summary_of_the_review": "An interesting LDP randomiser that takes into account the significance of bits in binary encoding of floating point numbers (and vectors). However, I think the presentation should be improved to meet the bar of ICLR. Currently, I think this paper will not be easily understandable to anyone else than those working close to this i.e. practical algorithms for LDP and federated learning.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "E_h7cHKHPuA", "reviewer": "Reviewer_yGHK", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Though the authors name their mechanism as $f$-RR and claim its novelty, it is indeed an asymmetric version of RAPPOR that has been studied previously in the context of frequency estimation (see [WBLJ 2019] for instance). The only difference is the specific choice of parameters.\n\n\n2. This paper tries to apply frequency estimation techniques (such as RR or RAPPOR), which are usually designed for categorical data, into privatizing continuous data. Therefore the proposed mechanism can be viewed as first quantizing the data (i.e., mapping a vector $v \\in \\mathbb{R}^r$ to $r$ binary strings), and then applying RAPPOR on it. However, recent works have shown that such a naive two-stage approach is usually highly sub-optimal (at least in several canonical tasks such as mean estimation, see [CKO 2020]). Therefore I highly doubt the optimality of the proposed algorithm.\n\n\n3. The authors claim that the proposed solution resolves the curse of privacy composition; however, from the main utility guarantee Theorem 4, I don't think the problem is solved. Theorem 4 only gives an error bound on a single coordinate, so when applying the algorithm to a $r$-dim vector, there should be an additional $r$ factor. In general, I don't think it is possible to improve the state-of-the-art LDP mechanisms (such as [BDFKR 2019]) as performance guarantees of these mechanisms (order-wisely) match the information-theoretic lower bounds. It would also be good if the authors can provide standard error guarantees for their algorithm (e.g. the $\\ell_1/\\ell_2$ error for mean estimation) and compare them with previous works.\n\n\n4. I also doubt the correctness of the experimental results. For instance, upon a quick look at the codes, the \"Duchi Mechanism\" (which, I believe, should be the privUnit mechanism in [BDFKR 2019]) is indeed implemented as [DJW 2013]. Note that [DJW 2013] is a weaker version of privUnit and is only optimal when $\\varepsilon = O(1)$. It would be good if the authors can include more implementation details in the appendix.\n\n\n\n[WBLJ 2019] Locally differentially private protocols for frequency estimation\n\n[CKO 2020] Breaking the Communication-Privacy-Accuracy Trilemma\n\n[BDFKR 2019] Protection Against Reconstruction and Its Applications in Private Federated Learning\n\n[DJW 2013] Minimax optimal procedures for locally private estimation", "summary_of_the_paper": "The paper proposes an $\\epsilon$-LDP mechanism, termed $f$-RR, to privatize a real number. The mechanism first maps $v$ into its binary representation (with a sign bit) and then flips each bit with probability $p_i$. The authors then extend their mechanism to privatize a $r$-dimensional vector by sequentially performing the (scalar version) algorithm for each of the $r$ coordinates. By picking proper parameters, the proposed mechanism preserves $\\epsilon$-LDP. Finally, several experimental results compared with other previous methods are provided.", "summary_of_the_review": "In general, the proposed privatization scheme is not novel, and the analysis seems not optimal. I appreciate the authors' efforts in conducting extensive experiments, but there might be some issues when comparing the proposed algorithm with previous works, which I hope the authors can clarify.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes BitRand, a bit-aware randomized response algorithm, to preserve local differential privacy in federated learning. The main idea is to take into account the bit indices and prioritise higher order bits focussed towards achieving a utility which is higher than other algorithms which are oblivious to the floating point bit representation. Additionally, the analysis allows the bit randomization probabilities not to be affected too much by the dimension of the data.

Overall, the paper lay right at the borderline of acceptance. The paper's core idea, their development and experiments were all liked by the reviewers. The main issue the reviewers brought up was the writing and structuring of the paper and the presentation of the overall results. Most reviewers agreed that the paper presentation was not ready to match the bar for ICLR. There are multiple suggestions that reviewers have made - through their questions and direct comments and addressing those and rewriting the paper to highlight these aspects better will significantly improve the paper.
Decision: Reject