mlsanityData to 7 Oct 2026

On Fast Leverage Score Sampling and Optimal Learning

arXiv 1810.13258 ↗First posted 31 Oct 2018stat.ML cs.DS cs.LGcited by 40

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 8; 2024: 5; 2025: 7; 2026: 7.

40 papers.

Sort:

  1. 2022Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluationscited by 31
  2. 2024Provably Accurate Shapley Value Estimation via Leverage Score Samplingcited by 23
  3. 2023Estimating Koopman operators with sketching to provably learn large scale dynamical systemscited by 15
  4. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14
  5. 2025Chameleon: A Flexible Data-mixing Framework for Language Model Pretraining and Finetuningcited by 14
  6. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  7. 2021Accumulation of Sub-Sampling Matrices with Applications to Statistical Computationcited by 10
  8. 2023Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Samplingcited by 10
  9. 2023Robust, randomized preconditioning for kernel ridge regressioncited by 8
  10. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  11. 2021Mean Nystr"om Embeddings for Adaptive Compressive Learningcited by 6
  12. 2023Deep Kernel Principal Component Analysis for Multi-level Feature Learningcited by 6
28 more
  1. 2026WildCat: Near-Linear Attention in Theory and Practicecited by 6
  2. 2022Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketchescited by 5
  3. 2024Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Choleskycited by 5
  4. 2021Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learningcited by 4
  5. 2025A Scalable Nystrom-Based Kernel Two-Sample Test with Permutationscited by 4
  6. 2025Computational Efficiency under Covariate Shift in Kernel Ridge Regressioncited by 4
  7. 2024FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learningcited by 3
  8. 2026AQKA: Active Quantum Kernel Acquisition Under a Shot Budgetcited by 3
  9. 2021Leverage Score Sampling for Complete Mode Coverage in Generative Adversarial Networkscited by 2
  10. 2022On The Relative Error of Random Fourier Features for Preserving Kernel Distancecited by 2
  11. 2022Error Analysis of Tensor-Train Cross Approximationcited by 1
  12. 2023A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphscited by 1
  13. 2023SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Datacited by 1
  14. 2025Learning where to learn: Training data distribution optimization for scientific machine learningcited by 1
  15. 2025Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Methodcited by 1
  16. 2025Interpretable Self-Supervised Learning via Representer Landmarks and Nystr"om Approximationcited by 1
  17. 2021Nonparametric estimation of continuous DPPs with kernel methodscited by 0
  18. 2021Tensor Network Kalman Filtering for Large-Scale LS-SVMscited by 0
  19. 2021Markov subsampling based Huber Criterioncited by 0
  20. 2022Ridgeless Regression with Random Featurescited by 0
  21. 2023Boosting Nystr"om Methodcited by 0
  22. 2023Snacks: a fast large-scale kernel SVM solvercited by 0
  23. 2025Joker: Joint Optimization Framework for Lightweight Kernel Machinescited by 0
  24. 2026Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximationcited by 0
  25. 2026How Low Can You Go? Active Learning for Sparse Model Discovery in the Ultra-Low-Data Limitcited by 0
  26. 2026Fast Length-Squared Sampling for Positive-Semidefinite Matricescited by 0
  27. 2026Spectral Convergence of Random Feature Method in Multiple Dimensionscited by 0
  28. 2026Certified Approximation for Interpretable Representer Landmarkscited by 0