Year: 2021

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 multidimensional 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 nearoptimal 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.

heading: 1 INTRODUCTION
text: In recent years, there has been a 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 a state-of-the-art technique for data privacy, and its local variant – local differential privacy (LDP) (Kasiviswanathan et al., 2011) – provides stronger privacy guarantees 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 (Differential Privacy Team), and Microsoft (Ding et al., 2017) for some basic frequency or histogram estimation tasks where raw user data is restricted to an n-bit discrete variable.
In the future, LDP has the promising potential to be adopted in more complex scenarios (Hassan et al., 2019; Dankar & El Emam, 2013; Zhao et al., 2014; Cortés et al., 2016) (e.g., health care, power grids, Internet of Things) that feature richer user data attributes that feed into more sophisticated downstream ML tasks. In such cases, today’s standard task-agnostic LDP approaches may not be ideal. For example, consider complex user data that must be anonymized before passing it into a ML task function, such as a neural network classifier for credit scores. A standard approach would be to 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, as the dimension and variability of user data inevitably grows, today’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 a user population, but minimally relevant for a 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 a fundamentally different task-aware LDP approach. 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
budget, we 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 concrete example). Crucially, user privacy is guaranteed under the same privacy budget according to the post-processing immunity of DP (Dwork et al., 2014) (i.e., one cannot make the output of a 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 a 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 underlying 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 a taskaware privacy preservation problem in which the effect of noise perturbation to preserve LDP is effectively considered, based on an 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 a heuristic learning algorithm for more general settings (Section 4). Third, we validate the effectiveness of our task-aware approach through three real-world experiments, 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 5). All the proofs are given in the Appendix.
Related Work. 1) Utility maximization in DP/LDP. Most theoretical DP/LDP research either provides a utility upper bound for a given privacy budget under some weak assumptions (Alvim et al., 2011; Kenthapadi et al., 2012; Duchi et al., 2013; Makhdoumi & Fawaz, 2013; Hardt & Talwar, 2010; Wang et al., 2019b; Acharya et al., 2020), or designs optimal privacy preservation mechanisms in some specific use cases (McSherry & Talwar, 2007; Wasserman & Zhou, 2010; Friedman & Schuster, 2010; Xiao et al., 2010; Thakurta & Smith, 2013; Kairouz et al., 2014; Geng & Viswanath, 2015; Liu et al., 2016; Yiwen et al., 2018; Joseph et al., 2019; Gondara & Wang, 2020; Wang et al., 2020). To the best of our knowledge, with respect to multi-dimensional user data, Murakami & Kawamoto (2019), Wang et al. (2019a) and Chen et al. (2021) are the only three similar works to ours. Murakami & Kawamoto (2019) develops a utility-maximizing LDP framework under the assumption that some data attributes may not be privacy-sensitive, 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-dimensional data with an objective of minimizing the worst-case noise variance, which naturally improves utility. Chen et al. (2021) preserves DP for images by adding noise to a latent representation learned through back-propagation 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 task-aware approach achieves a 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 requirements. 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 a task-specific output is directly predicted from the raw inputs (Muller et al., 2006; Wang et al., 2012; Donti et al., 2017; Zhou & Tuzel, 2018; Amos et al., 2018). Our work also follows such a practice, but introduces an LDP guarantee while improving the task performance. 3) DP in deep learning. The popularity of deep learning also draws great attention to DP preservation therein (Song et al., 2013; Shokri & Shmatikov, 2015; Abadi et al., 2016; Phan et al., 2016; Papernot et al., 2016; Phan et al., 2017; McMahan et al., 2018; Wang et al., 2018; Phan et al., 2019; Arachchige et al., 2019; Liu et al., 2020; Mireshghallah et al., 2020; Bu et al., 2020). Our work is fundamentally different. Instead of preserving LDP during the learning process, we use learning as a tool to find the salient representation that improves the task performance under a given privacy budget. In other words, we don’t perturb the gradient for backpropagation but perturb the representation to guarantee LDP. Furthermore, we don’t specifically deal with privacy preservation during the offline training process, which requires some ground truth user data (e.g., from a small set of consenting volunteers). However, LDP of user data is guaranteed after a trained model is deployed online.

