# One-Shot Distributed Generalized Eigenvalue Problem (DGEP): Concept, Algorithm and Experiments +
## 1 Introduction
We call this phenomenon the divergence of data covariance, which has been neglected in the previous work. Thus, although these distributed algorithms above perform well in theory and practice, they cannot be directly applied to distributed GEP. Due to the distributed data storage method, some techniques, e.g., partial differential equations, used in non-linear systems [23; 24] cannot be used in distributed GEP. In brief, there is not a general distributed algorithm for GEP formulated as in (1). To solve GEP in a distributed manner, in this paper, we propose a one-shot algorithm with high communication efficiency and bounded approximation error. To our best knowledge, it is the first sample-distributed algorithm for GEP. The key is to estimate the centered global covariance from local empirical data covariances. Generally, there are two types of distributed algorithms: multi-round communication and one-shot. Algorithms with multi-round communication are usually more accurate but suffer from the high communication cost and the privacy risk. One-shot algorithms overcome these shortcomings but require better design and approximation analysis. Thus, for the proposed algorithm, we investigate the upper bound of the approximation error, and show it is concerned with the eigenvalues of the empirical data covariance and the number of local servers. To demonstrate the effectiveness of the proposed distributed algorithm in practice, we consider Fisher's Discriminant Analysis (FDA) [25] and CCA as specific applications of GEP. Among them, distributed FDA achieves remarkable performance in the learning task of binary classification. However, CCA is more special for its symmetric self-adjoint dilation [26] of the empirical covariance matrix in the GEP form. When using the power method (PM), which is commonly used to solve GEP for computation efficiency, the iterations become inefficient due to the repeated non-zero generalized eigenvalues of the covariance matrix, namely, no eigengap (see Corollary 1 in [27]). Note that such a problem only exists in sample-distributed CCA while not in feature-distributed ones [28; 29]. To solve this problem in the sample-distributed setting, we reformulate the objective function of CCA and further propose the distributed multiple CCA algorithm for better convergence in the experiments. The main contributions of the paper are summarized as follows:  
* The first one-shot distributed algorithm is specially designed for the Generalized Eigenvalue Problem (GEP) with communication efficiency. * The efficient reformulated distributed multiple CCA algorithm is established for better convergence under the distributed GEP framework and proven necessary in some cases. * The approximation error is bounded theoretically in relation to the eigenvalues of the empirical data covariance and the number of local servers. The remainder of the paper is organized as follows. Section 2 gives a general framework of the distributed GEP algorithm in one-shot communication and its extensional applications. In Section 3, we analyze the approximation error of the proposed algorithm. Section 4 puts forward the distributed multiple CCA algorithm with the power method as one detailed application. The performance of numerical experiments is shown in Section 5. The conclusion is presented in Section 6. Based on our former conference paper, we provide thoughtful discussion about our formulation, the whole process, and extensional applications of distributed GEP in Section 2. We also complement the experiments both on synthetic and real-word datasets to illustrate the effectiveness of our proposed methods in Section 5.