<p>I tried to find a simple and accessible analysis of AIC. A definitive work seems to be Barron, Birgé, Massart, "Risk bounds for model selection via penalization"
<a href="https://link.springer.com/article/10.1007/s004400050210" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s004400050210</a>
though I can't vouch for accessibility.</p>

<p>Instead, let's analyze your sinusoids example. Suppose I have a parametric class of densities over <span class="math-container">$[0,1]$</span>, parametrized by a single parameter <span class="math-container">$\alpha$</span>, which is the frequency of the sinusoid. I take the positive part of the sinusoid and normalize the function to integrate to <span class="math-container">$1$</span> -- now it's a density. I can choose the <span class="math-container">$\alpha$</span> via any of the model selection techniques, including maximum likelihood and AIC. For any fixed <span class="math-container">$\alpha$</span>, I think all of these will converge (maybe even almost surely) to the true <span class="math-container">$\alpha$</span>. So why doesn't this contradict the fact that this family of functions (when thresholded at <span class="math-container">$0$</span>) has infinite VC-dimension?</p>

<p>It's all about the order of quantifiers. Finite VC-dimension means that you can specify a sample size <span class="math-container">$m_0(\epsilon,\delta)$</span> that will suffice to achieve <span class="math-container">$\epsilon$</span>-accuracy at <span class="math-container">$\delta$</span>-confidence -- <em>in advance of seeing any data</em>. In our model selection example above, you will not be able to specify such an <span class="math-container">$m_0(\epsilon,\delta)$</span>.</p>

<p>There are certainly infinite-VC classes that are learnable in this sense, which is weaker than PAC. For any target concept and distribution on the integers, you will eventually see enough examples to know the true concept to any desired accuracy -- you will just not be able to specify this sample size independently of the distribution and the target concept. (See Ex. 0.2(c) here
<a href="https://www.cs.bgu.ac.il/~asml162/wiki.files/hwk0.pdf" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~asml162/wiki.files/hwk0.pdf</a>
).</p>

CC BY-SA 4.0
2018-09-28T06:54:37.170Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/83769/discussion-on-answer-by-aryeh-how-can-aic-converge-in-the-limit-when-even-2-para).
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-09-26T09:27:55.987Z
2018-09-26T09:27:55.987Z
Aryeh
<p>AIC is used for <em>model selection</em> (i.e., density estimation, unsupervised learning) while VC theory is for supervised classification. "AIC is not a consistent model selection method":
<a href="https://robjhyndman.com/hyndsight/aic/" rel="nofollow noreferrer">https://robjhyndman.com/hyndsight/aic/</a></p>

<p>Various theoretical analyses of AIC are available; see here for example:
<a href="http://www.math.tau.ac.il/~felix/PAPERS/ieee2016.pdf" rel="nofollow noreferrer">http://www.math.tau.ac.il/~felix/PAPERS/ieee2016.pdf</a></p>

CC BY-SA 4.0
2018-09-25T22:17:42.807Z
Thanks.  However, the review article linked in the question indicates that the AIC convergence results apply to "regression", and even mentions a convergence example involving supervised linear regression (likewise VC-dim supports model selection, i.e. determining the tradeoff between sample error and model complexity in stuctural risk minimization).  Also, the link you provide says that "AIC does not assume the residuals are Gaussian"; but if in fact the convergence proofs do assume this, it still doesn't help to rule out infinite VC dimension models (which wouldn't be expected to converge)
Andy
CC BY-SA 4.0
2018-09-25T22:24:12.313Z
Regarding "consistency" it's true that AIC is not consistent (i.e. it does not converge to the "true" model with prob 1), but it is "efficient" e.g. according to ref 1 above "AIC is asymptotically efficient in mean squared error of estimation/prediction" i.e. the prediction error approaches zero in the limit.  Overall, I'm still unclear what assumption is being made in these convergence proofs that rules out infinite VC models which presumably will not converge to zero error out-of-sample, despite having low AIC (e.g. consider applying AIC to model selection for classification).
Andy
CC BY-SA 4.0
2018-09-26T09:13:27.257Z
I see I posted that too late at night -- included the wrong 2nd link (pasted) and also made some inaccurate statements (now removed). Will try to correct in a new answer.
Aryeh
CC BY-SA 4.0
2018-09-25T21:48:42.057Z
2018-09-26T09:12:26.390Z
2018-09-26T09:12:26.390Z
Aryeh
<p>AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1].  (Note that AIC refers to Akaike Information Criterion)</p>

<p>However, AIC relies solely on the number of parameters in the model to assess/penalize model complexity.  And yet models can have infinite representational capacity even with just 2 parameters, as measured by VC-dimension [2], e.g. {sign(sin(ωx + θ) : ω}.  So this infinite VC model can act as a lookup table and perfectly overfit the data, while only having 2 parameters in the penalty term, so it would have low AIC, but no guarantee of low error out-of-sample.</p>

<p>I'm assuming that the issue is that the AIC convergence theorems don't apply to all models, and in particular perhaps these infinite VC-dimension models violate one of the assumptions.  But at least based on the papers I've looked at so far it's not clear to me what assumption that might be (if any)?</p>

<p>By the way, according to this review article [1] the convergence theorems apply quite broadly e.g.:</p>

<blockquote>
  <p>When the true model is not in the candidate model set the AIC is
  efficient, in that it will asymptotically choose whichever model
  minimizes the mean squared error of prediction/estimation...
  The AIC's minimax rate of convergence in risk (and the BIC's lack of
  it) is a highly general result in regression and density estimation,
  and holds under more general circumstances than required for
  consistency properties discussed above. For example, the AIC is
  minimax-rate optimal regardless of whether the true model is finitely
  or infinitely dimensional; it is optimal whether the true model is
  among the candidates or not; and it extends to highly non-linear
  models, such as functions defined in Sobolev spaces</p>
