Task-aware Privacy Preservation for Multi-dimensional Data
Authors: Jiangnan Cheng
Ao Tang
Sandeep P. Chinchali
Venue: ICLR 2022 Submitted (2022)
Keywords: Privacy
Representation Learning

Abstract: Local differential privacy (LDP), a state-of-the-art technique for privacy preservation, has been successfully deployed in a few real-world applications. In the future, LDP can be adopted to anonymize richer user data attributes that will be input to more sophisticated machine learning (ML) tasks. However, today's LDP approaches are largely task-agnostic and often lead to sub-optimal performance - they will simply inject noise to all data attributes according to a given privacy budget, regardless of what features are most relevant for an ultimate task. In this paper, we address how to significantly improve the ultimate task performance for multi-dimensional user data by considering a task-aware privacy preservation problem. The key idea is to use an encoder-decoder framework to learn (and anonymize) a task-relevant latent representation of user data, which gives an analytical near-optimal solution for a linear setting with mean-squared error (MSE) task loss. We also provide an approximate solution through a learning algorithm for general nonlinear cases. Extensive experiments demonstrate that our task-aware approach significantly improves ultimate task accuracy compared to a standard benchmark LDP approach while guaranteeing the same level of privacy.

Under review as a conference paper at ICLR 2022
TASK- PRIVACY PRESERVATION FOR
DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Local differential privacy (LDP), a state-of-the-art technique for privacy preser- vation, has been successfully deployed in few real-world applications. In the future, LDP can be adopted to anonymize richer user data attributes that will be input to more sophisticated machine learning (MI.) tasks. However, today's LDP approaches are largely task-agnostic and often lead to sub-optimal performance they will simply inject noise to all data attributes according to a given privacy bud- get, regardless of what features are most relevant for an ultimate task. In this paper, we address how to significantly improve the ultimate task performance for multi- dimensional user data by considering a task-aware privacy preservation problem. The key idea is to use an mncoder-decoder framework to learn (and anonymize) lask-relevaní latent representation of user data, which gives analytical near- optimal solution for a linear setting with mean-squared error (MSE) task loss. We also provide an approximate solution through a learning algorithm for general nonlinear cases. Extensive experiments demonstrate that our task-aware approach significantly improves ultimate task accuracy compared to a standard benchmark LDP approach while guaranteeing the same level of privacy.
INTRODUCTION
In recent years, there has been tremendous growth in the volume of available data for machine learning (ML) tasks, leading to increasing emphasis on protecting user privacy. Differential privacy (DP) (Dwork et al., 2006 2014) is state-of-the thee--r technique for data privacy, and its local variant local differential privacy (LDP) (Kasiviswanathan et al., 2011) provides stronger privacy guar- antees for individual users without dependence on any trusted third party. In practice, LDP has been successfully deployed in products of companies like Google (Erlingsson et al., 2014), Apple (Dif-) Terential Privacy Team), and Microsoft (Ding et al.) 2017) for some basic frequency or histogram estimation tasks where raw user data is restricted to an nibit discrete variable.
In the future, LDP has the promising potential to be adopted in more complex scenarios (Hassan ct al. 9019 Dankar & El Emam 2013 Zhao et al.][2014] Cortés et al.] al.] (2166) (c.g., health care, power grids, Internet of Things) that feature richer user data attributes that feed into more sophisticated downstream MI. tasks. In such cases, today's standard task-agnostic LDPP approaches may not be ideal. For example, consider complex user data that must be anonymized before passing it into ML task function, such as neural network classifier for credit scores, A standard approach would be simply perturb the data by adding artificial noise whose scale depends on the sensitivity of user data (i.e. worst-case variation among a user population) and a given privacy budget, regardless of what ultimate task the anonymized data will be used for. However, the dimension and variability of user data inevitably grows, today's 's methods would generally have to increase the scale of noise to provide the same LDP guarantee, even though many data attributes might be highly variable across user population, but minimally relevant for task. As a consequence, one often adds excessive noise to all data attributes, which can severely degrade an ultimate task's performance.
To address these challenges, this paper introduces fundamentally different task-aware LDP ap- proach. Our method improves the performance of ML tasks that operate on multi-dimensional user data while still guaranteeing the same levels of privacy. Our key technical insight is to characterize the dependence of task performance on various user data attributes, which guides how we learn a concise, task-relevant encoding (i.e. latent representation) of user data. Then, for the same privacy

---

Under review as a conference paper at ICLR 2022
budget, can directly expose and perturb only the task-relevant encoding rather than raw user data, which often allows us to add less noise and thereby improve task accuracy (see Section 2 for a con- crete example). Crucially, user privacy is guaranteed under the same privacy budget according the post-processing immunity of DP (Dwork et al., 2014) (i.e., one cannot make the output of privacy algorithm less differentially private without additional knowledge). As such, an adversary cannot decode the anonymized latent representation to reduce the level of privacy. Our method allows us to learn and expose only high-valued data attributes and flexibly adjust their signal-to-noise ratio based on their importance to task. Moreover, when different data attributes are inter-dependent, task-aware LDP preservation is even more promising in that we can consider the utilities of the un- derlying orthogonal bases through principal component analysis (PCA) (Dunteman) 1989), instead of the raw data attributes.
Contributions. In light of prior work, our contributions are three-fold. First, we propose task- aware privacy preservation problem in which the effect of noise perturbation to preserve LDP effectively considered, based on encoder-decoder framework (Section 3) Second, in terms of task-aware privacy preservation, we obtain an analytical near-optimal solution for a linear setting and MSE task loss, and provide heuristic learning algorithm for more general settings (Section 4.. Third, we validate the effectiveness of our task-aware approach through three real- real-world experi- ments, which show our task-aware approach outperforms the benchmark approaches on overall task loss under various LDP budgets by as much as 73.0% (Section Appendix.
5
All the proofs are given in the
Related Work. 1) Utility maximization in DP/LDP. Most theoretical DP/LDP research either pro- vides a utility upper bound for given privacy budget under some weak assumptions (Alvim al.
2011
Kenthapadi et al. 2012 Duchi et al.) 2013: Makhdoumi & Fawaz 2013 Hardt & Talwar,
2010
Wang et al.) [219b]] Acharya et al. (2020). or designs optimal privacy preservation mecha- nisms in some specific use cases (McSherry & Talwar [007] Wasserman & Zhoul 2010 Fried-
man & Schuster, 2010; Xiao et al. 2010: Thakurta & Smith 2013| Kairouz et al. 2014,, Geng & Viswanath :015 Liu et al. 2016: Yiwen et 2018) 1018:JJsephh et al. 2019] Gondara & Wang 20200] Wang et al. 2020). To the best of our knowledge, with respect to multi-dimensionl user data, Murakami & Kawamoto (2019), Wang et al. (2019a) and Chen et al. (2021) are the only three sim- LDP framework under the assumption that some data attributes may not be privacy- sensstys,,,,ivve, and hence the utility improvement is mainly achieved by providing privacy guarantees for only a subset of attributes. Wang et al.] (2019a) mainly focuses on developing novel LDP mechanisms for multi-dimennional data with an objective of minimizing the worst-case noise variance, which naturally improves util- ity. Chen et al. (202T) preserves DP for images by adding noise to a latent representation learned through prok-propag of task loss. where the effect of noise perturbation is not considered. The key differences of our work are: i) we don't make additional assumptions on the sensitivity of user data, ii) our tasre approach achieves better task performance than standard LDP benchmarks by directly studying the dependencies between the task objective and different attributes of user data, and iii) we effectively capture the effect of noise perturbation resulting from privacy require- ments. 2) End-to-end (E2E) learning. There has been a wide variety of works training a cascade of deep neural networks (DNNs) through E2E learning, where tpsk-specific output is directly pre- dicted from the raw inputs (Muller et al., [0066] Wang et al. 2012 Donti et al. 2017 Zhou & Tuzel, 2018 Amos al., 2018). Our work also follows such a practice, but introduces [DP guarantee while improving the task performance. 3) DP in deep learning. The popularity of deep learning
faar works to ours. Murakami & Kawamoto (019)) develops a auility-maxinee
also draws great attention DP preservation therein (Song et al. | Shokri & Shmmaikov
2015
Abadi et al. 2016 Phan et al.
2016
Papernot et al. [0166] Phan et al.
et al. 2018
Wang et al.
2018 Phan et al.
2019
Arachchige et al. 2019;] Liu et al.
2020;] Mireshghallab al.
2020 Bu et al.] 2020). Our work is fundamentally different. Instead of preserving LDP during the
learning process. we use learning as tool to find the salient representation that improves the task performance under given privacy budget. In other words, we don't perturb the gradient for back- propagation but perturb the representation to guarantee LDP. Furthermore, we don't specificall deal with privacy preservation during the offline training process, which requires some ground truth user data (c.g., from a small set of consenting volunteers). However, LDP of user data is guaranteed after trained model is deployed online.
2

---

