# ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 23 Jun 2021.

## Builds on (most cited first, 16 of 16)

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Distributed learning with regularized least squares](https://mlsanity.com/paper/1608.03339/) (2016)
- [Learning with SGD and Random Features](https://mlsanity.com/paper/1807.06343/) (2018)
- [Solving Ridge Regression using Sketched Preconditioned SVRG](https://mlsanity.com/paper/1602.02350/) (2016)
- [Optimal Learning Rates for Localized SVMs](https://mlsanity.com/paper/1507.06615/) (2015)
- [NYTRO: When Subsampling Meets Early Stopping](https://mlsanity.com/paper/1510.05684/) (2015)
- [Spatial Decompositions for Large Scale SVMs](https://mlsanity.com/paper/1612.00374/) (2016)
- [Universal Consistency and Robustness of Localized Support Vector Machines](https://mlsanity.com/paper/1703.06528/) (2017)
- [Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up](https://mlsanity.com/paper/1905.03135/) (2019)
- [Multiscale regression on unknown manifolds](https://mlsanity.com/paper/2101.05119/) (2021)
- [Kernel Ridge Regression via Partitioning](https://mlsanity.com/paper/1608.01976/) (2016)
- [Kernel Conjugate Gradient Methods with Random Projections](https://mlsanity.com/paper/1811.01760/) (2018)

## Built on by (most cited first, 6 of 6)

- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)
- [Kernel PCA with the Nystr"om method](https://mlsanity.com/paper/2109.05578/) (2021)
- [Locally Smoothed Gaussian Process Regression](https://mlsanity.com/paper/2210.09998/) (2022)
- [Snacks: a fast large-scale kernel SVM solver](https://mlsanity.com/paper/2304.07983/) (2023)
- [BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning](https://mlsanity.com/paper/2610.13382/) (2026)

## Abstract (arXiv)

We introduce ParK, a new large-scale solver for kernel ridge regression. Our approach combines partitioning with random projections and iterative optimization to reduce space and time complexity while provably maintaining the same statistical accuracy. In particular, constructing suitable partitions directly in the feature space rather than in the input space, we promote orthogonality between the local estimators, thus ensuring that key quantities such as local effective dimension and bias remain under control. We characterize the statistical-computational tradeoff of our model, and demonstrate the effectiveness of our method by numerical experiments on large-scale datasets.