</blockquote>

<p>[1] <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3366160/" rel="nofollow noreferrer">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3366160/</a></p>

<p>[2] <a href="http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf" rel="nofollow noreferrer">http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf</a></p>

<machine-learning><it.information-theory><lg.learning><st.statistics><vc-dimension>
How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?
Andy
# How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

(Asked by: username_0 on 2018-09-25)

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to Akaike Information Criterion)

However, AIC relies solely on the number of parameters in the model to assess/penalize model complexity. And yet models can have infinite representational capacity even with just 2 parameters, as measured by VC-dimension [2], e.g. {sign(sin(ωx + θ) : ω}. So this infinite VC model can act as a lookup table and perfectly overfit the data, while only having 2 parameters in the penalty term, so it would have low AIC, but no guarantee of low error out-of-sample.

I'm assuming that the issue is that the AIC convergence theorems don't apply to all models, and in particular perhaps these infinite VC-dimension models violate one of the assumptions. But at least based on the papers I've looked at so far it's not clear to me what assumption that might be (if any)?

By the way, according to this review article [1] the convergence theorems apply quite broadly e.g.:

> When the true model is not in the candidate model set the AIC is
> efficient, in that it will asymptotically choose whichever model
> minimizes the mean squared error of prediction/estimation...
> The AIC's minimax rate of convergence in risk (and the BIC's lack of
> it) is a highly general result in regression and density estimation,
> and holds under more general circumstances than required for
> consistency properties discussed above. For example, the AIC is
> minimax-rate optimal regardless of whether the true model is finitely
> or infinitely dimensional; it is optimal whether the true model is
> among the candidates or not; and it extends to highly non-linear
> models, such as functions defined in Sobolev spaces

[1] <https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3366160/>

[2] <http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf>

**Tags:** machine-learning, it.information-theory, lg.learning, st.statistics, vc-dimension

---

## 2 answers

### Answer by username_1 on 2018-09-26. Score: 2

I tried to find a simple and accessible analysis of AIC. A definitive work seems to be Barron, Birgé, Massart, "Risk bounds for model selection via penalization"
<https://link.springer.com/article/10.1007/s004400050210>
though I can't vouch for accessibility.

Instead, let's analyze your sinusoids example. Suppose I have a parametric class of densities over $[0,1]$, parametrized by a single parameter $\alpha$, which is the frequency of the sinusoid. I take the positive part of the sinusoid and normalize the function to integrate to $1$ -- now it's a density. I can choose the $\alpha$ via any of the model selection techniques, including maximum likelihood and AIC. For any fixed $\alpha$, I think all of these will converge (maybe even almost surely) to the true $\alpha$. So why doesn't this contradict the fact that this family of functions (when thresholded at $0$) has infinite VC-dimension?

It's all about the order of quantifiers. Finite VC-dimension means that you can specify a sample size $m\_0(\epsilon,\delta)$ that will suffice to achieve $\epsilon$-accuracy at $\delta$-confidence -- *in advance of seeing any data*. In our model selection example above, you will not be able to specify such an $m\_0(\epsilon,\delta)$.

There are certainly infinite-VC classes that are learnable in this sense, which is weaker than PAC. For any target concept and distribution on the integers, you will eventually see enough examples to know the true concept to any desired accuracy -- you will just not be able to specify this sample size independently of the distribution and the target concept. (See Ex. 0.2(c) here
<https://www.cs.bgu.ac.il/~asml162/wiki.files/hwk0.pdf>
).

> **Comments:**
> **username_2**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/83769/discussion-on-answer-by-aryeh-how-can-aic-converge-in-the-limit-when-even-2-para).  

---

### Answer by username_1 on 2018-09-25. Score: 1

AIC is used for *model selection* (i.e., density estimation, unsupervised learning) while VC theory is for supervised classification. "AIC is not a consistent model selection method":
<https://robjhyndman.com/hyndsight/aic/>

Various theoretical analyses of AIC are available; see here for example:
<http://www.math.tau.ac.il/~felix/PAPERS/ieee2016.pdf>

> **Comments:**
> **username_0**: Thanks.  However, the review article linked in the question indicates that the AIC convergence results apply to "regression", and even mentions a convergence example involving supervised linear regression (likewise VC-dim supports model selection, i.e. determining the tradeoff between sample error and model complexity in stuctural risk minimization).  Also, the link you provide says that "AIC does not assume the residuals are Gaussian"; but if in fact the convergence proofs do assume this, it still doesn't help to rule out infinite VC dimension models (which wouldn't be expected to converge)  
> **username_0**: Regarding "consistency" it's true that AIC is not consistent (i.e. it does not converge to the "true" model with prob 1), but it is "efficient" e.g. according to ref 1 above "AIC is asymptotically efficient in mean squared error of estimation/prediction" i.e. the prediction error approaches zero in the limit.  Overall, I'm still unclear what assumption is being made in these convergence proofs that rules out infinite VC models which presumably will not converge to zero error out-of-sample, despite having low AIC (e.g. consider applying AIC to model selection for classification).  
> **username_1**: I see I posted that too late at night -- included the wrong 2nd link (pasted) and also made some inaccurate statements (now removed). Will try to correct in a new answer.  

---