20 to Under review as a conference paper at ICLR 2022
2 BACKGROUND AND MOTIVATING EXAMPLE
<-LDP (Kasivisaanathan et al., 2011). Let x E IR be an individual data sample, and X be the domain of x, which is assumed to be compact subset of R A randomized algorithm M X _ is said to satisfy e-LDP with privacy-budged
> 0, if Pr[M(() E S] s et Pr[M(Z') E S], Ve,r'' E EX C im M.
(1)
Essentially, when is small, one cannot readily differentiate whether the input of M is an individual user x' based on MM's outcome.
Laplace mechanism (Dwork et al., 2014). To release a sensitive function g : X + Rd under e-LDP, Ve > 0, the Laplace mechanism widely used mechanism which adds Laplace noise to function g:
MLap(I, 9. = g(x) + Lap"( 0, Aig
(2)
where Lap" b) is d-dimensional vector whose elements are ii.d. Laplace random variables with mean ja and scale b, which leads its variance to be 21?.. For concreteness, the analysis and evaluation of this paper focus on the Laplace mechanism although the central idea of learning task- relevant data representations is applicable to other random privacy mechanisms as well. Aig = ma (19(x) g(x')ll measures the sensitivity of g under the & norm.
A motivating example. Consider an example shown in Fig. [ For simplicity, we only consider an example with two people, Alice and Bob, and two data attributes, age and wage. Suppose we need to preserve c-LDP for each person with c = 1 and our task is to estimate the mean wage as closely as possible. straightforward task- agnostic approach will directly expose both the two data attributes, and add Laplace noise with scale each attribute. However, task-aware approach will ex- pose only the wage attribute and add Laplace noise with scale b 10. Both the approaches guarantee LDP under the same budget (c = 1), but the wage attribute given by the task-aware approach is less noisy, and can expect that the corresponding estimated mean wage (i.e. the ulti- mate task objective) close to the real value with higher probability.
Name
Age [years)
Wage (dollars)
Boo
38
Task-agnostic
Task-aware
Lap" (p 0, = 20) Lap(ss 0 10)
Wage (dollars)
Wage (dollars)
(years)
44
40
27
28
48
33
Pr(M(a) 8 se P:(M()))) Va,s' e ((29, (11, 2f
Figure I: Motivating example. A task- aware approach (right) is more ideal than a task-agnostic approach (left) in terms of a mean wage estimation task, since the former perturbs the wage at- tribute with smaller noise while guar- antecing the same LDP budget
In more complex scenarios, such when each data at- tribute is not redundant but is valued differently in terms of the considered task or data attributes are dependent but not perfectly correlated, etc., the optimal solution will not be as straightforward as the given example and will be ex- plored in the following sections.
3 PROBLEM FORMULATION
We now introduce the task-aware privacy preservation problem depicted in Fig. 2 Let y = f(x) e RT denote the task output associated with each ground truth data sample x. where f represents the task function. To guarantee e-LDP for each data sample v, its true value should never be exposed to the task function. Instead, an estimate of xr, denoted by á, is used as the input to the task function with the corresponding task output ý f()). The objective is minimize the overall task loss = [[ y)] due to the difference between & and æ, where æ follows distribution Dz, and is a task loss function that captures the discrepancy between task output and y, such as the common & and cross-entrope loss.
More concretely, is first mapped to latent representation 6 E 2 through an encoder function = (x; 0.), where 0, are a set of encoder parameters. ó is then perturbed by a Laplace noise vector E TR.2 That is, Ga is treated as the sensitive function g in Eq Next, & is reconstructed
3

---

Under review as a conference paper at ICLR 2022
from using decoder function 2 =ga(o + w; 0a) where fg set of decoder parameters. Note that in reality the encoder is deployed at the end of each individual user and in general has to be lightweight (e.g.. linear one hidden-layer neural network).
The optimal task-aware & minimizes L while pre- serving c-LDP. In other words, the task-aware pri- vacy preservation problem aims to co-design en- coder and decoder, i.e., find proper values for Z, 0g and Oa. such that L is minimized and e-LDP is pre- served. Formally,
Encoder
Noise
Decoder
Function
Loss
(r
ga(=;Ba)
パ(
OtNine Thaining Only
x7
f(
min 2,0..0a
C -m,, [(,
(3)
s.t.
= f(x), y fgalge (z;
(4)
Figure 2: Overall architecture of the task-
0c) + wz 0a)),
aware privacy preservation problem.
x ~ Dz, w ~ Lap² (0, A1ge
The difficulty of our task-aware LDP problem mainly comes from the discrepancy of the measure- ment of overall task loss L, which depends on Dz and captures the average performance, and the mechanism of preserving LDP, which depends on X and focuses only on the worst-case privacy guarantee.
Benchmarks. We now describe two natural approaches to preserve e-LDP. First, task-agnostic approach adds noise directly to the normalized = For convenience we assume is already nor- malized, and we have Z n and (x()) = z. Second, privacy-agnostie approach adds noise ø obtained by considering the problem defined in Eq 3 with a pre-determined Z S and w being part is neglected when designing the encoder,
zero vector instead. That is, the crivacy-preservate and hence proper Z needs to be pre-determined or would always conclude larger Z (under which more information can be delivered when noise is absent) is better. Both two benchmark ap- proaches still need to determine the optimal decoder parameters Og for input ø + Note that for the task-agnoste approach even though 9. is an identity function, the corresponding optimal 9a is usually not an identity function, exemplified in Section A.7.1
4 ANALYSIS
In this section, we solve the task-aware privacy preservation problem. Assuming linear model and mean-squared error (MSE) task loss, we are able find near-optimal analytical results, which shed clear insight on how to co-design an encoder and decoder. We then move to general settings and present heuristic learning algorithm which demonstrates strong empirical performance.
4.1 LINEAR MODEL WITH MSE TASK LOSS
In this subsection, we consider a linear model with MSE task loss. More specifically, encoder function Gr: decoder function Id, and task function f are assumed to linear functions in their corresponding inputs, and the loss function is [| v) The task function f can then be expressed as f(x) = Kx, where E mm is the task matrix.
Practicality of the setting. Linear transformation is common encoding and decoding approach for many dimeensionality-rducttoon techniques, such as PCA. And fg task loss is widely used in many application scenarios. For example, given N samples of 2, suppose value these samples in a few directions, given by task matrix K. Then the sum of the variance of these estimates by using & instead of will be + Ez a0 [[( x:) ) so L Ey, K x Ex w. [ y) [ is natural objective function.
want to estimate the mean
Contents. We first summarize key results. For our task-aware approach, the optimal decoder is first
determined in Proposition [ and then the optimal encoder and the corresponding optimal loss is
We may either normalize each dimension independently when x: is multi-variate random variable, normalize all the dimensions jointly when is uni-variate time-series.
4

---

Under review as a conference paper at ICLR 2022
formulated in Proposition 2 under Assumption [ We then relax Assumption | and provide lower and upper bounds for the optimal loss in Theorem and an approximate solution. All proofs are in the Appendix.
Detailed analysis. We start our analysis with a few definitions. First, without loss of generality, assume the covariance matrix of x Mrr i.e., B[(r Mz) -x)" ]. is positive definite, where Ne E R is the mean vector of x. This assumption guarantees x cannot be linear transformed to a low-dimensional representation without losing information.
We then factorize E[(x )z)((z [ax"] into LL through Cholesky decomposition, where L E R is lower triangular matrix with positive diagonal entries. For analytical convenience,
let
h = L- Mz), which can be viewed as another representation of æ, with mean μ4b = 0 and covariance matrix he
Let Ps, denote the distribution of h, and H { (x (x- -a) E X} denote the compact set that contains all the possible values of h ~ Dn, Since K K(ē-x) = P(h h)), where P = K working with data representation h with task matrix P is equivalent using z and K. Considering zero-centered instead of original æ saves us from considering the constant terms in the linear encoder and decoder functions.
Let E E R x and D E TR=x denote the encoder and decoder matrix associated with h, i.e., Eh and h D Eh + w). Without loss of generality, we let Z 2 and allow some rows of E to be zero. Equivalently, based on the relationship between x and h, we have e = EL (x 12) and ã Mr. LD L be expressed as Eew = I. where oy is the variance of the noise added to each dimension of ø.
Uss) + w.). We denote the covariance matrix of w by Ewear and it can
We first determine the optimal decoder that minimizes C for given encoder E, which is given by the following proposition.
Proposition 1 (Optimal decoder that minimizes L). An optimal decoder D that minimizes & for given encoder E. and o can be expressed as D = ET (FFE + (o and corresponding L is L= CTTPPT P) (P PE (EET + 10
where Tr(-) denotes the trace of a matrix.
The next main step is to find an encoder E that minimizes Eq 7 Since A Age. = max,, |/ e' Ill, where E(H)- = {Ehlh E H} the image of H under linear transformation E, the design of encoder E will affect A1ge and therefore o.. and for different H's the effect of E is also different in general. So we need to carefully consider the relationship between and H.
When computing A1ge we can actually use H's convex hull S instead of H itself, according to the following lemma. This brings some analytical convenience the further analysis.
Lemma 1 (Convex hull preserves A1ge).
A19.
max o,
||U 1|1.
For encoder E, consider its singular value decomposition (SVD) instead: UEVT, where U E Z and V E R are orthogonal matrices and Σ E IR Xxm a rectangular diagonal matrix. And the
singular values are denoted by o.. Tn. with |oi| 2 ... jo,))- Then designing E is equivalent to designing matrix U, V and Σ. The geometric interpretation of applying transform E = UVV to set S consists of three aabttransforms: 1) rotate by applying rotation matrix VT; : 2) scale V (S) by applying scaling matrix Σ; 3) rotate ΣV (S) by applying rotation matrix U. In general, the choice of any of U. Σ. and V will affect A.g. and hence -.
Agg. over U and V. The resulting and only depend on under Assumption (Proositioons 2 3). We then find the
Our overall strategy is to first minimize the loss L and the sensitivity value
optimal Σ that minimizes the L within given privacy budget (Proposition 4 By the end, we
relax Assumption | to discuss the quality of our solution (Theorem D.
We start by noting that for two points within a compact set, they must lay on the boundary to have the maximum E, distance. We then make the following assumption in terms of as, which the boundary of S. It decouples the relationship between the choice of V and the value of Aige.
Assumption 1 (Boundary aS is a centered hypersphere). The boundary aS is a centered hyper- sphere of radius 2 0, which is expressed as (h E IR" | r2)
5

---

Under review as a conference paper at ICLR 2022
This is strong assumption, but at the end of this subsection will give lower and upper bound of C for any possible as based on the results under this assumption. Since (V = (h R" ||41 = r2) ås for any orthogonal V. this assumption gives us a nice property: the choice of V doesn't t affect Aige and oh Based on the above assumption, we can safely consider the optimal design of V that minimizes L when E and of are given, which leads the following proposition.
Proposition 2 (Optimal rotation matrix V that minimizes & under Assumption T. Suppose the eigen-decompesition of the Gram matrix PT P is expressed as P PQ = QA, where = diag (11 ,,)) E Rax= is a diagonal matrix whose diagonal elements are eigenvalues with A1 2 ... 2 An 2 O, and Q E Rux" is an orthogonal matrix whose columns are corresponding normalized eigenvectors. Then, when E and o are given, L is minimized for V Q, any Z n, and any orthogonal U. And the corresponding L can be expressed as:
L
(9)
0
It is clear that choosing Z > n brings no additional benefit. Hence we can only consider Z = for simplicity.
After the first two sub-transforms E and VT, the boundary as = {h E R" [| r²} becomes
(ΣVT(S) {o E <R' Σ o0/0 r²]. which is a hyperellipsoid. We then have the following proposition that gives the optimal U which minimizes Aige.
Proposition 3 (Optimal rotation matrix U that minimizes Aig. under Assumption I. E, U m Aige. and the corresponding minimum value
For a given
minimizes
A 19c- 2r
(10)
Next, we need to consider how to design the scaling matrix Σ, or equivalently, the values of of.... , to minimize Eq/9 which is the only remaining piece. Clearly, for any given of. if we increase them proportionally. of also needs to be increased proportionally to preserve the same e-LDP. So without loss of generality, we impose an additional constraint > of M, where M is positive constant. And the following proposition gives the optimal choice of Σ that minimizes and preserves e-LDP with the Laplace mechanism.
o
Proposition 4 (Optimal scaling matrix Σ. that minimizes L and preserves e-DD with Laplace mech- anism under Assumption] I. The optimal choice of of ... o² that minimize C and preserve e-LDP with Laplace mechanism under constraint
of E
M given by
T (1+
8
8
M
Z'
Vi (1,2,.., ,Z' 2
Σ
2
2
(11)
Vi 2Z' + 1, 2' + 2,....
where 7' is the largest integer such that:
Vxz
8
8r
(1+ Zz
0,
(12)
Σ
2
and the corresponding L is
8r 8/2/2
2'
L
A,
2
+
Σ 1'
A
(13)
1+ 2' 2r
e
i=
For task-aware approach, Proposition 1 complete the optimal encoder and decoder design that preserves c-LDP with the Laplace mechanism under Assumption
Validation of Task Loss from Theoretical Results (Fig. 3). We now compare the performance of
our task-aware approach and the benchmark approaches when = and Assumption | hholds. The derivations of the benchmark approaches are in Section A.7 We consider three different settings

---

Under review as a conference paper at ICLR 2022
A3 X be 0, 1, 2 respectively. For the privacy-agnostic approactf] we use a pre-determined Z = 2. Our observations are: 1) Compared to the task-agnostic approach, largest improvement in setting 1, because 22:4 = 0 implies that J2:4 are purely redundant. We can even expect higher gain than setting 1 when we have larger and zero X2. 's, and the gain will be zero if all the X; 's are equal. 2) The privacy-agnostic approach completely missed the information carried by 23:4, which explains the improvement of our task-aware approach for small r/e in setting 2 and 3. We can expect higher gain than setting 3 when we have larger n and larger A2:n 's, and the gain will be zero if all the missed 2;'s 's correspond to zero X 's and all the other X are equal.
which have 4 and A1 4 in common. And in setting 1, 2, and 3 we let X2
task-aware approach achieves the
Transition to general boundary as. Based on the results under Assumption [ we can give a lower and upper bound of L. for general as, which is not necessarily a centered hyper- sphere.
Task aware (1)
Tesk aware (2) -.. Task uvare (3)
Tesl-ggnssic
Ted-aggnssii (2)
Takeagmandic (3)
Privecy-ppooii
Privacy appaooi
Ovenall Taak Lavect
Theorem (Lower and upper bound of L for general boundary aS when e-LDP is preserved with Laplace mechanism). Suppose as C {h E R rm I |1hll1 I rmaa)) Then when c- LDP is preserved with the Laplace mechanism, the optimal L is bounded by:
5.0
Figure 3: Theoretical overall task loss L com-
[(Fmin's Xi:n c) S L" S [(Tmax A1: c) (14)
parison when L = / and Assumption [holds. We consider three different settings which have and A = 4 in common. Difference between set- tings: 1) λ2:1 0; 2) λ2:4 = 1; 3) 22-4 = 2. For the privacy-agnoste approach we use Z = 2.
where L(r; Aum e) is the value of L determined by Eq and 13ror given radius r, eigenvalues A1:n and privacy budget e.
4
Therefore, to preserve e-LDP with the Laplace
mechanism, our task-aware solution for general as is: 1) First, find the smallest Timx and the largest Tmin that bound aS; 2) Then assume as is {h E R"1 = ) and choose the encoder E and decoder D based on Proposition 2 We don't 't use the corresponding o however, because it may guarantee higher LDP than needed. 3) Next, compute o for real 0S under decoder D and privacy budget
The associated loss for the task-aware approach is at most L( Arms e). Though in general not optimal, it differs from L by at most L(rmax; Atmn t) - [[rmini Aims <). The difference is small when 05 is "nearly" hypersphere, i.e., Fmax Tmin 0.
4.2 GENERAL SETTINGS
For more complex scenarios, it is challenging to give an analytical solution to the task-aware pri- vacy preservation problem, especially when the encoder function ge. decoder function Ja. and task function f correspond to neural networks. Thus, we present a heuristic learning algorithm. (The benchmark algorithms are given in Section A.7.4 due to space limit.)
Algorithm is our proposed task-aware algorithm for general settings. First, the privacy budget and the latent dimension Z are required inputs for the algorithm. In general, should be proper, i.e. it is neither too small (we can find a better solution by choosing a larger 2) nor too big (which introduces unnecessary complexity). In practice a practitioner may need to determine a proper Z on case-by-case basis (See Section A.9 of the Appendix for more details). Next, the algorithm adopts an alternating iteration approach, where in each epoch, we first update parameters le, 02 by their corresponding negative gradients in line 3, and then recompute Aige and re-sample w from (o, A /e) in line 4. Note that, in terms of encoder parameter 0g, instead of considering the gradient of L, we add an & regularization term 7)|@=]12 where is a positive constant. Therefore, update 0. with the negative gradient - -(Ve, L + 2ry0c). Without regularization, the ||@= will grow to infinity since we can always achieve a smaller L by increasing the scale of ş proportionally. But it is not direction are looking for, since o will also increase proportionally to guarantee e-LDP.
2 One can use another value of 7, under which the result may be slightly different but our task-aware approach will still outperform.
7

---

Under review as a conference paper at ICLR 2022
Algorithm Task-aware Algorithm for e-LDP Preservation in General Settings
Require: Privacy budget and Z
I: Initialize encoder/decoder parameters le Og and noise vector w
2: for T (0, 1,... Neepccss -1) do
3: Update te and da with -V C 2170e) and -V,,L, respectively, by one or multiple steps
4: Recompute Aige, and re-sample w from Lap" (0, A1ge/t)
5: end for
6: Return ser Og and Aige
Task-aware (Ours)
Task-agnostic
Privacy-agnostic
MSE Concunyrion
Tark Loss (18.s)
0.330
0.020
0.025
0.000
0/19
0.000
1/6
Figure 4: Results of Hourly Household Power Consumption. Left: Task loss [( y) under different LDP budgets. Right: MSE of power consumption for each hour, when = 5. Our task-aware approach achieves lower MSE for all the day-time hours.
EVALUATION
Our evaluation compares the performance of the proposed task-aware approach and the benchmark approaches. Three applications and corresponding datasets from the standard UCI Machine Learn- ing Repository (Dua Graff 2017) are considered: mean estimation of hourly household power consumption, real estate valuation, and breast cancer detection. Configuration and training details are provided in the appendix due to space limitations.
Mean Estimation of Hourly Household Power Consumption. We first consider a mean estimation problem, based on measurements individual household electric power consumption over four years (Hebrail & Berard 2012). Each data sample æ E I221 is time-series that contains the hourly household power consumption for one single day, and our objective is to estimate the mean of the hourly houschold power consumption for N days. As discussed in Section 4.1 can define the overall task loss in the following way:
L = EyEDD K( - x)
Σ K 11 1
(15)
where K diag(ki, k2, ... k24) factors the importance of the mean estimation for each hour. In our experiment we set k; = 2 for i E {9, 10, ,0} (i.e., day-time hours) and k; = for other i's (i.e., night-time hours). And we adopt linear encoder and decoder model. As the considered problem is based linear model with MSE task loss, we adopt the solutions developed in Section 4.1 for the three approaches (we choose
3 for the privacy-agnoste approact
Fig. shows our experimental results. First, on the left, we compare the task loss ((ğ. y) for the three approaches under different LDP budgets. For each approach, the overall task loss decreases when a larger LDP budget is given. Besides, for given LDP budget, our task-aware approach always outperforms the benchmark approaches on overall task loss L, and the maximum improvements against the task-agnostic and privacy respectively. Second, on the right, we select = 5 and compare the MSE of power consumption for each hour. We that task-aware approach achieves lower MSE for all the day-time hours, and a similar MSE for the night-time hours. This observation can be explained by three reasons: 1) We select higher k; for the day-time hours, task-aware approach gives higher priority to
approach are 22.9% (E 10) and 11.7% (e 5),
8

---

Under review as a conference paper at ICLR 2022
Task-aware (Ours)
Task-agnostic
Privacy-agnoste
0.000
Ti.k 1.sk 1
Lave 1.5
((5
0.50
0.000
0.30
0.00
0.00
0.5
0.1
0.6
0.
0100
1000
0.10
6.15
0.30
Figure 5: Task loss I(j. y) under different LDP budgets for real estate valuation (left) and breast cancer detection (right).
minimizing the loss for those dimensions in x; 2) Although x has 24 dimensions, the variance in task-aware
each dimension can be mostly explained by several common latent dimensions, approach still achieves similar MSE for the night-time hours; 3) Our task-aware approach is able to adopt different scales different latent dimensions according their task relevance while the privacy-agnostic approach cannot.
Next, consider real estate valuation problem and breast cancer detection problem. Both the problems are not based on the linear model with MSE task loss, so we use Algorithm developed in Section 4.2 to solve them (we use Z 3 for both our task-aware approach and the privacy-agnostic approach for fair comparison; and the performance of the task-aware approach under different Z's can be found in Section of the Appendix).
Real Estate Valuation. For this problem, we use historical real estate valuation data collected from Taiwan Yeh Hsu/ 2018 which contains 400+ instances. Here, x R contains attributes that are highly related to the value of a house, including transaction date, house age, geographic coordinates, etc. And y E represents the valuation of house. We first train a one-hidden-llaer feedforward neural network regression model using the ground truth and y, to serve our task function f. Then, we minimize the la loss of ò and y, based on a linear encoder and decoder model.
Breast Cancer Detection. For this problem, we use well-known breast cancer diagnostic dataset (ttrect et al., 1993) from Wisconsin, which contains 500+ instances. Here, x E IR:30 contains 30 attributes that measure 10 features of cell nucleus. And diagnosis result (malignant or benign). We first train a one-hidden-layer feedforward neural network classification model using the ground truth and y, to serve minimize the cross-entropy loss of ğ and with encoder and decoder both being one-hidden-layer feedforward neural networks.
binary variable that represents
task function f. Then aim to
Fig. shows the evaluation results. For both problems, we can see our task-aware approach nearly always outperforms the benchmark approaches overall task loss L under different LDP budgets, which demonstrates the effectiveness of our proposed solution. The maximum improvements against the task task-agnostic and privacy-agnostic approach are 21.9% = 5) and 13.5% (e 5) for real estate valuation, and are 73.0% (c = 20) and 45.6% (c 20) for breast cancer detection.
CONCLUSION AND FUTURE WORK
This paper provides principled task-aware privacy preservation method to improve the privacy- utility trade-off for ML tasks that increasingly operate on rich, multi-dimensional user data. We gave an analytical near-optimal solution for general linear encoder-decoder model and MSE task loss, and developed heuristic learning algorithm for more general nonlinear settings. Our evalu- ation showed that our task-aware approach outperforms the benchmark approaches on overall task loss under various LDP budgets. Our future work will focus the analysis of the task-aware pri- vacy preservation problem for approximate LDP and other LDP mechanisms as well as multi-task learning.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Jayadev Acharya, Kallista Bonawitz, Peter Kairouz, Daniel Ramage, and Ziteng Sun. Context aware local differential privacy. In International Conference on Machine Learning, pp. 52 62. PMLR, 2020.
Mário S Alvim, Miguel E Andrés, Konstantinos Chatzikokolakis, Pierpaolo Degano, and Catuscia Palamidessi. Differential privacy: on the trade-off between utility and information leakage. In International Workshop on Formal Aspects in Security and Trust, pp. 39-54. Springer, 2011.
Brandon Amos, Ivan Dario Jimenez Rodriguez, Jacob Sacks, Byron Boots, and Zico Kolter. Dif- ferentiable mpe for end-to-end planning and control. arXiv preprint arXiv: /810
100.1 I 13400, 2018.
Pathum Chamikara Mahawaga Arachchige, Peter Bertok, Ibrahim Khalil, Dongxi Liu, Seyit Camtepe, and Mohammed Atiquzzaman. Local differential privacy for deep learning. JEEE Internet of Things Journal, 7(7):5827-5842) 2019.
Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020(23), 2020.
John Casey. A TREATISE OF THE ANALYTICAL GEOMETRY OF THE POINT. LINE, CIRCLE, AND CONIC SECTIONS. 1893.
Jia- Wei Chen, Li-Ju Chen, Chia-Mu Yu, and Chun-Shien Lu. Perceptual indistinguishabiliy-neee (pi-net): Facial image obfuscation with manipulable semantics. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6478-6487, 2021.
Jorge Cortés, Geir E Dullerud, Shuo Han, Jerome Le Ny, Sayan Mitra, and George J Pappas. Dif- ferential privacy in control and network systems. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 4252-4222444 4272. IEEE, 2016.
Fida Kamal Dankar and Khaled EI Emam. Practicing differential privacy in health care: A review. Trans. Data Priv., 6(1):35-67, 2013.
Apple Differential Privacy Team. Learning with privacy at scale.
URL
httpss//ooc-aasstss.evvlll wew.:eeeeess.deeeee......... apole. htppo//e.ccoolllesssee////popppp daamaing-wttt--piivaa-a---------
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. arXiv preprint arXiv:1712.01524. 2017.
Priya Donti, Brandon Amos, and J Zico Kolter. Task-based end-to-end model learning in stochastic optimization. In Advances in Neural Information Processing Systems, pp.
2017.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httt:tttp//chhhi
ics. uui. wus.uucieeddmmm eddu/ml
John Duchi, Michael Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 429-438.
IEEE, 2013.
George H Dunteman. Principal components analysis. Number 69. Sage, 1989.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 23:4):211-4077 2014.
10

---

Under review as a conference paper at ICLR 2022
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preseevin ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1067, 2014.
Arik Friedman and Assaf Schuster. Data mining with differential privacy. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 493-502, 2010.
Quan Geng and Pramod Viswanath. The optimal noise-adding mechanism in differential privacy. IEEE Transactions on Information Theory, 62(2):925-911, 2015.
Lovedeep Gondara and Ke Wang. Differentially private small dataset release using random projec-
tions. In Conference on Uncertainty in Artificial Intelligence, pp. 639-648. PMLR, 2020.
Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, 705-714, 2010.
Muneeb UI Hassan, Mubashir Husain Rehmani, and Jinjun Chen. Differential privacy techniques for cyber physical systems: a survey. IEEE Communications Surveys & TTttorial, 22(1):746-789, 2019.
Georges Hebrail and Alice Berard. Individual household electric power consumption data set, 2012. URL http:////////accol....//////////
ics. htt.:aa.........attttaaaaaa.aaaa
Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. The role of interactivity in local dif- ferential privacy. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pp. 94-105. IEEE, 2019.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. arviv preprint arXiv: 1407.1338, 2014.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, (0(3))793-826, 2011.
Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra. Privacy via the johmson--lnddensrrass transform. arXiv preprint arXiv:1204.2606, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11))227--233) 1998.
Changchang Liu, Supriyo Chakraborty, and Prateck Mittal. Dependence makes you vulnberable: Differential privacy under dependent tuples. In NDSS, volume 16, pp. 21-24, 2016.
Ruixuan Liu, Yang Cao, Masatoshi Yoshikawa, and Hong 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 501. Springer, 2020.
Ali Makhdoumi and Nadia Fawaz. Privacy-utility tradeoff under statistical uncertainty. In 2013 5 Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1627- 1634. IEEE, 2013.
Brendan McMahan, Galen Andrew, Ulfar Erlingsson, Steve Chien, Ilya Mironov, Nicolas Paper- not, and Peter Kairouz. A general approach to adding differential privacy to iterative training procedures. arXiv preprint arXiv:1812.06210. 2018.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) pp. 103. IEEE, 2007.
Fatemehsadat Mireshghallah, Mohammadkazem Taram, Ali Jalali, Ahmed Taha Elthakeb, Dean Tullsen, and Hadi Esmacilzadeh. A principled approach to learning stochastic representations for privacy in deep neural inference. arXiv preprint arXiv:2003. /2/54, 2020.

---

Under review as a conference paper at ICLR 2022
Urs Muller, Jan Ben, Eric Cosatto, Beat Flepp, and Yann L Cun. Off-road obstacle avoidance through end-to-end learning. In Advances in neural information processing systems, pp. 739- 746. Citeseer, 2006.
Takao Murakami and Yusuke Kawamoto. Utility-optimized local differential privacy mechanisms for distribution estimation. In 28th {USENIX} Security Symposium (!USENIX) Security 19), pp- 1877-1894, 2019.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. arXiv preprint 1:X.055610.05755. 2016.
NhatHai Phan, Yue Wang, Xintao Wu, and Dejing Dou. Differential privacy preservation for deep auto-encoders: an application of human behavior prediction. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 30, 2016.
NhatHai Phan, Xintao Wu, Han Hu, and Dejing Dou. Adaptive laplace mechanism: Differential
privacy preservation in deep learning. In 2017 IEEE International Conference on Data Mining (ICDM), pp. 385-394. IEEE, 2017.
NhatHai Phan, Minh Vu, Yang Liu, Ruoming Jin, Dejing Dou, Xintao Wu, and My T Thai. Het- erogeneous gaussian mechanism: Preserving differential privacy in deep learning with provable robustness. arXiv preprint /rXiv:/906.00 aee:::906044444 2019.
Axel Ruhe. Perturbation bounds for means of eigenvalues and invariant subspaces. BIT Numerical Mathematics, 1033):343-354, 1970.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1310-1321, 2015.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. 2013 IEEE Global Conference on Signal and Information Processing. pp. 245-248 248. IEEE, 2013.
W Nick Street, William H Wolberg, and Olvi I. Mangasarian. Nuclear feature extraction for breast tumor diagnosis. In Biomedical image processing and biomedical visualization, volume 1905, pp. 861-870. International Society for Optics and Photonics, 1993.
Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, pp. 819-850. PMLR, 2013.
John Von Neumann. Some matrix-inequalitee and metrization of matric space. 1937.
Di Wang, Marco Gaboardi, Adam Smith, and Jinhui Xu. Empirical risk minimization in the non- interactive local model of differential privacy. Journal of machine learning research, 21(000), 2020.
Wang, Jianguo Zhang, Weidong Bao, Xiaomin Zhu, Bokai Cao. and Philip S Yu. Not just privacy: Improving performance of private deep learning in mobile cloud. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2407- 2416, 2018
Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. Collecting and analyzing multidimennional data with local differential privacy. 20/9 IEEE 35th International Conference on Data Engineering (ICDE), pp. 638-649 IEEE, 2019a.
Tao Wang, David J Wu, Adam Coates, and Andrew Y Ng. End-to-end text recognition with convolu- tional neural networks. In Proceedings of the 21st international conference on pattern recognition (ICPR2012), pp. 3304-3308. IEEE, 2012.
Yu-Xiang Wang. Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1226-1235. PMLR, 2019b.
12

---

Under review as a conference paper at ICLR 2022
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-38)) 2010.
Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. Differential privacy via wavelet transforms.
IEEE Transactions knowledge and data engineering, 23(8):1200-1214 2010.
I-Cheng Yeh and Tuannunng Hsu. Building real estate valuation models with comparative approach through case-based reasoning. Applied Soft Computing, 65:260-271. 2018.
Nie Yiwen, Wei Yang, Liusheng Huang. Xike Xie, Zhenhua Zhao, and Shaowei Wang. A utilityy optimized framework for personalized private histogram estimation. IEEE Transactions on Knowledge and Data Engineering. 31(4):655-60) 669, 2018.
Jing Zhao, Taeho Jung, Yu Wang, and Xiangyang Li. Achieving differential privacy of data disclo- sure in the smart grid. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications, pp. 504-512. IEEE, 2014.
Yin Zhou and Oncel Tuzel. Voxelnet: End-to-end learning point cloud based 3d object detection. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition, pp. 4490- 4499, 2018
13

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1
PROOF OF PROPOSITION]
|
Proof. We have
[ - -E 1)h + Dw)
(16)
=ETT(P(DE-T)M) (DE P P Tr(DDww' PTPP))
(17)
-Tr(P(DE -T(P(DE-T)DDE- I) + Tr(PD DJ PT).
(18)
And verify that D E SEEE + + is zero point of
VC VD =P 22 T)E + D T)
(19)
Then we plug the expression of D into Eq 18 and get Eq
A.2 PROOF OF LEMMA I
In this subsection we give the proof of Lemma[] Here we treat E as a mapping instead of matrix, and its inverse mapping, which is also linear, is denoted by E-1,
We first prove the following lemma.
Lemma (Convex hull after linear transformation). E(S) is the convex hull of E(H).
Proof. Since H C S, we have E(H) C E(S). And for any v, E E(S) and E [0, 1]. we have 8h + (1 5)h' S, where h E--E(1y (v-( n and h (v') n S. Thus du + (1 8)v² E(öh + 5)h) E E(S). Therefore, E(S) is convex set containing E(H).
If (S) is not the convex hull, then we can find convex set such that E(H) C E(S). Then we have H S 1eE-e(00 (B) C S (If E (B) = S, we will have B E(E (B) E(S), which is not true). Besides, for any h h1' E (B) and å E [0, 1), we have ov E B, where U- E(h) and o' B(h'). Thus oh+ (1 5)h' E E + (1
EB) ns.
Therefore, E (B) n is a convex set containing H. This is contradictory to the fact that the convex hull of H. So ES)) must be the convex hull of E(H).
O
Now we can proceed the proof of Lemma] 1
Proof. Notice that Aige ma |V of l1, so our target is to prove
max w,
max |10- E.E'
||0 - 1/|11-
(20)
First, since E(H) S E(S), we have max,, || 11111 2 max ||v ||v-~oll v'Ih-
Next, suppose v 02 are the two points in E(S) such that the e, distance between them the largest. Since E(S) is the convex hull of E(H), we can express as (Vi E {1,2)):
p())
Li Di.
(21)
s.t. J. E E(H), Vj E (1))),
(22)
((1)
Σ 4. 1, and 4.j 20, Vj (1,2,...,pi)),
(23)
where p(i) is an positive integer, Vi E {1,2}. For convenience, we let A max,, "' m ||v- v'll1. Clearly, A S m'E ||v v/1
14

