Corella: A Private Multi Server Learning Approach based on Correlated Queries
Hamidreza Ehteram Mohammad Ali Maddah-Ali Mahtab Mirmohseni
stat.ML cs.CR cs.IT cs.LG math.IT







Corella: A Private Multi Server Learning Approach
 based on Correlated Queries
    Hamidreza Ehteram,
	Mohammad Ali Maddah-Ali,
	and Mahtab Mirmohseni
	Hamidreza Ehteram and Mahtab Mirmohseni are with the Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran (emails: ehteram.hamidreza@ee.sharif.edu, mirmohseni@sharif.edu).
	Mohammad Ali Maddah-Ali is with Nokia Bell Labs, Holmdel, NJ, USA (email: mohammad.maddahali@nokia-bell-labs.com).

    December 30, 2023
========================================================================================================================================================================================================================================================================================================================================================================================================




The emerging applications of machine learning algorithms on mobile devices motivate us to offload the computation tasks of training a model or deploying a trained one to the cloud or at the edge of the network. One of the major challenges in this setup is to guarantee the privacy of the client data. Various methods have been proposed to protect privacy in the literature. Those include (i) adding noise to the client data, which reduces the accuracy of the result, (ii) using secure multiparty computation (MPC), which requires significant communication among the computing nodes or with the client, (iii) relying on homomorphic encryption (HE) methods, which significantly increases computation load at the servers. In this paper, we propose Corella as an alternative approach to protect the privacy of data. The proposed scheme relies on a cluster of servers, where at most T ∈ℕ of them  may collude, each running a learning model (e.g., a deep neural network). Each server is fed with the client data, added with strong noise, independent from user data. The variance of the noise is set to be large enough to make the information leakage to any subset of up to T servers information-theoretically negligible. On the other hand, the added noises for different servers are correlated. This correlation among the queries allows the parameters of the models running on different servers to be trained such that the client can mitigate the contribution of the noises by combining the outputs of the servers, and recover the final result with high accuracy and  with a minor computational effort. In other words, instead of running a learning algorithm on top of a privacy-preserving platform, enabled by MPC or HE, in the proposed approach, the model is trained in presence of the strong noises, correlated across the servers, to achieve high accuracy, without communication and computation overheads of MPC or HE. We evaluate Corella framework for two learning algorithms, the classification, using deep neural networks, and the autoencoder, as supervised and unsupervised learning tasks, respectively. Simulation results for various datasets demonstrate the accuracy of the proposed approach for both problems.




Privacy Preserving Machine Learning, Private Edge Computing, Secure Machine Learning.









§ INTRODUCTION
 

With the expansion of machine learning (ML) applications, dealing with high dimensional datasets and models, particularly for the low resource devices (e.g., mobile units), it is inevitable to offload heavy computation and storage tasks to the cloud servers. This raises a list of challenges such as communication overhead, delay, operation cost, etc. One of the major concerns, which is becoming increasingly important, is maintaining the privacy of the used datasets, either the training dataset or the user dataset, such that the level of information leakage to the cloud servers is under control.

The information leakage of the training dataset may occur either during the training phase or from the trained model. In the training phase privacy, a data owner that offloads the task of training to some untrusted servers is concerned about the privacy of his sampled data. In the trained model privacy, the concern is to prevent the trained model to expose information about the training dataset. On the other hand, in the user data privacy, a client wishes to employ some server(s) to run an already trained model on his dataset while preserving the privacy of his dataset against curiosity of servers. 