heading: 2 BACKGROUND AND MOTIVATING EXAMPLE
text: -LDP (Kasiviswanathan et al., 2011). Let x ∈ Rn be an individual data sample, and X be the domain of x, which is assumed to be a compact subset of Rn. A randomized algorithmM : X 7→ Rd is said to satisfy -LDP with privacy-budget > 0, if
Pr[M(x) ∈ S] ≤ e Pr[M(x′) ∈ S], ∀x, x′ ∈ X,S ⊆ imM. (1) Essentially, when is small, one cannot readily differentiate whether the input ofM is an individual user x or x′ based onM’s outcome. Laplace mechanism (Dwork et al., 2014). To release a sensitive function g : X 7→ Rd under -LDP, ∀ > 0, the Laplace mechanism is a widely used mechanism which adds Laplace noise to function g:
MLap(x, g, ) = g(x) + Lapd(µ = 0, b = ∆1g ), (2)
where Lapd(µ, b) is a d-dimensional vector whose elements are i.i.d. Laplace random variables with mean µ and scale b, which leads its variance to be 2b2. For concreteness, the analysis and evaluation of this paper focus on the Laplace mechanism although the central idea of learning taskrelevant data representations is applicable to other random privacy mechanisms as well. ∆1g = maxx,x′∈X ‖g(x)− g(x′)‖1 measures the sensitivity of g under the `1 norm.
A motivating example. Consider an example shown in Fig. 1. 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 -LDP for each person with = 1 and our task is to estimate the mean wage as closely as possible. A straightforward taskagnostic approach will directly expose both the two data attributes, and add Laplace noise with scale b = 20 to each attribute. However, a task-aware approach will expose only the wage attribute and add Laplace noise with scale b = 10. Both the approaches guarantee LDP under the same budget ( = 1), but the wage attribute given by the task-aware approach is less noisy, and we can expect that the corresponding estimated mean wage (i.e. the ultimate task objective) is close to the real value with a higher probability.
In more complex scenarios, such as when each data attribute 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 explored in the following sections.

heading: 3 PROBLEM FORMULATION
text: We now introduce the task-aware privacy preservation problem depicted in Fig. 2. Let y = f(x) ∈ Rm denote the task output associated with each ground truth data sample x, where f represents the task function. To guarantee -LDP for each data sample x, its true value should never be exposed to the task function. Instead, an estimate of x, denoted by x̂, is used as the input to the task function with the corresponding task output ŷ = f(x̂). The objective is to minimize the overall task loss L = E[l(ŷ, y)] due to the difference between x̂ and x, where x follows distribution Dx, and l is a task loss function that captures the discrepancy between task output ŷ and y, such as the common `2 and cross-entropy loss.
More concretely, x is first mapped to a latent representation φ ∈ RZ through an encoder function φ = ge(x; θe), where θe are a set of encoder parameters. φ is then perturbed by a Laplace noise vector w ∈ RZ . That is, ge is treated as the sensitive function g in Eq.2. Next, x̂ is reconstructed
from φ+ w using a decoder function x̂ = gd(φ+ w; θd) where θd are a 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 or one hidden-layer neural network).
The optimal task-aware x̂ minimizes L while preserving -LDP. In other words, the task-aware privacy preservation problem aims to co-design encoder and decoder, i.e., find proper values for Z, θe and θd, such that L is minimized and -LDP is preserved. Formally,
min Z,θe,θd
L = Ex,w[l(ŷ, y)], (3)
s.t. y = f(x), (4) ŷ = f(gd(ge(x; θe) + w; θd)), (5)
x ∼ Dx, w ∼ LapZ(0, ∆1ge ). (6)
The difficulty of our task-aware LDP problem mainly comes from the discrepancy of the measurement of overall task loss L, which depends on Dx 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 -LDP. First, a task-agnostic approach adds noise directly to the normalized x1. For convenience we assume x is already normalized, and we have Z = n and ge(x) = x. Second, a privacy-agnostic approach adds noise to φ obtained by considering the problem defined in Eq.3-6 with a pre-determined Z ≤ n and w being a zero vector instead. That is, the privacy-preservation part is neglected when designing the encoder, and hence a proper Z needs to be pre-determined or one would always conclude a larger Z (under which more information can be delivered when noise is absent) is better. Both two benchmark approaches still need to determine the optimal decoder parameters θd for input φ + w. Note that for the task-agnostic approach even though ge is an identity function, the corresponding optimal gd is usually not an identity function, as exemplified in Section A.7.1.

heading: 4 ANALYSIS
text: In this section, we solve the task-aware privacy preservation problem. Assuming a linear model and mean-squared error (MSE) task loss, we are able to 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 a heuristic learning algorithm which demonstrates strong empirical performance.

