1
$\begingroup$

Could someone please explain to me why in VC theory, specifically, when calculating the VC dimension, the growth function needs to be polynomial in order for the learning algorithm to be consistent? Why polynomial, and where does the name growth function come from exactly?

Improve this question
$\endgroup$
7
  • $\begingroup$ Its probably due to Sauers lemma. Also what did you mean by consistent? Like agnostic PAC, NUL, are you talking about the case of consistent learnability? $\endgroup$ – user9947 Apr 13 '20 at 7:40
  • $\begingroup$ I am kinda new to the field, so I am not familiar with such lemma. Yea, agnostic PAC. If I understood correctly, ERM is consistent (meaning all functions in function class F will converge to 0 as number of training samples approaches infinite) if and only if VC dimension of function class F is finite. $\endgroup$ – Stefan Radonjic Apr 13 '20 at 11:13
  • 1
    $\begingroup$ @StefanRadonjic Hi and welcome to AI SE :) I suggest you provide a link to the source that states what you're asking and the definition of "consistent" that you're using. I would also suggest you ask the question "where does the name growth function come from exactly?" in a separate post (because that's a distinct question that deserves its own post, in my opinion). $\endgroup$ – nbro♦ Apr 13 '20 at 13:34
  • 1
    $\begingroup$ @StefanRadonjic Ok, please, then provide a formal answer to your question below. Future readers would benefit from this answer! Btw, you need to tag me with @nbro so that I receive a notification of your message, otherwise, I may not see your messages. It was just luck that I saw your comment above! $\endgroup$ – nbro♦ Apr 14 '20 at 18:11
  • 1
    $\begingroup$ @nbro Alright. I will be sure to do that as soon as possible. Once again, thank you for all of the information. $\endgroup$ – Stefan Radonjic Apr 14 '20 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.