Guaranteed distributed machine learning: Privacy-preserving empirical risk minimization

1.   Introduction

With the proliferation of Mobile Sensor Networks ^[1], mobile devices (i.e., smartphones, tablets, personal digital assistant, laptop computers, smart watches, e-readers) are widely preferred by users since it is gradually occupying an imperative position in sensor-based activity recognition ^[2], coupled with the rapid growth of its per capita holding. Privacy-preserving ^[3] is a fundamental challenge for the massive structured and unstructured ^[4] datasets generated in these numerous smart applications that rely on data aggregation and combined learning across diverse nodes. Existing approaches take different methods to address these privacy concerns. Two predominant approaches are secure Multiparty Computation (MPC) and Differential Privacy (DP) ^[5].

MPC is a preferred option to optimize a computational function over jointly distributed data resources with the application of cryptographic primitives (i.e., oblivious transfer, secret sharing, and homomorphic encryption) whiles keeping these data private. MPC under different adversarial models have been studied in numerous computer domains (e.g., ^[6]). One of the initial private data mining methods in this domain was proposed by Lui et al. ^[7], which was preceded by plethora of works considering various applications or implementation of adversarial models. Most of the existing MPC primitives to help meet the secure requirements are based on the advancement in fully homomorphic encryption (FHE) ^[8]. It enables data providers to encrypt individual datasets with the public key and outsource a computation to the cloud server. The cloud server computes on the encrypted datasets and therefore generates encrypted intermediate results. In the absence of the secrete key, cloud server basically serves as a computation platform that is unable to access any of the individual records. Current emphasis has been on achieving realistic and efficient Distributed machine learning (DML)with the application of MPC primitives ^[9], and in some domains these approaches have demonstrated to scale hundreds of millions of records to learning tasks ^[10]. Notwithstanding the considerable benefits of MPC, it still has an inevitable obstacle: issues of security and privacy. The cloud server may be semi-honest and even malicious in specific cases, which means it may be motivated to infer from the individual's confidential information for profit or curiosity during the training of the machine learning models. This is becoming a non-trivial privacy concern for outsourced secure multiparty computation.

Differential privacy comes in handy to inject noise into the intermediate results to avoid inferring sensitive information about any specific individual record. However, in order to balance privacy and model usability, careful calibration of the statistical noise is required. Conversely, accomplishing the trade-off amid the privacy and utility of the DP algorithm still remains a problem. Concretely, unlike prevailing approaches involving the use of differential privacy on classifiers, they only protect the training data during the learning process; there is no focus on mitigating the privacy risk of black-box inference attacks on the resultant machine learning model. In the architecture of differential privacy, Empirical Risk Minimization (ERM) plays a crucial role as it encompasses a myriad of tasks in machine learning. In cases where one knows how to implement ERM privately (DP-ERM), for extended machine learning problems, essentially regression and classification, it, therefore, becomes easy to obtain differentially private algorithms. The initial representative works in this line of study was conducted by ^[11]. DP-ERM should have indistinguishable intermediate results when there is a small modification in the input datasets. Specifically, earlier studies on DP-ERM to guarantee differentially private optimization are based on three methods: Objective Perturbation, Output Perturbation (OP), and Gradient Perturbation(GP).

Concretely, existing approaches have demonstrated that it may be applied to permit privacy-preserving in the centralized domain with an individual entity possessing the entire dataset. However, there is a more prevailing problem where data is owned by multiple organizations in the distributed domain. Consider the real-world application of this paradigm in medical research where multiple hospitals may wish to collaboratively train a model with the application of the sensor-based activities recognition medical records generated from a large number of patient wearable mobile devices without exposing their individual data instances to other parties. This powerful method has been integrated with Distributed machine learning in the pioneering study of Pathak et al. ^[12], which securely aggregates locally trained classifiers with the application of output perturbation to establish differential privacy. Since the allocated noise in the model is inversely proportional to the smallest dataset with $p$ parties, Jayaraman et al. ^[13] later improved the noise scale by a factor of $\sqrt{p}$ with the adoption of secure model aggregation of locally trained classifiers ^[14] and then execute naïve aggregation of the locally trained models whiles providing meaningful privacy guarantee. Their proposed output perturbation algorithm is capable of improving Pathak et al.'s ^[12] protocol by a component of $p$ by injection of statistical noise within the secure MPC domain based on a required noise scale which is inversely proportional to the volume of the whole dataset.

Despite the recurrent progress in such markets, for several hospitals to deploy mobile sensor networks in a Pervasive healthcare monitoring setup to accumulate health dataset through mobile devices to develop innovative diagnostic classifiers from these patient records, there are still quite some few threatening issues:

(a) Such existing works ^[12,13] provides model parameters without any uncertainty. Therefore, making it extremely difficult to add capabilities for quantifying uncertainty in the model coefficients.

(b) In cases where the data is extremely huge with each individual data provider having only one training instance, application of classifier aggregation method for generating a global model from multiple locally trained classifiers based on the use of parameter averaging technique may lead to information leakages. Since the parameter averaging is only applicable to the collection of the same model type, which will also tend to generate less accurate global aggregated classifiers in comparison to the centralized domain.

(c) Since the accuracy of the model relies heavily on the pre-specified amount of iterations -T, in situations where the iteration is too little, the learning procedure will discontinue well short of the optimal, and the larger the iteration, the smaller the privacy budget $\epsilon_{t}$ for each iteration. therefore, it requires large volumes of statistical noise to be injected at every gradient iteration, hence causing the swamping of the signal contributed by the gradient in the iterative training procedure.

(d) In the initial stage of ERM optimization, gradients are anticipated to remain very huge, this is to enable the learning algorithm to find adequate parameter updates irrespective of when the gradient is not computed accurately. Nonetheless, the gradient begins to decrease and requires accurate measurement as the current parameter $w_{t}$ approaches the optimal values. This is to enable the optimization algorithm to continue minimizing or approximately minimizing the loss function $f$. This implies that on the grounds that total privacy cost remains unchanged it is important to apply an adaptive iterative privacy budget allotment than a fixed allotment.

