# Dimension lower bounds for linear approaches to function approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 17 references that are in the map.
- First posted on arXiv 18 Aug 2025.

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

- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)

## Abstract (arXiv)

This short note presents a linear algebraic approach to proving dimension lower bounds for linear methods that solve L2 function approximation problems. The basic argument has appeared in the literature before (e.g., Barron, 1993) for establishing lower bounds on Kolmogorov n-widths. The argument is applied to give sample size lower bounds for kernel methods.