# Large Scale Kernel Learning using Block Coordinate Descent

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2016.

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

- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes](https://mlsanity.com/paper/2405.18457/) (2024)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features](https://mlsanity.com/paper/2106.02614/) (2021)
- [Joker: Joint Optimization Framework for Lightweight Kernel Machines](https://mlsanity.com/paper/2505.17765/) (2025)
- [Exploiting Block Coordinate Descent for Cost-Effective LLM Model Training](https://mlsanity.com/paper/2506.12037/) (2025)
- [GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra](https://mlsanity.com/paper/2609.08136/) (2026)
- [BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning](https://mlsanity.com/paper/2610.13382/) (2026)

## Abstract (arXiv)

We demonstrate that distributed block coordinate descent can quickly solve kernel regression and classification problems with millions of data points. Armed with this capability, we conduct a thorough comparison between the full kernel, the Nystr"om method, and random features on three large classification tasks from various domains. Our results suggest that the Nystr"om method generally achieves better statistical accuracy than random features, but can require significantly more iterations of optimization. Lastly, we derive new rates for block coordinate descent which support our experimental findings when specialized to kernel methods.