# Optimal Learning Rates for Localized SVMs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2015.

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

- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Kernel spectral joint embeddings for high-dimensional noisy datasets using duo-landmark integral operators](https://mlsanity.com/paper/2405.12317/) (2024)
- [Total Stability of SVMs and Localized SVMs](https://mlsanity.com/paper/2101.12678/) (2021)
- [Nystr"om Regularization for Time Series Forecasting](https://mlsanity.com/paper/2111.07109/) (2021)
- [Adaptive Parameter Selection for Kernel Ridge Regression](https://mlsanity.com/paper/2312.05885/) (2023)
- [Locally Adaptive and Differentiable Regression](https://mlsanity.com/paper/2308.07418/) (2023)
- [Local Binary and Multiclass SVMs Trained on a Quantum Annealer](https://mlsanity.com/paper/2403.08584/) (2024)
- [Gradient Boosted Binary Histogram Ensemble for Large-scale Regression](https://mlsanity.com/paper/2106.01986/) (2021)
- [Breaking the curse of dimensionality with Isolation Kernel](https://mlsanity.com/paper/2109.14198/) (2021)
- [Locally Smoothed Gaussian Process Regression](https://mlsanity.com/paper/2210.09998/) (2022)
- [Kernel-Based Distributed Q-Learning: A Scalable Reinforcement Learning Approach for Dynamic Treatment Regimes](https://mlsanity.com/paper/2302.10434/) (2023)
- [Lp- and Risk Consistency of Localized SVMs](https://mlsanity.com/paper/2305.09385/) (2023)
- [Out-of-Distribution generalization of quantile regression with heavy tailed inputs: an SVM approach](https://mlsanity.com/paper/2606.00265/) (2026)

## Abstract (arXiv)

One of the limiting factors of using support vector machines (SVMs) in large scale applications are their super-linear computational requirements in terms of the number of training samples. To address this issue, several approaches that train SVMs on many small chunks of large data sets separately have been proposed in the literature. So far, however, almost all these approaches have only been empirically investigated. In addition, their motivation was always based on computational requirements. In this work, we consider a localized SVM approach based upon a partition of the input space. For this local SVM, we derive a general oracle inequality. Then we apply this oracle inequality to least squares regression using Gaussian kernels and deduce local learning rates that are essentially minimax optimal under some standard smoothness assumptions on the regression function. This gives the first motivation for using local SVMs that is not based on computational requirements but on theoretical predictions on the generalization performance. We further introduce a data-dependent parameter selection method for our local SVM approach and show that this method achieves the same learning rates as before. Finally, we present some larger scale experiments for our localized SVM showing that it achieves essentially the same test performance as a global SVM for a fraction of the computational requirements. In addition, it turns out that the computational requirements for the local SVMs are similar to those of a vanilla random chunk approach, while the achieved test errors are significantly better.