Motivation:
The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of algorithmic randomness is transformation-invariant. I was motivated to find such a theorem for a couple reasons.
Such a theorem may be used to perform empirical tests using machine learning to determine whether a dataset was sampled from an algorithmically random process as well as to test extraordinary claims that a machine learning model can efficiently simulate algorithmically random processes.
Might this theorem be known by a particular name?
The learning problem:
Let's suppose $F_{\theta}$ is a function space that is useful for statistical learning(ex. Deep Neural Networks) such that $D_N = (X_N,Y_N)$ is a dataset where $X_N=\{X_i\}_{i=1}^{2N}$, the $X_i$ are sampled i.i.d. from a discrete random variable $X$, and $Y_N=\{Y_i\}_{i=1}^{2N} \in \{0,1\}^{2N}$ are the class labels.
If $D_N$ is split into balanced training and test sets $D_N^\text{train}$ and $D_N^\text{test}$ then we have $D_N^\text{train}=(X_N^\text{train},Y_N^\text{train})$ and $D_N^\text{test}=(X_N^\text{test},X_N^\text{test})$ such that $\lvert X_N^\text{train} \rvert = \lvert X_N^\text{test} \rvert = N$ and $X_N^\text{train} \cup X_N^\text{test} = X_N$.
Furthermore, we shall assume that the training and test sets are balanced so we have:
\begin{equation} \frac{1}{N} \sum_i Y_i^\text{train} = \frac{1}{N} \sum_i Y_i^\text{test} = \frac{1}{2} \tag{1} \end{equation}
Defining algorithmic randomness:
Now, $X$ is algorithmically random relative to $F_{\theta}$ if $X$ is incompressible relative to $F_{\theta}$ in the sense that for any choice of train-test split we have:
\begin{equation} \mathbb{E}[K(X |F_{\theta})] = \min_{f \in F_{\theta}} \mathbb{E}[K(X |f)] \sim N \cdot \ln \lvert X \rvert \tag{2} \end{equation}
where I used the fact that the expected Kolmogorov Complexity equals the Shannon entropy, and applied the Shannon source-coding theorem to i.i.d. data.
The conjecture:
In consequence, (1) implies that for a particular sample $X_N \sim X$ it may be possible to find $f \in F_{\theta}$ such that $\forall i \in [1,2N], f(X_i) = Y_i$ on the condition that the Kolmogorov Complexity:
\begin{equation} K(f) \sim 2N \tag{3} \end{equation}
as this would amount to memorisation and not discovering regularities in $D_N$ since $X$ is algorithmically random relative to $F_{\theta}$. To be precise, if an arbitrary mathematical transformation $T$(ex. random matrix) is applied to $D_N$ so:
\begin{equation} X'_N = T \circ X_N \tag{4} \end{equation}
given that $f(X_i)=Y_i \implies \delta_{f(X_i),Y_i} = 1$, the solution to the empirical risk minimisation problem may be formulated as follows:
\begin{equation} \hat{f} = \max_{f \in F_{\theta}} \frac{1}{N} \sum_{i=1}^N \delta_{f(X'_i),Y_i} \tag{5} \end{equation}
and for large $N$, the expected performance on the test set is approximated by:
\begin{equation} \lim_{N \to \infty} \frac{1}{N} \sum_{i=N+1}^{2N} \delta_{\hat{f}(X'_i),Y_i} = \frac{1}{2} \tag{6} \end{equation}
Note: I am implicitly interested in natural signals which exhibit algorithmic randomness, and the transformations $T$ are arbitrary to the extent that they don't change the phase-space dimension of the processes responsible for generating natural signals.
References:
- Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.
- Jerome H. Friedman, Robert Tibshirani, and Trevor Hastie. The Elements of Statistical Learning. Springer. 2001.
