Randomized kernel selection with spectra of multilevel circulant matrices

Lizhong Ding, Shizhong Liao, Yong Liu, Peng Yang, Xin Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


Kernel selection aims at choosing an appropriate kernel function for kernel-based learning algorithms to avoid either underfitting or overfitting of the resulting hypothesis. One of the main problems faced by kernel selection is the evaluation of the goodness of a kernel, which is typically difficult and computationally expensive. In this paper, we propose a randomized kernel selection approach to evaluate and select the kernel with the spectra of the specifically designed multilevel circulant matrices (MCMs), which is statistically sound and computationally efficient. Instead of constructing the kernel matrix, we construct the randomized MCM to encode the kernel function and all data points together with labels. We build a one-to-one correspondence between all candidate kernel functions and the spectra of the randomized MCMs by Fourier transform. We prove the statistical properties of the randomized MCMs and the randomized kernel selection criteria, which theoretically qualify the utility of the randomized criteria in kernel selection. With the spectra of the randomized MCMs, we derive a series of randomized criteria to conduct kernel selection, which can be computed in log-linear time and linear space complexity by fast Fourier transform (FFT). Experimental results demonstrate that our randomized kernel selection criteria are significantly more efficient than the existing classic and widely-used criteria while preserving similar predictive performance.
Original languageEnglish (US)
Title of host publicationThe Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)
StatePublished - Feb 2018


Dive into the research topics of 'Randomized kernel selection with spectra of multilevel circulant matrices'. Together they form a unique fingerprint.

Cite this