Efficient Protocol for Collaborative Dictionary Learning in Decentralized Networks

1 Introduction

Since the advent of Bitcoin [Nakamoto, 2008], cryptocurrencies with decentralized architectures have been creating a lot of excitement in the information technology industry. Their design principle of decentralized, secure, and transparent transaction management is casting a new light on machine learning algorithms, especially in the field of federated learning [Yang et al., 2019]. In Bitcoin, the traditional notion of security is partly replaced with a stochastic approach in validating data consistency. Our original research motivation was if we could do something similar in the field of secure federated or collaborative learning.

Collaborative learning with IoT (Internet-of-Things) devices is one of the recent interesting applications in distributed learning. The statistical nature of IoT data is entirely different from e.g. transaction data among financial institutions. Noisy multivariate real-valued data are the primary data type. They may be too low-level to be protected with existing cryptographic technologies. Security requirements should be entirely different frommoney transfer, too. In many IoT domains, some high-level statistics such as a production yield are of more interest, rather than the exact values of individual data samples.

Figure 1 illustrates the collaborative learning environment we are interested in. In a typical setting, the S clients belong to different companies. They wish to improve their own prediction model by exploiting data owned by the other clients, but they do not want to share their own data with the rivals. One such example is collaborative anomaly detection of industrial assets owned by different companies. The goal is to learn S anomaly detection models customized to each asset based on secure collaborative efforts.

In such a scenario, secure multi-party computation via homomorphic encryption [Lindell, 2005] is typically considered as a solution candidate. However, as we will show later, for transactions involving a large amount of low-level sensor data, strictly secure homomorphic encryption methods will be too expensive and probably unnecessary [Wu, 2005]. This paper addresses such a situation. Our major technical challenges are two-fold. First, to formalize the task of distributed collaborative learning in a specific language of machine learning. Second, to develop a practical method for collaboration or consensus building that does not rely on conventional methods for Byzantine agreement [Sankar et al., 2017] and cryptographic secure multi-party computation.

The contribution of the paper is to provide a clear solution to those challenges. For the first challenge, we formalize the problem as multi-task density estimation of a mixture of the exponential family. Thanks to a specific form of the exponential family, collaborative learning is nicely separated into three steps of local updates, consensus, and optimization. For the second challenge, we will show that an efficient dynamic consensus algorithm, whose original idea was first proposed in the field of multi-agent research [Olfati-Saber et al., 2007], works well. Leveraging useful properties of a particular type of graphs, which are often used to build a robust network of communication [Feldman et al., 1988], we also provide a theoretical guarantee on the efficiency of the proposed consensus algorithm for the first time in the context of collaborative learning.

2 RelatedWork

From a machine learning perspective, related work relevant to the present paper can be categorized into three groups: Multi-task density estimation in general, privacy-preserving distributed learning, and consensus building in decentralized environments.

First, regarding multi-task density estimation on multivariate real-valued data, Chiquet et al. [2011] and Honorio et al. [2010] proposed a multi-task density estimation of sparse Gaussian, which is in the exponential family. Another work [Id´e et al., 2017] extends those models to mixtures. However, they lack the context of privacy preservation. In the context of applications of Blockchain, the concept of separation of local and global variables has been proposed for a micropower grid optimization [M¨unsing et al., 2017], but it is not applicable to density estimation. Xie et al. [2017] discuss differential privacy in multi-task learning under the distributed setting, but they did not discuss secure consensus building.

Second, regarding privacy-preserving distributed learning, major research topics include the use of homomorphic encryption (HE) and secret sharing [Danezis et al., 2013; Mahimkar and Rappaport, 2004]. One recent popular approach to multi-task and transfer learning is to reuse network weights over deep neural networks (DNNs) and incorporate a privacy-preservation mechanism in stochastic gradient via HE [Bonawitz et al., 2017] and secret sharing [Mohassel and Zhang, 2017]. However, most of them assume the availability of the central coordinator.

