2
$\begingroup$

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?

$\endgroup$
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$
    – usul
    Commented Nov 18, 2023 at 1:34

2 Answers 2

2
$\begingroup$

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.)

$\endgroup$
1
  • 1
    $\begingroup$ Really nice! I'll go through these papers. Thanks! $\endgroup$
    – rivana
    Commented Nov 19, 2023 at 17:13
1
$\begingroup$

You cannot. See the No free lunch theorem (e.g., here and here and here and many other resources).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.