INV-ASKIT: A Parallel Fast Direct Solver for Kernel Matrices

Chenhan D. Yu, William B. March, Bo Xiao, George Biros

TL;DR

This paper introduces INV-ASKIT, a novel parallel algorithm for efficiently factoring and inverting large kernel matrices, which are common in machine learning and scientific computing. By leveraging a hierarchical approximation technique, INV-ASKIT achieves significant speedups, enabling the solution of linear systems with these matrices in near-linear time, even for datasets with millions of points and high dimensionality.

What Problem Does This Paper Address?

Kernel matrices, which represent pairwise interactions between data points, are fundamental to many machine learning algorithms (like Support Vector Machines and Gaussian Processes) and scientific simulations. However, these matrices are typically dense and ill-conditioned, making standard operations like matrix inversion computationally prohibitive, often scaling as O(N³) or requiring many iterations with iterative solvers. This severely limits their application to large-scale problems. While fast methods exist for low-dimensional data, high-dimensional datasets remain a significant challenge. This paper tackles this by developing a parallel algorithm that can efficiently handle these large, high-dimensional kernel matrices.

Methods

The core of INV-ASKIT builds upon a previous method called ASKIT, which approximates a kernel matrix K as a sum of a block-diagonal matrix (D) and a low-rank matrix (UV). INV-ASKIT extends this by developing a fast direct solver for the inverse of (λI + K), where λ is a regularization parameter and I is the identity matrix. The method employs a hierarchical decomposition of the kernel matrix, recursively partitioning it into smaller blocks. The inverse is then computed using the Sherman-Morrison-Woodbury (SMW) formula, applied recursively to the hierarchical structure.

Key aspects of the method include:

  • Hierarchical Decomposition: The kernel matrix is recursively broken down based on a binary tree structure of the data points.
  • Low-Rank Approximation: Off-diagonal blocks of the kernel matrix are approximated by low-rank matrices, which is the key to achieving efficiency.
  • Sherman-Morrison-Woodbury (SMW) Formula: This formula is used to efficiently compute the inverse of a matrix that has been modified by a low-rank update.
  • Parallelism: The algorithm is designed for both shared and distributed memory parallelism, allowing it to scale to large numbers of cores.
  • Adaptive Skeletonization: The ASKIT method uses an adaptive approach to select "skeleton" points for the low-rank approximation, which helps in controlling accuracy.

Datasets

The paper evaluates INV-ASKIT on several real-world and synthetic datasets:

  • COVTYPE: A dataset with 0.5 million points in 54 dimensions.
  • SUSY: A dataset with 4.5 million points in 8 dimensions.
  • MNIST: A dataset with 2 million points in 784 dimensions.
  • NORMAL: A synthetic dataset generated from a 6D normal distribution embedded in 64 dimensions, used for weak scaling experiments.
  • NORMAL (16M): A larger synthetic dataset used for strong scaling experiments.

The authors also mention using a polynomial kernel in addition to the Gaussian kernel.

Key Insights and Ideas

  • Bridging the Gap for High Dimensions: The paper demonstrates that hierarchical methods like ASKIT, when combined with efficient inversion techniques like INV-ASKIT, can effectively handle kernel matrices in high-dimensional spaces, a significant challenge for many existing methods.
  • Scalability is Achievable: The authors show that INV-ASKIT can scale to very large problem sizes (up to 32M x 32M matrices) and a large number of cores (4,096), achieving impressive parallel efficiency.
  • Near-Linear Time Solvers: The core contribution is achieving O(N log N) work for solving linear systems with kernel matrices, a dramatic improvement over the O(N²) or O(N³) complexity of naive methods.
  • Flexibility with Kernels: The method is not restricted to symmetric kernels and can handle variable bandwidths, making it applicable to a wider range of problems.
  • Preconditioning Power: INV-ASKIT can serve as a powerful preconditioner for iterative solvers like GMRES, significantly speeding up convergence for classification tasks.

Key Results

  • Factorization Complexity: Sequential factorization takes O(N log² N) work, and parallel factorization achieves near-linear scalability.
  • Solving Complexity: Solving linear systems takes O(N log N) work.
  • Large-Scale Performance: The largest run involved approximately factorizing a 32M x 32M matrix on 4,096 cores.
  • Accuracy: The method achieves competitive classification accuracy on real-world datasets, often reaching 96-100% for training and testing.
  • Speedup: INV-ASKIT as a preconditioner can speed up convergence of GMRES by 2x to 5x for classification tasks.
  • Parallel Efficiency: The method achieves up to 52% of peak FLOPS efficiency on large-scale experiments.

Limitations and Future Work

  • Numerical Stability: The paper acknowledges that a theoretical analysis of numerical stability is not provided, though it is noted as being relatively easy to prove for symmetric positive-definite matrices.
  • Symmetries Not Exploited: Certain symmetries of the kernel matrix (e.g., symmetry) are not explicitly exploited, which could further reduce factorization time.
  • Parameter Tuning: The authors did not extensively tune various algorithm parameters.
  • Amortizing Factorization Cost: Optimizations for amortizing factorization cost over different values of λ are not discussed.
  • ASKIT Limitations: Fundamental limitations inherited from ASKIT remain, such as the requirement for off-diagonal blocks to admit low-rank approximations. Kernels that are highly oscillatory or lead to large norms in the sparse correction might not work well.
  • Future Work: The authors plan to focus on further optimization, including dynamic scheduling to address parallelism shrinking, exploring lower-cost factorization variants, extending to GPU architectures, and integrating with higher-level algorithms like support vector machines.

Summary updated

Abstract

We present a parallel algorithm for computing the approximate factorization of an N-by-N kernel matrix. Once this factorization has been constructed (with N log2 N work), we can solve linear systems with this matrix with N log N work. Kernel matrices represent pairwise interactions of points in metric spaces. They appear in machine learning, approximation theory, and computational physics. Kernel matrices are typically dense (matrix multiplication scales quadratically with N) and ill-conditioned (solves can require100s of Krylov iterations). Thus, fast algorithms for matrix multiplication and factorization are critical for scalability. Recently we introduced ASKIT, a new method, which resembles N-body methods, for approximating a kernel matrix. Here we introduce INV-IASKIT, a factorization scheme based on ASKIT. We describe the new method, derive complexity estimates, and conduct an empirical study of its accuracy and scalability. We report results on real-world datasets including "COVTYPE" (0.5M points in 54dimensions), "SUSY" (4.5M points in 8 dimensions) and "MNIST"(2M points in 784 dimensions) using shared and distributed memory parallelism. In our largest run we approximately factorize a dense matrix of size 32M × 32M (generated from points in 64 dimensions) on 4,096 Sandy-Bridge cores. To our knowledge these results improve the state of the art by several orders of magnitude.
BibTeX
@misc{yu2016inv,
  author = {Chenhan D. Yu and William B. March and Bo Xiao and George Biros},
  title = {{INV-ASKIT: A Parallel Fast Direct Solver for Kernel Matrices}},
  year = {2016},
  eprint = {1602.01376},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.01376},
}
Figure