---

Under review as a conference paper at ICLR 2022
Notice that 21 22 can be expressed the linear combination of 01,
02 bj
mM [1,2) E ( ..tt.pp(22 p(2)}. That is, 3ri,4 2 O such that:
p(1) ((2)
p(1) p(2)
11 -1-09 02
Vi 82,0), s.t. ΣΣ
1a.0 1.
(24)
q=
Then have
p(1) p(2)
11 02/11
(1. -22
(25)
g=1
p(1) p(2)
p(1) p(2)
(1359(01. -21g)112
1i. Vo.ll(015 62,4)11
(26)
/=
j=1g=1
p() x())
Vig
AS max
110 v'111.
(27)
/=1
So we also have max,, e(E(S) |10 - 21 S max,, |/V -''l
Thus A1g. max,, | 0'111 max, ||- v v'11
A.3 PROOF OF PROPOSITION 2
Proof. We have Tr(PTT) P) Dr= Li= A; which is fixed number. Therefore we focus on maximizing the second trace term in Eq
For any Z 2 n we have
EE + o I UT + o diag of + - ... on + ow o D
U.
(28)
Z n in total
Thus we have for any orthogonal U:
E (EET
+ o EF
(29)
1
1
1
1
=VTTUT U'diag(
JUT
UEVT
(30)
o + 02
02
+
02
22
=VE diag
(31)
+ +
W
n
+
02
of
=V ddiag
VT
(32)
of + oZ
o
So ET (EET T is a positive semi-definite matrix with eigen-values oftoz
2 0. Then by Ruhe's trace inequality (Ruhe 1970) (a corollary of Von Neumanns trace
incquality (Von Neumann 1937)):
n
PE (EET + - <
(33)
0. + o²
and when V Q the equality holds. So we have Eq 9 for V Q, any Z 2 and any orthogonal
U.
A.4 PROOF OF PROPOSITION 3
In this subsection we give the proof of Proposition 3 For convenience we let a; r|os), Vi {1, 2. .-. nn., and then the hyperellipsoid {u E _R" "2 / 7² } can be written as {v e RT ET 1 /2/a²² = 1}. which is the standard expression. And we also have a 2 02 2 ... 2 On.
Before proving Proposition 3 first give lemmas related to the properties of hyperellipsoid.
15

---

Under review as a conference paper at ICLR 2022
Lemma 3 (Tangent hyperplane of hyperellipsoidd) Any tangent hyperplane of hyperellipsoid {u R" E== ///a = 1) can be expressed as:
11
13
a?uu 3 "
(34)
where U1, U2 are the coefficients.
Proof. It can be easily verified that point IR" such that
azu,
i
j E (1,2, n mk)
(35)
located on the hyperellipsoid. And by adjusting the values of u1, U2, ... Un we can express any point the hyperellipsoid with Eq 35 Moreover, the tangent hyperplane for point of tangency can be expressed as
= 1.
(36)
Plugging Eq 35 into Eq
we get Eq
Lemma 4 (Locus of vertices of circumscribed orthotope). The vertices of any orthotope that
circumscribes hyperellipsoid {u E | "' ut /a/ = 1] is on hypersphere {u E R 3'EE of
E
Proof. When n = 2, the hypersphere reduces to a circle that is well-known as the orthoptic circle of ellipse (Casey) 1893). We hereby generalize this result to any n.
vertex of a circumscribed orthotope can be viewed as the intersection n tangent hyperplanes. According to Lemma we can express them
Σ Ug
Cffly Vi f1,2,... (1))........
(37)
where is the index of the i-th hyperplane. Here we let ーー= uZ, = 1, E f1,2, ....,................ .n). Besides, these hyperplanes are perpendicular to each other, so the coefficients also satisfy Σm= Uj = 0, vk * j. So if let "x" be matrix with Ui, on the i-th row and j-th column, Vi,j, then $2
an orthogonal matrix, and further have Σn " 1, Vi (1,2, ... ,n].
Thus the considered vertex satisfies Eq 37
Vi E (1,2, .n.. which implies it also satisfies:
12
n
n
Σ>
0 1 1.j
(38)
1=1
1=1
1=1 i=1==1
For the left hand side, we have
n
n
Ui.Wi,k
(39)
1=
jzp
Σ
03
Σ
Ui Mr.jūi,)))ff =
Σ
(40)
1=1
1=1
j$p 1=1
1=1
And for the right hand side,
W
Σ o3.
(41)
==
j=1
1=1
Ø=1
Thus the vertex is hypersphere (u E
md
Σl af)
16

---

Under review as a conference paper at ICLR 2022
Since the equation of centered hypersphere after rotation remains unchanged, we have the follow- ing corollary.
Corollary (Locus of the vertices of circumscribed orthotope after rotation). The vertices of any orthotope that circumscribes hyperellipsoid {8 R E; v2/ag 1} after rotation is on hyper-
sphere {o E R" Σx= -i= 0,.)
Now we can proceed to the proof Proposition
3
Proof. We first consider the case when is power 2.
For the rotated hyperellipsoid, we consider whether there's any point e E R" s.t. | 2
V イーー az. Suppose we couldn't 't find such a point. Then consider any tangent hyperplane whose normal vector has the following form: (u1, "2 un). S.L. un +1, vi E 21, ,,, ,.). It can be expressed as:
Σ Uj W(u,, u2, Un))
(42)
where W (wi, u2, ... un) + R maps (ii, un) to a corresponding constant. And we
have W (w1, U2. un) E== a².
Since is a power of 2. we can find Hadamard matrix Ω in R=*" whose elements are either 1 or -1, such that QΩ = n!. We let uz, be the element of R on the i-th row and j-th column, Vi, and consider the intersection of the following n tangent hyperplanes:
リイ = WWw (W U12 U,,)), ViE (1,2,... ,n,
(43)
1=1
whose intersection point must satisfy:
(Wu,,, u.,,, (i,,))
(44)
Similar to the proof of Lemma 4 we can easily prove the left hand side equals n Σý= vz. and the right hand side strictly less than n Σj= az- Thus the intersection point doesn't locate on the hypersphere {v R Σn o/ - } But since the considered n hyperplanes surfaces of circumscribed orthotope, the intersection point is hence a vertex and must be on the hypersphere {v II E'= of Σi= a²), according to Corollary This contradiction means
also the
that, the assumption that cannot find point i T s.t. ||ö|| a3 is false.
Thus the point R" s.t. |l
exists, and the é distance between and - (which both lie on the hyperepllisoid) is 2 Σn= Thus we have Aıg. 2 2 Eド= oj.
For U = I, which means we don't actually rotate the ellipsoid {u E R" Σ 0f/a = 1}. we have for any point on the ellipsoid
n lual
n
(45)
according to the Cauchy- Cauchy-Schwand Schwartz inequality. This implies any point on the hyperellipsoid has ||ul] 5 / /y= az. So Agge 5 2 Σ ag. Combined with the result in the above paragraph we know Aige 2 - a3 for U I.
Thus the proposition is proved for n being a power of 2. For other n's, we can treat the considered hyperellipsoid as degenerated hyperellipsoid in space Ra where ñ is the smallest power of 2 such that ñ > n. This implies the proposition still holds.
Therefore, the proposition is true for any n2.
17

