undefined | Better HN

0 pointstlb6y ago0 comments

How would you prove that?

Here's a simple counterexample to what I understand your theorem to say: consider an infinite search space: 𝕽∞ and a utility function: 1-|x|. There's a single global optimum at (0, ...), and the gradient of the utility function would find it quickly.

0 comments

pcmaffey6y ago

You missed the point that there is no global optimum. The GP’s novelty function is optimized for novelty, that’s all.

antt6y ago

Counter example: R^1 with a random function. There is no algorithm that can find a global maximum other than checking every point in R^1, of which there is an uncountable number.

salty_biscuits6y ago

Not all cost surfaces are equally likely to occur in real problems... Also depends on the constraints, linear assignment (i.e. one job to one worker with a big matrix of cost for job to worker and you minimize the sum) has a polynomial complexity solution.

antt6y ago

We are not talking about real problems here. Reality is so far from linear, so path dependent, so temporally dependent that by the time you gather 10 data points to try and match some function to the function is already outdated and error prone.

This is infinitely truer for when you try and find absolute maxima and minima and not just local ones.

tlbOP6y ago

Sure, some functions have no global maximum. But the comment I replied to claimed a theorem that every utility function on infinite search space has no global maximum, which isn't true.

shalmanese6y ago

All models are wrong, some are useful. GP presents an interesting way of framing real life decision making processes. That it happens to not be 100% accurate in all aspects is mostly trivia.

j / k navigate · click thread line to collapse

0 comments

pcmaffey6y ago

You missed the point that there is no global optimum. The GP’s novelty function is optimized for novelty, that’s all.

antt6y ago

Counter example: R^1 with a random function. There is no algorithm that can find a global maximum other than checking every point in R^1, of which there is an uncountable number.

salty_biscuits6y ago

antt6y ago

This is infinitely truer for when you try and find absolute maxima and minima and not just local ones.

tlbOP6y ago

Sure, some functions have no global maximum. But the comment I replied to claimed a theorem that every utility function on infinite search space has no global maximum, which isn't true.

shalmanese6y ago

All models are wrong, some are useful. GP presents an interesting way of framing real life decision making processes. That it happens to not be 100% accurate in all aspects is mostly trivia.

j / k navigate · click thread line to collapse