Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.
For a specific f(), I'm defining a term 'complexity', estimating how difficult is the given function to optimize. I attempted a solution in low dimension, but I might not be on the right track to generalize to n-dimn. This concept probably has a name and a better existing approximation, but here's what I have:
f(x) has input values bound [0, 5], x = [x1, x2, x3, x4...] (n-dimn), and f() outputs a single continuous value for 'success', bound [0, 1]
For input [x1, x2], calculate f(x) = y, and then relabel (x1, x2, y) as (x, y, z) for the plots below.
If it's easy to achieve an output of 1 through any random input, then you have a low complexity space.
An example f() space, where all input values result in z=1 (low complexity):
An example f() space, where only one input value results in z=1 (high complexity):
Complexity measured as volume enclosed between the xy-plane and the z-hyperplane seems valuable, but it alone does not work, because increasing volume at z=0.8 depth is 'worth more' than the same amount increased at 0.2 depth (in terms of optimizing for z=1). It's not just the z=1 region that is important as 'success', but also where z=0.9, z=0.8, etc. proportionally.
So what I've come up with so far is to compute a grid of inputs, and get their output values: i.e. f([0, 0])=0.0 f([0, 1])=0.3 f([0, 2])=0.2 ... then plot those to approximate the z-hyperplane. If I sum all the sample's z-values (0, .3, .2...) (and as the number of samples on the grid increases), it gives a nice sort of depth-weighted volume estimate.
There's a problem that local minima can cause increased volume (lower complexity), yet lead away and make it more difficult to navigate toward any deeper / global min's (higher complexity). (Weighted volume might handle this, but I'm unsure)
Example f() space where both have the same volume (picture's not exact, but you get it right? and I rotated axes, sry):
How can I incorporate that factor, that some points on the function increase volume, but the addition of that volume contributes less than if the volume was adjacent to a deeper space (in a similar function, ex. the f() on the right, above)? It seems like the critical feature that distinguishes those two hyperplanes is that the sign of the slope flips, where the negative slope leads into a local min, away from the global min, and the more frequently the sign flips, the harder the function will be to optimize.
If I iterate the grid rows and cols, and calculate the number of slope sign changes, that might be useful, or there might be a way to use trig to project a line and see what depth it intersects the hyperplane, but this is where I realized I need help.
My original idea was to define complexity as how resistant are the output values to fluctuations in the input values, given a specific input. So I have a decent estimate with my 'weighted-volume' calculation, but it's still lacking.
(1) Do you recognize the 'complexity' concept as another existing term?
I found 'fitness landscape analysis' in evolutionary optimization
(2) If not, can I improve beyond 'weighted-volume'?
(3) Will this work for higher dimensions?