Measure of complexity of a function

Question

Generally, when we try to write a function to fit to a group of points (curve fitting), it is important to find a balance between the accuracy and complexity of the function. The following picture shows different examples of this.

If the function is excessively simple at the cost of accuracy, it will underfit (such as with the line). On the other hand, if the function is excessively complex, it will overfit (such as with the curve on the right).

I am looking for a formal and widely accepted definition for the complexity of the function. One definition I was thinking about was how much the slope varies. Letting the average slope of the function in an interval be $\bar{m}$, then I can write the complexity as $$\int_a^b (f'(x)-\bar{m})^2 dx$$

where $f(x)$ is the function, $a$ is the lower endpoint, and $b$ is the upper endpoint.

Expanding the square, I get $$\int_a^b (f'(x)^2 - 2\bar{m}f'(x) + \bar{m}^2)dx = \int_a^bf'(x)^2dx - 2\bar{m}\int_a^bf'(x)dx + \bar{m}^2\int_a^bdx$$

Using the Fundamental Theorem of Calculus on the second integral, I get $$\int_a^bf'(x)^2dx - 2\bar{m}(f(b)-f(a)) + \bar{m}^2(b-a)$$

Because $\bar{m}$ is $$\frac{f(b)-f(a)}{b-a}$$ I can simplify the above equation to get $$\int_a^bf'(x)^2dx - \frac{\left(f(b)-f(a)\right)^2}{b-a}$$

The higher this value is, the more "complex" and varying the function is. If this value is $0$, then $f(x)$ is a line from $a$ to $b$.

Are there other measures of the complexity of a function? If so, what are the corresponding equations for them?

Edit: I am not looking for a complexity function dependent on the points. For example, $f(x) = x$ should have the same complexity no matter what points are on the graph.

Edit 2: A problem with the above definition of complexity is that $c^x$ would have a very high complexity (when I believe it should have a lower value). Specifically, from $a$ to $b$, the complexity is $$ \ln(c) \frac{c^{2b}-c^{2a}}{2} - \frac{(c^b-c^a)^2}{b-a}$$ which increases exponentially with respect to $b$.

Answer 1

This may not be what you are looking for.Since you are using in context of overfitting, I thought you might be interested to look into this.

One thing I can quickly think is of VC- dimension . VC dimension is complexity of whole class of functions not just single function.It forms whole basis of Statistical Learning Theory.There is something called fundamental theorem of Learning Theory that states that class of functions is learnable (under snotion of PAC Learnability) if and only if class of functions have finite VC dimension.It actually gives both lower and upper bounds for sample comlexity.Now larger the VC dimension , larger is sample complexity and hence you need large number of points to reliably learn the class

Some examples of VC-Dimension

1. VC dimension of hyperplanes in $f:\mathbb{R}^d $ is $d$
2. VC dimension of affine hyperplanes in $\mathbb{R}^d$ is $d+1$
3. VC dimension of all set of functions on $\mathbb{R}^d$ is $\infty$

note that above is all in context of classification (functions range are $\{ 0 , 1\}$) there is extensions to regression case as well

Answer 2

Have you heard of Kalman filters? They balance noise level against precision.
Rather than a single formula, it uses a weighted mean of previous function values to predict the next function value.