Approximate Kernel Selection with Strong Approximate Consistency

Lizhong Ding, Yong Liu, Shizhong Liao, Yu Li, Peng Yang, Yijie Pan, Chao Huang, Ling Shao, Xin Gao

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Kernel selection is fundamental to the generalization performance of kernel-based learning algorithms. Approximate kernel selection is an efficient kernel selection approach that exploits the convergence property of the kernel selection criteria and the computational virtue of kernel matrix approximation. The convergence property is measured by the notion of approximate consistency. For the existing Nyström approximations, whose sampling distributions are independent of the specific learning task at hand, it is difficult to establish the strong approximate consistency. They mainly focus on the quality of the low-rank matrix approximation, rather than the performance of the kernel selection criterion used in conjunction with the approximate matrix. In this paper, we propose a novel Nyström approximate kernel selection algorithm by customizing a criterion-driven adaptive sampling distribution for the Nyström approximation, which adaptively reduces the error between the approximate and accurate criteria. We theoretically derive the strong approximate consistency of the proposed Nyström approximate kernel selection algorithm. Finally, we empirically evaluate the approximate consistency of our algorithm as compared to state-of-the-art methods.
Original languageEnglish (US)
Pages (from-to)3462-3469
Number of pages8
JournalProceedings of the AAAI Conference on Artificial Intelligence
StatePublished - Sep 7 2019


Dive into the research topics of 'Approximate Kernel Selection with Strong Approximate Consistency'. Together they form a unique fingerprint.

Cite this