There are various techniques to provide privacy in machine learning, with the following three major categories: 


	
  * Randomization, Perturbation, and Adding Noise:
	Applying these techniques to the client data or the ML model can be used to confuse the servers and to reduce the level of information leakage, at the cost of sacrificing the accuracy of the results. 
	
	In <cit.>, it is shown that parameters of a trained model can leak sensitive information about the training dataset. Various approaches based on the concept of differential privacy <cit.> have been proposed to provide privacy to reduce this leakage. A randomized algorithm is differentially private if its output distributions for any two input adjacent datasets, i.e., two datasets that differ only in one element,  are close enough. 
	This technique has been applied to principal component analysis (PCA) <cit.>, support vector machines (SVM) <cit.>, linear and logistic regression  <cit.>, deep neural networks (DNNs) <cit.>, and distributed and federated learning <cit.>. 
	The caveat is that the privacy-accuracy tradeoff in these approaches <cit.> bounds the scale of randomization and thus limits its ability to preserve privacy.
	
	
	
	K-anonymity <cit.> is another privacy preserving framework, in which the data items, related to one individual cannot be distinguished from the data items of at least K-1 other individuals in the released data. It is known that K-anonymity framework would not guarantee a reasonable privacy, particularly for high-dimensional data <cit.>. 
	
	
	
	
	
  * Secure Multiparty Computation:
	This approach exploits the existence of a cluster of servers, some of them non-colluding, to guarantee information-theoretic privacy in some classes of computation tasks like the polynomial functions <cit.>. This approach can be applied to protect the privacy of the data, while executing an ML algorithm on that cluster <cit.>. In other words, MPC algorithms have been mathematically designed such that, the computation is done accurately, while the privacy is guaranteed perfectly. On top of this private and accurate layer of computation, any algorithm  can be executed, including ML algorithms, which can be represented (or approximated) with some polynomial computation in each round.  The shortcoming of this solution is that it costs the network a huge communication overhead, that scales with the degree of the polynomials. To reduce this communication overhead, one solution is to judiciously approximate the functions with some lower-degree polynomials such that the number of interaction among the servers is reduced to some extent <cit.>. Another solution is to rely on Lagrange coding to develop an MPC with no communication among servers <cit.>. That approach can also exploit the gain of parallel computation. The major disadvantage of <cit.> is that this time the number of required servers scales with the degree of the polynomials. 
	
	
	
  * Homomorphic Encryption: 
	Homomorphic encryption <cit.> is another cryptography tool that can be applied for ML applications <cit.>. It creates a cryptographically secure framework between the client and the servers, that allows the untrusted servers to process the encrypted data directly. However computation overhead of HE schemes is very high. This disadvantage is directly reflected in the time needed to train a model or use a trained one as reported in <cit.>. 
	On the other hand, this framework is based on computational hardness assumption, and does not guarantee information-theoretic privacy.




 §.§ Our contributions


In this paper, we propose Corella as an alternative approach to preserve privacy in offloading ML algorithms, based on sending  correlated queries to the  servers.  These correlated queries are generated by adding strong noises to the user data, where the added noises are independent of the data itself, but correlated across the servers. The variance of the noises is large, which makes the information leakage to the servers negligible. On the other hand, the correlation among the noises allows us to train the parameters of the model such that the user can mitigate the contribution of the noises and recover the result by combining the answers received from the servers.  Note that in this method each server runs a regular machine learning model (say a deep neural network) with no computation overhead. In addition, there is absolutely no communication among the servers. Indeed, servers may not even be aware of the existence of each other.  Thus the proposed scheme provides information-theoretic privacy,  while maintaining the communication and computation costs affordable, and still achieves high accuracy. 

In particular, we assume a client with limited computation and storage resources who wishes to run an ML task on his data. Thus for processing, it relies on a cluster of N ∈ℕ servers. We consider a semi-honest setup, meaning that all servers are honest in compliance with the protocol,  but an arbitrary subset of up to T ∈ℕ of them may collude to learn about data. Corella framework is designed for this setup by feeding correlated noisy data to each server. The added noises are designed such that the information leakage to any T colluding servers remains negligible, while the system can be trained to achieve high accuracy. We apply Corella for both supervised and unsupervised learning. 

In summary, Corella offers the following desirable features: 

	
  * Thanks to the designed strong noise added to the user data, the information leakage to any subset of up to T servers is negligible.
	
  * The correlation among the noises enables the system to be trained such that the user can mitigate the contribution of the noises by combining the correlated answers and recover the final result with high accuracy. 
	
  * There is no communication among the servers. Indeed, the servers may not be aware of the existence of the others.  Moreover, the computation load per server is the same as running a classical learning algorithm, e.g., a deep neural network.


In other words, the proposed scheme resolves the tension between privacy and accuracy, and still avoids the huge computation and communication load (or employing a large number of servers), needed in HE and MPC schemes. This is particularly important, when communication resources are scarce, e.g., wireless networks.



Remark 1: Note that in the schemes based on randomization, perturbation, and adding noise, there is no opportunity to effectively eliminate the contribution of those privacy-protective actions (i.e., the added confusion). Thus, increasing the strength of those actions, e.g., noise variance, to improve the privacy will deteriorate the level of accuracy. This challenge has been resolved in Corella, by adding correlated noises for different servers. This provides the opportunity for the system to mitigate the contribution of the noises by combining the output of the servers. Indeed, the system gradually learns to exploit this opportunity during the training phase. However, in conventional schemes  based on randomization, perturbation, and adding noise, this opportunity does not basically exist to be exploited. 


On the other hand, in MPC based schemes,  the noises added for different servers are correlated. This is similar to what we do in Corella. 
However, in MPC, the algorithm is developed to completely eliminate the added noises. In other words, unlike Corella, the system does not learn to mitigate the effect of the noises, but has been mathematically designed to absolutely remove them. This is done at the cost of prohibitive communication load among the servers, or using extra servers,   proportional to the degree of the function for  polynomial models in both cases.  However, in Corella, the model, including  the one deployed in the servers and pre- and post-processing ones in the client, is gradually trained to mitigate the contribution of the noises. This means that in the initial iterations of the learning phase, the effect of the noises is not taken care of, however, thorough learning,  the effect of the noises will be mitigated. This is done without any communication among the servers and with very few servers. 

