Skip to main content

Questions tagged [no-free-lunch-theorems]

For questions related to the various No Free Lunch (NFL) theorems (both in the context of machine learning and optimization).

Filter by
Sorted by
Tagged with
1 vote
1 answer

No-Free-Lunch: Calculation of the number of sequences of examples of size $m$

In the proof of No-Free-Lunch Theorem from the book Understanding Machine Learning: From Theory to Algorithms Cambridge University Press, p.37-38, the author wrote: Let $C$ be a subset of the domain ...
Tran Khanh's user avatar
1 vote
1 answer

If a neural network is a universal function approximator, can it have any prior beliefs?

Let us confine ourselves to the case where we have a $n$ dimensional input and a $+1$ or $-1$ output. It can be shown that: For every $n$, there exists a dense NN of depth 2, such that it contains ...
user avatar
3 votes
0 answers

Are No Free Lunch theorem and Universal Approximation theorem contradictory in the context of neural networks?

To my understanding NFL states that, we cannot have an hypothesis (let's assume it is an approximator like NN in this case) class that can't achieve certain accuracy parameters $\leq \epsilon$ with ...
user avatar
7 votes
4 answers

Are PAC learnability and the No Free Lunch theorem contradictory?

I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems ...
Jonathan Azpur's user avatar
14 votes
1 answer

What are the implications of the "No Free Lunch" theorem for machine learning?

The No Free Lunch (NFL) theorem states (see the paper Coevolutionary Free Lunches by David H. Wolpert and William G. Macready) any two algorithms are equivalent when their performance is averaged ...
user avatar
13 votes
2 answers

Are the shortcomings of neural networks diminishing?

Having worked with neural networks for about half a year, I have experienced first-hand what are often claimed as their main disadvantages, i.e. overfitting and getting stuck in local minima. However, ...
user avatar