Approximate Kernel Selection with Strong Approximate Consistency

  • Lizhong Ding Inception Institute of Artificial Intelligence
  • Yong Liu Chinese Academy of Sciences
  • Shizhong Liao Tianjin University
  • Yu Li King Abdullah University of Science and Technology
  • Peng Yang King Abdullah University of Science and Technology
  • Yijie Pan Chinese Academy of Sciences
  • Chao Huang Chinese Academy of Sciences
  • Ling Shao Inception Institute of Artificial Intelligence
  • Xin Gao King Abdullah University of Science and Technology


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.

AAAI Technical Track: Machine Learning