Analysis of Nyström method with sequential ridge leverage score sampling

Daniele Calandriello 1 Alessandro Lazaric 1 Michal Valko 1
1 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix Kt. To avoid storing the entire matrix Kt, Nyström methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed Kt . The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, [15, 1] show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for Kt. While exact RLSs are as difficult to compute as a KRR solution, we may be able to approximate them well enough. In this paper, we study KRR problems in a sequential setting and introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates. INK-ESTIMATE maintains a small sketch of Kt, that at each step is used to compute an intermediate estimate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel matrix is sufficient. Second, the algorithm requires a fixed, small space budget to run dependent only on the effective dimension of the kernel matrix. Finally, our sketch provides strong approximation guarantees on the distance ∥Kt−Kt∥2 , and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step.
Type de document :
Communication dans un congrès
Uncertainty in Artificial Intelligence, Jun 2016, New York City, United States
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01343674
Contributeur : Michal Valko <>
Soumis le : samedi 9 juillet 2016 - 01:04:16
Dernière modification le : mercredi 25 avril 2018 - 15:42:48

Fichier

calandriello2016analysis.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01343674, version 1

Collections

Citation

Daniele Calandriello, Alessandro Lazaric, Michal Valko. Analysis of Nyström method with sequential ridge leverage score sampling. Uncertainty in Artificial Intelligence, Jun 2016, New York City, United States. 〈hal-01343674〉

Partager

Métriques

Consultations de la notice

286

Téléchargements de fichiers

131