heading: 4.1 LINEAR MODEL WITH MSE TASK LOSS
text: In this subsection, we consider a linear model with MSE task loss. More specifically, encoder function ge, decoder function gd, and task function f are assumed to be linear functions in their corresponding inputs, and the loss function is l = ‖(ŷ − y)‖22. The task function f can then be expressed as f(x) = Kx, where K ∈ Rm×n is the task matrix. Practicality of the setting. Linear transformation is a common encoding and decoding approach for many dimensionality-reduction techniques, such as PCA. And `2 task loss is widely used in many application scenarios. For example, given N samples of x, suppose we want to estimate the mean value of these samples in a few directions, given by task matrix K. Then the sum of the variance of these estimates by using x̂ instead of x will be 1NEx,w[‖K(x̂−x)‖ 2 2], so L = Ex,w[‖K(x̂−x)‖22] = Ex,w[‖(ŷ − y)‖22] is a natural objective function. Contents. We first summarize key results. For our task-aware approach, the optimal decoder is first determined in Proposition 1, and then the optimal encoder and the corresponding optimal loss is
1We may either normalize each dimension independently when x is a multi-variate random variable, or normalize all the dimensions jointly when x is a uni-variate time-series.
formulated in Proposition 2-4 under Assumption 1. We then relax Assumption 1 and provide lower and upper bounds for the optimal loss in Theorem 1 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, we assume the covariance matrix of x− µx, i.e., E[(x− µx)(x− µx)>], is positive definite, where µx ∈ Rn 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 − µx)(x − µx)>] into LL> through Cholesky decomposition, where L ∈ Rn×n is a lower triangular matrix with positive diagonal entries. For analytical convenience, we let h = L−1(x − µx), which can be viewed as another representation of x, with mean µh = 0 and covariance matrix Σhh = I . Let Dh denote the distribution of h, and H = {L−1(x− µx)|x ∈ X} denote the compact set that contains all the possible values of h ∼ Dh. SinceK(x̂−x) = P (ĥ−h), where P = KL, working with data representation h with task matrix P is equivalent to using x and K. Considering zero-centered h instead of original x saves us from considering the constant terms in the linear encoder and decoder functions.
Let E ∈ RZ×n and D ∈ Rn×Z denote the encoder and decoder matrix associated with h, i.e., φ = Eh and ĥ = D(Eh+ w). Without loss of generality, we let Z ≥ n and allow some rows of E to be zero. Equivalently, based on the relationship between x and h, we have φ = EL−1(x − µx) and x̂− µx = LD(EL−1(x− µx) +w). We denote the covariance matrix of w by Σww, and it can be expressed as Σww = σ2wI , where σ 2 w is the variance of the noise added to each dimension of φ.
We first determine the optimal decoder D that minimizes L for a given encoder E, which is given by the following proposition. Proposition 1 (Optimal decoder D that minimizes L). An optimal decoder D that minimizes L for a given encoder E and σ2w can be expressed as D = E >(EE> + σ2wI) −1, and corresponding L is
L = Tr(P>P )− Tr(P>PE>(EE> + σ2wI)−1E), (7) where Tr(·) denotes the trace of a matrix.
The next main step is to find an encoder E that minimizes Eq.7. Since ∆1ge = maxv,v′∈E(H) ‖v − v′‖1, where E(H) = {Eh|h ∈ H} is the image of H under linear transformation E, the design of encoder E will affect ∆1ge and therefore σ2w, and for different H’s the effect of E is also different in general. So we need to carefully consider the relationship between E and H .
When computing ∆1ge we can actually use H’s convex hull S instead of H itself, according to the following lemma. This brings some analytical convenience in the further analysis. Lemma 1 (Convex hull preserves ∆1ge).
∆1ge = max v,v′∈E(S)
‖v − v′‖1. (8)
For encoderE, consider its singular value decomposition (SVD) instead: UΣV >, whereU ∈ RZ×Z and V ∈ Rn×n are orthogonal matrices and Σ ∈ RZ×n is a rectangular diagonal matrix. And the singular values are denoted by σ1, · · · , σn with |σ1| ≥ · · · ≥ |σn|. Then designing E is equivalent to designing matrix U , V and Σ. The geometric interpretation of applying transformE = UΣV > to set S consists of three sub-transforms: 1) rotate S by applying rotation matrix V >; 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 ∆1ge and hence σ2w.
Our overall strategy is to first minimize the loss L and the sensitivity value ∆1ge over U and V . The resulting U and V only depend on Σ under Assumption 1 (Propositions 2, 3). We then find the optimal Σ that minimizes the L within a given privacy budget (Proposition 4). By the end, we relax Assumption 1 to discuss the quality of our solution (Theorem 1).
We start by noting that for two points within a compact set, they must lay on the boundary to have the maximum `1 distance. We then make the following assumption in terms of ∂S, which is the boundary of S. It decouples the relationship between the choice of V and the value of ∆1ge. Assumption 1 (Boundary ∂S is a centered hypersphere). The boundary ∂S is a centered hypersphere of radius r ≥ 0, which is expressed as {h ∈ Rn|‖h‖22 = r2}.
This is a strong assumption, but at the end of this subsection we will give a lower and upper bound of L for any possible ∂S based on the results under this assumption. Since ∂V (S) = {h ∈ Rn|‖h‖22 = r2} = ∂S for any orthogonal V , this assumption gives us a nice property: the choice of V doesn’t affect ∆1ge and σ2w. Based on the above assumption, we can safely consider the optimal design of V that minimizes L when Σ and σ2w are given, which leads to the following proposition. Proposition 2 (Optimal rotation matrix V that minimizes L under Assumption 1). Suppose the eigen-decomposition of the Gram matrix P>P is expressed as P>PQ = QΛ, where Λ = diag(λ1, · · · , λn) ∈ Rn×n is a diagonal matrix whose diagonal elements are eigenvalues with λ1 ≥ · · · ≥ λn ≥ 0, and Q ∈ Rn×n is an orthogonal matrix whose columns are corresponding normalized eigenvectors. Then, when Σ and σ2w are given, L is minimized for V = Q, any Z ≥ n, and any orthogonal U . And the corresponding L can be expressed as:
L = n∑ i=1 λi − n∑ i=1 λi σ2i σ2i + σ 2 w . (9)
It is clear that choosing a Z > n brings no additional benefit. Hence we can only consider Z = n for simplicity.
After the first two sub-transforms Σ and V >, the boundary ∂S = {h ∈ Rn|‖h‖22 = r2} becomes ∂ΣV >(S) = {v ∈ Rn| ∑n i=1 v 2 i /σ 2 i = r
2}, which is a hyperellipsoid. We then have the following proposition that gives the optimal U which minimizes ∆1ge. Proposition 3 (Optimal rotation matrix U that minimizes ∆1ge under Assumption 1). For a given Σ, U = I minimizes ∆1ge, and the corresponding minimum value is
∆1ge = 2r √√√√ n∑ i=1 σ2i . (10)
Next, we need to consider how to design the scaling matrix Σ, or equivalently, the values of σ21 , · · · , σ2n, to minimize Eq.9, which is the only remaining piece. Clearly, for any given σ21 , · · · , σ2n if we increase them proportionally, σ2w also needs to be increased proportionally to preserve the same -LDP. So without loss of generality, we impose an additional constraint ∑n i=1 σ 2 i = M , where M is a positive constant. And the following proposition gives the optimal choice of Σ that minimizes L and preserves -LDP with the Laplace mechanism. Proposition 4 (Optimal scaling matrix Σ that minimizes L and preserves -LDP with Laplace mechanism under Assumption 1). The optimal choice of σ21 , · · · , σ2n that minimize L and preserve -LDP with Laplace mechanism under constraint ∑n i=1 σ 2 i = M is given by
σ2i = M · ( √ λi∑Z′ i=1 √ λi (1 + Z ′ · 8r 2 2 )− 8r 2 2 ), ∀i ∈ {1, 2, · · · , Z ′}
0, ∀i ∈ {Z ′ + 1, Z ′ + 2, · · · , n} (11)
where Z ′ ≤ n is the largest integer such that: √ λZ′∑Z′
i=1
√ λi
(1 + Z ′ · 8r 2 2 )− 8r 2 2 > 0, (12)
and the corresponding L is
L = 8r 2/ 2
1 + Z ′ · 8r2/ 2 ( Z′∑ i=1 √ λi) 2 + n∑ i=Z′+1 λi. (13)
For our task-aware approach, Proposition 1-4 complete the optimal encoder and decoder design that preserves -LDP with the Laplace mechanism under Assumption 1.
Validation of Task Loss from Theoretical Results (Fig. 3). We now compare the performance of our task-aware approach and the benchmark approaches when L = I and Assumption 1 holds. The derivations of the benchmark approaches are in Section A.7. We consider three different settings
which have n = 4 and λ1 = 4 in common. And in setting 1, 2, and 3 we let λ2 = λ3 = λ4 be 0, 1, 2 respectively. For the privacy-agnostic approach2, we use a pre-determined Z = 2. Our observations are: 1) Compared to the task-agnostic approach, our task-aware approach achieves the largest improvement in setting 1, because λ2:4 = 0 implies that x2:4 are purely redundant. We can even expect higher gain than setting 1 when we have larger n and zero λ2:n’s, and the gain will be zero if all the λi’s are equal. 2) The privacy-agnostic approach completely missed the information carried by x3:4, which explains the improvement of our task-aware approach for small r/ in setting 2 and 3. We can expect higher gain than setting 3 when we have larger n and larger λ2:n’s, and the gain will be zero if all the missed xi’s correspond to zero λi’s and all the other λi’s are equal.
Transition to general boundary ∂S. Based on the results under Assumption 1, we can give a lower and upper bound of L∗ for general ∂S, which is not necessarily a centered hypersphere. Theorem 1 (Lower and upper bound of L∗ for general boundary ∂S when -LDP is preserved with Laplace mechanism). Suppose ∂S ⊂ {h ∈ Rn : r2min ≤ ‖h‖22 ≤ r2max}. Then when - LDP is preserved with the Laplace mechanism, the optimal L∗ is bounded by: L(rmin;λ1:n, ) ≤ L∗ ≤ L(rmax;λ1:n, ) (14)
where L(r;λ1:n, ) is the value of L determined by Eq.12 and 13 for given radius r, eigenvalues λ1:n and privacy budget .
Therefore, to preserve -LDP with the Laplace mechanism, our task-aware solution for general ∂S is: 1) First, find the smallest rmax and the largest rmin that bound ∂S; 2) Then assume ∂S is {h ∈ Rn|‖h‖22 = r2max}, and choose the encoder E and decoder D based on Proposition 2-4. We don’t use the corresponding σ2w however, because it may guarantee a higher LDP than needed. 3) Next, compute σ2w for real ∂S under decoderD and privacy budget .
The associated loss for the task-aware approach is at most L(rmax;λ1:n, ). Though in general not optimal, it differs from L∗ by at most L(rmax;λ1:n, ) − L(rmin;λ1:n, ). The difference is small when ∂S is “nearly” a hypersphere, i.e., rmax − rmin ≈ 0.