The rest of the paper is organized as follows.  Section <ref> formally presents Corella framework. Section <ref> is indicated to explaining how to use Corella framework for two popular learning tasks. In Section <ref>, the experimental results are discussed. Section <ref> is dedicated to concluding remarks.




 §.§ Notations
 
Capital italic bold letter X denotes a random vector. Capital non-italic bold letter X denotes a random matrix. Capital non-italic non-bold letter X denotes a deterministic matrix. I(X;Y) indicates the mutual information between the two random vectors X and Y. 
For a function g, the computation cost (e.g., the number of multiplications) and storage cost (e.g., the number of parameters) are denoted as (g) and (g), respectively. (X), for X=[x_1,…,x_n]^⊤∈ℝ^n, is defined as X-μ/σ, where μ = 1/n∑_i=1^n x_i and σ^2 = 1/n∑_i=1^n (x_i-μ)^2. log x is calculated in base 2 (i.e., log_2 x). For T ∈ℕ, [T]={1,…,T}. 𝒩(μ,σ^2) denotes Gaussian distribution with mean μ and variance σ^2. W[:,{t_1,…,t_T}] denotes a submatrix of W, consisting of the columns t_1,…,t_T of matrix W.



§ GENERAL CORELLA FRAMEWORK
 

We consider a system including a client, with limited computation and storage resources, and N servers. The client has an individual data and wishes to run an ML algorithm (e.g., deep neural networks, autoencoder) on it with the aid of the servers, while he wishes to keep his data private from the servers. 
All servers are honest, except up to T<N of them, which are semi-honest. It means that all servers follow the protocol, but an arbitrary subset of up to T servers may collude to gain information about the client data. 
The client sends queries to the servers, and then by combining the received answers, he will derive the result. In other words, we are concerned about privacy of the client data.

The system is operated in two phases, the training phase, and then the inference phase. 

In the training phase, the dataset 𝒮_m={(X^(1),Y^(1)),…,(X^(m),Y^(m))} consisting of m ∈ℕ samples are used by the client to train the model, where (X^(i),Y^(i)) denotes the data sample and its target (e.g., label in the supervised learning), for i=1,…,m.
In addition, the client generates m independent and identically distributed (i.i.d.) noise samples 𝒵_m={(Z_1^(1), …, Z_N^(1)),…, (Z_1^(m), …, Z_N^(m))}, where each noise sample (Z_1^(i),…, Z_N^(i)), with N correlated components, is sampled from a joint distribution ℙ_Z = ℙ_Z_1,…, Z_N. 
The noise components are independent of dataset 𝒮_m.



The data flow diagram is shown in Fig. <ref>, where for simplicity, the sample index (i) is omitted from the variables. For i=1… m, the client, having access to dataset 𝒮_m and noise component set 𝒵_m, uses a preprocessing function g_ to generate N queries 

    (Q_1(X^(i),Z^(i)_1),…, Q_N(X^(i),Z^(i)_N))= g_(X^(i),Z^(i)),

and sends Q_j(X^(i),Z^(i)_j) to the j-th server, for j=1,…,N. 
In response, the j-th server applies a function (a model) f_j, which will be trained, and generates the answer A^(i)_j as,

    A^(i)_j = f_j(Q_j(X^(i),Z^(i)_j)).

By combining all answers from N servers using a post-processing function g_, the client estimates the target,

    Ŷ^(i)= g_(A^(i)_1,…,A^(i)_N),

while the information leakage from the set of queries to any arbitrary T servers must be negligible.

In the training phase, the goal is to design or train the set of functions ℱ={g_,g_,f_1,…,f_N} and ℙ_Z according to the following optimization problem


	ℱ,ℙ_Z1/m ∑_i=1^m {Ŷ^(i),Y^(i)}
	
	I(X^(i);{Q_j(X^(i),Z^(i)_j), j ∈𝒯 }) ≤ε
	∀i ∈[m]
	∀𝒯 ⊂[N], |𝒯| ≤T

where {Ŷ^(i),Y^(i)} shows the loss function between Ŷ^(i) and Y^(i), for some loss function  and the constraint guarantees to preserve ε-privacy in terms of information leakage through any set of T queries, for some privacy parameter ε∈ℝ_≥ 0. We desire that the computation and storage costs of g_ and g_ be low.

In the inference phase, to deploy this model to estimate the target of a new input X, the client chooses (Z_1,…,Z_N), sampled from designed distribution ℙ_Z, independent of all other variables in the network, and follows the same protocol and uses the designed or trained functions set  ℱ.

This framework can apply to both supervised and unsupervised ML algorithms. In the next section, we show how to use Corella framework for the classification and the autoencoder tasks, as two popular examples of supervised and unsupervised learning tasks.

Remark 2: One of the interesting aspects of Corella framework is that the servers don't communicate with each other at all. Indeed, they may not be even aware of the existence of the other servers.




