Block Basis Factorization for Scalable Kernel Evaluation

Ruoxi Wang, Yingzhou Li, Michael W. Mahoney, Eric DarveSIAM J. Matrix Anal. Appl 2019 · OpenReview

TL;DR

Kernel methods, while powerful, suffer from quadratic complexity that limits their scalability. This paper introduces Block Basis Factorization (BBF), a novel structured low-rank approximation method that significantly extends the applicability of efficient kernel evaluation to scenarios where traditional methods fail, particularly for datasets with complex decision boundaries and varying class properties.

What Problem Does This Paper Address?

Kernel methods, widely used in machine learning, rely on kernel matrices. However, constructing, storing, and applying these matrices typically involves quadratic complexity with respect to the number of data points. While low-rank approximations offer a solution by reducing computational and storage costs, they often struggle with accuracy when the kernel matrix doesn't exhibit a clear spectrum gap or when the optimal kernel parameters lead to higher-rank matrices. This is particularly problematic in scenarios like imbalanced datasets or when dealing with complex, non-smooth decision boundaries, where smaller kernel bandwidths (leading to higher ranks) are necessary for optimal performance. The paper aims to bridge this gap by developing a method that remains efficient and accurate even for these higher-rank kernel matrices.

Methods

The core contribution is the Block Basis Factorization (BBF), a structured low-rank approximation. Unlike traditional low-rank methods that approximate the entire matrix with two factors, BBF partitions the kernel matrix into blocks and approximates each block using a shared column basis for each row of blocks. This structure is inspired by hierarchical matrices and butterfly factorizations.

The BBF construction involves three main steps:

  1. Clustering and Permutation: The data is divided into clusters, and the kernel matrix is permuted accordingly, creating a block structure.
  2. Basis Construction: For each row of blocks, a representative column basis is computed. This is done using a novel randomized sampling procedure and a randomized SVD, aiming for accuracy and stability.
  3. Inner Matrix Construction: The interactions between these bases are then compressed into a smaller "inner matrix." This step also employs sampling-based techniques for efficiency.

The key novelty lies in how BBF leverages the structure of kernel matrices, particularly the observation that sub-matrices representing interactions within clusters are often numerically low-rank. This allows for a more efficient representation than standard low-rank approximations, especially when the overall matrix rank is higher.

Datasets

The paper evaluates its method on several real-world datasets, including:

  • Abalone
  • Mushroom
  • Cpusmall
  • Pendigits
  • Census house
  • Forest covertype

These datasets are available from the UCI repository, libsvm website, and Kaggle. The data was normalized to have zero mean and unit standard deviation for each dimension.

Key Insights and Ideas

  • Small bandwidths are crucial for complex decision boundaries: The paper strongly argues that for datasets with non-linear or complex decision boundaries (small radius of curvature), a smaller kernel bandwidth is often necessary for high accuracy. This directly leads to higher-rank kernel matrices.
  • Low-rank methods falter with higher ranks: Traditional low-rank approximations become inefficient and less accurate when the kernel matrix rank increases, which is precisely the scenario where BBF shines.
  • Structure is key: BBF exploits the inherent structure of kernel matrices, particularly the idea that interactions within localized groups (clusters) can be approximated more efficiently than global interactions.
  • Block basis is more accurate than diagonal basis: Computing column bases from entire row-submatrices (as in BBF) leads to better accuracy for off-diagonal blocks compared to using only diagonal blocks (as in some other methods).
  • Trade-off between rank and bandwidth: The paper highlights the inverse relationship between kernel bandwidth and matrix rank, and how choosing optimal bandwidths for specific classes can lead to matrices that are poorly approximated by standard low-rank methods.

Key Results

  • Superior Accuracy: BBF consistently achieves significantly lower reconstruction errors compared to state-of-the-art low-rank approximation methods (like Nyström variants, MEKA) across various datasets and memory budgets. It often outperforms even SVD-based approximations.
  • Scalability: The BBF construction algorithm achieves linear complexity (O(n)) for many machine learning kernels, making it suitable for large-scale datasets.
  • Robustness: The proposed randomized algorithm for BBF construction is shown to be stable, producing errors with smaller variance compared to other randomized methods.
  • Efficiency for Higher Ranks: BBF demonstrates its advantage particularly in the small-h regime (smaller bandwidths), where traditional low-rank methods struggle due to increased matrix rank.
  • Competitive Performance in Kernel Ridge Regression: When applied to kernel ridge regression, BBF-approximated kernels lead to competitive or superior prediction accuracy compared to other methods, especially when considering memory constraints.

Limitations and Future Work

  • Complexity Dependence on k: While BBF offers linear complexity in n (number of data points), the factorization and application costs can depend quadratically on k (number of clusters). The authors suggest that for many machine learning kernels, k is manageable, but a very large k could impact linearity.
  • Downstream Inference Efficiency: While BBF excels at approximating the kernel matrix, further work is suggested to optimize downstream inference tasks. This includes relaxing orthogonality constraints on the basis matrices and exploring interpolative decomposition.
  • Evaluation Metric: The paper primarily uses the Frobenius norm for approximation error. Future work could explore alternative metrics that better reflect downstream performance, such as those that emphasize high-rank approximations for generalization.
  • Regularization Parameter: The current BBF construction does not explicitly consider regularization parameters used in many learning algorithms. Investigating how regularization can facilitate low-rank compression within BBF is a promising future direction.

Summary updated

Abstract

Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed that for some datasets with wide intraclass variability, the optimal kernel parameter for smaller classes yields a matrix that is less well-approximated by low-rank methods. In this paper, we propose an efficient structured low-rank approximation method---the block basis factorization (BBF)---and its fast construction algorithm to approximate radial basis function kernel matrices. Our approach has linear memory cost and floating point operations for many machine learning kernels. BBF works for a wide range of kernel bandwidth parameters and extends the domain of applicability of low-rank approximation methods significantly. Our empirical results demonstrate the stability and superiority over the state-of-the-art kernel approximation algorithms.
BibTeX
@article{wang2019block,
  author = {Ruoxi Wang and Yingzhou Li and Michael W. Mahoney and Eric Darve},
  title = {{Block Basis Factorization for Scalable Kernel Evaluation}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2019},
  url = {https://openreview.net/forum?id=xI_Peug4bV},
}
Figure