The basic pipeline for securely training distributed machine learning models in this scenario is illustrated in Figure 1, where the secure multi-party machine learning framework is a composition of p + 1 data providers $\{\emptyset_{1}, \emptyset_{2}, \ldots, \emptyset_{p} \}$ and a cloud server. In this architecture, the assumption is that each data provider $\emptyset_{i}$, who holds their individual private dataset $\mathcal{D}_{i}$ medical records and a training model $\theta$ generated from the dataset, is willing to improve the accuracy of the globally trained model without leaking any sensitive information about the locally owned confidential dataset.

In this paper, we argue that it is of great significance to introduce differentially-private distributed machine learning algorithms to thrash out the three outlined fundamental problems in the current protocol ^[13,14]. We apply both output perturbation and gradient perturbation with the injection of statistical noise inside a secure multi-party computation domain. The inherent strategy is to demonstrate that our output perturbation algorithm securely aggregates the locally trained models which are encrypted with distinct encryption primitives or even with distinctive keys to achieving $\epsilon$-differential privacy with the addition of statistical Laplace noise to the aggregated classifiers parameters. In our gradient perturbation scheme, individual data owners jointly execute an adaptive iterative gradient-based protocol where they securely aggregate the local gradients per each iteration with distinctive share $\epsilon_{t}$ of the total privacy budget $\epsilon$. Therefore providing ($\epsilon$, $\delta$)-differential privacy with the application of adaptive gradient descent approach for zero-mean Concentrated DP ^[15] (zCDP).

This protocol offers ($\epsilon, \delta$)-differential privacy guarantee in the honest-but-curious security threat environment by the underlying cryptosystem and privacy-preserving primitives. In this domain, adversaries may only obtain negligible opportunities to leak the sensitive data instance since the individual models are globally encrypted. It provides a more practicable and efficiency privacy-preserving primitive in the Distributed machine learning domain.

The principal contribution to this work can be summarized in threefold:

● To strongly achieve computationally more efficient and also maintain higher accuracy irrespective of how the dataset is partitioned when accurate machine learning models are privately trained in the distributed setting, we apply noise bounds for each of our two chosen protocols; multi-scheme output perturbation (MS-OP) and gradient perturbation (MS-GP) method in our proposed algorithm.

● For our gradient perturbation method, we present a private gradient descent protocol based on zCDP ^[15] which is more robust than ($\epsilon, \delta$)-differential and also attain minimum known bound on the privacy budget. In this algorithm step size per iteration and privacy, the budget is dynamically decided at run-time grounded on the value of injected statistical noise obtained for the current iteration of the gradient. Additionally, the noise is generated within the secure multiparty protocol. This will enable us to inject a unique copy of statistical noise as compared to existing approaches that aggregate noise from individual data owners.

● Our algorithm is validated on real human activity datasets against other recently proposed empirical risk minimization algorithms on Distributed learning; whiles alternating the number of data owners and volumes of the local dataset. We empirically show the effectiveness of the proposed protocol for an extended privacy level. Our simulations indicate the practicality and feasibility of our model and are very close to the non-private classifier relative to the accuracy of the classifiers and their generalization errors.

In Section 2, we provide an outline of the related works. Section 3 presents some preliminaries and the definition of multi-party Differential privacy in the distributed domain. The proposed architecture is given in Section 4. Experimental results for the proposed architecture will be demonstrated in Section 5, Section 6 deals with the comparative evaluation of our algorithm.

2.   Related works

Distributed machine learning (DML) ^[16] as a decentralized machine learning theory enables distributed training on a large scale of a dataset in edge devices including electronic meters, and sensors smartphones where no individual node is capable of getting the intelligent decision from a massive dataset within an appreciable period of time. DML technique has earned a remarkable reputation in numerous pragmatic areas such as visual object detection, health records, big data analysis, control policies, and medical text extraction. Regrettably, as the number of distributed data owners increases, the guarantee for the security of the datasets from the individual data owners becomes extremely difficult. This lack of security will increase the threat that adversaries attack the dataset preceded by the manipulation of the intermediate training result. Therefore, affecting data integrity which is a key component in training machine learning models. Adversarial data attacks ^[17] is one of the distinctive ways with the aim of corrupting the machine learning models by contaminating data during the training phase. Consider in a scenario where newly generated datasets are expected to be updated periodically by the data owners for improving the models, the adversary is likely to gain more chances of poisoning the dataset, posing a severe threat in the Distributed machine learning models. This kind of threat is considered one of the most imperative emerging security threats against machine learning models. Since the adversarial attack has the potential of misleading the diverse machine learning methods, a widely applicable DML protection mechanism is urgently required to be investigated. There have been numerous works conducted on privacy-preserving DML, most of the research approaches were greatly stimulated by privacy-preserving machine learning and data mining. The existing literature on privacy-preserving DML basically falls into two major categories: cryptography-based technique and perturbation-based methods.