§ CORELLA IN ACTION
 

The objective in this section is to use Corella framework to develop two learning algorithms, (1) privacy-preserving classification, based on deep neural networks, and (2) privacy-preserving autoencoder, as classical examples for supervised and unsupervised learning, respectively.




 §.§ Classification Using Deep Neural Netwoks

In this task, the client wishes to label his data, using N servers, where up to T of them may collude. In this problem, Y is the label of X. The structure of the algorithm has been shown in Fig. <ref>. Here, we explain the different components of the proposed algorithm.






  §.§.§ Correlated joint distribution ℙ_Z
 
The following steps describe how we generate samples of Z. First a matrix W∈ℝ^T × N is formed, such that any submatrix of size T × T of W is full rank.
Then a random matrix Z̅ = [Z̅_1,…,Z̅_T] ∈ℝ^s × T, independent of X, is formed where each entry is chosen independently and identically from 𝒩(0,σ^2_Z̅), where s is the size of each query and σ^2_Z̅ is a positive real number, denoting the variance of each entry. Then, let Z be 

    Z= [Z_1, …, Z_N] = Z̅W.




  §.§.§ Preprocessing function g_

This function, which generates the queries, consists of three blocks: (i) the sample vector X is passed through a neural network with learnable parameters, denoted by g̅_; (ii) the output of first block, U=g̅_(X), is  to Û (as defined in the notation <ref>); (iii) the query of the j-th server, Q_j, is generated by adding the noise component Z_j to Û. Therefore, 

    Q_j = G(X) + Z_j=(g̅_(X))+ Z_j.


Since the client has limited computing resources, g̅_ can be a neural network with one layer or even an identity function. As there is no a priori bound on the range of the output of a neural network (e.g., g̅_), the advantage of (·) function is that provides such a bound. 
As we will see in Subsection <ref>, a large enough noise variance σ^2_Z̅ is sufficient to make the constraint of optimization (<ref>) be satisfied, independent of the choice of g̅_ function.






  §.§.§ Post-processing function g_
 
We form g_ by running a neural network with learnable parameters,  denoted by g̅_, over the sum of the received answers from the servers. Therefore,

    Ŷ = g̅_(A) = g̅_(∑_j=1^N A_j).
 

To limit the burden of the computation and storage on the client, we desire to keep these costs at the client side low. Hence in the implementation, we allocate at most a single-layer neural network to g̅_ and g̅_.



  §.§.§ Functions f_1 to f_N
 These functions are chosen as some multi-layer neural networks with learnable parameters. The parameters of f_1 to f_N will be different.



  §.§.§ Training
 To train the learnable parameters of ℱ, we use some a particular form of gradient descent optimization algorithms to minimize the loss of optimization (<ref>). In other words, we train a model, consisting of N separate neural networks f_1 to f_N and two networks g̅_ and g̅_. The details of this method are presented in Algorithm <ref>. In this algorithm, the parameters of the model are denoted by θ and the training batch size is indicated by b. 





  §.§.§ Proof of privacy preserving
 In Theorem <ref>, we show that the proposed method satisfies ε-privacy, if

    σ^2_Z̅≥1/2ln 2 ps/ε,

where s is the size of each query and

    p = max_Ω∈𝒲{1⃗^ ⊤(ΩΩ^⊤)^-11⃗}∈ℝ_+.

𝒲 denotes the set of all T × T submatrices of W and 1⃗ denotes the all-ones vector with length T.

