# FALKON: An Optimal Large Scale Kernel Method

arXiv: https://arxiv.org/abs/1705.10958 · HTML: https://mlsanity.com/paper/1705.10958/

## Key facts

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

## Built on by (most cited first, 30 of 84)

- [Challenges in Training PINNs: A Loss Landscape Perspective](https://mlsanity.com/paper/2402.01868/) (2024)
- [Neural Fields as Learnable Kernels for 3D Reconstruction](https://mlsanity.com/paper/2111.13674/) (2021)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Conditional Distributional Treatment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regression](https://mlsanity.com/paper/2102.08208/) (2021)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [A Fast, Well-Founded Approximation to the Empirical Neural Tangent Kernel](https://mlsanity.com/paper/2206.12543/) (2022)
- [Making Look-Ahead Active Learning Strategies Feasible with Neural Tangent Kernels](https://mlsanity.com/paper/2206.12569/) (2022)
- [An Extensible Benchmark Suite for Learning to Simulate Physical Systems](https://mlsanity.com/paper/2108.07799/) (2021)
- [A Witness Two-Sample Test](https://mlsanity.com/paper/2102.05573/) (2021)
- [Interpolating Classifiers Make Few Mistakes](https://mlsanity.com/paper/2101.11815/) (2021)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [xRFM: Accurate, scalable, and interpretable feature learning models for tabular data](https://mlsanity.com/paper/2508.10053/) (2025)
- [Few-shot Backdoor Attacks via Neural Tangent Kernels](https://mlsanity.com/paper/2210.05929/) (2022)
- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [Memory-Scalable and Simplified Functional Map Learning](https://mlsanity.com/paper/2404.00330/) (2024)
- [Chameleon: A Flexible Data-mixing Framework for Language Model Pretraining and Finetuning](https://mlsanity.com/paper/2505.24844/) (2025)
- [Toward Large Kernel Models](https://mlsanity.com/paper/2302.02605/) (2023)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regression](https://mlsanity.com/paper/2201.06314/) (2022)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Stein transport for Bayesian inference](https://mlsanity.com/paper/2409.01464/) (2024)
- [Kernel Regression with Infinite-Width Neural Networks on Millions of Examples](https://mlsanity.com/paper/2303.05420/) (2023)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [The Unreasonable Effectiveness of Patches in Deep Convolutional Kernels Methods](https://mlsanity.com/paper/2101.07528/) (2021)
- [Sampling from Arbitrary Functions via PSD Models](https://mlsanity.com/paper/2110.10527/) (2021)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Fast kernel methods for Data Quality Monitoring as a goodness-of-fit test](https://mlsanity.com/paper/2303.05413/) (2023)
- [Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization](https://mlsanity.com/paper/2106.08598/) (2021)

## 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.