Fast Statistical Leverage Score Approximation in Kernel Ridge Regression

Yifan Chen, Yun Yang

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

7 Citations (Scopus)

Abstract

Nyström approximation is a fast randomized method that rapidly solves kernel ridge regression (KRR) problems through subsampling the n-by-n empirical kernel matrix appearing in the objective function. However, the performance of such a sub-sampling method heavily relies on correctly estimating the statistical leverage scores for forming the sampling distribution, which can be as costly as solving the original KRR. In this work, we propose a linear time (modulo poly-log terms) algorithm to accurately approximate the statistical leverage scores in the stationary-kernel-based KRR with theoretical guarantees. Particularly, by analyzing the first-order condition of the KRR objective, we derive an analytic formula, which depends on both the input distribution and the spectral density of stationary kernels, for capturing the non-uniformity of the statistical leverage scores. Numerical experiments demonstrate that with the same prediction accuracy our method is orders of magnitude more efficient than existing methods in selecting the representative sub-samples in the Nyström approximation.

Original languageEnglish
Title of host publicationProceedings of The 24th International Conference on Artificial Intelligence and Statistics
EditorsArindam Banerjee, Kenji Fukumizu
PublisherML Research Press
Pages2935-2943
Number of pages9
Publication statusPublished - Apr 2021
Event24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021 - Virtual, Online, United States
Duration: 13 Apr 202115 Apr 2021
https://proceedings.mlr.press/v130/

Publication series

NameProceedings of Machine Learning Research
PublisherML Research Press
Volume130
ISSN (Print)2640-3498

Conference

Conference24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period13/04/2115/04/21
Internet address

Scopus Subject Areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Fast Statistical Leverage Score Approximation in Kernel Ridge Regression'. Together they form a unique fingerprint.

Cite this