Dimension lower bounds for linear approaches to function approximation

Abstract

This short note presents a linear algebraic approach to proving dimension lower bounds for linear methods that solve $L^2$ 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.

First appeared on author's homepage in August 2021 https://www.cs.columbia.edu/~djhsu/papers/dimension-argument.pdf