Body: <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-13T11:13:42.983Z
Comments.Text: 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.
Comments.UserDisplayName: Stefan Radonjic
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-13T13:34:43.753Z
Comments.Text: @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).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-14T18:04:25.983Z
Comments.Text: Hello! Thank you for your suggestion, however I've manage to partially answer this question. I although have a new one which I will post shortly with source and everything. Thank you!
Comments.UserDisplayName: Stefan Radonjic
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-14T18:11:29.073Z
Comments.Text: @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!
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-14T18:16:00.163Z
Comments.Text: @nbro Alright. I will be sure to do that as soon as possible. Once again, thank you for all of the information.
Comments.UserDisplayName: Stefan Radonjic
Tags: <machine-learning><vc-dimension><vc-theory>
Title: Why does the growth function need to be polynomial in order for the learning algorithm to be consistent?
UserDisplayName: Stefan Radonjic
ThreadText: # Why does the growth function need to be polynomial in order for the learning algorithm to be consistent?
  
  (Asked by: username_0 on 2020-04-13)
  
  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?
  
  **Tags:** machine-learning, vc-dimension, vc-theory
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: @username_0 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).  
  > **username_0**: Hello! Thank you for your suggestion, however I've manage to partially answer this question. I although have a new one which I will post shortly with source and everything. Thank you!  
  > **username_1**: @username_0 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 `@username_1` 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!  
  > **username_0**: @username_1 Alright. I will be sure to do that as soon as possible. Once again, thank you for all of the information.  
  
  ---
  
  ## 0 answers
  
  