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?
1
-
1$\begingroup$ 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. $\endgroup$– usulNov 18 at 1:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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).
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.)
-
1$\begingroup$ Really nice! I'll go through these papers. Thanks! $\endgroup$– rivanaNov 19 at 17:13
$\begingroup$
$\endgroup$