heading: 4.2 GENERAL SETTINGS
text: For more complex scenarios, it is challenging to give an analytical solution to the task-aware privacy preservation problem, especially when the encoder function ge, decoder function gd, 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 1 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, Z should be proper, i.e., it is neither too small (we can find a better solution by choosing a larger Z) nor too big (which introduces unnecessary complexity). In practice a practitioner may need to determine a proper Z on a 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 θe, θd by their corresponding negative gradients in line 3, and then recompute ∆1ge and re-sample w from LapZ(0,∆1ge/ ) in line 4. Note that, in terms of encoder parameter θe, instead of considering the gradient of L, we add an `2 regularization term η‖θe‖2 where η is a positive constant. Therefore, we update θe with the negative gradient −(∇θeL + 2ηθe). Without regularization, the ‖θe‖2 will grow to infinity since we can always achieve a smaller L by increasing the scale of φ proportionally. But it is not a direction we are looking for, since σ2w will also increase proportionally to guarantee -LDP.
2 One can use another value of Z, under which the result may be slightly different but our task-aware approach will still outperform.
Algorithm 1 Task-aware Algorithm for -LDP Preservation in General Settings Require: Privacy budget and Z
1: Initialize encoder/decoder parameters θe, θd and noise vector w 2: for τ ∈ {0, 1, · · · , Nepochs − 1} do 3: Update θe and θd with −(∇θeL+ 2ηθe) and −∇θdL, respectively, by one or multiple steps 4: Recompute ∆1ge, and re-sample w from LapZ(0,∆1ge/ ) 5: end for 6: Return θe, θd and ∆1ge

heading: 5 EVALUATION
text: 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 Learning 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 of individual household electric power consumption over four years (Hebrail & Berard, 2012). Each data sample x ∈ R24 is a time-series that contains the hourly household power consumption for one single day, and our objective is to estimate the mean of the hourly household power consumption for N days. As discussed in Section 4.1, we can define the overall task loss in the following way:
L = Ex∼Dx [‖K(x̂− x)‖22] = 24∑ i=1 k2iEx∼Dx [‖x̂i − xi‖22] (15)
where K = diag(k1, k2, · · · , k24) factors the importance of the mean estimation for each hour. In our experiment we set ki = 2 for i ∈ {9, 10, · · · , 20} (i.e., day-time hours) and ki = 1 for other i’s (i.e., night-time hours). And we adopt a linear encoder and decoder model. As the considered problem is based on a linear model with MSE task loss, we adopt the solutions developed in Section 4.1 for the three approaches (we choose Z = 3 for the privacy-agnostic approach2).
Fig. 4 shows our experimental results. First, on the left, we compare the task loss l(ŷ, y) for the three approaches under different LDP budgets. For each approach, the overall task loss L decreases when a larger LDP budget is given. Besides, for a 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-agnostic approach are 22.9% ( = 10) and 11.7% ( = 5), respectively. Second, on the right, we select = 5 and compare the MSE of power consumption for each hour. We see that our task-aware approach achieves a 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 a higher ki for the day-time hours, so our task-aware approach gives higher priority to
minimizing the loss for those dimensions in x; 2) Although x has 24 dimensions, the variance in each dimension can be mostly explained by several common latent dimensions, so our task-aware approach still achieves a similar MSE for the night-time hours; 3) Our task-aware approach is able to adopt different scales to different latent dimensions according to their task relevance while the privacy-agnostic approach cannot.
Next, we consider a real estate valuation problem and a breast cancer detection problem. Both the problems are not based on the linear model with MSE task loss, so we use Algorithm 1 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 A.9 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 ∈ R6 contains 6 attributes that are highly related to the value of a house, including transaction date, house age, geographic coordinates, etc. And y ∈ R represents the valuation of a house. We first train a one-hidden-layer feedforward neural network regression model using the ground truth x and y, to serve as our task function f . Then, we minimize the `2 loss of ŷ and y, based on a linear encoder and decoder model.
Breast Cancer Detection. For this problem, we use a well-known breast cancer diagnostic dataset (Street et al., 1993) from Wisconsin, which contains 500+ instances. Here, x ∈ R30 contains 30 attributes that measure 10 features of a cell nucleus. And y is a binary variable that represents a diagnosis result (malignant or benign). We first train a one-hidden-layer feedforward neural network classification model using the ground truth x and y, to serve as our task function f . Then we aim to minimize the cross-entropy loss of ŷ and y, with encoder and decoder both being one-hidden-layer feedforward neural networks.
Fig. 5 shows the evaluation results. For both problems, we can see our task-aware approach nearly always outperforms the benchmark approaches on overall task loss L under different LDP budgets, which demonstrates the effectiveness of our proposed solution. The maximum improvements against the task-agnostic and privacy-agnostic approach are 21.9% ( = 5) and 13.5% ( = 5) for real estate valuation, and are 73.0% ( = 20) and 45.6% ( = 20) for breast cancer detection.

heading: 6 CONCLUSION AND FUTURE WORK
text: This paper provides a principled task-aware privacy preservation method to improve the privacyutility trade-off for ML tasks that increasingly operate on rich, multi-dimensional user data. We gave an analytical near-optimal solution for a general linear encoder-decoder model and MSE task loss, and developed a heuristic learning algorithm for more general nonlinear settings. Our evaluation showed that our task-aware approach outperforms the benchmark approaches on overall task loss under various LDP budgets. Our future work will focus on the analysis of the task-aware privacy preservation problem for approximate LDP and other LDP mechanisms as well as multi-task learning.