The cryptography-based methods typically incorporate cryptographic tools to preserve the privacy of the datasets. Secure multiparty computation may potentially address these security threat in the DML system. Though acquiring information with the aggregation of the dataset from multi-parties is a critical task for machine learning, in a real-world business setting, the prevention of privacy leakages while carrying out this privacy-preserving task is a very crucial requirement for secure multiparty computation. Secure multi-party computation problem refers to collaborative execution of a statistical function together by multiple data owners. After the computation, individual data owners acquire accurate results and no one can get more knowledge than the dataset inferred from the public intermediate results. Secure multiparty algorithms are basically cryptographic-based methods that apply a typical cryptographic technique to perform these Distributed machine learning tasks. The data owners try not to expose any knowledge on original data except that can be inferred from the output ^[7] of the Distributed machine learning task. Over the past few years, secure multiparty computation has widely been applied to achieve privacy-preserving in the distributed machine since it is more effective and efficient than other privacy-preserving algorithms. Secure MPC is capable of supporting floating-point and fix-point arithmetic operations ^[18], this arithmetic functions can be executed with controlled linear complexity ^[19]. Owing to these benefits, exploring the potential of secure multiparty computation required for privacy-preserving in Distributed machine learning has gained considerable attention over the past few years. Initial proposals to secure two-party(2PC) computation was first introduced by Yao ^[20] in 1982. Subsequently, Goldreich et al. ^[21] generalized and stretched 2PC method to the secure multiparty computer (MPC) problem. Secure MPC later gains so much research attention to finding practical ways of exploring the potential in this domain. Gentry ^[8] with the aid of homomorphic encryption with ideal lattices primitive was the first to introduce secure MPC. This was later preceded by numerous researchers proposing various secure MPC implementations, including Lost-cost Multi-party Computation for Dishonest Majority ^[22] Semi-homomorphic Encryption and Active-Secure Two-Party Computation ^[25]. To the highest degree, these algorithms can be categorized into two major methods such as secret sharing and homomorphic encryption. Gentry et al. ^[8] achieve the initial scheme with multiplicative and additive homomorphism respectively, this will require a long period of time to execute the complex circuits during the performance of the inevitable elimination of the noise. To the contrary, secrete sharing primitive ^[24] is capable of calculating infinite times of any multiplication and addition with an additional exchange of datasets. In a typical example of a two-party domain, Bansal et al. ^[26] applied secure scalar and secret sharing to protect privacy leakages during the training process which is not trivial to be extended to the secure multi-party models. Yuan et al. ^[27] propose a privacy-preserving back-propagation algorithm for secure multi-party deep learning over arbitrarily partitioned datasets grounded on BGN homomorphic encryption ^[28]. Nevertheless, the primitive requires all the data owners to be online and interactively collaborate to decrypt the ciphertext of the intervening parameters during each iteration. In ^[29], Hesamifard et al. propose a privacy-preserving machine learning algorithm using encrypted data to make encrypted predictions in the cloud. Since fully homomorphic encryption(FHE) ^[8] generates high computational complexities, they proposed a confidentially binary classification-based method to find a trade-off between the degree of the polynomial approximation and the secure performance of the training model. Li et al. ^[30] with the aid of multi-key fully homomorphic encryption (MK-FHE) ^[31] also propose a privacy-preserving multi-party deep learning primitive, in this setting, the individual data owners encrypts their datasets with different public keys and outsource them to the cloud server, the cloud server therefore train the deep learning classifiers with the application of MK-FHE. Based on the relevant literature above, it is obvious that most of the cryptography-based algorithms use fully homomorphic or multi-key fully homomorphic encryption primitives to encrypt the entire dataset before outsourcing it to the cloud server.

With the addition of noise to the raw dataset, the perturbation-based method is able to protect the privacy of the dataset. Agrawal et al. ^[32] proposes an algorithm that injects elaborately designed noise to the training data while preserving the statistical properties to enable the training of Naive Bayes classifier. With the gradual explosion of the digitized dataset, Fong et al. ^[33] offered a privacy-preserving learning algorithm by transforming the original dataset into groups of unreal datasets whiles preserving the accuracy for the learning model. Furthermore, this algorithm ensures that the original data samples cannot be reconstructed without the whole group of constructed datasets. DP is a strong golden standard to guarantee privacy-preserving for algorithms on aggregated datasets, which is widely applied in privacy-preserving DML to ensure that the dominance of any single data owners record is insignificant. DP has been utilized in many existing applications by large-scale businesses such as US Census Bureau ^[34]. A typical Distributed machine learning strategy applied in this domain is Empirical Risk Minimization (ERM), where the average error of the trained model over the aggregated datasets is minimized. There have been numerous proposals to advance the works on privacy-preserving algorithms for ERM problems with the application of variations of differential privacy. This paradigm is known as Differentially Private Empirical Risk Minimization (DP-ERM) ^[13]. DP-ERM reduces the empirical risk whiles providing the assurance the intermediate results of the learning model is differentially private based on the aggregated training dataset. This privacy-preserving guarantee ensures strong protection against potential adversaries such as inference attacks. To guarantee privacy-preserving in this domain, it is always essential to launch randomness to the training protocol. Based on the time for noise injection, there are mainly three ways to initiate randomness: objective perturbation, output perturbation, and gradient perturbation. This work introduces a differentially-private (DML) algorithms with the application of both gradient perturbation and output perturbation whiles injecting the noise within the secure multi-party computation.

3.   Preliminaries and problem definition

In this section, we introduce the notations (Table 1) in our proposed protocol and the necessary background for our analyses, including empirical risk minimization, zero-concentrated differential privacy, and basic assumptions in secure multi-party computation.

3.1.   Problem setting

Given a dataset $D =$ $\left\{d_{1}, \cdots, d_{n}\right\}$ from a data universe $\mathcal{X}$ and a closed convex set $\mathcal{C} \subseteq \mathbb{R}^{p},$ DP-ERM is to find $x_{\rm {priv }} \in \mathcal{C}$ so as to minimize the empirical risk, i.e.,

with the guarantee of being differentially private, where $f$ is the loss function and $r$ is some simple (non)smooth convex function called regularizer. When the inputs are drawn i.i.d from an unknown underlying distribution $\mathcal{P}$ on $\mathcal{X},$ we also consider the population risk $\mathbb{E}_{z \sim \mathcal{P}}[f(x, z)].$ If the loss function is convex, the utility of the algorithm is measured by the expected excess empirical risk, i.e.,

or the expected excess population risk (i.e., generalization error), i.e.,

where the expectation of $\mathcal{A}$ is taking over all the randomness of the algorithm.

3.2.   Differential privacy