myTheoremTheorem
[ε-privacy]
	Let  X be a random vector, sampled from some distribution ℙ_X, Z = [Z_1, …, Z_N] and Q = [Q_1, …, Q_N] as defined in (<ref>) and (<ref>). If conditions (<ref>) and (<ref>) are satisfied, then for all 𝒯⊂{1,…, N} of size T, we have 
	
    I (X;  {Q_j,  j ∈𝒯}) ≤ε.

	
	
		Let K = 𝔼[ G(X) G(X)^T] denote the covariance matrix of G(X). Since G(X) is , then  (K) = s. In addition,  consider  the set  𝒯 = {t_1, …, t_T}, where  𝒯⊂ [N] and |𝒯|=T, also let Ω_𝒯= W(:, 𝒯), and Q_𝒯=[Q_t_1, …, Q_t_T]. 
		Then, we have 
		
    Q_𝒯 = [G(X), Z̅]  [1⃗, Ω_𝒯^⊤]^⊤,

		where Z̅ is defined in <ref>. In addition, we define  
		
    [ω_1,…,ω_T]= 1⃗^⊤Ω_𝒯^-1.

		Thus we have,
		
    I (X;  {Q_j,  j ∈𝒯}) = I(X;Q_𝒯) 
       (a)= I(X;Q_𝒯Ω_𝒯^-1)
    		= h(Q_𝒯Ω_𝒯^-1) - h(Q_𝒯Ω_𝒯^-1 | X) 
       (b)= h(ω_1G(X)+Z̅_1,…,ω_TG(X)+Z̅_T) - h(Z̅) 
       (c)≤∑_t= 1^T (h(ω_tG(X)+Z̅_t)-h(Z̅_t)) 
       (d)≤∑_t = 1^T 1/2( log((2π e)^s  (ω^2_tK+σ_Z̅^2I_s)) - log(2π e σ_Z̅^2)^s )
       (e)≤1/2∑_t = 1^T ( log( (1/σ_Z̅^2)^s ((ω_t^2K+σ_Z̅^2I_s)/s)^s ) ) 
       (f)=s/2∑_t = 1^T log(ω_t^2+σ_Z̅^2/σ_Z̅^2)(g)≤s/2ln 2∑_t= 1^T ω_t^2/σ_Z̅^2(h)≤ε,

		
		
		
		
		
		where 
		(a) follows since Ω_𝒯 is a full rank matrix; (b) follows from (<ref>), (<ref>) and the fact that Z̅ is independent of X; (c) follows from inequality h(A,B)≤ h(A) + h(B) for any two random vectors A and B, and the fact that the set of random vectors {Z̅_1,…,Z̅_T} is mutually independent; (d) follows because Z̅ is independent of X and jointly Gaussian distribution maximizes the entropy of a random vector with a known covariance matrix <cit.>; (e) follows from the fact that by considering a symmetric and positive semi-definite matrix H  = ω_t^2 K +σ_Z̅^2I_s with eigenvalues λ_k, we have (H) = ∏_k=1^sλ_k and (H) = ∑_k=1^sλ_k, and therefore we obtain (H) ≤ ((H)/s)^s using the inequality of arithmetic and geometric means; (f) follows since (K) = s; (g) follows due to ln(x+1) ≤ x; and (h) follows from (<ref>), (<ref>),  (<ref>), and  by substituting ∑_t = 1^T ω_t^2 = 1⃗^ ⊤(Ω_𝒯Ω_𝒯^⊤)^-11⃗≤  p. 
		
	
	
	



In the next section, we will evaluate the performance of the proposed scheme for several datasets.



 §.§ Autoencoder




As an example of an unsupervised task, here we focus on autoencoder. An autoencoder has two stages: an encoding stage and a decoding stage. In the encoding stage, the client wishes to compress X to a latent L_j ∈ℝ^l, and store latent L_j in the j-th server, and at a later time, in the decoding stage, reconstruct X from latent L_j, for j = 1 … N. The real number R_=x/l indicates the compression ratio, where x and l denote the size of X and L_j, respectively. In this problem, Y is equal to X. Here we explain the components of the algorithm. In terms of the process of the noise generating we follow the same steps as explained in Subsection <ref> (see (<ref>)). For other components, we have three different scenarios (shown in Fig. <ref>): 




  §.§.§ Scenario 1: Offloading The Encoding Stage (Fig. <ref>)

In this scenario the client wishes to offload the encoding stage to the servers. To generate the queries by g_, the client passes X through g̅_ and then normalizes the output to Û. Having noise component Z_j, he sends query Q_j=Û+Z_j to the j-th server. The j-th server applies f_j to encode and compress received query Q_j to latent L_j ∈ℝ^l, and then stores L_j. When the client wants to reconstruct X, the j-th server sends A_j=L_j to the client. The client passes the sum of received answers, i.e., A=∑_j=1^N A_j, through function g̅_, which implements the decoding stage, to recover X̃ (as an estimation of X). In this problem, we desire that the computation and storage costs of function g̅_ be low. Hence in the implementation, we may set g̅_ equal to an identity function.



  §.§.§ Scenario 2: Offloading The Decoding Stage (Fig. <ref>)

In this scenario the client wishes to offload the decoding stage to the servers. Here function g_ consists of both the encoding stage and the query generating processes, and is done at the client side. The client uses g̅_ to compress X to U∈ℝ^l, then he normalizes the output to Û, and sends query Q_j=Û+Z_j to the j-th server. The j-th server stores latent L_j = Q_j ∈ℝ^l. When the client wants to reconstruct X, the j-th server uses f_j to decode and decompress L_j to A_j and send answer A_j to the client. Then, the client passes A=∑_j=1^N A_j through g̅_ to recover X̃. Here, we desire that the computation and storage costs of g̅_ be low. Thus in the implementation, we may set g̅_ equal to an identity function. 



  §.§.§ Scenario 3: Offloading Both Encoding and Decoding Stages (Fig. <ref>)

