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
1answer
94 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 ...
2
votes
0answers
70 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 ...
4
votes
2answers
378 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 ...
10
votes
1answer
823 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 ...
11
votes
2answers
684 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, ...