Third, regarding consensus building in decentralized environments, much work has been done in the context of the Byzantine generals problem [Sankar et al., 2017; Cachin and Vukoli´c, 2017]. However, most of them focus on relatively simple decision-making on categorical data such as "attack or retreat," and how they can be generalized to noisy realvalued data is not necessarily clear. On the other hand, in the field of multi-agent research, dynamic distributed consensus has been one of the popular research topics [Ren et al., 2005; Olfati-Saber et al., 2007]. Although most of them do not pay attention to privacy preservation, recently, Ruan et al. [2017; 2019] proposed an interesting framework that incorporates the idea of dynamic multi-agent coordination into pairwise HE. To the best of our knowledge, their work is the only method applicable to the task of fully decentralized secure collaborative dictionary learning. Unfortunately, however, their protocols suffer from the high computational cost of HE. The use of other multi-party computation algorithms such as the Shamir scheme is another option, but Goryczka et al. [2013] pointed out that it can be even slower than HE-based methods as the network size grows.

To summarize, although much work has been done for privacy-preserving federated/distributed learning, most of them either assume the existence of the central coordinator or suffer from high computational costs. In contrast to the existing work, the advantages of the proposed method are summarized as:

• Principled. Algorithms are derived as a natural consequence of the maximum likelihood.
• Guaranteed. Convergence in consensus and data privacy are guaranteed.
• Fast. Several orders of magnitude faster than the HEbased alternative.

3 Problem Setting

This section summarizes the problem setting of collaborative dictionary learning.

3.1 Collaborative Dictionary Learning

The goal of collaborative dictionary learning is to learn the probability density function (p.d.f.) of real-valued noisy multivariate data under a multi-task learning setting. As shown in Fig. 1, there are S client nodes or the clients in the network. The clients s = 1, . . . , S privately have their own data

where N s is the number of samples of the s-th client, and M is the dimensionality of data, which is assumed to be common across all the clients. Each of the client has a unique partner called the consensus node. The consensus nodes receive intermediate statistics from their partner client, and somehow communicate with the other consensus nodes to update the model at hand.

In the network, we assume that there is no central coordinator who can see the raw data Ds , but we assume that the network router does basic bookkeeping jobs such as the management of communication paths and clock synchronization, as is the case in Bitcoin.

The S client-consensus node pairs collaboratively learn the p.d.f. in the form of mixture model:

where Θ ≡ {θ1, . . . , θK} is the set of model parameters, K is the number of mixture components, f(xs | θk) is the density function specified later, and πs is the mixture weight of the s-th client with ∑Kk=1 πsk = 1. The model parameters Θ are shared by the S clients while the mixture weights are specific to each client. Since our goal is to learn S density functions p1 , . . . , pS , this is a multi-task density estimation problem. Since k distinguishes distinctive patterns, we may call Θ the dictionary and each θk can be called a word.

3.2 Privacy Requirements

In the typical setting, the client-consensus node pairs belong to different companies or organizations competing with each other. They are in a "permissioned" network [Ahram et al., 2017], where the identity of the clients and consensus nodes has been verified and is known to all the network participants.

In permissioned networks, the clients are naturally assumed to be honest but curious. They are honest because sending falsified information will cause degradation of the model learned. Unless their goal is to destroy everything, they will not be able to benefit from such malicious acts. Also, the clients are curious; they want to exploit information from the other clients, because, in general, the more data are available for training, the better accuracy the model will get. This is especially true in anomaly detection, which is a major application of density estimation because the number of anomalous samples is generally very limited.

Under these assumptions, there are two major privacy concerns in collaborative dictionary learning. One is what we call the internal privacy, which is privacy preservation among the S client nodes, addressing the question of how those selfish clients can collaboratively build the model while keeping data privacy. The other is what we call the external privacy, which addresses privacy concerns when sharing a learned dictionary with a third-party.

The priorities of those privacies depend on applications. In this particular work, we focus on the internal privacy. We assume that Ds has many samples N s ≫ 1 whose values have been affected by some observation noise. Parameters learned Θ will be a function of the original samples. There might be a nonzero possibility of getting reverse-engineered the raw samples fromΘ, but the risk should be relatively low because the observation noise works as a privacy-preservation mechanism.

To summarize, our goal is to learn the dictionary words Θ = {θ1, . . . , θK} and the client-specific mixture weights Π ≡ {π1 , . . . , πS } through collaboration in the decentralized environment (i.e. no trusted central coordinator) while preserving data privacy among the S clients.

4 General Framework of Collaborative Dictionary Learning

This section presents the framework for collaborative dictionary learning for the exponential family.

4.1 Expectation-Maximization Framework

As usual, we introduce a latent indicator variable zs ∈ {0, 1}K , where ∑Kk=1 zsk = 1, to represent the mixture model:

where Cat stands for the categorical distribution. In general, when point-estimating {θk}, {πs }, we use the prior distribution on Θ as p(Θ) = ∏Kk=1 p(θk) and on Π as p(Π) = ∏Ss=1 p(πs ) and follow the MAP (maximum a posteriori) framework.

The model parameters are determined by maximizing the log likelihood function:

where Z is the collective notation of {zs(n) }. Since directly optimizing L0 is intractable because of the marginalization over Z, we instead maximize the lower bound L via Jensen's inequality:

where c. is an unimportant constant and Q(Z) is given by

where

Obviously, Q(Z) includes unknown parameters. Thus the learning process has to be iterative. First, {rs(n) } are initialized. Given Q(Z), the model parameters Π,Θ are determined by maximizing L. Then, Q(Z) is re-evaluated to move on to the next maximization. This is nothing but the standard expectation-maximization (EM) procedure.

If we use the Dirichlet distribution p(πs ) ∝ (πs 1 · · · πsK )γ for p(Π), where γ is a given constant (∼ 1), by differentiating L with respect to πsk , we can easily see

where N s k ≡ ∑N s n=1 rs(n) k .

4.2 Learning with Exponential Family

To point-estimate {θk}, we need to give a specific form to the density. Now, let us see what happens if we use the exponential family for the density:

where ⊤ is the vector (or matrix) transpose, H(·),G(·) are a scalar function, and η(·), T (·) are a (column) vector function satisfying required mathematical properties as a p.d.f.

With this expression, the lower bound L (Eq. (6)) becomes

Algorithm 1 Collaborative dictionary learning

• 1: Initialize dictionary {θk}Kk=1
• 2: Initialize {rs(n) k } in each client
• 3: repeat
• 4: LocalUpdates: Compute {rs(1) , . . . , rs(N s ) }, {T s 1 , . . . , T sK }, and {N s 1 , . . . ,N sK } in each client s, using the current dictionary.
• 5: Consensus: Securely compute Eq. (12).
• 6: Optimization: Solve Eq. (13) to update the dictionary.
• 7: until convergence

where T s k ≡ ∑N s n=1 rs(n) k T(xs(n) ). Here we have dropped all the terms independent of Θ. Thanks to the log-linear form of the exponential family, once we compute

the dictionary words {θk} can be found by maximizing Eq. (11) without any communication among the clients:

This means that the whole EM learning algorithm can be completely separated into three steps: LocalUpdates, Consensus, and Optimization, as sketched in Algorithm 1. As shown, only the consensus step involves communication among the consensus nodes. 1 . Note that the consensus has to be built every EM iteration. The use of expensive homomorphic encryption is obviously not an ideal solution (see Sec. 6.3). The next section looks at how to efficiently but securely build consensus.

5 Consensus Building with Privacy

Now we consider how to compute the summations of Eq. (12). Since the summations can be performed elementwise, without loss of generality, we consider the problem of computing the sum of scalars {ξ s } in this section:

where ξ s 's are constants to be summed, 1S ∈ RS is the vector whose elements are all one, and we defined ξ s (0) = ξ s . At a high level, our strategy is twofold. One is to limit the number of nodes each consensus node is allowed to communicate. The other is to introduce randomness to obfuscate local data.

5.1 Dynamic Consensus

Assume that the consensus nodes have been indexed with consecutive integers 1, . . . , S by the network router. Let A ∈ {0, 1}S×S be the incidence matrix of a graph whose nodes are the consensus nodes and edges represent a bilateral communication channel between the nodes. See Fig. 1 for an example, where a cycle graph of S = 6 is illustrated.

1 It can be performed also after the step of Optimization to guarantee the uniqueness of Θ.

Given the incidence matrix, each consensus node s can communicate only with the connected nodes. At each s, consider the following updates:

where t is the number of update rounds, and ϵ is a given parameter controlling convergence. All the S nodes perform this update locally. In the matrix form, Eq. (15) is written as

where IS is the S-dimensional identity matrix, D is the degree matrix of A, and ξ(t) ≡ (ξ 1 (t), . . . , ξ S (t))⊤.

The nature of a stationary solution is governed by the eigenvalues of Wϵ and thus the spectrum of A. As can be easily verified, u1 = 1 √S 1S is an ℓ2-normalized eigenvector of Wϵ whose eigenvalue is λ1 = 1. If this is non-degenerated and the absolute value of the other eigenvalues is less than one, Eq. (16) will converges to the stationary solution ξ∗

