3
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Bjørn Kjos-Hanssen ♦
    Sep 28, 2018 at 6:54
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$
    – Andy
    Sep 25, 2018 at 22:17
  • $\begingroup$ 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). $\endgroup$
    – Andy
    Sep 25, 2018 at 22:24
  • $\begingroup$ 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. $\endgroup$
    – Aryeh
    Sep 26, 2018 at 9:13

Your Answer

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

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