3 ms·

The No Free Lunch theorem. Technically put, "any two optimization algorithms are equivalent when their performance is averaged across all possible problems" M

The No Free Lunch theorem. Technically put, "any two optimization algorithms are equivalent when their performance is averaged across all possible problems" More intuitively paraphrased, "if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.". I forget if either or any of these are actually proven, or if they're the "folkloric" intuitions from more technical papers. More boldly overstated, there's no such thing as a general optimisation, all optimisations are relative to a subset of possible inputs. In extremis, there's exists a situation where Bogosort is preferable to Quicksort.

rincebrain 10y ago
I think this is provably false, probably, since you can compose a pathological case where you have a no-op that adds an O(n) (or more) step to the runtime and an optimization step that purely removes that no-op. There's optimizations which are tradeoffs against reducing the valid input space (or optimization for the common input cases), and then there's optimizations that eliminate unnecessary operations or combine things cleverly without degrading the worst-case scenario.
- AndrewOMartin 10y ago
  I'm not immediately convinced by your no-op example because I can conceive of situations that needs a little extra time to be passed between actions, such as in the case of sorting elements whose value isn't easily determinable and is best estimated n clock ticks after the previous action. This is of course a million miles away from the kind of sorting problems you get in Computer Science 101, but this is my point, the traditional sorting problems happen in a very well defined context, as soon as that changes, you might find any algorithm being optimal. Including Bogosort and, for example, quicksort with some extra no-ops. I like your point, but for the reason above I still think the No Free Lunch theorem is valuable, else I wouldn't have had this insight in the first place. At least, I consider it an insight, YMMV.
  - rincebrain 10y ago
    Sure, it's certainly valuable to realize that you rarely get an optimization in one case that's not pessimal in another, and it is well-removed from the constrained environments that people work through for demoing algorithms. I was just thinking in terms of more abstract optimization (e.g. platform-agnostic ones that just strictly reduce work to be done) versus platform-specific optimizations/workarounds/bin-packing (like nops to prevent your pipelines or cache lines from being pathological).
azeirah 10y ago
A friend of mine once thought up a parallel universe where, by pure chance, bogosort always correctly sorts every single array, boggling the minds of everybody in that universe.
- nitrogen 10y ago
  The novel Anathem might be interesting to your friend.
jmount 10y ago
The "no free lunch theorem" is really not useful. It has been proven, but only for the useless statement that an algorithm that does better on some case does worse on some other case (that you may not care about). Originally it was for search using that if you happen to look the right place first you win. This almost made sense, but then it get extended to general optimization, algorithms, and machine learning. There are in fact algorithms that do better than others with respect to realistic distributions. And that contradicts the strong interpretations of the no-free lunch theorem bandied about in search, algorithms, and machine learning.

rincebrain 10y ago

I think this is provably false, probably, since you can compose a pathological case where you have a no-op that adds an O(n) (or more) step to the runtime and an optimization step that purely removes that no-op. There's optimizations which are tradeoffs against reducing the valid input space (or optimization for the common input cases), and then there's optimizations that eliminate unnecessary operations or combine things cleverly without degrading the worst-case scenario.

AndrewOMartin 10y ago
I'm not immediately convinced by your no-op example because I can conceive of situations that needs a little extra time to be passed between actions, such as in the case of sorting elements whose value isn't easily determinable and is best estimated n clock ticks after the previous action. This is of course a million miles away from the kind of sorting problems you get in Computer Science 101, but this is my point, the traditional sorting problems happen in a very well defined context, as soon as that changes, you might find any algorithm being optimal. Including Bogosort and, for example, quicksort with some extra no-ops. I like your point, but for the reason above I still think the No Free Lunch theorem is valuable, else I wouldn't have had this insight in the first place. At least, I consider it an insight, YMMV.
- rincebrain 10y ago
  Sure, it's certainly valuable to realize that you rarely get an optimization in one case that's not pessimal in another, and it is well-removed from the constrained environments that people work through for demoing algorithms. I was just thinking in terms of more abstract optimization (e.g. platform-agnostic ones that just strictly reduce work to be done) versus platform-specific optimizations/workarounds/bin-packing (like nops to prevent your pipelines or cache lines from being pathological).

azeirah 10y ago

A friend of mine once thought up a parallel universe where, by pure chance, bogosort always correctly sorts every single array, boggling the minds of everybody in that universe.

nitrogen 10y ago
The novel Anathem might be interesting to your friend.

jmount 10y ago

The "no free lunch theorem" is really not useful. It has been proven, but only for the useless statement that an algorithm that does better on some case does worse on some other case (that you may not care about). Originally it was for search using that if you happen to look the right place first you win. This almost made sense, but then it get extended to general optimization, algorithms, and machine learning. There are in fact algorithms that do better than others with respect to realistic distributions. And that contradicts the strong interpretations of the no-free lunch theorem bandied about in search, algorithms, and machine learning.