One-shot Distributed Algorithm for Generalized Eigenvalue Problem

Kexin Lv, Fan He, Xiaolin Huang, Jie Yang, Liming Chen

TL;DR

This paper introduces a novel "one-shot" distributed algorithm for the Generalized Eigenvalue Problem (GEP), enabling efficient computation across multiple servers without iterative communication. The method addresses convergence issues in existing distributed approaches, particularly for scenarios with repeated eigenvalues, and demonstrates strong performance in applications like Canonical Correlation Analysis and Fisher's Discriminant Analysis.

What Problem Does This Paper Address?

The Generalized Eigenvalue Problem (GEP) is fundamental to many high-dimensional statistical models, including Principal Component Analysis (PCA), Canonical Correlation Analysis (CCA), and Fisher's Discriminant Analysis (FDA). However, as datasets grow and are stored across distributed servers (for memory or privacy reasons), solving GEP efficiently becomes challenging. Existing distributed methods for eigenvalue decomposition often struggle with GEP due to the divergence of empirical covariance matrices and can face convergence barriers, especially when dealing with repeated eigenvalues (a common issue in CCA and FDA). This paper aims to bridge this gap by proposing a general, efficient, and communication-light distributed GEP framework.

Methods

The core contribution is a "one-shot" distributed GEP algorithm (DGEP). Instead of iterative communication between local servers and a central server, DGEP requires only a single communication round. Local servers compute their local covariance matrices and broadcast them to a central server. The central server then aggregates these matrices to approximate the global covariance and solves the GEP using standard methods like Singular Value Decomposition (SVD) or power iteration.

For scenarios with repeated eigenvalues, which can cause convergence issues in standard power methods, the paper proposes a modified approach for distributed CCA. This involves breaking down the problem into two parts and using power iterations on each, effectively addressing the "no eigengap" problem and improving convergence. The theoretical analysis focuses on bounding the approximation error, considering the divergence of data covariance and the number of local servers.

Datasets

The paper evaluates its algorithms on:

  • Synthetic datasets: Used to demonstrate the performance of DGEP in terms of running time and error.
  • GSE2187 dataset: A real cRNA microarray dataset for binary classification (drugs vs. toxicants) used to evaluate FDA.
  • Gene expression datasets (Lymphoma and SRBCT): Real datasets used to evaluate distributed CCA for multi-classification problems.

The paper does not introduce new benchmarks but applies its methods to existing, well-known datasets.

Key Insights and Ideas

  • One-shot communication is feasible for GEP: The paper demonstrates that a single communication round between local servers and a central server is sufficient for solving GEP, significantly reducing communication overhead compared to iterative methods.
  • Addressing the "no eigengap" problem in distributed CCA: The proposed modification for distributed CCA effectively handles scenarios where the approximated covariance matrix lacks a clear eigengap, a common issue that hinders convergence in traditional power methods.
  • Approximation error is influenced by data divergence and server count: The theoretical analysis highlights that the accuracy of the distributed GEP solution is directly related to how much the local covariances diverge and the number of local servers involved.
  • GEP is a unifying framework: The paper shows how various machine learning tasks like FDA and CCA can be naturally formulated as GEP instances, allowing a single distributed algorithm to address multiple problems.

Key Results

  • Effectiveness in FDA: The DGEP-SVD and DGEP-PM algorithms achieved classification accuracies comparable to the centered SVD benchmark on the GSE2187 dataset, with only a slight decrease despite covariance divergence.
  • Performance in distributed CCA: The proposed Algorithm 2 for distributed CCA significantly outperformed DGEP-PM (a simpler distributed CCA approach) on gene datasets, especially as the number of local servers increased. For instance, on the SRBCT dataset, Algorithm 2 achieved accuracies up to 60% for training and 46% for testing, while DGEP-PM reached only 41% and 36% respectively.
  • Scalability: The running time of DGEP increases with the number of local servers (N), but the errors remain low, indicating good scalability.

Limitations and Future Work

  • Assumption of synchronous communication: The distributed systems are assumed to ignore node failure and asynchronous communication. This is a common simplification in distributed systems research but might not hold in all real-world scenarios.
  • Equal data scale assumption: The paper assumes local servers have a similar scale of data to ensure synchronous communication doesn't cause significant delays.
  • Future work: The paper suggests that the proposed algorithms sacrifice some computation efficiency for communication efficiency, implying that further research could explore trade-offs for even greater computational speed. The analysis of approximation error could also be extended.

Summary updated

Abstract

Nowadays, more and more datasets are stored in a distributed way for the sake of memory storage or data privacy. The generalized eigenvalue problem (GEP) plays a vital role in a large family of high-dimensional statistical models. However, the existing distributed method for eigenvalue decomposition cannot be applied in GEP for the divergence of the empirical covariance matrix. Here we propose a general distributed GEP framework with one-shot communication for GEP. If the symmetric data covariance has repeated eigenvalues, e.g., in canonical component analysis, we further modify the method for better convergence. The theoretical analysis on approximation error is conducted and the relation to the divergence of the data covariance, the eigenvalues of the empirical data covariance, and the number of local servers is analyzed. Numerical experiments also show the effectiveness of the proposed algorithms.
BibTeX
@inproceedings{lv2020one,
  author = {Kexin Lv and Fan He and Xiaolin Huang and Jie Yang and Liming Chen},
  title = {{One-shot Distributed Algorithm for Generalized Eigenvalue Problem}},
  booktitle = {ICCAI},
  year = {2020},
  url = {https://openreview.net/forum?id=EMJ6ereAbs4},
}
Figure