Dimension lower bounds for linear approaches to function approximation
This work provides incremental theoretical insights into the limitations of linear approaches for function approximation, relevant to researchers in approximation theory and machine learning.
The paper tackles the problem of proving dimension lower bounds for linear methods in L^2 function approximation, applying an existing linear algebraic argument to derive sample size lower bounds for kernel methods.
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.