because only the largest eigenvalue survives in the spectral expansion after an infinite number of transitions [Strang, 1976]. This means that all of the consensus nodes have the same value of ¯ ξS upon convergence, achieving consensus.

5.2 RandomChunking Algorithm

One obvious issue of the update equation (15) is that the consensus nodes have to share the local value ξ s with the connected neighbors. However, we can easily fix this issue by using a simple secret sharing scheme by splitting the local statistic ξ s into a few chunks {ξ s[h] } such that ∑h ξ s[h] = ξ s . Since the summation is a linear operation, ¯ ξ = ¯ ξ [1] + · · · + ¯ ξ [Nc] obviously holds, where ¯ ξ [h] ≡ ∑Ss=1 ξ s[h] .

In this algorithm, if all the Nc chunks from one node happen to go to the same node, the recipient node can reproduce the raw data. This can be prevented by having the network router randomly choose an A from a pool of incidence matrices A that is non-overlapping (i.e. any pair of the matrices do not share the same edge). Hence we conclude:

Proposition 1. In Algorithm 2, Nc = 2 suffices to secure privacy if the set A is non-overlapping and the router always chooses an A ∈ A that is different from the previous chunking round.

What if we cannot generate multiple A's that are nonoverlapping, which happens when A is dense, or, the router cannot keep the memory of a previously used A? Fortunately, even in that case, one can show that the probability of privacy breach pb is upper bounded as

where dmax is the maximum degree. As long as A is sparse and thus dmax ≪ S, we can make pb arbitrarily small by

Algorithm 2 Dynamic consensus with random chunking

• 1: Input: ϵ, Nc. Graph pool A.
• 2: Initialize ¯ ξ = 0.
• 3: Each consensus node splits ξ s into Nc chunks.
• 4: for ic ← 1, . . . ,Nc do
• 5: Randomly draw an A fromA.
• 6: repeat
• 7: Perform update (15) in each s.
• 8: until convergence
• 9: ¯ ξ ← ¯ ξ + ¯ ξ [ic]
• 10: end for

choosing a sufficiently large Nc. A proof of Eq. (18) and detailed mathematical discussions are left to another paper due to page limitation.

5.3 Cycle Graphs

As a concrete example of sparse graphs, consider the S-node cycle graph of order b, which is a regular graph with the degree of d = 2b and will be symbolically denoted by CbS hereafter. See Fig. 2 for some examples. The cycle graphs are preferable in our context because of its sparseness (for better privacy) and symmetry (for better democracy).

To study convergence behaviors in Eq. (17), we introduce the set of orthonormal bases e1, . . . , eS in the S-dimensional Euclidean space such that A = ∑i,j Ai,jeie⊤j . In this representation, the incidence matrix of CbS is given by

for S ≥ 2b + 1 under the periodic boundary condition (e.g. j = 0 and S + 1 correspond to S and 1, respectively, etc.). Now it is straightforward to verify that

is the eigenvector of A, where i is the imaginary unit. From this, we see that the largest eigenvalue of Wϵ is ν1 = 1 with u1 = 1 √S 1S. The second largest eigenvalue is given by

For 0 < ϵ < 1/(2d), this is the second absolute largest, too.

This analytic representation allows a convergence analysis in the limit of S → ∞. The convergence is governed by ν2/ν1. Since 1- cos 2πj S ≈ 1 2 ( 2πj S )2 in this limit, we have

Therefore, in order for (ν2/ν1)t to be a small positive value, say, δ/√S, the number of iteration t should satisfy 2

2 The factor of 1/√S comes from the prefactor of Eq. (17).

To summarize, we have proved the following proposition:

Proposition 2. For the cycle graph of order b, the update equation (15) achieves an aggregation consensus at the unique stationary point. The number of iterations t to achieve a value of error δ/√S is given by t ∼ O ( S2 ln(√S/δ) ϵb3 ).

In words, the number of iterations required for convergence is of the order of S2 . This result is specific to the cycle graph. Then, can we improve the convergence rate by choosing another graph? The next section provides the answer.

5.4 Modified Cycle Graph