heading: A APPENDIX

heading: A.1 PROOF OF PROPOSITION 1
text: Proof. We have
L = E[‖K(x̂− x)‖22] = E[‖P (ĥ− h)‖22] = E[‖P ((DE − I)h+Dw)‖22] (16) = E[Tr(P (DE − I)hh>(DE − I)>P>) + Tr(PDww>D>P>)] (17) = Tr(P (DE − I)(DE − I)>P>) + Tr(PDΣwwD>P>). (18)
And we can verify that D = E>(EE> + σ2wI) −1 is a zero point of
∇L ∇D = 2P>P ((DE − I)E> +D · σ2wI). (19)
Then we plug the expression of D into Eq.18 and get Eq.7.

heading: A.2 PROOF OF LEMMA 1
text: In this subsection we give the proof of Lemma 1. Here we treat E as a mapping instead of a matrix, and its inverse mapping, which is also linear, is denoted by E−1.
We first prove the following lemma.
Lemma 2 (Convex hull after linear transformation). E(S) is the convex hull of E(H).
Proof. Since H ⊆ S, we have E(H) ⊆ E(S). And for any v, v′ ∈ E(S) and δ ∈ [0, 1], we have δh + (1 − δ)h′ ∈ S, where h ∈ E−1(v) ∩ S and h′ ∈ E−1(v′) ∩ S. Thus δv + (1 − δ)v′ = E(δh+ (1− δ)h′) ∈ E(S). Therefore, E(S) is a convex set containing E(H). If E(S) is not the convex hull, then we can find a convex set B such that E(H) ⊆ B ⊂ E(S). Then we have H ⊆ E−1(B)∩S ⊂ S (If E−1(B)∩S = S, we will have B = E(E−1(B)∩S) = E(S), which is not true). Besides, for any h, h′ ∈ E−1(B)∩S and δ ∈ [0, 1], we have δv+(1−δ)v′ ∈ B, where v = E(h) and v′ = E(h′). Thus δh+ (1− δ)h′ ∈ E−1(δv+ (1− δ)v′)∩S ∈ E−1(B)∩S. Therefore, E−1(B) ∩ S is a convex set containing H . This is contradictory to the fact that S is the convex hull of H . So E(S) must be the convex hull of E(H).
Now we can proceed to the proof of Lemma 1.
Proof. Notice that ∆1ge = maxv,v′∈E(H) ‖v − v′‖1, so our target is to prove
max v,v′∈E(S) ‖v − v′‖1 = max v,v′∈E(H) ‖v − v′‖1. (20)
First, since E(H) ⊆ E(S), we have maxv,v′∈E(S) ‖v − v′‖1 ≥ maxv,v′∈E(H) ‖v − v′‖1.
Next, suppose v1, v2 are the two points inE(S) such that the `1 distance between them is the largest. Since E(S) is the convex hull of E(H), we can express vi as (∀i ∈ {1, 2}):
vi = p(i)∑ j=1 ti,j ṽi,j , (21)
s.t. ṽi,j ∈ E(H), ∀j ∈ {1, 2, · · · , p(i)}, (22) p(i)∑ j=1 ti,j = 1, and ti,j ≥ 0, ∀j ∈ {1, 2, · · · , p(i)}, (23)
where p(i) is an positive integer, ∀i ∈ {1, 2}. For convenience, we let A = maxv,v′∈{ṽi,j |∀i,j} ‖v − v′‖1. Clearly, A ≤ maxv,v′∈E(H) ‖v − v′‖1.
Notice that v1 − v2 can be expressed as the linear combination of ṽ1,j − ṽ2,q , ∀j ∈ {1, 2, · · · , p(1)}, q ∈ {1, 2, · · · , p(2)}. That is, ∃γj,q ≥ 0 such that:
v1 − v2 = p(1)∑ j=1 p(2)∑ q=1 γj,q(ṽ1,j − ṽ2,q), s.t. p(1)∑ j=1 p(2)∑ q=1 γj,q = 1. (24)
Then we have
‖v1 − v2‖1 =‖ p(1)∑ j=1 p(2)∑ q=1 γj,q(ṽ1,j − ṽ2,q)‖1 (25)
≤ p(1)∑ j=1 p(2)∑ q=1 ‖γj,q(ṽ1,j − ṽ2,q)‖1 = p(1)∑ j=1 p(2)∑ q=1 γj,q‖(ṽ1,j − ṽ2,q)‖1 (26) ≤ p(1)∑ j=1 p(2)∑ q=1 γj,qA = A ≤ max v,v′∈E(H) ‖v − v′‖1. (27)
So we also have maxv,v′∈E(S) ‖v − v′‖1 ≤ maxv,v′∈E(H) ‖v − v′‖1.
Thus ∆1ge = maxv,v′∈E(H) ‖v − v′‖1 = maxv,v′∈E(S) ‖v − v′‖1.

heading: A.3 PROOF OF PROPOSITION 2
text: Proof. We have Tr(P>P ) = ∑n i=1 λi, which is a fixed number. Therefore we focus on maximizing the second trace term in Eq.7. For any Z ≥ n we have
EE> + σ2wI = UΣΣ >U> + σ2wI = Udiag(σ 2 1 + σ 2 w, · · · , σ2n + σ2w, σ2w, · · · , σ2w︸ ︷︷ ︸
Z−n in total
)U>. (28)
Thus we have for any orthogonal U :
E>(EE> + σ2wI) −1E (29)
=V Σ>U> · Udiag( 1 σ21 + σ 2 w , · · · , 1 σ2n + σ 2 w , 1 σ2w , · · · , 1 σ2w )U> · UΣV > (30) =V Σ>diag( 1
σ21 + σ 2 w , · · · , 1 σ2n + σ 2 w , 1 σ2w , · · · , 1 σ2w )ΣV > (31)
=V diag( σ21
σ21 + σ 2 w
, · · · , σ 2 n
σ2n + σ 2 w
)V >. (32)
So E>(EE> + σ2wI) −1E is a positive semi-definite matrix with eigen-values σ
2 1
σ21+σ 2 w ≥ · · · ≥
σ2n σ2n+σ 2 w ≥ 0. Then by Ruhe’s trace inequality (Ruhe, 1970) (a corollary of Von Neumanns trace inequality (Von Neumann, 1937)):
Tr(P>PE>(EE> + σ2wI) −1E) ≤ n∑ i=1 λi σ2i σ2i + σ 2 w
(33)
and when V = Q the equality holds. So we have Eq.9 for V = Q, any Z ≥ n and any orthogonal U .

heading: A.4 PROOF OF PROPOSITION 3
text: In this subsection we give the proof of Proposition 3. For convenience we let ai = r|σi|,∀i ∈ {1, 2, · · · , n}, and then the hyperellipsoid {v ∈ Rn| ∑n i=1 v 2 i /σ 2 i = r
2} can be written as {v ∈ Rn| ∑n i=1 v 2 i /a 2 i = 1}, which is the standard expression. And we also have a1 ≥ a2 ≥ · · · ≥ an.
Before proving Proposition 3, we first give two lemmas related to the properties of a hyperellipsoid.
Lemma 3 (Tangent hyperplane of hyperellipsoid). Any tangent hyperplane of hyperellipsoid {v ∈ Rn| ∑n i=1 v 2 i /a 2 i = 1} can be expressed as:
n∑ j=1 ujvj = √√√√ n∑ j=1 a2ju 2 j , (34)
where u1, u2, · · · , un are the coefficients.
Proof. It can be easily verified that point ṽ ∈ Rn such that
ṽj = a2juj√∑n q=1 a 2 qu 2 q , j ∈ {1, 2, · · · , n}, (35)
is located on the hyperellipsoid. And by adjusting the values of u1, u2, · · · , un we can express any point on the hyperellipsoid with Eq.35. Moreover, the tangent hyperplane for point of tangency ṽ can be expressed as
n∑ j=1 ṽjvj a2j = 1. (36)
Plugging Eq.35 into Eq.36 we get Eq.34.
Lemma 4 (Locus of the vertices of circumscribed orthotope). The vertices of any orthotope that circumscribes hyperellipsoid {v ∈ Rn| ∑n i=1 v 2 i /a 2 i = 1} is on hypersphere {v ∈ Rn| ∑n i=1 v 2 i =∑n
i=1 a 2 i }.
Proof. When n = 2, the hypersphere reduces to a circle that is well-known as the orthoptic circle of an ellipse (Casey, 1893). We hereby generalize this result to any n.
A vertex of a circumscribed orthotope can be viewed as the intersection of n tangent hyperplanes. According to Lemma 3, we can express them as:
n∑ j=1 ui,jvj = √√√√ n∑ j=1 a2ju 2 i,j , ∀i ∈ {1, 2, · · · , n}, (37)
where i is the index of the i-th hyperplane. Here we let ∑n j=1 u 2 i,j = 1,∀j ∈ {1, 2, · · · , n}. Besides,
these hyperplanes are perpendicular to each other, so the coefficients also satisfy ∑n i=1 ui,jui,k = 0, ∀k 6= j. So if we let Ω ∈ Rn×n be a matrix with ui,j on the i-th row and j-th column, ∀i, j, then Ω is an orthogonal matrix, and we further have ∑n i=1 u 2 i,j = 1,∀i ∈ {1, 2, · · · , n}.
Thus the considered vertex satisfies Eq.37, ∀i ∈ {1, 2, · · · , n}, which implies it also satisfies: n∑ i=1 ( n∑ j=1 ui,jvj) 2 = n∑ i=1 n∑ j=1 a2ju 2 i,j . (38)
For the left hand side, we have n∑ i=1 ( n∑ j=1 ui,jvj) 2 = n∑ i=1 n∑ j=1 u2i,jv 2 j + 2 n∑ i=1 ∑ j 6=p ui,jui,kvjvp (39)
= n∑ j=1 ( n∑ i=1 u2i,j)v 2 j + 2 ∑ j 6=p ( n∑ i=1 ui,jui,k)vjvp = n∑ j=1 v2j . (40)
And for the right hand side, n∑ i=1 n∑ j=1 a2ju 2 i,j = n∑ j=1 ( n∑ i=1 u2i,j)a 2 j = n∑ j=1 a2j . (41)
Thus the vertex is on hypersphere {v ∈ Rn| ∑n i=1 v 2 i = ∑n i=1 a 2 i }.
Since the equation of a centered hypersphere after rotation remains unchanged, we have the following corollary. Corollary 1 (Locus of the vertices of circumscribed orthotope after rotation). The vertices of any orthotope that circumscribes hyperellipsoid {v ∈ Rn| ∑n i=1 v 2 i /a 2 i = 1} after rotation is on hyper-
sphere {v ∈ Rn| ∑n i=1 v 2 i = ∑n i=1 a 2 i }.
Now we can proceed to the proof of Proposition 3.
Proof. We first consider the case when n is a power of 2. For the rotated hyperellipsoid, we consider whether there’s any point ṽ ∈ Rn s.t. ‖ṽ‖1 ≥√∑n j=1 a 2 j . Suppose we couldn’t find such a point. Then consider any tangent hyperplane whose normal vector has the following form: (u1, u2, · · · , un), s.t. ui = ±1,∀i ∈ {1, 2, · · · , n}. It can be expressed as:
n∑ j=1 ujvj = W (u1, u2, · · · , un), (42)
where W : (u1, u2, · · · , un) 7→ R maps (u1, u2, · · · , un) to a corresponding constant. And we have W (u1, u2, · · · , un) < √∑n j=1 a 2 j .
Since n is a power of 2, we can find a Hadamard matrix Ω in Rn×n whose elements are either 1 or -1, such that ΩΩ> = nI . We let ui,j be the element of R on the i-th row and j-th column, ∀i, j, and consider the intersection of the following n tangent hyperplanes:
n∑ j=1 ui,jvj = W (ui,1, ui,2, · · · , ui,n), ∀i ∈ {1, 2, · · · , n}, (43)
whose intersection point must satisfy: n∑ i=1 ( n∑ j=1 ui,jvj) 2 = n∑ i=1 n∑ j=1 (W (ui,1, ui,2, · · · , ui,n))2. (44)
Similar to the proof of Lemma 4, we can easily prove the left hand side equals n ∑n j=1 v 2 j , and the
right hand side is strictly less than n ∑n j=1 a 2 j . Thus the intersection point doesn’t locate on the
hypersphere {v ∈ Rn| ∑n i=1 v 2 i = ∑n i=1 a 2 i }. But since the considered n hyperplanes are also the surfaces of a circumscribed orthotope, the intersection point is hence a vertex and must be on the hypersphere {v ∈ Rn| ∑n i=1 v 2 i = ∑n i=1 a 2 i }, according to Corollary 1. This contradiction means
that, the assumption that we cannot find a point ṽ ∈ Rn s.t. ‖ṽ‖1 ≥ √∑n j=1 a 2 j is false.
Thus the point ṽ ∈ Rn s.t. ‖ṽ‖1 ≥ √∑n j=1 a 2 j exists, and the `1 distance between ṽ and −ṽ (which
both lie on the hyperepllisoid) is 2 √∑n
j=1 a 2 j . Thus we have ∆1ge ≥ 2 √∑n j=1 a 2 j .
For U = I , which means we don’t actually rotate the ellipsoid {v ∈ Rn| ∑n i=1 v 2 i /a 2 i = 1}, we have for any point on the ellipsoid
( n∑ i=1 |vi|)2 = ( n∑ i=1 ai · |vi| ai )2 ≤ ( n∑ i=1 a2i )( ∑ i=1 v2i a2i ) = n∑ i=1 a2i , (45)
according to the Cauchy-Schwartz inequality. This implies any point v on the hyperellipsoid has ‖v‖1 ≤ √∑n j=1 a 2 j . So ∆1ge ≤ 2 √∑n j=1 a 2 j . Combined with the result in the above paragraph we
know ∆1ge = 2 √∑n j=1 a 2 j 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 a degenerated hyperellipsoid in space Rñ, where ñ is the smallest power of 2 such that ñ > n. This implies the proposition still holds.
Therefore, the proposition is true for any n.