In this scenario the client wishes to offload both encoding and decoding stages to the servers. To generate the queries by g_, the client passes X through g̅_ and normalizes the output to Û, and then sends query Q_j=Û+Z_j to the j-th server. The j-th server applies f_j^ to compress the received query to latent L_j ∈ℝ^l, and then stores L_j. When the client wants to reconstruct X, the j-th server applies f_j^ to decode L_j to A_j and send A_j to the client. The client passes the sum of received answers, i.e., A=∑_j=1^N A_j, through g̅_ to reconstruct X̃. In this scenario, f_j(.)= f_j^(f_j^(.)) and we desire to have low computation and storage costs for g̅_ and g̅_. Hence in the implementation, we may set both g̅_ and g̅_ equal to an identity function.

Model training and poof of privacy-preserving in this algorithm are the same as discussed in Subsection <ref> (see <ref> and <ref>).



§ EXPERIMENTS

This section is dedicated to reporting simulation results. In Subsection <ref>, the implementation details of the proposed method is presented. In Subsections <ref> and <ref>, the performance of the proposed method is evaluated for the classification and the autoencoder tasks, respectively.



 §.§ The Implementation Details
 







For the classification and the autoencoder tasks, the proposed algorithm is evaluated for MNIST <cit.>, Fashion-MNIST <cit.>, and Cifar-10 <cit.> datasets by using their standard training sets and testing sets. Furthermore, for the autoencoder task, we evaluate the method for CelebA dataset <cit.>. The only used preprocessings on images are Random Crop and Random Horizontal Flip on Cifar-10 training dataset for the classification task, and padding MNIST and Fashion-MNIST images on all sides with zeros of length 4 to fit in a network with input size 32 × 32. We set the training batch size equal to 128.


We employ Convolutional Neural Networks (CNNs) in g̅_, f_j, and g̅_. We initialize the network parameters by Kaiming initialization <cit.>. 
For each value of the standard deviation of the noise, we continue the learning process until the loss converges, i.e., when the difference in consecutive losses diminishes. We also use Adam optimizer <cit.> and decrease the learning rate from 10^-3 to 2 × 10^-5 gradually during the training.
For N=2 and T=1, we choose

    W_1 × 2=
    [  1 -1 ].

For N=3 and T=2, we choose

    W_2 × 3=
    [       0  √(3/4) -√(3/4);       1    -1/2    -1/2 ].

For N=4 and T=3, we choose

    W_3 × 4=
    [       0  √(8/9) -√(2/9) -√(2/9);       0       0  √(2/3) -√(2/3);       1    -1/3    -1/3    -1/3 ].

For N=5 and T=2, we choose

    W_2 × 5=
    [ sin 0α sin 1α sin 2α sin 3α sin 4α; cos 0α cos 1α cos 2α cos 3α cos 4α ],

where α = 2π/5.




 §.§ The Classification Task











In this setup, f_j is a neural network with several convolutional layers and two fully connected layers with the Rectified Linear Unit (ReLU) activation function (see Table <ref> for details). To limit the computation cost of the pre- and post-processings at the client, we use at most one convolutional layer in g̅_ and at most one fully connected layer in g̅_. In particular, g̅_ is either an identity function, denoted by 𝖨𝖽𝖾𝗇., or a convolutional layer with n_i∈ℕ output channels. In addition, g̅_ can be a fully connected layer, with a vector of length n_o∈ℕ as the input, and generating 10 outputs, representing 10 different classes. The input vector of length n_o is formed by adding the N vectors of length n_o, received the from servers. In addition, we also consider a very simple case for g̅_, where n_o = 10 and at the client side, we simply add up the vectors of length n_o, received from the servers. In other words, in this case g̅_ is equal to the identity function. We represent the structure of g̅_ and g̅_ by (n_i→ n_o), where the number of the output channels at g̅_ is equal to n_i (with the exception that n_i=𝖨𝖽𝖾𝗇. means g̅_ is the identity function, i.e., g̅_(X) = X), and the number of the output neurons at f_j is equal to n_o (with the exception that n_o=𝖨𝖽𝖾𝗇. means  g̅_(A) = A). In Table <ref>, c_i denotes the number of the input image channels. Since the variance of the input queries can be high (see equation (<ref>)) we use (.) function at the first stage of f_j. We use the cross-entropy loss function between Y and 𝗌𝗈𝖿𝗍𝗆𝖺𝗑(Ŷ) for {Ŷ,Y}.




  §.§.§ Experiment 1


In this experiment, we focus on MNIST dataset, and consider a system with N=2 servers, no colluding (T=1). In addition, we use identity mapping for both g̅_ and g̅_. This means the number of the output neurons at the servers is 10 and we simply add the received answers of the servers to find the label of the client data. This case is denoted by ( 𝖨𝖽𝖾𝗇.→𝖨𝖽𝖾𝗇.). Fig. <ref> reports the accuracy for the testing and training dataset versus the training epoch number for σ_Z̅=70, representing a very strong noise. This figure shows that the proposed approach allows the model of the servers to train in presence of the strong but correlated noises, such that the client can mitigate the contribution of the noises by combining the outputs of the servers. 



