I may have some misconceptions here, but by my understanding, the Vapnik-Chervonenkis dimension of a class of functions describes the number of points it can be guaranteed to classify correctly. I'm looking for a comparable measure of dimension that will work for regression or interpolation, rather than categorization, presumably a measure that has been defined and well-studied in the context of data analytics or machine learning.
For concreteness I'm thinking about a class of real-valued functions $\mathcal{C} \subseteq [\mathbb{R} \to \mathbb{R}]$ on $\mathbb{R}$, and would like to say that $\mathrm{dim}(\mathcal{C}) \geq d $ if given $d$ distinct points $x = (x_i)$ (or perhaps for any $n$ points) there is an $f = f_y \in \mathcal{C}$ which takes prescribed values $y = (y_i)$ on $x$.
Obviously polynomials of degree $<d$ are a natural class of functions with dimension $d$ under this definition. A closely related concept is that of a Haar/Chebyshev space. But since I am interested in data science and machine learning, I would be interested in approximate functions too, say that $f \in \mathcal{C}$ need only take values arbitrarily close to the prescribed values.
$\bullet$ What notions of dimension like this exist and find use in data science or machine learning? Is Vapnik-Chervonenkis dimension more closely related than I thought?
$\bullet$ (How) can this notion of dimension be used to characterize what type of function should be used to fit a larger collection of points? For example, if you try to use linear regression on parabola-shaped scatterplot, you won't have a good time. But how to know that quadratic polynomials would be better, without visually inspecting the data?
$\bullet$ Is there any relation between size/number of layers of perceptrons and this interpolation/regression dimension?