Scaling up Kernel SVM on Limited Resources: A Low-rank Linearization Approach

Kai Zhang, Liang Lan, Zhuang Wang, Fabian MoerchenAISTATS 2012 · OpenReview

Abstract

Kernel Support Vector Machine (SVM) delivers state-of-the-art results in non-linear classification, but the need to maintain a large number of support vectors poses a challenge in large-scale training and testing. In contrast, linear SVM is much more scalable even on limited computing resources, but the learned model cannot capture non-linear concepts. To scale up kernel SVM on limited resources, we propose a low-rank linearization approach that transforms a non-linear SVM to a linear one via a novel, approximate empirical kernel map computed from efficient low-rank approximation of kernel matrices. We call it LLSVM (Low-rank Linearized SVM). Our algorithm inherits the high efficiency of linear SVMs and the rich representability of kernel classifiers. Evaluation against large-scale linear and kernel SVMs on several truly large datasets shows that the proposed method achieves a better tradeoff between scalability and model representability.

The Scalability Bottleneck in Kernel SVMs

Kernel SVMs are powerful tools for non-linear classification, yet they suffer from the "curse of kernelization." While linear SVMs can scale to millions of data points using modern solvers, they often fail to capture complex, non-linear patterns. Kernel methods address this by mapping data into high-dimensional spaces, but this requires computing and storing an $n \times n$ kernel matrix. As datasets grow, the number of support vectors typically increases, leading to significant computational and memory overhead. For instance, training a standard kernel SVM on millions of samples can take days even on high-performance clusters, making it impractical for users with limited resources like standard desktop PCs.

Methodology: Low-rank Linearized SVM (LLSVM)

The LLSVM approach bridges the gap between non-linear representability and linear scalability through a two-step transformation:

  1. Low-Rank Linearization: The authors demonstrate that a kernel SVM can be mathematically reformulated as a linear SVM by decomposing the kernel matrix. Since exact decomposition is computationally prohibitive ($O(n^3)$), LLSVM utilizes the Nyström method. It selects a small set of $k$ "landmark" points—optimized via fast k-means clustering—to generate an approximate, low-dimensional empirical kernel map. This projects the data into a $k$-dimensional linear space where $k \ll n$.
  2. Fast Linear Optimization: With the data explicitly mapped, the problem is solved using Selective Block Minimization (SBM), a state-of-the-art linear SVM solver designed for out-of-core learning, allowing it to handle datasets larger than the available RAM.
Figure 1: Trade-off between error rate and time consumption as the number of landmark points varies across different datasets.

Experimental Results

The LLSVM algorithm was evaluated on several large-scale datasets, including IJCNN, webspam, covType, and Ncheckerboard. The results highlight a superior balance between efficiency and accuracy:

  • Massive Scalability: On the 8-million sample mnist8m-b dataset, standard kernel solvers failed to complete within 24 hours. LLSVM successfully trained in 22 hours with a 2.59% error rate on a standard PC. On the noisy Ncheckerboard (800k samples), LLSVM achieved a 0.59% error rate in just 429 seconds.
  • Improved Accuracy over Linear Models: LLSVM significantly outperformed linear SVMs where non-linearity is crucial. For the covType dataset, the error rate dropped from 23.75% (linear SVM) to 14.95% (LLSVM).
  • Efficient Inference: By reducing the model to a linear form based on $k$ landmark points, LLSVM offers drastically faster prediction times compared to traditional kernel SVMs that rely on a large number of support vectors.

Conclusion

LLSVM provides a practical framework for training high-performance non-linear classifiers on large datasets using modest hardware. By shifting the computational burden from the SVM optimizer to an efficient matrix approximation step, it enables the use of kernel methods in scenarios previously reserved for linear models. Future work includes exploring parallelization and extending the linearization framework to semi-supervised learning and metric learning tasks.

Summary updated

Abstract

Kernel Support Vector Machine delivers state-of-the-art results in non-linear classification, but the need to maintain a large number of support vectors poses a challenge in large scale training and testing. In contrast, linear SVM is much more scalable even on limited computing recourses (e.g. daily life PCs), but the learned model cannot capture non-linear concepts. To scale up kernel SVM on limited resources, we propose a low-rank linearization approach that transforms a non-linear SVM to a linear one via a novel, approximate empirical kernel map computed from efficient low-rank approximation of kernel matrices. We call it LLSVM (Low-rank Linearized SVM). We theoretically study the gap between the solutions of the optimal and approximate kernel map, which is used in turn to provide important guidance on the sampling based kernel approximations. Our algorithm inherits high efficiency of linear SVMs and rich repesentability of kernel classifiers. Evaluation against large-scale linear and kernel SVMs on several truly large data sets shows that the proposed method achieves a better tradeoff between scalability and model representability.
BibTeX
@inproceedings{zhang2012scaling,
  author = {Kai Zhang and Liang Lan and Zhuang Wang and Fabian Moerchen},
  title = {{Scaling up Kernel SVM on Limited Resources: A Low-rank Linearization Approach}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=jttjjKyEpY},
}
Figure