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?

  • $\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, 2020 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$ Apr 13, 2020 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, 2020 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, 2020 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$ Apr 14, 2020 at 18:16


You must log in to answer this question.

Browse other questions tagged .