heading: A.5 PROOF OF PROPOSITION 4
text: Proof. First, to preserve -LDP with Laplace mechanism, the minimum σ2w required is:
σ2w = 2 · (∆1ge)
2
2 = 2 ·
4r2 · ∑n i=1 σ 2 i
2 =
8r2M
2 , (46)
based on Proposition 3 and constraint ∑n i=1 σ 2 i = M .
Next we need to determine σ21 , · · · , σ2n. The considered problem is an optimization problem which aims at minimizing L in Eq.9 under constraint ∑n i=1 σ 2 i = M and σ 2 i ≥ 0 (here we view σ2i instead of σi as the decision variable). Note that though in Eq.9 we also have σ21 ≥ σ2n, we 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 KarushKuhnTucker (KKT) approach, with the following Lagrangian function:
F (σ21 , · · · , σ2n, α1, · · · , αn, β) = n∑ i=1 λi − n∑ i=1 λi σ2i σ2i + σ 2 w + n∑ i=1 αi(−σ2i ) + β( n∑ i=1 σ2i −M),
(47)
where α1, · · · , αn and β are Lagrangian multipliers. We know that the solution will automatically guarantee σ21 ≥ · · · ≥ σ2n, so we can safely assume there exists Z ′ ≤ n such that αi = 0 for i ≤ Z ′, and αi > 0 for i > Z ′. Then for i > Z ′ we have σ2i = 0, and for i ≤ Z ′ we have
∇F ∇σ2i = − σ 2 w (σ2i + σ 2 w) 2 λi = β. (48)
Combining with ∑Z′ i=1 σ 2 i = M and Eq.46 we eventually get Eq.11. Enforcing σ 2 Z′ > 0 we get Eq.12. And plugging Eq.11 into Eq.9 we get Eq.13.

