<p>To be more precise, if you want a distribution-free generalization bound, then you must have some inductive bias (these are the no-free-lunch theorems referenced by D.W.). For binary classification, this amounts to the hypothesis class having a finite VC-dimension (necessary and sufficient).</p>
<p>If you allow distribution-dependent rates, then finite VC-dimension is no longer necessary. Much less is formally known in this setting, but here is a first step:</p>
<p><a href="https://arxiv.org/abs/2209.04054" rel="nofollow noreferrer">https://arxiv.org/abs/2209.04054</a>
(Cohen, K., &quot;Local Glivenko-Cantelli&quot;, COLT 2023).</p>
<p>Finally, if you are content with (say, strong) Bayes-consistency and no rate, then, at least in metric spaces, there is a universal learner without any inductive bias:</p>
<p><a href="https://projecteuclid.org/journals/annals-of-statistics/volume-49/issue-4/Universal-Bayes-consistency-in-metric-spaces/10.1214/20-AOS2029.full" rel="nofollow noreferrer">https://projecteuclid.org/journals/annals-of-statistics/volume-49/issue-4/Universal-Bayes-consistency-in-metric-spaces/10.1214/20-AOS2029.full</a>
(Hanneke et al., &quot;Universal Bayes consistency in metric spaces&quot;, AOS 2021.)</p>

CC BY-SA 4.0
2023-11-19T17:13:18.577Z
Really nice! I'll go through these papers. Thanks!
rivana
CC BY-SA 4.0
2023-11-19T13:16:22.590Z
2023-11-19T13:16:22.590Z
Aryeh
<p>You cannot.  See the No free lunch theorem (e.g., <a href="https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization" rel="nofollow noreferrer">here</a> and <a href="https://en.wikipedia.org/wiki/No_free_lunch_theorem" rel="nofollow noreferrer">here</a> and <a href="https://ai.stackexchange.com/q/15650/1794">here</a> and many other resources).</p>

CC BY-SA 4.0
2023-11-17T20:12:48.203Z
2023-11-17T20:12:48.203Z
D.W.
<p>I want to understand the intuition behind the classic setting of learning theory, we always assume that the model belongs to some known class. Was there a formal proof that we can or can not learn a model with zero inductive bias meaning with no knowledge of the hypothesis class?</p>

CC BY-SA 4.0
2023-11-18T01:34:06.530Z
One way to put it is that the required sample complexity is known to grow with the VC-dimension of the hypothesis class. If your potential hypothesis class contains all possible functions, it has maximum possible VC-dimension, implying an exponential or infinite sample complexity in a nontrivial setting.
usul
<machine-learning><pac-learning>
Learning with zero inductive bias
rivana
# Learning with zero inductive bias

(Asked by: username_0 on 2023-11-15)

I want to understand the intuition behind the classic setting of learning theory, we always assume that the model belongs to some known class. Was there a formal proof that we can or can not learn a model with zero inductive bias meaning with no knowledge of the hypothesis class?

**Tags:** machine-learning, pac-learning

> **Comments:**
> **username_1**: One way to put it is that the required sample complexity is known to grow with the VC-dimension of the hypothesis class. If your potential hypothesis class contains all possible functions, it has maximum possible VC-dimension, implying an exponential or infinite sample complexity in a nontrivial setting.  

---

## 2 answers

### Answer by username_2 on 2023-11-19. Score: 2 | Accepted answer

To be more precise, if you want a distribution-free generalization bound, then you must have some inductive bias (these are the no-free-lunch theorems referenced by username_3). For binary classification, this amounts to the hypothesis class having a finite VC-dimension (necessary and sufficient).

If you allow distribution-dependent rates, then finite VC-dimension is no longer necessary. Much less is formally known in this setting, but here is a first step:

<https://arxiv.org/abs/2209.04054>
(Cohen, K., "Local Glivenko-Cantelli", COLT 2023).

Finally, if you are content with (say, strong) Bayes-consistency and no rate, then, at least in metric spaces, there is a universal learner without any inductive bias:

<https://projecteuclid.org/journals/annals-of-statistics/volume-49/issue-4/Universal-Bayes-consistency-in-metric-spaces/10.1214/20-AOS2029.full>
(Hanneke et al., "Universal Bayes consistency in metric spaces", AOS 2021.)

> **Comments:**
> **username_0**: Really nice! I'll go through these papers. Thanks!  

---

### Answer by username_3 on 2023-11-17. Score: 1

You cannot. See the No free lunch theorem (e.g., [here](https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization) and [here](https://en.wikipedia.org/wiki/No_free_lunch_theorem) and [here](https://ai.stackexchange.com/q/15650/1794) and many other resources).


---

