Asymptotic equivalence of Akaike Information Criterion and cross-validation?

Question

I've been studying information criteria for a while now from the book of Konishi et al. and I came across a chapter where the authors refer to publication made by Stone in 1977, in which he proves the claim that Akaike Information Criteria (AIC) and cross-validation are asymptotically equivalent. In my reference book this proof is also demonstrated in a more general information criterion case. This claim, as I've understood, should be true both in linear and nonlinear regression, but the form of the information criterion is not the same in all cases.

I was shown an example where the claim made by Stone seems not to hold and I wish to better understand what's going on under the hood. Here is the problem:

Take the following classifier model:

$$f(x)=\text{sign}(\sin(tx)),\;\;t>0.$$

Our task is to select such a frequency parameter $t$ such that a given data set $(x_1, y_1), ...(x_n, y_n)$, where $x_i\in\mathbb{R}$ and $y\in\{-1, 1\}\;\forall\,i$ is classified as well as possible. The values of the $y_i$s are labels of the data points and are selected randomly. It is known that no matter what data set we have, we can always select such a value of $t$ so that we get a perfect classification. In below is an example illustration of the function $f(x)$ which correctly classifies all data points:

The argument of this example is that because such a $t$ always exists that produces a perfect classification, so the squared error term in $AIC$ is zero and we left with only the bias term, which in this case would be $2*1=2$ ($t$ only parameter), so $AIC=2$.

In case of a leave-one-out cross-validation (LOOCV), we would get asymptotically a classification error where approximately $50$% of the data points were classified wrongly, since the classifier can not guess the labels of the test points due the random phenomena.

So AIC-value would be $2$ and LOOCV would have a value of $CV=\sum_{i=1}^n (y_i-f(x_i))^2 = $ $4n/2=2n\;$ ($50$% of data points misclassified) no matter how many data points we have.

My question: Does this prove that Stone's claim is wrong? Or is there a fundamental misunderstanding on how AIC should be applied here?

P.S. please ask me if you need more information.

Answer 1

Quoting Stone's paper:

The key assumption that gives our asymptotic equivalence with Akaike's criterion is: The conditional distribution of $y$ given $x$ in the distribution $P$ is $f(y\mid x,\theta^*)$ for some unique $\theta^* \in \Theta$, that is, the conventional model ${f(y\mid x,\theta), \theta \in \Theta}$ is true.

Since each $y_i$ is generated randomly, it is not the case that the model implied by the classifier is true, so the purported counterexample violates this key assumption.

Also notice that if a $t$ exists that accurately classifies any dataset, then more than one $t$ exists for any particular dataset. To see this, imagine some dataset and then create two new datasets by augmenting the initial one with new observations until the $t$ found for each of the new datasets is found to be different. Then the initial subset of data would be correctly classified with two different parameter values. Then this counterexample also violates the uniqueness requirement assumed in maximum likelihood-related derivations. This means that, asymptotic equivalence aside, $AIC$ shouldn't even be used in this scenario.