heading: A.6 PROOF OF THEOREM 1
text: In this subsection we give the proof of Theorem 1.
We start with two definitions: L∗(∂S;P, ) denotes the optimal loss for any boundary ∂S, task matrix P that preserves -LDP with Laplace mechanism; R(r) = {h ∈ Rn|‖h‖22 = r2} is the centered hypersphere with radius r.
Next we give the following lemma.
Lemma 5 (Invariance of the optimal loss after scaling).
L∗(∂S;P, ) = L∗(∂ρ(S);P, ρ ), (49)
where ρ > 0 is a scalar and ρ(S) = {ρh|h ∈ S}.
Proof. We only need to consider fixed task matrix P . For any encoder E, decoder D and noise variance σ2w, if they preserve -LDP with Laplace mechanism for boundary ∂S, then we have
σw ≥ √ 2 · ∆1ge = √
2 · ∆1ρge ρ , (50)
where
∆1ρge = ρ max h,h′∈S ‖Eh− Eh′‖1 = max v,v′∈ρ(S) ‖Ev − Ev′‖1. (51)
Thus we know encoder E, decoder D and noise variance σ2w also preserve ρ -LDP with Laplace mechanism for boundary ∂ρ(S). And the reverse also holds true.
So we must have L∗(∂S;P, ) = L∗(∂ρ(S);P, ρ ).
Now we can proceed to the proof of Theorem 1.
Proof. We first construct a distributionDh′ , s.t. points drawn from Dh′ are uniformly distributed on R(2n−1). Then h′ ∼ Dh′ satisfies Σh′h′ = I . And we also have ∂S′ = R(2n−1), where S′ is the convex hull of H ′ (H ′ is the domain of h′ ∼ Dh′ ). According to Proposition 4, for h′ ∼ Dh′ we have L∗(R(2n−1);P, ρ ) = L(2n−1;λ1:n, ρ ), ∀ρ, > 0. We next consider scalar ρ = 2n−1/rmin and the optimal loss L∗(∂ρ(S);P, ρ ). For any encoder E, decoder D and noise variance σ2w, if they preserve ρ -LDP to boundary ∂ρ(S), then they preserve at least ρ -LDP to boundary R(2n−1), since R(2n−1) ⊂ ρ(S). Thus we have L∗(∂ρ(S);P, ρ ) ≥ L∗(R(2n−1);P, ρ ). This further implies:
L∗(∂S;P, ) = L∗(∂ρ(S);P, ρ ) (52) ≥L∗(R(2n−1);P, ρ ) = L(2n−1;λ1:n, ρ ) = L(rmin;λ1:n, ). (53)
So the lower bound of Theorem 1 is proved. The upper bound can be proved in the same way.

