# Does the “No Free Lunch Theorem” apply to general statistical tests?

A woman I was working for asked me to do a one-way ANOVA on some data. I replied that the data were repeated measures (time series) data, and that I thought the assumption of independence was violated. She replied that I should not worry about the assumptions, just do the test and she would take into account that the assumptions might not have been met.

That did not seem right to me. I did some research, and found this wonderful blog post by David Robinson, K-means clustering is not a free lunch, which exposed me to the No Free Lunch Theorem. I have looked at the original paper and some follow on stuff, and frankly the math is a bit over my head.

The gist of it -- according to David Robinson -- seems to be that the power of a statistical test comes from its assumptions. And he gives two great examples. As I wade through the other articles and blog posts about it, it seems to always be referenced in terms of either supervised learning or search.

So my question is, does this theorem apply to statistical tests in general? In other words, can one say that the power of a t-test or ANOVA comes from its adherence to the assumptions, and cite the No Free Lunch Theorem?

I owe my former boss a final document regarding the work I did, and I would like to know if I can reference the No Free Lunch Theorem in stating that you cannot just ignore the assumptions of a statistical test and say you'll take that into account when evaluating the results.

• Why don't you just do "secretly" a repeated measures ANOVA? – Horst Grünbusch Jun 23 '15 at 13:54
• @HorstGrünbusch Actually, the data and testing has been discussed on the forum before, with specific questions about repeated measures ANOVA, and it turns out that a linear mixed effects model is probably the best choice. – rwjones Jun 23 '15 at 14:54
• This is well answered already, so a more flippant response can be added. You could ask your boss exactly how she would take into account the consequences of violating the assumptions ("being cautious" would be better than nothing!). In short, it is a long and hard path to get enough understanding and experience to know when you can be careless about assumptions. Rupert G. Miller's Beyond ANOVA (New York: Wiley, 1986 and later reprints) is a good source on the consequences and a major theme therein is that ignoring independence assumptions is one of the most dangerous things you can do. – Nick Cox Jun 23 '15 at 17:36
• @NickCox Well, she's no longer my boss, and this particular situation is the principal reason why. It was basically the culmination of a lot of sloppy thinking and sloppy project management on her part in an otherwise decent research environment. That aside, thanks for the book recommendation. From the sound of it, it's one of the things I'm looking for to cite in my final report. – rwjones Jun 23 '15 at 19:32

## 2 Answers

I don't know of a proof but I'll bet this applies quite generally. An example is an experiment with 2 subjects in each of 2 treatment groups. The Wilcoxon test cannot possibly be significant at the 0.05 level, but the t-test can. You could say that its power comes more than half from its assumptions and not just from the data. To your original problem, it is not appropriate to proceed as if the observations per subject are independent. To take things into account after the fact is certainly not good statistical practice except in very special circumstances (e.g., cluster sandwich estimators).

You can cite the No Free Lunch Theorem if you want, but you could also just cite the Modus Ponens (also known as the Law of Detachment, the basis of deductive reasoning), which is the root of the No Free Lunch Theorem.

The No Free Lunch Theorem encompass a more specific idea: the fact that there's no algorithm that can fit all purposes. In other words, the No Free Lunch Theorem is basically saying that there's no algorithmic magic bullet. This roots on the Modus Ponens, because for an algorithm or a statistical test to give the correct result, you need to satisfy the premisses.

Just like in all mathematical theorems, if you violate the premisses, then the statistical test is just empty of sense, and you cannot derive any truth from it. So if you want to explain your data using your test, you must assume that the required premisses are met, if they're not (and you know that), then your test is dead wrong.

That's because scientific reasoning is based on deduction: basically, your test/law/theorem is an implication rule, which says that if you have the premisse A then you can conclude B: A=>B, but if you don't have A, then you can either have B or not B, and both cases are true, that's one of the basic tenets of logical inference/deduction (the Modus Ponens rule). In other words, if you violate the premisses, the result doesn't matter, and you cannot deduce anything.

Remember the binary table of implication:

A   B   A=>B
F   F    T
F   T    T
T   F    F
T   T    T


So in your case, to simplify, you have Dependent_Variables => ANOVA_correct. Now, if you use independent variables, thus Dependent_Variables is False, then the implication will be true, since the Dependent_Variables assumption is violated.

Of course this is simplistic, and in practice your ANOVA test may still return useful results because there is almost always some degree of independence between dependent variables, but this gives you the idea why you just can't rely on the test without fulfilling the assumptions.

However, you can also use tests which premisses are not satisfied by the original by reducing your problem: by explicitly relaxing the independency constraint, your result may still be meaningful, althrough not guaranteed (because then your results apply to the reduced problem, not the full problem, so you cannot translate every results except if you can prove that the additional constraints of the new problem do not impact your test and thus your results).

In practice, this is often used to model practical data, by using Naive Bayes for example, by modelling dependent (instead of independent) variables using a model that assume independent variables, and surprisingly it works often very well, and sometimes better than models accounting for dependencies. You can also be interested by this question about how to use ANOVA when the data doesn't exactly meet all expectations.

To summary: if you intend to work on practical data and your goal is not to prove any scientific result but to make a system that just works (ie, a web service or whatever practical application), the independency assumption (and maybe other assumptions) can be relaxed, but if you're trying to deduce/prove some general truth, then you should always use tests which you can mathematically guarantee (or at least safely and provably assume) that you satisfy all premisses.

• If I understand your argument correctly, you start by saying that no application of statistics for which assumptions are not met exactly is valid. If true, this is very bad news indeed. Most econometrics books (to give just one example) spend their time explaining that it is wrong (one-word summary) and in detail precisely why. However, you seem to change your tack in the middle and what you are advocating instead is then fuzzy. Somehow working on the data can be sound even when it is logically invalid. I can't see a clear line of advice here therefore. – Nick Cox Jun 23 '15 at 17:44
• The point is: if the premisses are violated, you cannot take the test's results at face value since the inference is biased. However, you can still try it and if you're confident and experienced enough, you can still get something out of it, but mostly on practical implementations where in fact you don't care about scientific reasoning (you're just trying to model the data for some practical goal, not trying to infer some well-grounded general truth about the world). So my answer is not a "one-word summary", it's just the general case (wrong) vs specific case (may be ok). – gaborous Jun 23 '15 at 23:46
• PS: My statement does not only concerns statistics applications but any application of any logical or mathematical theorem/rule/test, this is true of any reasoning using inference and induction. But I am interested in your econometrics books references, the other ref you provided in a comment of the OP's question was very pertinent. – gaborous Jun 23 '15 at 23:47
• Thanks for adding comment, but I have to say that I don't find your statement especially clear or well-founded. I can't see that working scientists (I'm one) will grasp your distinction between data analysis for scientific reasoning and for practical goals. I'll leave it there except to commend textbooks such as those of Jeff Wooldridge as in effect extended essays on which assumptions are crucial, which not, and large grey area in between. amazon.com/Jeffrey-M.-Wooldridge/e/B001IGLWNY – Nick Cox Jun 24 '15 at 8:27
• Thank you for the reference. I have just found another question where they mention a paper that explains why naive independence assumptions can still work on data with dependent variables: "The paper seems to prove that (naive) bayes is good not only when features are independent, but also when dependencies of features from each other are similar/opposite between features" stats.stackexchange.com/a/23491/25538 – gaborous Jun 24 '15 at 8:40