mlsanityData to 14 Oct 2026

FALKON: An Optimal Large Scale Kernel Method

arXiv 1705.10958 ↗First posted 31 May 2017stat.ML cs.LGcited by 84

Not on the map. Why?

Abstract (arXiv)

Kernel methods provide a principled way to perform non linear, nonparametric learning. They rely on solid functional analytic foundations and enjoy optimal statistical properties. However, at least in their basic form, they have limited applicability in large scale scenarios because of stringent computational requirements in terms of time and especially memory. In this paper, we take a substantial step in scaling up kernel methods, proposing FALKON, a novel algorithm that allows to efficiently process millions of points. FALKON is derived combining several algorithmic principles, namely stochastic subsampling, iterative solvers and preconditioning. Our theoretical analysis shows that optimal statistical accuracy is achieved requiring essentially O(n) memory and O(n√n) time. An extensive experimental analysis on large scale datasets shows that, even with a single machine, FALKON outperforms previous state of the art solutions, which exploit parallel/distributed architectures.

Key facts. Cited by 84 papers in the map (data through 14 Oct 2026). First posted on arXiv 31 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 18; 2022: 18; 2023: 13; 2024: 16; 2025: 10; 2026: 9.

84 papers.

Sort:

  1. 2024Challenges in Training PINNs: A Loss Landscape Perspectivecited by 113
  2. 2021Neural Fields as Learnable Kernels for 3D Reconstructioncited by 58
  3. 2022Unbalanced Optimal Transport, from Theory to Numericscited by 46
  4. 2021Conditional Distributional Treatment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regressioncited by 40
  5. 2022Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluationscited by 32
  6. 2022A Fast, Well-Founded Approximation to the Empirical Neural Tangent Kernelcited by 30
  7. 2022Making Look-Ahead Active Learning Strategies Feasible with Neural Tangent Kernelscited by 25
  8. 2021An Extensible Benchmark Suite for Learning to Simulate Physical Systemscited by 24
  9. 2021A Witness Two-Sample Testcited by 23
  10. 2021Interpolating Classifiers Make Few Mistakescited by 22
  11. 2022Learning new physics efficiently with nonparametric methodscited by 21
  12. 2021Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processescited by 17
38 more
  1. 2023Stochastic Gradient Descent for Gaussian Processes Done Rightcited by 17
  2. 2025xRFM: Accurate, scalable, and interpretable feature learning models for tabular datacited by 16
  3. 2022Few-shot Backdoor Attacks via Neural Tangent Kernelscited by 15
  4. 2023Estimating Koopman operators with sketching to provably learn large scale dynamical systemscited by 15
  5. 2024Memory-Scalable and Simplified Functional Map Learningcited by 14
  6. 2025Chameleon: A Flexible Data-mixing Framework for Language Model Pretraining and Finetuningcited by 14
  7. 2023Toward Large Kernel Modelscited by 13
  8. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  9. 2022Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regressioncited by 11
  10. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  11. 2024Stein transport for Bayesian inferencecited by 11
  12. 2023Kernel Regression with Infinite-Width Neural Networks on Millions of Examplescited by 9
  13. 2023Robust, randomized preconditioning for kernel ridge regressioncited by 9
  14. 2021The Unreasonable Effectiveness of Patches in Deep Convolutional Kernels Methodscited by 8
  15. 2021Sampling from Arbitrary Functions via PSD Modelscited by 8
  16. 2022Stochastic Zeroth order Descent with Structured Directionscited by 8
  17. 2023Fast kernel methods for Data Quality Monitoring as a goodness-of-fit testcited by 8
  18. 2021Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretizationcited by 7
  19. 2021ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitionscited by 6
  20. 2022Local Random Feature Approximations of the Gaussian Kernelcited by 6
  21. 2021Multiscale Laplacian Learningcited by 5
  22. 2023Reinforcement Learning with Function Approximation: From Linear to Nonlinearcited by 4
  23. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  24. 2024Optimal Kernel Quantile Learning with Random Featurescited by 4
  25. 2025Computational Efficiency under Covariate Shift in Kernel Ridge Regressioncited by 4
  26. 2021Sharp Analysis of Random Fourier Features in Classificationcited by 3
  27. 2022Learn Fast, Segment Well: Fast Object Segmentation Learning on the iCub Robotcited by 3
  28. 2023On Mitigating the Utility-Loss in Differentially Private Learning: A new Perspective by a Geometrically Inspired Kernel Approachcited by 3
  29. 2024On the Approximation of Kernel functionscited by 3
  30. 2024Supervised Kernel Thinningcited by 3
  31. 2024Fast training of large kernel models with delayed projectionscited by 3
  32. 2021A Note on Optimizing Distributions using Kernel Mean Embeddingscited by 2
  33. 2021Kernel PCA with the Nystr"om methodcited by 2
  34. 2022Adaptive Cholesky Gaussian Processescited by 2
  35. 2022Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergencecited by 2
  36. 2023On the Nystrom Approximation for Preconditioning in Kernel Machinescited by 2
  37. 2024Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selectioncited by 2
  38. 2024Learning Analysis of Kernel Ridgeless Regression with Asymmetric Kernel Learningcited by 2

50 most cited of 84 All 84 (JSON)