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
31 views

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
487 views

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
124 views

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
1k views

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
1k views

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
827 views

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