---

Under review as a conference paper at ICLR 2022
A.5 PROOF OF PROPOSITION 4
Proof. First, to preserve e-LDP with Laplace mechanism, the minimum o required is:
0 2 (Aige) = 4, - o 8r
(46)
2
based on Proposition 3 and constraint Σi= of = M.
Next we need to determine ........ ,o" The considered problem is an optimization problem which aims minimizing C in Eq 9 under constraint Di=1 of M and of 2 0 (here view of instead of the decision variable). Note that though in Eg we also have of o don't need to explicitly consider this constraint, because minimizing L will implicitly guarantee that, according to the rearrangement inequality. This problem can be solved by KarushKuhnTuckkr (KKT) approach, with the following Lagrangian function:
11
F(o .. , on, On B)
A
Σ
Ca(-oat) +
of M),
+
(47)
where a,,... .n, and 8 are Lagrangian multipliers. We know that the solution will automatically
guarantee of 2 2 o so we can safely assume there exists Z' S such that a; = 0 for S Z', and a; > 0 for Z'. Then for Z' we have of and for I Z' we have
FF
B
(48)
V
(af
Combining with 2i=1 M and Eq 46
eventually get Eq 11 Enforcing o3
get
Eq
And plugging Eq into Eq we get
Eq
13
A.6 PROOF OF THEOREM 1
In this subsection we give the proof of Theorem
We start with two definitions: L (aS: P..) c) denotes the optimal loss for any boundary as, task matrix P that preserves e-LDP with Laplace mechanism; R(r) = {h E R²I] r² is the centered hypersphere with radius r.
Next we give the following lemma.
Lemma (Invariance of the optimal loss after scaling).
(aS; P,e) =
(49)
where p > O is a scalar and p(S) = (ph|h E S).
Proof.
We only need to consider fixed task matrix P. For any encoder E, decoder D and noise variance 2 they preserve c-LDP with Laplace mechanism for boundary ds, then we have
Aig. 2
A1pge
Tw 2 2
(50)
where
Aipg. = = max h.EsS
|Eh Eh'll 112
max v.0(E((S)
|
Ev'll2
(51)
Thus we know encoder E, decoder D and noise variance of also preserve Pc-LDP with Laplace mechanism for boundary Öp(S). And the reverse also holds true.
So we must have L (OS; P. = (Op(S))) P.)).
Now can proceed the proof of Theorem 1
18

