On Fast Leverage Score Sampling and Optimal Learning - Archive ouverte HAL Access content directly
Conference Papers Year :

On Fast Leverage Score Sampling and Optimal Learning

(1, 2, 3) , (4) , (5) , (4, 5)
1
2
3
4
5

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.
Fichier principal
Vignette du fichier
BLESS_flattened.pdf (789.2 Ko) Télécharger le fichier
Vignette du fichier
imgs/cerr_vs_lambda.pdf (17.58 Ko) Télécharger le fichier
Vignette du fichier
imgs/HIGGSAUC.pdf (21.75 Ko) Télécharger le fichier
Vignette du fichier
imgs/RACCLS.pdf (39.96 Ko) Télécharger le fichier
Vignette du fichier
imgs/SUSYAUC.pdf (21.3 Ko) Télécharger le fichier
Vignette du fichier
imgs/timecomparison.pdf (19.86 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01958879 , version 1 (19-12-2018)

Identifiers

Cite

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⟩
53 View
203 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More