The "no free lunch" theorem, in a very broad sense, states that when averaged over all possible problems, no algorithm will perform better than all others. For optimization, there appears to be some "almost no free lunch theorems" that would imply that no optimizer is the best for all possible problems, and that seems rather convincing for me: it is common sense in the optimization community that no algorithm is better than all others, and you need to use as much problem-specific knowledge as possible.
However, this fact (that no known algorithm is better than all others) may be due to limitations in our current understanding of optimization, and not to a provable theoretical result. One thing is saying that we don't have an all-in-one optimizer, and another very different thing is to say that it cannot exist.
For what I've seen, the NFL theorem for optimization only considers deterministic algorithms, while almost all good optimizers have some degree of randomness. Also, the NFL considers the set of all functions, most of which are un-compressible in the Kolmogorov sense, while most of the useful functions in practice are very compressible: expressed either as compositions of elementary functions, or by some probabilistic model, or by simulation, but I don't know of any useful function that is strictly un-compressible in the Kolmogorov sense.
So, my question is, for the set of practically interesting functions, which are very compressible, and for the set of currently used optimization algorithms, most of which are stochastic to some degree, does the NFL holds at all? Are there any theoretical results that disregard the existence of a "perfect" optimizer for this restricted set of functions and algorithms? Or should we strive for the design of an all-in-one optimizer that can beat all currently available technique.
After Göedel and NP-Completeness, I would rather think that the NFL holds for optimization as well, since it seems that there is no such thing as a free lunch in almost all areas of CS. However, a good theoretical result would be nice.
Hey Piad, old friend over here,
Let me start saying I am an engineer and I have very little idea about the subject. When I have to optimize I usually try to find out on internet what is the best algorithm for my application and I go with it; if I don´t find one, I choose anyone and let the computer do its work, ;)
Anyway, your question is really interesting and it made me spend one hour reading about the subject online. I think this paper covers part of your question: ftp://ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/biblio/gecco2006etc/papers/lbp124.pdf
The guy claims that "there is a free lunch for the class of all n-compressible target functions f: X->Y given reasonable conditions on n, |X| and |Y|". This should cover the part of narrowing the set of target functions to practically interesting ones. The basic idea of the demonstration is to use the "Sharpened no free lunch" results that say that the theorem only applies to closed under permutations classes of target functions. The author proceeds to show that the class of functions he is considering is not closed under permutation, thus, the theorem doesn´t apply.
I hope I am not talking nonsense here, but this paper looks serious and so do the references. Check it out, you will surely understand the theory behind much better,
Regards
Thanks Peter, nice to hear about you!!
I've downloaded the paper and will read it as soon as I have a chance. I've skimmed a bit through it. The sharpened NFL sounds very interesting, in that it narrows the set of functions to subsets which can hold compressible functions. The part I'm missing is for stochastic search algorithms, since the original theorem is explicitly defined for deterministic search algorithms, which, lets face it, are not used that much.
Any way, thanks a lot for the contribution. I'll read it more thoroughly and come back when I have a better understanding.
These references are important:
1- David H. Wolpert and William G. Macready (1997). No Free Lunch Theorems for Optimization. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 1(1): 67-82.
http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf
2-Yu-Chi Ho and David L. Pepyen. (2001). Simple Explanation of the N 0 Free Lunch Theorem of Optimization. Proceedings of IEEE. 4409-4414.
http://www.cc.gatech.edu/~isbell/reading/papers/nfl-optimization-explanation.pdf
Also see answers to a similar topic 'Which heuristic optimization method is the simplest and easiest to use?' on RG few days ago.
https://www.researchgate.net/post/Which_heuristic_optimization_method_is_the_simplest_and_easiest_to_use
yes, it just covers the part of narrowing the set of functions, nothing about stochastic search algorithms, if I manage to find anything about the latter I will let you know. Take care man, hope everything is ok over there
Some important applications use measurements as part of their objective function evaluation. Those are quite uncompressable (of course, the range of possible results can be limited, etc., but measurements get close).
I think there is an important point missing in the description and discussions on the NFL theorem here: that the set-up of that theorem assumes that all problem data is equally probable. We may translate that to say that we have NO guarantees of any properties of an optimization problem, such as convexity, Lipschitz continuous gradients, and so on. In this case it is obvious that we cannot expect that a gradient method shall work better than anything.
But as soon as we move away from that "I know nothing! assumption, we can do better. For example, as soon as Lipschitz continuity or convexity is present it is possible to utilize bounding techniques, the former linking to cuts in a search tree, the second to sub gradients geometrically pointing towards the optimal solution set.
I for one see little interest in the NFL theorem - because we always will have a better situation than what it describes. It is hence for us an unnecessary theorem.
@Michael:
I think somewhat different about the "unnecessary theorem". Working together with industry partners, you often hear the wish expressed that you should deliver an optimization algorithm which solves every problem for them, no matter what they throw at it, because that shifts the load from the modelling part to the solver part, and often the industrial partners do not want to meddle with their modelling or (even worse) to disclose some of their models. But then it is usually impossible to assume structure or any other properties of the functions involved. Then you can use the NFL theorem as one possible argument in trying to convince them that proper modelling and structure information is the first and very important step towards a _good_ method for solving their problem.
Yes, Hermann, that is indeed a good argument: "look more closely into the problem and you should be able to find something useful". That exercise is always rewarding, and I would criticize those industry partners every day for being lazy - because that's what they are, if they do not take the time to investigate the problem more.
But recall that that does not mean that the NFL theorem in itself contains much of use. :-)
I agree completely with Hermann and Michael. To be cynical, the NFL theorem does have a significant implication within in the world of academia. It is used to justify ``evolutionary computing'' and other elementary heuristic methods. After all, according to NFL, all algorithms have an equal number of weak spots. This argument allows researchers to bypass the difficult mathematics of optimization theory and churn out thousands of journal papers.
I have something like an all-in-one optimizer, at least for a broad range of problems, no parameters to be concerned about, the set-it-and-forget-it type, and it works (well, at least for me, for whatever I tried it, to be precise); almost like a free-lunch:
http://web.unbc.ca/~bluskovi/pdo.pdf
Journal of Combinatorial Optimization, 2015, DOI 10.1007/s10878-014-9826-x.
The final publication is available at link.springer.com; more precisely, here:
http://link.springer.com/article/10.1007/s10878-014-9826-x
Supplementary material (illustration on how PDO works in one possible instance; finding cyclic designs):
http://static-content.springer.com/esm/art%3A10.1007%2Fs10878-014-9826-x/MediaObjects/10878_2014_9826_MOESM1_ESM.pdf
A practical aspect for ML engineering is that the NFT forces us to formally define a problem. This is important since algorithms can be compared only within such a problem.
Most of the papers do not define the problem properly, and I do not think that referring to the domain is enough (e.g., face detection, activity recognition, etc.). Unfortunately, this makes the effort of many researchers not useful for further works and real-world applications.
PS: I know this is an old question but I hope to help our community anyway. My idea is compliant with the Michael Patriksson's comment above but more from an academic perspective.
- Badges
- Science topic
- Similar topics
- Force