Skip to Main content Skip to Navigation
Conference papers

On Fast Leverage Score Sampling and Optimal Learning

Abstract : Leverage score sampling provides an appealing way to perform approximate computations for large matrices. Indeed, it allows to derive faithful approximations with a complexity adapted to the problem at hand. Yet, performing leverage scores sampling is a challenge in its own right requiring further approximations. In this paper, we study the problem of leverage score sampling for positive definite matrices defined by a kernel. Our contribution is twofold. First we provide a novel algorithm for leverage score sampling and second, we exploit the proposed method in statistical learning by deriving a novel solver for kernel ridge regression. Our main technical contribution is showing that the proposed algorithms are currently the most efficient and accurate for these problems.
Document type :
Conference papers
Complete list of metadata
Contributor : Alessandro Rudi <>
Submitted on : Wednesday, December 19, 2018 - 9:10:12 AM
Last modification on : Thursday, July 1, 2021 - 5:58:09 PM
Long-term archiving on: : Wednesday, March 20, 2019 - 1:45:14 PM


  • HAL Id : hal-01958879, version 1
  • ARXIV : 1810.13258



Alessandro Rudi, Daniele Calandriello, Luigi Carratino, Lorenzo Rosasco. On Fast Leverage Score Sampling and Optimal Learning. NeurIPS 2018 - Thirty-second Conference on Neural Information Processing Systems, Dec 2018, Montreal, Canada. pp.5677--5687. ⟨hal-01958879⟩



Record views


Files downloads