Let $D = \{d_{1}, d_{2}, ..., d_{n}\}$ represent $n$ data points, each derived from some setting $\mathcal{D}$. Two neighboring databases D and $D^{'}$; if $|D|$ = $|D^{'}|$ differing in exactly one data point. $D^{'}$ is obtained by the addition or removal of one observation from $D$. The concept of DP was commenced by Dwork ^[5] and outlined as follows:

Definition 1. $(\epsilon, \delta)$-DP ^[5]. A randomized mechanism $\mathcal{M}$ satisfy $(\epsilon, \delta)$-DP if for every event $\mathcal{S}$ $\subseteq$ range $(\mathcal{M})$ and for all $D, D^{'} \in D^{n}$,

when $\delta = 0$, $\mathcal{M}$ accomplishes pure DP by providing stronger privacy protection than approximate DP with $\Delta > 0$. We can add noise sampled form Guassisan and Laplace distributions respectively to achieve $\epsilon$-DP and $(\epsilon, \delta)$-DP where the noise is proportional to $\ell_{2}$ norm sensitivity of $\mathcal{M}$; given as $\Delta \mathcal{M} = \lVert \mathcal{M}(D)- \mathcal{M}(D^{\prime})\rVert$.

Definition 2. ($\ell_{1}$and $\ell_{2}$ norm sensitivity) Let $q : D^{n} \leftarrow \mathbb{R}^{d}$ be a query function. The $\ell_{1}$(resp. $\ell_{2}$) sensitivity of $q$, denoted by $\Delta_{1}(q)$ (resp., $\Delta_{2}(q)$) is defined as follows:

The $\ell_{1}$ and $\ell_{2}$ sensitivities represent the maximum change in the output value of $q$ (over all possible neighboring databases in $D^{n}$) when one individual's data is changed.

Theorem 1. Let $\epsilon \in (0, 1)$ be arbitrary and $q$ be a query function with $\ell_{2}$ sensitivity of $\Delta_{2}(q)$. The Gaussian Mechanism, which returns $q(D) + N(0, o^{2})$ Let $\epsilon \in (0, 1)$ be arbitrary and $q$ be a query function with $\ell_{2}$ sensitivity of $\Delta_{2}(q)$. The Gaussian Mechanism ^[35], which returns $q(D) + N(0, \sigma^{2})$ with

is ($\epsilon, \delta$)-DP

A critical property of DP is its privacy guarantee reduces gracefully under the composition. The most basic composition result shows that the privacy loss grows linearly under k-fold composition ^[36]. This implies, if we sequentially apply an $(\epsilon, \delta)$-differential privacy algorithm $n$ times on the same data, the resulting process is $(n\epsilon, n\delta)$. Dwork et al. ^[37] provided a booting method to construct an improved privacy-preserving synopsis on the queries with an advanced composition; the loss function upsurges sub-linearly at the rate of $\sqrt{n}$.

Theorem 2. For all $\epsilon, \delta, \delta^{\prime}\geq 0$ the class of ($\epsilon, \delta$)-differential private mechanisms satisfy $(\epsilon^{\prime}, n\delta + \delta^{\prime})$-differential privacy under k-fold adaptive composition for $\epsilon ^{\prime} = {\sqrt{2n}In(\frac{1}{\delta^{\prime}})\epsilon + n\epsilon(e^{\epsilon - 1})}$ as stated in the advance composition ^[37].

3.3.   Zero-concentrated differential privacy

Whiles, differential privacy is suitable for algorithms such as output perturbation, it is not the preferred choice for gradient perturbation which is essentially repeated sampling of statistical noise during the iterative learning process. Bun and Stainke ^[15] provided zero-concentrated DP (zCDP). which has a tight composition bound and a preferable option for gradient perturbation. We define $\rho$-zCDP by the introduction of the privacy loss random variable as applied in the definition of zCDP.

Definition 3. For an output $0\in range(\mathcal{M})$, the privacy loss random variable $\mathcal{Z}$ of the mechanism $\mathcal{M}$ is defined as follows:

$\rho$-zCDP therefore imposes a bound on the moment generating function of the privacy loss $\mathcal{Z}$ and requires it to be tightly concentrated around zero mean, hence it is unlikely to distinguish $\mathcal{D}$ from $\mathcal{D}{'}$. Formally, it important to satisfy the following:

where ${D_{\alpha}\left(M(D) \| \mathcal{M}\left(D^{\prime}\right)\right)}$ is the $\alpha$-Rényi divergence. In this work, we apply the resulting zCDP composition.

Lemma 1. ^[15] If two mechanisms satisfy $\rho_{1}$ -zCDP and $\rho_{2}$ -zCDP, then their composition satisfy $(\rho_{1} + \rho_{1})$-zCDP

If two mechanisms satisfy $\rho_{1}$ -zCDP and $\rho_{2}$ -zCDP, then their composition satisfy $(\rho_{1} + \rho_{2})$-zCDP

Lemma 2. ^[15] The Gaussian mechanism returns $q(\mathcal{D})+\mathcal{N}(0, \sigma^{2})$ satisfies $\Delta_{2}(q)^{2}/(2\sigma^{2})$-zCDP

Lemma 3. ^[15] If $\mathcal{M}$ satisfies $\epsilon$-DP, then $\mathcal{M}$ satisfy $(\frac{1}{2}\epsilon^{2})$-zCDP, then $\mathcal{M}$ is $(\rho+2 \sqrt{\rho \log (1 / \delta)}, \delta)$-DP for any $\delta > 0$.

3.4.   Secure multi-party computation

In our security threat model, we consider honest-but-curious (semi-honest) data providers who wish to collaboratively train a model without exposing their individual inputs to other data owners. Data providers do not collude to temper with the collaborative functionality or inject garbage input data, they are capable of passively inferring about inputs of other data providers depending on the implementation of the algorithm. We applied generic secure multiparty computation primitives to securely aggregate locally trained classifiers and their gradients. K. Owusu-Agyemang et al. ^[38] demonstrated the secure aggregation of multiple individual datasets and locally trained models. This method will enable our model to have a secure verifiable computation delegation from the aggregated locally trained models. Therefore helping the data owners to also update their locally trained models with higher accuracy improvement. In this paper, we can use this method to achieve our secured multi-party model aggregation. For circumstances where there is a high risk of collusion, numerous secure multi-party protocols can be used to an individual honest data provider even if all other data owners are malicious. The focus of this paper is not to improve or evaluate the execution of the secure multiparty computation, since our proposed algorithm is capable of been implemented using well know secured multiparty computation algorithms.

3.5.   Multi-party machine learning

We demonstrate our OP and GP methods with the theoretical analysis of DP and generalization error bound. The following ERM objective is considered:

where $\ell(\theta)$ is a convex loss function that is G-Lipschitz and L-smooth over $\theta \in \mathbb{R}^{d}$. $N(\cdot)$ is the regularization term. We consider $R(\cdot)$ to be $\lambda$-strongly convex. Individual data instance $(x_{i}; y_{i}) \in {D}$ lies in a unit ball. For an individual $j$, with dataset $D_{j}$ of size $n_{j}$, we denote its data instance as $(x_{i}^{j}, y_{i}^{j})$.

3.6.   Synthesizing coupling for Noisy Max Report

Given $\varphi = \{w_{1}, w_{2}, ..., w_{n}\}$ $\in \mathbb{R}^{n}$ and $f: \mathbb{R}^{n}\rightarrow \mathbb{R}$ as a function that implicitly depends on $\mathcal{D}$. In cases where we want to pick a point $w_{i} \in \varphi$ with highest $\ell(w_{i}, \mathcal{D})$. An algorithm $(\epsilon)$-DP called Report Noisy Max Mechanism ^[36] injects independent statistical noise from Lap$(\bigtriangleup_{1}(\ell/\epsilon))$ to each $\ell(w_{i})$, for $i \in [n]$, whiles returning the index $i$ of the maximum value i.e.,

with Lap($\lambda$) denoting a Laplace noise allocation with 0 mean and scale parameter $\lambda$; the notation $[n]$ is used to denote the set $\{1, 2, 3, ...n\}$. Although Report Noisy Max is $\epsilon$DP for arrays of any length; and it was originally considered to operate with pure $\epsilon$-DP, it has also been affected by inaccurate privacy proofs in lots of previous proposals. To prove this stronger guarantee, it is essential to apply a more sophisticated coupling strategy ^[39]. To enable ^[39] to work with $\rho$-zCDP Lemma 3 conversion result is applied. Hence the $\epsilon$-differential private protocol satisfies $\frac{\epsilon^{2}}{2}$-zCDP. Consequently, anytime we wish to use zCDP, we assign $\rho^{'}$ of the privacy budget to Coupling Strategies, we represent the Coupling Strategies by $\epsilon = \sqrt{2\rho{'}}$.

3.7.   Gradient estimation for zCDP

An algorithm for the recycling of the gradients estimates that were not useful during the parameter updates will be applied in our main protocol. At iteration $r$ we will use $\rho^{'}_{r}$-zCDP privacy budget for the estimation of the privacy budget. If $\Delta_{2}(\Delta \ell) = L_{2}$ sensitivity of the gradients of $\ell$ then, we can then measured as $G_{r} = \Delta \ell(w_{r}) + N(O, \frac{\Delta_{2}(\Delta \ell)^{2}}{2\rho_{r}})$ A larger share of privacy budget $\rho_{r+1} > \rho_{r}$ is triggered if the accuracy is not enough. Another independent measurement is initiated using $\rho_{r+1} - \rho_{r}$ privacy budget $G^{'}_{r} = \Delta \ell(w_{r}) + N(O, \frac{\Delta_{2}(\Delta \ell)^{2}}{2(\rho_{r+1} - \rho_{r})})$. Therefore $G_{r} + G^{'}_{r} = \hat{G}_{r} = \frac{\rho_{r}G_{r} + (\rho_{r+1} - \rho_{r})G^{'}_{r}}{\rho_{r} + (\rho_{r+1} - \rho_{r})}$.

We demonstrate the estimated gradient as : $E[\hat{G}_{t}] = \nabla \ell({\bf{w}}_{r})$

4.   Our proposed architecture

4.1.   Model aggregation with output perturbation:

In our proposed distributed machine learning protocol, we extend the differential privacy bound of ^[40] for the output perturbation algorithm, where adequate noise is injected to preserve the privacy of individual data owners and final output throughout the learning process. Our model aggregation with the output the perturbation model is represented in Figure 2.

Theorem 3. In our aggregated model estimator, $\hat{\theta} = \frac{1}{m} \sum_{j = 1}^{m}\hat{\theta}^{(j)}$ where $\widehat{\theta}^{(j)} =$ $\arg \min _{\theta} \frac{1}{n_{j}} \sum_{i = 1}^{n_{j}} \ell\left(\theta, x_{i}^{(j)}, y_{i}^{(j)}\right)+\lambda N(\theta)$ with an optimal model estimator $\theta^{*}$ learning from the centralized individual dataset such that the data reside in a unit ball and $\ell(\cdot)$ is $G$ -Lipschitz, we therefore obtain:

Proof. For an individual data owner $P_{j},$ the local model estimator is given as:

Therefore the centralized model estimator is stated as:

The values of $g_{1}$ and $G_{2}$ are represented as follows:

With the application of Lemma $[\mathrm{1}]$ of Chaudhuri and Monteleoni ^[40] we obtain $\|\widehat{\theta}^{(j)}-\theta^{*}\| = \frac{G}{\lambda} \sum_{l \neq j} \frac{1}{n_{l}}.$ With the application of triangle inequality, we have:

In minimizing the local objective function $R_{D}(\theta) = \frac{1}{n} \sum_{i = 1}^{n} \ell\left(\theta, x_{i}, y_{i}\right)+\lambda N(\theta)$, we obtain $\widehat{\theta}^{(j)}$ as its corresponding local model estimator.

is the perturbed aggregate model estimator; where $\eta$ is the Laplace noise injected into an aggregated model estimator to obtain DP. We, therefore, adopt K.Owusu-Agyemang et al. ^[38] secure model aggregation for our secure MPC model. The theory below administers a bound on the quantity of noise required to attain DP.

Theorem 4. If $\widehat{\theta}_{{priv }} = \frac{1}{k} \sum_{j = 1}^{k}\widehat{\theta}^{(j)}+\eta$ is the perturbed aggregate model estimator whiles $\widehat{\theta}^{(j)} = \arg \min _{\theta} \frac{1}{n_{j}} \sum_{i = 1}^{n_{j}} \ell\left(\theta, x_{i}^{(j)}, y_{i}^{(j)}\right)+\lambda P(\theta)$ with the data reside in a unit ball and $\ell(\cdot)$ is G-Lipschitz, then $\widehat{\theta}_{{priv }}$ is $\epsilon$-differentially private if : $\eta = \operatorname{Lap}\left(\frac{2 G}{k n_{(1)} \lambda \epsilon}\right)$

$n_{(1)}$ represent the volume of the minimum data set amid the $k$ data owners, regularization parameter $\lambda$ and DP budget $\epsilon$.

Proof. As there are $k$ entities representing one record of data owner $j$ altered in the neighboring datasets formally:

Provision of a bound on the excess empirical risk and true risk is similar to ^[12] and ^[13] with our bounds tighter than both of them as we demand very fewer DP noise.

Theorem 5. If a perturbed aggregated model estimator $\widehat{\theta}_{{priv}} = \frac{1}{m} \sum_{j = 1}^{m} \widehat{\theta}^{(j)}+\eta$ where $\widehat{\theta}^{(j)} = \arg \min _{\theta} \frac{1}{n_{j}} \sum_{i = 1}^{n_{j}} \ell\left(\theta, x_{i}^{(j)}, y_{i}^{(j)}\right)+\lambda N(\theta)$ and an optimum model estimator $\theta^{*}$ learning from the centralized data such that the data reside in a unit ball and $\ell(\cdot)$ is $G$ -Lipschitz and $L$ -smooth, then the bound on excess empirical risk is given as:

where $A_{1}$ is an absolute constant.

Proof. With the application of Taylor's Expansion, we therefore obtain:

where $\theta = \alpha \widehat{\theta}_{{priv}}+(1-\alpha) \theta^{*}$ for some $\alpha \in[0, 1].$ By definition, $\nabla R(\theta^{*}) = 0,$ thus we get

since $\ell(\cdot)$ is $L$ -smooth, we have $\left\|\nabla^{2} J(\theta)\right\| \leq \lambda+L,$ therefore

Theorem 6. If a perturbed aggregated model estimator $\widehat{\theta}_{{priv }} = \frac{1}{k} \sum_{j = 1}^{k}\widehat{\theta}^{(j)}+\eta$ where $\widehat{\theta}^{(j)} = \arg \min _{\theta} \frac{1}{n_{j}} \sum_{i = 1}^{n_{j}} \ell\left(\theta, x_{i}^{(j)}, y_{i}^{(j)}\right)+\lambda P(\theta)$ and an optimum model estimator $\theta ^{*}$ trained on the centralized data to this extent dataset reside in a unit ball and $\ell(\cdot)$ is G-Lipschitz and L-smooth, then the bound on excess empirical risk is grounded on probability at minimum $1-\gamma$:

where $n$ is the volume of the centralized dataset. $\widetilde{R}(\theta) = \mathbb{E}_{x, y}[\ell(\theta, x, y)]+\lambda N(\theta), A_{1}, A_{2}$ are absolute constants, and the expectation is taking relative to the noise $\eta$.

4.2.   Gradient perturbation with adaptive iteration privacy budget

We give considerable attention to a centralized private empirical risk minimization to adopt per-iteration privacy budget for $k$ entities, with individual data set $\mathcal{D}_{j}$ of volume $n_{j}$ of independent observations.

Data owners can collaboratively train a differentially private classifier by adopting the per-iteration privacy budget by the addition of noise to the aggregated gradient inside secure MPC to make individual iteration progress towards an optimal solution. It is imperative to consider that the regularization expression in Eq (4.3) has no privacy guarantee and does not have any privacy implications since it is independent of the data sets. Our adaptive iterative gradient perturbation method is represented in Figure 3.

Theorem 7. With a Distributed model estimator $\theta_{T}$ attained by minimizing ${J}_\mathcal{R}(\theta)$ followed by $T$ iterations of our gradient descent method executed collaboratively by $k$ participants individually possessing dataset $D^{j}$ of size $n_{j}$ with each data instance $\{d_{1}, d_{2}, {d}_{n}\} \in D^{j}$ reside in a unit ball and $\ell(\theta)$ is G-Lipschitz and L-smooth above $\theta \in A$. $\frac{1}{L}$ as the learning rate whiles gradients are perturbed with statistical noise using the Gaussian mechanism with variance $\sigma^2$ in $z \in \mathcal{N}(\mathcal{O}, {\sigma^2}{I})$, then $\theta_{T}$ is $(\epsilon_{tot}, \delta_{tot})$-differentially private if:

with $n_{i}$ been the least data volume amid the individual $k$ participants.

Proof. With initial gradient at step $i$

The magnitude of the Gaussian noise $\sigma^{2}$ on the highest impact an individual can exhibit on $g_{t}$ which is measured by $\Delta_{2}(g)$. To bound $\Delta_{2}(g)$ quantity, we apply the gradient clipping method of ^[41] to compute the gradient $\nabla \ell(w, x_{i}^{(j)}, y_{i}^{(j)})$ for $\{i = 1, 2..., n\}$ we clip the gradient in $L_{2}$-norm and divide it by Max(1, $\frac{\parallel \nabla \ell(w, x_{i}^{(j)}, y_{i}^{(j)})\parallel_{2}}{A_{g}}$), compute the sum and add the Gaussian noise with the variance $\frac{A_{g}^{2}}{2\rho_{gm}}$ and eventually normalize it to a unit norm. That is to ensure $L_{2}$-sensitivity of the gradient is bounded by $A_{g}$ to satisfy $\rho_{gm}$-zCDP by Lemma 2. In a secure MPC learning domain, since an algorithm cannot depend on a guarantee in expectation (i.e. $\mathrm{E}[\nabla \ell({\bf{w}}_{t}; d_{i_{t}}) | {\bf{w}}_{t}] = \nabla f({\bf{w}}_{t})$), it is important to efficiently apply per-iteration budget. We therefore deploy the privacy budget by testing if a given noisy estimate $\hat{g}_{t}$ of gradient is in a descent direction by applying a portion of the privacy budget $\rho_{nmax}$. Our algorithm then construct $\Omega = \{f({\bf{w}}_{t}-\alpha {\hat{g}}_{t}): \alpha \in \Phi\}$ where $\Omega$ represent the objective value evaluated at $\{{\bf{w}}_{t}-\alpha {\hat{g}}_{t}\}$ whiles $\Phi$ is the set of pre-defined step sizes. Then it decides which step volume yields the minimum objective value using the coupling strategy. We bound the sensitivity of $\ell$ by using the concept of gradient clipping to $f$ objective function. With a specified fixed clipping threshold $A_{b}$, we then calculate $\ell(w_{t}; x_{i}, y_{i})$, clipping the values greater than $A_{b}$ to take the summation of the clipped values.

In cases where the direction $-\hat{g}_{t}$ is considered to be in a bad direction by the coupling strategy, our proposed protocol escalates the privacy budget for the estimation of the noisy gradient $\rho_{gn}$ by a factor of $1+\gamma$ We utilize the gradient averaging method to improve the validity of the gradient by subtracting $\rho_{0}$ from $\rho_{gn}$ i.e(noisy gradient) to enable us to get the current gradient. The coupling strategy is applied to verify the new direction again. it is continuously applied until it returns a non-zero index i.e., attaining a decent direction.

Our proposed iterative gradient perturbation-based scheme is a composition of coupling Strategy $\epsilon,$ and $\frac{\epsilon^{2}}{2}$ as the basic tools to enable us to achieve diverse types of differential privacy; Gaussian mechanism on the other hand is also applied to provide zCDP. Algorithm 2 demonstrates the details of each step of our proposed gradient perturbation-based-algorithm.

Theorem 8. We apply the conversion tools provided by Lemmas 2 and 3 to enable us to compare other algorithms that use approximated ($\epsilon, \delta$). Given ($\epsilon_{T}, \delta_{T}$)-DP as the total privacy budget and with the application of Lemma 3 we achieve the subsequent inequality for $\rho$:

With the overall privacy budget $\rho$ for zCDP, our protocol vigorously calculates and subtracts the quantity of essential privacy budget whenever it requires access to the data sets throughout the run-time. This promises that the complete execution of our protocol meets $\rho$-zCDP. SGD method with continuous step sizes, in general, cannot assure the convergence to the optimal irrespective of how a strongly convex objective function can become. For this reason, the discrepancy in private gradient estimation is expected to be managed. In order to assure convergence, stochastic optimization methods basically implement the conditions $\sum_{t} \alpha_{t}^{2} < \infty$ and $\sum_{t} \alpha_{t} = \infty$ based on their step size ^[42]. This will enable the differences in the updates to diminish progressively towards the optimal. Consequently, we monitor our step sizes chosen by the coupling strategy method and adaptively manage the scope of step sizes in $\Theta$. We therefore initialize $\Theta$ with fairly spaced $n$ points ranging from 0 and $\alpha_{max}$. An update of $\alpha_{\max } = (1+\eta) \max(\alpha_{t}, \alpha_{t-1}, \dots, \alpha_{t-\tau+1})$ is performed at every iteration $\tau$; with $(\alpha_{t}$ denoting the step size chosen at iteration $t$. Our algorithm is empirically observed to adaptively alter the scope of step sizes depending on the relative position of the present iteration to the optimal. The validity of our proposed scheme basically depends on $\rho$-zCDP composition which accounts for the cost of privacy for each primitive.

Theorem 9. Algorithm 2 Meets $\rho$-zCDP and ($\epsilon_{T}, \delta_{T}$)-DP

Proof. We expect values of ($\epsilon_{T}, \delta_{T}$) where no $\rho$-zCDP privacy budget is offered to our algorithm. Line 2 is capable of imagining the correct value of $\rho$ to such a degree that $\rho$-zCDP can additionally satisfy frail ($\epsilon_{T}, \delta_{T}$). For our algorithm to achieve pure zCDP mode with the utilization of the privacy budget; Line 7 measures the noisy gradient, Line 12 performing the coupling strategy for noisy max whiles Line 18 is responsible for averaging the gradient. Furthermore, Line 3 guarantees that remaining privacy budget is always above 0 while Line 14 ensures our privacy budget is not exhausted. This is very critical to our algorithm since the weights are the output that is visible outside our proposed protocol. Our algorithm satisfies $\rho$-zCDP when all protocol operations apply the required share of the privacy budget allocated.

5.   Performance analysis

We validate the performance of the simulation for our proposed algorithm for regression and classification tasks. Based on Wang et al. ^[43] method, we perform a pre-processing of the datasets. In our classification task, we apply a regularized logistic regression classifier over three (3) real-world datasets i.e., Adult ^[44], CICIDS2018 ^[45] and CICMalDroid2020 ^[46]. Table 2 represents the features of the datasets explored in the investigation.

In this domain, we predict if the interconnection is a denial-of-service(DoS) attack or otherwise. We indiscriminately sample 70,000 individual data along with dividing amongst training dataset of 50,000 records whiles the 20,000 records are used as a test set. With ${\bf{x}}_{i} \in \mathbb{R}^{p+1}, y_{i} \in\{-1, +1\},$ and $\lambda > 0$ as the regularization coefficient. Throughout our simulations; we set coefficient $\lambda = 0.001$, learning rate $\eta = 1$, failure probability $\theta = 0.001$, $\epsilon = 0.05$ privacy budget, G-Lipschitz constant $= 1$ and entire iterations $T = 1000$ for GD. We validate our proposed output perturbation and gradient perturbation-based algorithms with other benchmarks relative to optimality and relative accuracy loss. In the case of regression, relative accuracy loss is termed as mean square error (MSE) $\theta$ and $\theta^{*}$ which is the difference in accuracy over the test data.

5.1.   Benchmark for comparison

In our proposed multi-party computation output perturbation-based model aggregation (MS-OP), we demonstrate the comparison of this model with Pathak et al. ^[12] which is represented as $PAT$, other cutting-edge differential privacy benchmarks are also achieved by the application of objective perturbation and output perturbation techniques of Wang et al. ^[43] on each of the locally trained model estimator $\widehat{\theta_{j}}$ to attain a differentially private local model estimator whiles aggregation of the classifier is computed to attain differentially private aggregated classifier $\widehat{\theta}_{{priv }}$ with confidence intervals for the parameters in the model. For our experiments on our proposed adaptive iterative gradient perturbation-based learning algorithm, we adopt a benchmark of aggregation for locally perturbed gradients ^[23] with the aim of improving the noise bound by applying zCDP and coupling strategy ^[39] also for the verification of the privacy budget. Our proposed multi-party computation output perturbation-based model aggregation and multiparty computation adaptive iterative gradient perturbation-based frameworks is represented as MS-OP and MS-GP respectively (with the application of Algorithm 2). In all our simulations there is a variation of the number of data owners $p$ from 100–1000 with up to 50,000 data owners with each of them possessing only one data instance.

Result on Adult Dataset: The Adult ^[44] data is a composition of demographic information of approximately 47,000 individuals, In this domain, our duty is to predict if annual income of data owners is exceed or below ＄50,000.00 threshold. During the pre-processing stage, we obtained 104 features for each of the records, whiles the missing values were removed therefore yielding 45,222 records with 30,000 of them now forming the training dataset whiles the rest are used for the testing of our model. In our simulation on the Adult dataset, our proposed MS-OP and MS-GP methods outperform the benchmarks both with respect to the accuracy loss and optimality gab as demonstrated in Figure 4.

Result on CICMalDroid2020 Dataset: As the amount of data owners $p$ grows and with the decrease in the size of the local data, the relative accuracy of all the models begins to decrease with the exclusion of MS-GP as represented in Figure 5. It is obvious that the performance of the benchmarks algorithms begins to depreciate basically owing to the huge volumes of statistical noise injected within the classifier. Furthermore, the performance of MS-OP also deteriorates with the reduction in the size of the local dataset owing to the loss in information from partitioning of the dataset which has been one of the challenges with the aggregation of locally trained classifiers.

Result on CICIDS2018 Dataset: With the reduction in the amount of local dataset which is as a result of the decrease in the number of data owners $p$, there is a great decrease in the performance of all the methods with the exception of MS-GP (Figure 6). Although there is a reduction in the performance of MS-OP as the size of the local dataset is reduced, it continues to outperform the benchmarks of existing model aggregation. We observed that as $p = 1000$, the performance of W-LObjP is weaker as compared to the W-LOP, this is due to the deviation in the objective function of W-LObjP ($n$). It is important to note that the utility of PAT is greatly affected as a result of the huge amount of statistical noise injected into the model, resulting in the plot been out of range for $p = 1000$ (Figure 6).

Table 3 is a summary of the amount of noise for the individual algorithms requires to preserve differential privacy. As stated in Table 3, MS-GP add the lowest amount of statistical noise to the model. Though it is obvious W-LOP injects noise in a similar range as our proposed MS-GP, it applies the statistical noise in a profoundly different approach. Whereas the existing algorithms inject the sampled statistical noise into the optimal non-private model either thorough output perturbation and gradient perturbation to minimize the objective function $J(\theta)$, whiles optimizing an exclusively different objective function $R^{\prime}(\theta) = R(\theta)+{Lap}\left(\frac{2G}{p_{1} \epsilon}\right)$, therefore explaining the increases in optimality gap as the value for the amount $p_{(1)}$ of the dataset decreases.

Variations in Parameters for the Simulation: It's important to note that all of the real-world datasets we used in the experiments have a variety of numerical and categorical characteristics. We apply some of the most common pre-processing agorithms in machine learning, such as converting all categorical features into a collection of binary variables by creating one binary variable for each individual distinct class; and re-scaling all numerical features into the range of [0, 1] to ensure that all features have the same size. To meet the specification, we normalized each observation to a unit norm $(i.e., \parallel x \parallel_2 = 1 \; {for}\; i = 1, 2, ..., p)$. To compare our approach to other standard methods on a real-world data set in order to demonstrate its efficacy.

Specifically, we also consider (regularized) logistic regression on the three(3) real world data sets. We therefore validate the minimization error $\mathbb{E} F\left(w_{privacy}, S\right)-F(\hat{w}, S)$ and running time of our algorithms based on different $\epsilon = \{0.05, 0.5, 0.1\}$ and $\delta = 0.001$ (see Table 4 for more details).

6.   Conclusions

In this work, we prove that an appreciable among of statistical noise in a distributed learning domain can be reduced when it is generated and injected into a model within a secure multi-party computation. Our paper shows how the statistical noise as a prerequisite for our distributed learning domain may be minimized by generating and injecting noise inside a secure computation. Both of our proposed multi-scheme output perturbation (MS-OP) and gradient perturbation (MS-GP) algorithms were both to achieve $\epsilon$-DP and ($\delta, \epsilon$)-differential privacy respectively. Though the aggregation of our locally trained models requires only a single secure aggregation, it still remains very efficient. Our MS-GP method has also been able to improve on the optimization algorithm in this multi-party differential privacy setting whereby the privacy budget at each iteration has been adaptively determined depending on the utility of privacy-preserving statistics. In the future, we will try and explore the potential of our framework in other domains.

Acknowledgement

This work was supported in part by the National Natural Science Foundation of China (No.61672135), the Frontier Science and Technology Innovation Projects of National Key R & D Program (No.2019QY1405), the Sichuan Science and Technology Innovation Platform and Talent Plan (No.20JCQN0256), and the fundamental Research Funds for the Central Universities (No.2672018ZYGX2018J057).

Conflict of interest

All authors declare that there is no conflicts of interest in this paper.