Scalable ridge Leverage score sampling for the Nyström method - Aix-Marseille Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Scalable ridge Leverage score sampling for the Nyström method

Résumé

The Nyström method, known as an efficient technique for approximating Gram matrices, builds upon a small subset of the data called landmarks, whose choice impacts the quality of the approximated Gram matrix. Various sampling methods have been proposed in the literature to choose such a subset, among which some based on ridge Leverage scores, which come with good theoretical and practical results. Nevertheless, direct computation of ridge leverage scores has an Θ(n 3) computation cost if n is the number of data, which is prohibitive when n is large. To tackle this problem, we here propose a Θ(n) divideand-conquer (DAC) method to approximate ridge leverage scores and we provide theoretical guarantees and empirical results regarding their ability to blend with the Nyström approximation strategy. Our experimental results show that the proposed approximate leverage score sampling scheme achieves a good trade-off between predictive performance and running time. Ridge leverage scores, Nyström approximation, kernel methods.
Fichier principal
Vignette du fichier
Scalable_ridge_Leverage_score_sampling_for_the_Nyström_method_CHERFAOUI_KADRI_RALAIVOLA.pdf (619.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03597111 , version 1 (04-03-2022)

Identifiants

  • HAL Id : hal-03597111 , version 1

Citer

Farah Cherfaoui, Hachem Kadri, Liva Ralaivola. Scalable ridge Leverage score sampling for the Nyström method. ICASSP, May 2022, Singapour, Singapore. ⟨hal-03597111⟩
82 Consultations
372 Téléchargements

Partager

Gmail Facebook X LinkedIn More