Fig. <ref> reports the accuracy for the testing dataset at the end of the training phase versus σ_Z̅ and ε for different σ_Z̅ ranging from 0 to 70. It shows that using Corella, the client achieves 90% accuracy while the privacy leakage is less than ε = 0.12, thanks to the strong noise with σ_Z̅ = 70. 
Also, this figure visualizes the inputs and the outputs of the servers for an MNIST sample in this experiment. As you can see, when logσ_Z̅ = 6, the input of each server is severely noisy, and we cannot identify the label of the input from it. Still, the client can detect the label with high accuracy.
Fig. <ref> shows the answer of each server (which is a vector of length 10), where the correct label is "8" and σ_Z̅=70. As you can see, in the answer of an individual server (A_1 and A_2), the correct label (here "8") does not rank among the labels with highest values. However, when we add the values correspondingly, "8" has the highest value in the result. In particular, after applying softmax, the density on the correct label is significantly higher than the rest. This observation intuitively confirms the privacy and accuracy of the proposed Corella method. 



A similar effect is shown in Fig. <ref>. In this figure, we use a test sample from MNIST dataset with label "6" as the input. We want to visualize how each server is confused about the correct label (here "6"), with an incorrect one (say "9"). Each plot in the second row of Fig. <ref> is a 2D-plot histogram, representing the joint distribution of two neurons of the output of server one, i.e., A_1[6] and A_1[9] (A_1[6] on the x-axis and A_1[9] on the y-axis). We have this figure for different values of σ_Z̅. If the point (A_1[6],  A_1[9]) is above the line y=x, i.e., A_1[9] > A_1[6], it means that server one incorrectly prefers label "9" to label "6". 
In the first row in Fig. <ref>, we have the same plots for A[9] versus A[6], where A=A_1+A_2. As we can see, even for large noise (i.e., σ_Z̅=70), server one chooses "6" or "9" almost equiprobably, while the client almost always chooses the label correctly. This shows that, in our proposed method, simultaneous training of the two networks f_1 and f_2 on the correlated queries allows the system to be trained such that the distribution of the noise at the output of the system does not confuse the client about the correct label (see the first row in Fig. <ref>).




  §.§.§ Experiment 2
 


In this part, we evaluate the performance of the proposed method for N=2 and T=1, for three different datasets, including MNIST, Fashion-MNIST, and CIFAR-10, and for various levels of noise. In addition, we compare the performance of the method, with the case where we have only one server and we add noise to the input to protect privacy of the data. For the system with one server, we train the model, in the presence of noise. For each dataset, we plot the accuracy of the proposed method for two models and σ_Z̅ = 0 to 70. Figures <ref>, <ref>, and <ref> demonstrate both the accuracy of the proposed method and the accuracy of the system with one server, versus logε and σ_Z̅. Figures <ref>, <ref>, and <ref> compare the accuracy of the proposed method with the case with one server. Figures <ref>, <ref>, and <ref> show that unlike the systems with one server, Corella achieves a good accuracy for various datasets, even for high level of noises. For example, in Fig. <ref>, the client with low post-processing in N( 𝖨𝖽𝖾𝗇.→32) achieves 95% accuracy for σ_Z̅ = 70, while with a single server and adding noise with the same variance, we can achieve 13% accuracy (see Fig. <ref>). This comparison emphasizes on the fact that having more than one server with correlated noise world allow the system to mitigate the contribution of the noise, even when the noise is strong. However with one server, even with training, the system cannot eliminate the noise. Thus, the ability of noise mitigation in Corella follows not only from training in the presence of noise but also the fact that we have more than one server and the noises are correlated. In general, although the accuracy of Corella decreases with increasing the variance of the noise, it still converges to a reasonable value.





  §.§.§ Experiment 3




In this experiment, we discuss the client costs in terms of the computation, storage, and communication. In Table <ref>, we evaluate the proposed algorithm for various models and values for (N,T). We report the test accuracy for three datasets and the computation and storage costs of the client relative to the computation and storage costs of one of the servers. In this table, (·) and (·) denote the number of products (representing computational complexity) and the number of the parameters (representing storage complexity) in a model, respectively. In addition, we report the size of each query, denoted by s, relative to the size of the client data (the image size).

In this table, the difference in the cost of the client and each server (in terms of computational and storage complexity) is quite evident. On the other hand, the communication load between the client and each server is low, which is in the order of the size of X (in the stage of sending query), and in the order of the size of Y (in the stage of receiving answer). The low costs of computation and communication at the client side, and the guarantee of good accuracy make Corella framework suitable for practical use cases in mobile devices and the internet of things (IoT).





 §.§ The Autoencoder Task