The other sparse graph we consider is a modified version of cycle graph called the cycle with inverse chords [Vadhan and others, 2012], which is C1S with an extra edge from each node s to a node j by the rule (s - 1)(j - 1) = 1 mod S. Let λi be the i-th largest eigenvalue of A. For the cycle with chords, it is known that λ1 -λ2 > 0 is lower-bounded by a constant, say λ. In our context, this means that the ratio ν2/ν1 is also lower-bounded by 1 - λ/ϵ. Following the same reasoning of the previous subsection, we have:

Proposition 3. For the cycle with inverse chords, the number of iterations t to achieve a value of error δ/√S is given by t ∼ O ( ln(√S/δ) | ln(1-λ/ϵ)| ).

Notice the difference from Proposition 2. Here t depends on S only through lnS. In other words, no matter how large the number of clients is, the number of iterations to converge is almost constant. The next section confirms this remarkable property through numerical experiments.

6 Experiments

This section presents experimental results on the proposed dictionary learning protocol. The goal of this section is (1) to illustrate how the multi-task dictionary learning framework works, (2) to provide a qualitative picture of convergence properties, especially faster convergence of the modified cycle graph, and (3) to show computational efficiency of the proposed consensus algorithm.

6.1 LearningMulti-Modal Patterns

To illustrate how the proposed multi-task learning framework can capture multi-modal patterns, we ran the proposed algorithm on a synthetic data set. For the density model, we used Gaussian with M = 4. The samples were generated from distinctive three Gaussians as illustrated in Fig. 3. In practice, determining K can be a major issue. We initialized the model with K = 6, which is larger than the ground truth, and observed if the algorithm can correctly capture the three modes. The results are shown in the figure, where the ground truth is successfully recovered. As is well-known [Corduneanu and Bishop, 2001], by setting γ = 0, the mixture model can automatically identify the major components, unless initialization used is too pathological. However, it is recommended to use a finite γ for better generalizability if a reasonable estimate for initialization is not available.

6.2 Convergence in Consensus Building

To confirm Propositions 2 and 3, we computed the number of iterations t to achieve (ν2/ν1)t = 1 √S 10-3 in Fig. 4. We used ϵ = 1/dmax, where dmax is the maximum node degree. For the cycle graphs on the left, we see that the dependency on S follows a parabolic trend, which is consistent with Eq. (23). On the other hand, for the cycle with chords, t is much smaller than that of the cycle graphs and grows very slowly with S, which is also consistent with Proposition 3.

Another observation that looks interesting is that the curve fluctuates a lot in the latter. In the original construction, the cycle with chords is defined only for primes. We extended the construction for non-primes by mechanically applying the mathematical definitions. The fluctuation is partly due to this extension. However, we observed much fluctuation even for primes. This implies that the cycle with chords intrinsically bears some randomness. Further analyzing this point would be an interesting future research topic.

6.3 Computational Efficiency

Finally, we compared the proposed consensus algorithm with the state-of-the-art multi-party algorithm proposed by Ruan et al. [Ruan et al., 2017], which shares the same graph-based dynamic consensus scheme but uses pairwise secure computation through additive homomorphic encryption. The cycle graph with b = 2 was used for both and ξ s 's were initialized by the uniform distribution in [-10, 10]. In each of the different choices of S, convergence was declared when the rootmean-squared error (RMSE) per node is below 0.01. Since we set Nc = 5, the number of total iterations is about five times larger in the proposed model. For homomorphic encryption, we used homomorpheR [Narasimhan, 2019] that implements the Paillier cryptosystem, which enables the addition of numbers without decryption.

Figure 5 compares the two approaches. In spite of about five times more iterations, our method is several orders of magnitude faster than the encryption-based method. The major bottleneck is at the step of the key pair generation, which was made at every iteration. We could improve computation time by e.g. recycling the keys, but the computational overhead is so large that our proposed solution seems to be virtually only the practical solution for our problem.

7 Concluding Remarks

We have proposed a new framework of secure collaborative learning in a decentralized environment. First, by formalizing the task as multi-task density estimation of a mixture of the exponential family, we showed that collaborative learning among competing clients can be nicely separated three steps: LocalUpdates, Consensus, and Optimization. Second, for the Consensus step, which is most critical for privacy preservation, we proposed an efficient consensus algorithm which is several orders of magnitude faster than encryption-based alternatives while keeping a certain level of security. Our analysis showed that the number of iterations required for consensus is just the logarithm of the network size.

Acknowledgments

T. I. thanks Dr. Sachiko Yoshihama for helpful comments.