3
$\begingroup$

I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here, because I have not found a good discussion of it anywhere else.

The NFL theorems are very interesting theoretical results which do not hold in most practical circumstances, because a key assumption of the NFL theorems is rather strong. This assumption is, roughly speaking, that the performance of an algorithm is averaged over all problem instances drawn from a uniform probability distribution. In realistic applications the problems an algorithm typically encounters are NOT drawn from a uniform distribution, and are instead drawn from what is likely a very interesting and complicated distribution specific to the general problem setting.

So, while the NFL theorems are quite interesting results, do they have any practical implications? Or are they merely theoretical results?

EDIT: By practical implications, I mean novel or improvements over existing algorithms, improved hyper-parameter selection, and things of that nature. I would even be interested to learn of NFL-inspired theorems that do apply to realistic search/optimization/learning problems.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ See this question: cs.stackexchange.com/questions/21758/… , the answers go into the usage of NFL. Also, note that the NFL theorems are 'negative' results, so all practical use of them is limited to saying we cannot achieve something. Some call this inherently theoretical. You should specify what you mean by 'theoretical result'. $\endgroup$ – Discrete lizard♦ Feb 16 '18 at 18:51
  • $\begingroup$ @Discretelizard none of the responses go into applications, they are concerned with interpretations. As for the distinction between a theoretical and a practical result, I am relying on colloquial understandings of the terms. $\endgroup$ – Surgical Commander Feb 16 '18 at 21:35
  • $\begingroup$ @D.W. It is admittedly a broad question, but I would be happy to have ANY implication pointed out to me for ANY of the NFL theorems. After spending some time on searching myself, I am starting to doubt whether there are any practical implications whatsoever. $\endgroup$ – Surgical Commander Feb 16 '18 at 21:35
  • 1
    $\begingroup$ I feel like you have essentially already answered your own question. Indeed, real-world inputs are arguably not arbitrary but drawn from some specific distribution since they model human interaction, a physical process, or so on. $\endgroup$ – Juho Feb 17 '18 at 9:36
  • $\begingroup$ @SurgicalCommander Well, I most certainly don't know it's precise colloquial meaning in this context. Given that your background is in Physics, while most people here have background in CS or math, the meaning could very well differ between you and the potential answer-er. $\endgroup$ – Discrete lizard♦ Feb 17 '18 at 10:19
4
$\begingroup$

A practical implication is that there is no silver bullet: we shouldn't expect any single optimization method to be perfect for all problems. Rather, we should try to design optimization methods that are tailored to the problem we're trying to solve.

For instance, if you want to use local search, you'll probably need to define a neighborhood relation (a set of moves that makes "small" changes to the current solution) that is informed by the problem domain. See, e.g., https://cs.stackexchange.com/a/88016/755 for a recent example of this here on this site.

A practical implication is that machine learning won't work if there is no structure at all on the space of possible models/hypotheses. Instead, we need some kind of prior that makes some models more likely than others.

Often, we assume a prior that assume "simpler" models are more likely than complex one's (Occam's razor: all else being equal, the simpler explanation is more likely to be true). This leads to use of regularization in machine learning, as it effectively applies Occam's razor to candidate models. So, you can think of the NFL theorems as providing some kind of theoretical justification for regularization or theoretical understanding that helps us see what the role of regularization is and provides some partial explanation for the empirical observation that it seems to often be effective.

You could characterize these as "NFL theorems tell us some directions that won't work", which arguably has value as it helps us avoid wasting time on something that won't work and helps point us towards directions that are more likely to work.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.