In this experiment, we evaluate the proposed method for the autoencoder task. The network structures of Encoder(·) and Decoder(·) are presented in Table <ref>. In this table, c_i and c_o denote the number of channels of the input image (i.e., the client data) and the latent, respectively. As detailed in Table  <ref>, the encoder includes three convolutional layers. Similarly, the decoder is composed of three transposed convolutional layers. 
We choose the network structures of g̅_, f_j, and g̅_ as follows: (i) in offloading the encoding stage (Scenario 1), g̅_(X)=X, f_j(Q_j)= Encoder(Q_j), and g̅_(A)= Decoder(A); (ii) in offloading the decoding stage (Scenario 2), g̅_(X)= Encoder(X), f_j(Q_j)= Decoder(Q_j), and g̅_(A)=A; (iii) in 
offloading both encoding and decoding stages (Scenario 3), g̅_(X)=X, f_j(Q_j)= Decoder(Encoder(Q_j)), and g̅_(A)=A.
We use the mean squared error (MSE) loss between 𝗌𝗂𝗀𝗆𝗈𝗂𝖽(Ŷ) and Y for {Ŷ,Y}, where Y is equal to image X, Ŷ denotes the output of the model, and the range of the pixels of image X is [0,1].




  §.§.§ Experiment 4







At first, we evaluate our proposed method for CelebA dataset for the compression ratio R_=8, (N,T)=(2,1), and logε = 0, 2, and 4. When each layer of the encoder halves the height and width of its input (see Table <ref>), the latent size is equal to c_o ×h/8×w/8, where h and w represent the height and the width of the input image. Thus R_=c_i × h × w/c_o ×h/8×w/8=64 × c_i/c_o. As a result, for R_=8, we choose c_o=24, noting that CelebA images have 3 color channels (i.e., c_i=3).
Fig. <ref> visualizes the input image (X), the queries (Q_1 and Q_2), the answers (A_1 and A_2), and the reconstructed image (X̂=𝗌𝗂𝗀𝗆𝗈𝗂𝖽(Ŷ)), for different images from CelebA dataset. To plot the latent, we reshape it to an image with three channels. This figure shows that Corella method allows the client to offload privately the computational tasks of the encoder or the decoder, and then reconstruct the images, with high quality (shown in Fig. <ref> and Fig. <ref>), or offload both the computational tasks of the encoder and the decoder, and then reconstruct the images, with acceptable quality (shown in Fig. <ref>).



Remark 3: 
For Scenario 3, one may suggest an alternative but naive method as follows.  We train two autoencoders separately, one to encode X+Z and decode its latent to back X+Z, and the other to encode X-Z and decode its latent to X-Z, where Z is a noise with high variance. Then the client adds the outputs from the two decoders to reconstruct X. While this approach might seem reasonable, it doesn't work in practice. The reason is that X+Z has a very high entropy, and thus cannot be compressed to a short latent and then be recovered accurately. The same statement holds for X-Z. The reason that Corella overcomes this problem is that in Corella, both servers are trained simultaneously such that the final result at the client is accurate. However, the input and the output of the autoencoder in each server are not similar at all. Fig. <ref> demonstrates this observation clearly.



One may ask if a single server can recover the original image from the query of one of the servers (say server one), if it is trained to. We evaluate this scenario and report in Fig. <ref>. Fig. <ref> shows the result if we train a single server to recover the image from the query of server one in scenario two, while Fig. <ref> shows the same result if a server is trained to recover the image from the query of server one in scenarios one and three. These figures show that reconstructing client image from the query received by one server is almost impossible.



In Table <ref>, we report the experimental results for various datasets, compression ratios, different scenarios, and tuples (N,T). In this table, the client loss and the server loss are denoted by l_ and l_, respectively. The server loss is equal to the loss of the image reconstruction when T servers collude and run a neural network, to reconstruct the client image from their queries. The network structure is the same as what described in Table <ref>, where the T received queries are concatenated in the input. This means that we set the number of the input channels (c_0 in Scenario 2 and c_i in Scenario 1 and Scenario 3)  equal to T times the number of channels of a single query. These results show that the difference between the client loss and the server loss is significant. Therefore, while T colluding servers learn nothing from the received queries, the client can recover the image with good quality.








§ CONCLUSION


In this paper, we propose Corella as a privacy-preserving framework for offloading machine learning algorithms. This is particularly important for mobile devices that have limited computing resources.  In Corella, we add strong noise to the data before sending it to each server. However, to provide an opportunity to mitigate the resulting confusion and so guarantee a reasonable accuracy, the added noises to different servers are designed to be correlated.  Unlike MPC that guarantees that added noises will be eliminated completely through carefully designed excessive interaction among the servers (or alternatively using many servers), in Corella, the servers are trained to mitigate the effect of noise. Interestingly, with this method, we simultaneously achieve a high level of accuracy and a high level of privacy, with only a few servers (e.g., just two), and without any communication among the servers. Indeed, in Corella framework, in the process of training the model to predict the result (e.g., label) accurately, the model is also trained to mitigate the effect of the noises. Correlation among the noises provides the chance for this training to be successful, which is confirmed experimentally.








IEEEtran



