Scalable Gaussian Kernel Support Vector Machines with Sublinear Training Time Complexity

Gaussian kernel Support Vector Machines (SVMs) deliver state-of-the-art generalization performance for non-linear classification, but the time complexity of their training process is at least quadratic w.r.t. the size of training set, preventing them from scaling up on large datasets. To address this issue, we propose a novel approach to large-scale kernel SVMs in sublinear time w.r.t. the size of training set, which combines three well-known and efficient techniques with theoretical guarantees. First, we subsample massive samples to reduce the sample size. Then, we use the random Fourier feature mapping on the subsamples to construct explicit random feature space where we can train a linear SVM to approximate the corresponding Gaussian kernel SVM. Finally, we use parallel algorithms to make our approach more scalable. Deriving the upper bounds of kernel matrix approximation error, hypothesis error and excess risk w.r.t. the size of training set and the dimension of random feature space, we establish the theoretical foundation of our proposed approach. In this way, we can reduce the time complexity of training kernel SVMs without sacrificing much accuracy. Our proposed approach achieves high accuracy and has sublinear training time complexity, which exhibits good scalability theoretically and empirically.