If Machine learning is about making accurate predictions, isn't it a catch-22 situation with the no free lunch theorem? If Statistics is about making approximate summaries while Machine Learning is about making predictions as accurate as possible, doesn't it create a paradox due to the no free-lunch theorem?
 A: You're rarely in a situation where you're trying to apply ML to a problem where no assumptions would make sense.
In particular, the ML version of the no free lunch theorem will tell us that there are "as many" targets for which choosing say "best cross-validation error" and "worst cross-validation error" have better off-training set error, but we're generally not in circumstances where we're blindly trying to get good OTS error with no idea what we might see.
Which is to say the very broad possibilities under which no free lunch applies are usually much broader than the specific situations we're generally in. Good cross validation error will often be a pretty useful guide to OTS performance for particular applications - ones with the kinds of regularity that will make good cross-validation performance work pretty well (say, where the situations we haven't seen will nevertheless be pretty consistent with the ones we have).
It does tell us a couple of things -- for example, we have to be very careful about being over-broad in our claims about the performance of such things; good cross validation really doesn't offer any guarantee across all possible behaviors. It also tells us that we should expect to see a variety of different approaches doing relatively well in different circumstances; for all that one approach might be very good in one set of situations, there'll be other situations where other things will be better.
A: No Free Lunch (or NFL) is often viewed as a negative result. “Over the set of all problems, any two computational search algorithms have identical performance”. Incidentally, this could also be stated as “over the set of all computational search algorithms, any two problems are equivalent”. There is no universal optimizer. 
However, what it really means is, if we have a non-uniform probability distribution over our data, then we can learn something about the distribution (i.e. we can do better than random guessing). This is usually the case in the real world, which is why Occam ’s razor appears to be correct in practice.
In (offline supervised) machine learning, we assume the training dataset, and testing dataset are drawn the same probability distribution. This is also the case with predictive statistics. Hence, there is no contradiction. 