---

Under review as a conference paper at ICLR 2022
Proof. We first construct a distribution Di', s.t. points drawn from D uniformly distributed on R(2 Then h' ~ DNy satisfies Enen = I. And we also have 0s' = R(22-l) where S' the convex hull of H' (H' is the domain of h' Dr.). According to Proposition for h' Dr have L (R((2"=)); Pc) = f(2"-1; >1,,, pe). 4p, O.
We next consider scalar p 22-1/rmma and the optimal loss (3p())) P. pc). For any encoder E, decoder D and noise variance o? if they preserve pc-LDP to boundary Op(S), then they preserve least pe-LDP boundary R(2"-1), since I((2=1) C p(S). Thus we have L (op(S); Z C (R((2=));; Pe).
This further implies:
()) = (O0pS))
(52)
26 (R(("" L(2 Xi:n pe) = [(Tmin A1ms e).
(53)
So the lower bound of Theorem
i proved. The upper bound can be proved in the same way.
A.7 BENCHMARKS
A.7.1 TASK LOSS FOR TASK-AGNOSTH APPROACH
One can obtain the resultant optimal L for the task-agnostic approach by letting E L and using 7 as stated in Proposition | It is worth noting that the associated decoder D = L (LL + not an identity matrix in general.
Corollary (Optimal L for the task-agnostic approach that ) For the task-agnostic approach, the optimal L that preserves e-LDP is
C = TT(PPP -) Tr(P PL +0)1)'-),
(54)
where of = -(( with (x) x.
A.7.2
TASK LOSS FOR PRIVACY-AGNOSTE APPROACII
Through similar analysis as Proposition 2 one can obtain the resultant optimal L for the privacy- agnostic approach, which has pre-determined Z n.
Corollary (Optimal L for the privacy crivacy-agnostic approach that preserves c-LDP), For the privacy- agnostic approach with a pre-determined Z < n, the optimal L that preserves e-LDP is
C =
z
A
0
Σ
n
A
(55)
02
(=++1
where 0² = =2(Aige) -2/
Proof. For privacy-agnostic approach, we have Z < Since for encoder we need to select the top-Z Z principal components, we have V = Q. Similar to the proof of Proposition for given Z < have
EE + USE UT t Udiag + to..... ......, .0. + DUT
(56)
and through similar derivations we eventually get
Z Σ
o²
TT(PTPE' (EET + -0
=
A 2
(57)
m
Combined with Eq. we get Eq. 55
19

---

Under review as a conference paper at ICLR 2022
A.7.3 TASK LOSS FOR BENCHMARK APPROACHES WHEN L AND ASSUMPTION HOLDS
When L and Assumption D holds, for the task-agnostic approach, according Eq. 54 we have
of 1 o
nt 8
L
Tr(P
P)
A
(58)
1+n 8
For the privacy-agnosti approach, according Eq. oy's and minimum ò1 Sige, we get
55
and Eq.
10
and assuming we have equal
Z 8r /22
2
C 1 8r
X
A
(59)
2/2
i=++1
where the value of Z is pre-determined.
A.7.4 BENCHMARK ALGORITHMMS UNDER GENERAL SETTINGS
For the vacy preservation by updating Og and Oa with -Ve and C, respectively. Next, we fix en- coder parameters 0g and train the decoder with input e + w (a modification of Algorithm [iine 3-4). The task aask-agnostic approach trains the decoder in the same way, but fixes ge an identity mapping function.
approach, we first train the encoder and decoder without considering pri-
A.8 CONFIGURATION AND TRAINING DETAILS OF THE EVALUATION
Table I: Evaluation Details
APPLICATION
NUM OF SAMPLES
TRAIN/TEST SPLIT
TRAINING EPOCHS RUNTIME
HOUSEHOLD POWER
1417
0.7/0.3
NA
< 1 MIN
REAL ESTATE BREAST CANCER
414
0.7/0.3
2000
< 2 HRS
569
0.7/0.3
2000
< HRS
Our evaluation runs on a personal laptop with 2.7 GHz Intel Core 15 processor and 8-GB 1867 MHz DDR3 memory. Our code is based on Pytorch. We use the Adam optimizer and learning rate 10-3 3 for all the applications. The number of samples, train/test split, training epochs, re- sulting runtime consumption is based on the thcoretical solutions, so "training epochs", which is associated with the gradient-based method, doesn't 't apply.) We also provide all our documented code supplemen- tary material and will make it publicly-available after the review process. All three datasets cited in the evaluation are publicly-availate from the standard UCI Machine Learning Repository (Dua & Grafi 2017) and anonymized using standard practices. The individual dataset licenses were available.
summarized in Table [1] (Note that the evaluation for hourly houschold power
For task function f. we use me--iddeen-laye layer feedforward neural network with input size hidden size 1.5n and output size 1 in both the real estate valuation and breast cancer detection experiments. The activation function used by the hidden layer and output layer is a Rectified Linear Unit (ReLU). In our experiments, we find that the chosen network architecture is good enough to yield near-zero loss with ground truth x and and to avoid overfitting we don't 't choose deep neural network. For example, we did not see any task improvement using a two layer network etc.
For the encoder/decoder,, we use a one-layer neural network (linear model) with input and output size n in the real estate valuation experiment. For this experiment, a linear encoder/decoder model is already enough to provide good performance (see the next subsection for further details). We use -aeeeidden- feedforward neural network with input size n, hidden size n and output size n in the breast cancer detection experiment. The activation functions used by the hidden layer and output layer are a logistic and identity function, respectively.
For the heuristic learning algorithm developed in Section set 77 0.2 and 7) 0.001 in real estate valuation and breast cancer detection experiments, respectively; and in both experiments, for each epoch update 0. and 0g by 15 steps.
20

---

Under review as a conference paper at ICLR 2022
0.600
Task lip 8)
Task Loss ((5--))
0005
0.400
0.010
0.200
3
00005
2 30
0.000
0.2
0.4
0.5
0.8
G- 10"
0.1
0.15
0.2
1/c
1/e
Figure 6: Task loss ((), y) of our task-aware approach under different Zs for real estate valuation (left) and breast cancer detection (right).
Task-aware (Ours)
Task-agnostic
Privacy-agnostic
0.020
Task 1(0r.1
0.015
0.010
0.005
Figure 7: Task loss 1(0, y) under different LDP budgets for real estate valuation, when one- one-hidden- layer feedforward neural network adopted for both encoder and decoder.
A.9 A PROPER Z SHOULD BE DETERMINED ON A CASE-BY-CASE BASIS
practitioner may need determine proper Z on a case-by-case basis for our task-aware approach. Fig. 6 illustrates the performance of task-aware approach under different Z's for real estate valuation and breast cancer detection experiments. We can observe that in both two experiments, obtained the best performance average when Z 3, i.e., n/2 for real estate valuation and n/10 for breast cancer detection
mentioned in Section 4.2
A. NON-LINEAR ENCODER AND DECODER MODEL IN REAL ESTATE VALUATION EXPERIMENT
Theoretically, increasing the model complexity of the encoder and decoder can potentially provide a better performance. However, in our real estate valuation experiment we find that linear encoder and decoder model is already good enough.
To illustrate this, we adopt one-hidden-layer feedforward neural network architecture for both en- coder and decoder, which has input size n, hidden size n and output size n, and the activation functions used by the hidden layer and output layer are ReLU and identity function, respectively. Then we set 7 0.001 and repeat the real estate valuation experiment (with other configurations being the same). We observe the performance of our task-aware approach is worse in Fig. 7 than in Fig. 55] The explanation is, due the unnecessary complexity of the encoder and decoder, it harder to learn good encoder and decoder parameters heuristically. Thus, conclude that using simple encoder and decoder, as also observed for the other datasets, is sufficient for high task accuracy.
A.11 EXPERIMENT WITH NIGH-DIMENSIONAAL DATA
'The privacy-agnosta approach also achieves the hest performance average under the chosen Z's
21

---

Under review as a conference paper at ICLR 2022
Task-aware (Ours)
aass-agnostic
Privacy-agnostt
1,300.00
Task L (S..3)
Task Loos 31
2.00
1,000000
1.30
1.00
0.50
0.00
0.30
0.15
0.20
0.05
0.30
0.35
0.20
1/c
1/c
Figure 8: Task loss 1(0. y) under different LDP budgets for handwritten digit recognition.
To illustrate task-aware approach in Section 4.2 also works well for high-dimensional data, such as image data, we consider a handwritten digit recognition problem with well known MNIST dataset LeCun et (998). Here, 7874 represents 28 28 image handwritten digit. And E {0, 1, .. 9} is discrete variable represents the digit in the image. We first train a linear classification model using the ground truth x and y, to serve our task function f. Then we aim to minimize the cross-entropy loss of ÿ and with linear encoder and decoder. We use Z = 10 for both our task-aware approach and the arivacy-agnostic approach.
Fig. 5 shows the evaluation result. Since the task loss L of the task-agnostic approach is much larger separate sub-figure on the left. the right, we can
than the other two approaches, we put see our task-aware approach always outperforms the privacy-agnosti approach on overall task loss under different LDP budgets, which demonstrates the effectiveness our proposed solution. The maximum improvement against the crivcc--agnssie approach is 23.8% (e 20).
22


Reviews:
[{"review_id": "uEbTjT12vii", "reviewer": "Reviewer_mTuz", "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": "I think this paper addresses an important problem which is improving the privacy-utility trade-off in LDP where there are multiple users' data.\nThe proposed approaches solves the problem in an efficient way. The motivation is clear, it is well-structured and well-written. In my opinion, there are three things that can improve this paper. i) The paper presents a heuristic learning algorithm, but the analysis of the task-aware privacy preservation problem for approximate LDP would be more interesting. ii) Comparison with the state of the art approaches both in text and experiments could be improved. In the current version, the difference between the previously proposed methods is not so clear. iii) The results on larger datasets and the result in terms of accuracy. \n\n", "summary_of_the_paper": "This paper proposes a task aware local-DP approach to improve the performance on multi-dimensional data with same level of privacy. This approach is based on encoder-decoder framework that perturbs only the task relevant encoding instead of the raw user data that generally causes less noise addition and improves the task accuracy. Besides, the paper provide a heuristic learning algorithm for more general settings. The proposed approach is compared with task agnostic and privacy agnostic approaches on different datasets and the results show the proposed method outperformes them on overall task loss under different privacy budgets.", "summary_of_the_review": "This paper considers and important problem and brings an efficient solution. It is well-written. The experiments shows the performance improvement of the proposed method. However, the experiements could be extended on larger datasets and they can be compared with SOTA.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Vw4tosOROEj", "reviewer": "Reviewer_r5c5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": " Strengths\n+ The problem formulation is simple and easy to follow to get the idea of the proposed method. \n+ They provide an intensive and rigorous analysis for an analytical near-optimal solution for a linear setting and MSE task loss in terms of task-aware privacy preservation analysis.\n\nWeaknesses\n-\tFirst, the general idea of the paper is interesting, but it seems to be incremental and at an early stage of this work. The novelty is limited. The idea of redistributing the noise across input features has been extensively studied, for instance, with autoencoder-decoder and layer-wise relevant propagation, and forward derivatives (Phan et al., 2017; 2019). These references should be considered as baselines for comparison to highlight the novelty of the proposed approach. However, these critical references are missing. \n-\tSecond, the reviewer does not understand why we need LDP here and why not centralized DP? What is the threat model? Training the autoencoder-decoder would need a centralized server to gather all the data tuples together. If so, there is no need for LDP.\n-\tThird, how practical is Assumption 1? It is not clear at all in the current writing. Also, it is unclear to the reviewer that why Propositions 1-4 result in an optimal encoder and decoder design that preserves $\\epsilon$-LDP.\n-\tIn the analysis, a linear model with an MSE task loss is used in the analysis and experiments, which may not be easy to extend to other complex tasks, such as deep learning. \n-\tExperimental results can be improved. The datasets used in the experiments still have a limited number of dimensions, such as dim=24 in power consumption, dim=6 in real estate valuation, and dim=30 in breast cancer detection. It would be interesting if the work can be done with the more complex datasets and learning tasks, such as image datasets with thousands of dimensions and deep learning tasks for example. Adaptive mechanisms such as (Phan et al., 2017; 2019; 2020) and other related works listed below can be considered as baseline approaches for comparison. \n-\tThe compared benchmark approaches are unclear. There is no place to define or refer to the compared method. The reviewer needs to guess what it means. Also, there is a limited number of comparisons, which makes the paper unconvincing. \n\nNhatHai Phan, Xintao Wu, Han Hu, Dejing Dou. Adaptive Laplace Mechanism: Differential Privacy Preservation in Deep Learning. IEEE ICDM'17.\n\nNhatHai Phan, Minh Vu, Yang Liu, Ruoming Jin, Xintao Wu, Dejing Dou, and My T. Thai. Heterogeneous Gaussian Mechanism: Preserving Differential Privacy in Deep Learning with Provable Robustness. IJCAI'19.", "summary_of_the_paper": "This paper provides task-aware privacy preservation to improve the task performance for multi-dimensional user data for deploying a trained model. The paper’s spirit is to use an encoder-decoder framework with a Laplace noise added to learn a task-relevant but LDP privacy preserved latent representation of user data. The author also provides an analytical near-optimal solution for a linear setting with mean-squared error task loss. They show the effectiveness of their method via experiments on three real-world datasets.", "summary_of_the_review": "The general idea of the paper is interesting, but it seems to be an early stage of this work. Investigating the work with more complex datasets and tasks and more baseline comparisons would make the paper more convincing. There are a lot baseline of LDP or task-aware work to compare with the work, for example\n[1] Wang, N., Xiao, X., Yang, Y., Zhao, J., Hui, S. C., Shin, H., ... & Yu, G. (2019, April). Collecting and analyzing multidimensional data with local differential privacy. In 2019 IEEE 35th International Conference on Data Engineering (ICDE) (pp. 638-649). IEEE.\n[2] Liu, R., Cao, Y., Yoshikawa, M., & Chen, H. (2020, September). Fedsel: Federated sgd under local differential privacy with top-k dimension selection. In International Conference on Database Systems for Advanced Applications (pp. 485-501). Springer, Cham.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "Pr1WHEQgRm", "reviewer": "Reviewer_S4hg", "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": "Strengths:\n1. The problem of improving utility and privacy trade-off in local differentially private ML is an important practical problem.\n2. For linear encoder and decoder, and MSE loss setting, an analytical near-optimal solution is provided. The comparisons among task-aware approach and the benchmark approaches give an intuitive interpretation of why the parameters obtained from task-aware approach are better. \n \n\nMy main concern in this paper is whether the proposed method can preserve local DP. \n1. The local DP setting is not clearly given, which I mean, interactive [1] or non-interactive setting [2]? \n2. Based on my understanding of this paper,  Algorithm 1 needs $N_{epochs}$ to find the encoder, decoder and sensitivity. During this interactive proposes, the algorithm continues to query the sensitive user data samples. I think the composition theorem should be considered. \n3. For achieving private local data representation,  Wang et al. in [3] also proposed a lightweight privacy-preserving mechanism consisting of arbitrary data nullification and DP noise addition. Compared with [3], I find Algorithm 1 follows a quite similar process when learning the model parameters. Since [3] introduces data nullification and adversary training, their method may be more efficient and better than this paper in terms of communication and utility. Please provide a comparison with [3]. \n\n\n[1] Joseph, Matthew, Jieming Mao, Seth Neel, and Aaron Roth. \"The role of interactivity in local differential privacy.\" In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 94-105. IEEE, 2019.\n[2] Wang, D., Gaboardi, M., Smith, A., & Xu, J. (2020). Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy. Journal of machine learning research, 21(200).\n[3] Wang, Ji, Jianguo Zhang, Weidong Bao, Xiaomin Zhu, Bokai Cao, and Philip S. Yu. \"Not just privacy: Improving performance of private deep learning in mobile cloud.\" In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2407-2416. 2018.", "summary_of_the_paper": "This paper proposes a task-aware local DP method to improve the privacy and\u0002utility trade-off for multi-dimensional user data. Also, a analytical near-optimal solution for a general linear encoder-decoder model and MSE loss is provided. For neural network cases (i.e., nonlinear encoder-decoder), the authors present a heuristic learning algorithm to get the model parameters. The experiments results demonstrate the effectiveness of the proposed methods. ", "summary_of_the_review": "This paper proposed a good analysis for task-aware local DP.  However, my main concern is the setting of local DP.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "G4MKjTlWo2v", "reviewer": "Reviewer_mz4E", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The curse of dimensionality and the problems it creates for utility of DP mechanisms is an important problem that has been studied for a long time. The approach this paper take's creates the following concerns:\n\n1. The main idea of this  paper  which is dimensionality reduction, has already been proposed before, in numerous contexts such as random projections [1] or sparse regression [2]. The idea of mixing this with task-awareness and considering how a model would use features and adding noise only to features that are used has also been studied before [3]. It would be great if the paper quantifies its differences with these prior work/missing citations better.\n\n2. How much overhead does this add to the user's side, in terms of latency and computation complexity? It will help to know how much extra latency gets added compared to doing normal local DP. The user seems to need to be able to carry out the encoder operation. \n\n3. How much of this method's success depend on a correct analysis of what feature is related to the  task? How easy or hard is it to get such details? Some more clarity in explaining this would certainly help readability. It seems like the effectiveness of this method relates to how well related features can be extracted, and what this model is learning and if it really relates to how this data would be used in the future for other training tasks. This could even circle back to interpretability and how different models might use different features. \n\n4. Although the paper claims effectiveness in high-dimensonal cases, the experiments  create the question \"how well would this method scale in the presence of real-world, high dimensional data?\", like medical images which are often large in size. The datasets used here are very small compared to real-life scenarios.  \n\n[1] Kenthapadi K, Korolova A, Mironov I, Mishra N. Privacy via the Johnson-Lindenstrauss Transform. Journal of Privacy and Confidentiality. 2013;5(1):39-71.\n\n[2] Thakurta AG, Smith A. Differentially private feature selection via stability arguments, and the robustness of the lasso. InConference on Learning Theory 2013 Jun 13 (pp. 819-850). PMLR.\n\n[3] Mireshghallah F, Taram M, Jalali A, Elthakeb AT, Tullsen D, Esmaeilzadeh H. A principled approach to learning stochastic representations for privacy in deep neural inference. arXiv preprint arXiv:2003.12154. 2020 Mar.", "summary_of_the_paper": "The paper addresses the problem of large loss in utility due to the addition of noise in a local-DP setup, especially when working with high dimensional data. To mitigate this problem, the paper proposes an encoder-decoder setup in which noise is applied through the encoder, in a lower-dimension to decrease its effect on utility. Then  Laplace random noise is applied to each point's encoding in the latent space. The training  of the autoencoder is done over an offline phase on public data and with respect to the main task that the data is to be used for.  The approach is then evaluated empirically.", "summary_of_the_review": "\nThe main reasons for my recommendation are:\n\n1. similarity to prior work, the novelty of this work and it's benefits are not well identified\n\n2. How useful the extracted dimensions would be in high dimensions and for models that might use different set of features is not clear.\n\n", "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: This work considers the problem of how to predict on sensitive user points while preserving their privacy. It proposes a fairly straightforward way to create a local randomizer that optimizes loss for a given model subject to preserving LDP. The work also gives theoretical analysis of the randomizer for least squares linear regression. 
The problem formulation is different from the standard LDP framework where privacy of training data points needs to be preserved. The submission does not motivate this setting and I don't see a good motivation for this problem either. More importantly, it does not sufficiently emphasize that the problem is entirely different from prior work. Indeed all reviewers were confused about various aspects of comparison with previous work. Therefore, in my opinion, the submission is not sufficiently well motivated and clearly presented to be accepted.
Decision: Reject