# A Bound on the Maximal Marginal Degrees of Freedom

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 31 references that are in the map.
- First posted on arXiv 20 Feb 2024.

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

- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Approximation beats concentration? An approximation view on inference with smooth radial kernels](https://mlsanity.com/paper/1801.03437/) (2018)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Statistical Robustness of Empirical Risks in Machine Learning](https://mlsanity.com/paper/2005.08458/) (2020)

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

- [On the Approximation of Kernel functions](https://mlsanity.com/paper/2403.06731/) (2024)

## Abstract (arXiv)

Kernel ridge regression, in general, is expensive in memory allocation and computation time. This paper addresses low rank approximations and surrogates for kernel ridge regression, which bridge these difficulties. The fundamental contribution of the paper is a lower bound on the minimal rank such that the prediction power of the approximation remains reliable. Based on this bound, we demonstrate that the computational cost of the most popular low rank approach, which is the Nystr"om method, is almost linear in the sample size. This justifies the method from a theoretical point of view. Moreover, the paper provides a significant extension of the feasible choices of the regularization parameter. The result builds on a thorough theoretical analysis of the approximation of elementary kernel functions by elements in the range of the associated integral operator. We provide estimates of the approximation error and characterize the behavior of the norm of the underlying weight function.