heading: A.7 BENCHMARKS

heading: A.7.1 TASK LOSS FOR TASK-AGNOSTIC APPROACH
text: One can obtain the resultant optimal L for the task-agnostic approach by letting E = L and using Eq.7 as stated in Proposition 1. It is worth noting that the associated decoder D = L>(LL> + σ2wI) −1 is not an identity matrix in general.
Corollary 2 (Optimal L for the task-agnostic approach that preserves -LDP). For the task-agnostic approach, the optimal L that preserves -LDP is
L = Tr(P>P )− Tr(P>PL>(LL> + σ2wI)−1L), (54)
where σ2w = 2(∆1ge) 2/ 2 with ge(x) = x.

heading: A.7.2 TASK LOSS FOR PRIVACY-AGNOSTIC APPROACH
text: Through similar analysis as Proposition 2, one can obtain the resultant optimal L for the privacyagnostic approach, which has a pre-determined Z ≤ n. Corollary 3 (Optimal L for the privacy-agnostic approach that preserves -LDP). For the privacyagnostic approach with a pre-determined Z ≤ n, the optimal L that preserves -LDP is
L = Z∑ i=1 λi σ2w σ2i + σ 2 w + n∑ i=Z+1 λi. (55)
where σ2w = 2(∆1ge) 2/ 2.
Proof. For privacy-agnostic approach, we have Z ≤ n. Since for encoder we need to select the top-Z principal components, we have V = Q. Similar to the proof of Proposition 2, for a given Z ≤ n, we have
EE> + σ2wI = UΣΣ >U> + σ2wI = Udiag(σ 2 1 + σ 2 w, · · · , σ2Z + σ2w)U>, (56)
and through similar derivations we eventually get
Tr(P>PE>(EE> + σ2wI) −1E) = Z∑ i=1 λi σ2i σ2i + σ 2 w . (57)
Combined with Eq. 7 we get Eq. 55.

heading: A.7.3 TASK LOSS FOR BENCHMARK APPROACHES WHEN L = I AND ASSUMPTION 1 HOLDS
text: When L = I and Assumption 1 holds, for the task-agnostic approach, according to Eq. 54, we have
L = σ 2 w 1 + σ2w · Tr(P>P ) = n · 8r 2/ 2 1 + n · 8r2/ 2 n∑ i=1 λi. (58)
For the privacy-agnostic approach, according to Eq. 55 and Eq. 10, and assuming we have equal σi’s and minimum δ1ge, we get
L = Z · 8r 2/ 2 1 + Z · 8r2/ 2 Z∑ i=1 λi + n∑ i=Z+1 λi, (59)
where the value of Z is pre-determined.

heading: A.7.4 BENCHMARK ALGORITHMS UNDER GENERAL SETTINGS
text: For the privacy-agnostic approach, we first train the encoder and decoder without considering privacy preservation by updating θe and θd with −∇θeL and −∇θdL, respectively. Next, we fix encoder parameters θe and train the decoder with input φ+w (a modification of Algorithm 1 line 3-4). The task-agnostic approach trains the decoder in the same way, but fixes ge to an identity mapping function.

heading: A.8 CONFIGURATION AND TRAINING DETAILS OF THE EVALUATION
text: Our evaluation runs on a personal laptop with 2.7 GHz Intel Core I5 processor and 8-GB 1867 MHz DDR3 memory. Our code is based on Pytorch. We use the Adam optimizer and learning rate 10−3 for all the applications. The number of samples, train/test split, training epochs, and resulting runtime are summarized in Table 1. (Note that the evaluation for hourly household power consumption is based on the theoretical solutions, so “training epochs”, which is associated with the gradient-based method, doesn’t apply.) We also provide all our documented code as supplementary material and will make it publicly-available after the review process. All three datasets cited in the evaluation are publicly-available from the standard UCI Machine Learning Repository (Dua & Graff, 2017) and anonymized using standard practices. The individual dataset licenses were not available.
For task function f , we use a one-hidden-layer feedforward neural network with input size n, 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 y, and to avoid overfitting we don’t choose a 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 one-hidden-layer 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 4.2, we set η = 0.2 and η = 0.001 in real estate valuation and breast cancer detection experiments, respectively; and in both experiments, for each epoch we update θe and θd by 15 steps.

heading: A.9 A PROPER Z SHOULD BE DETERMINED ON A CASE-BY-CASE BASIS
text: As mentioned in Section 4.2, a practitioner may need to determine a proper Z on a case-by-case basis for our task-aware approach. Fig. 6 illustrates the performance of our task-aware approach under different Z’s for real estate valuation and breast cancer detection experiments. We can observe that in both two experiments, we obtained the best performance on average when Z = 3, i.e., n/2 for real estate valuation and n/10 for breast cancer detection3.

heading: A.10 NON-LINEAR ENCODER AND DECODER MODEL IN REAL ESTATE VALUATION EXPERIMENT
text: 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 encoder 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 η = 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. 5. The explanation is, due to the unnecessary complexity of the encoder and decoder, it is harder to learn good encoder and decoder parameters heuristically. Thus, we conclude that using a simple encoder and decoder, as also observed for the other datasets, is sufficient for high task accuracy.

heading: A.11 EXPERIMENT WITH HIGH-DIMENSIONAL DATA
text: 3The privacy-agnostic approach also achieves the best performance on average under the chosen Z’s.
To illustrate our 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 al. (1998). Here, x ∈ R784 represents a 28 × 28 image of handwritten digit. And y ∈ {0, 1, · · · , 9} is a discrete variable represents the digit in the image. We first train a linear classification model using the ground truth x and y, to serve as our task function f . Then we aim to minimize the cross-entropy loss of ŷ and y, with linear encoder and decoder. We use Z = 10 for both our task-aware approach and the privacy-agnostic approach.
Fig. 5 shows the evaluation result. Since the task loss L of the task-agnostic approach is much larger than the other two approaches, we put it in a separate sub-figure on the left. On the right, we can see our task-aware approach always outperforms the privacy-agnostic approach on overall task loss L under different LDP budgets, which demonstrates the effectiveness of our proposed solution. The maximum improvement against the privacy-agnostic approach is 23.8% ( = 20).

Review summaries:
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.

This paper proposes a task-aware local DP method to improve the privacy andutility 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. 

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.

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.