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.


  1. Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.
  2. Jerome H. Friedman, Robert Tibshirani, and Trevor Hastie. The Elements of Statistical Learning. Springer. 2001.
  • $\begingroup$ This is probably of minor importance to the core of the discussion, but you're having index problems when splitting you dataset between train and test. Are your samples (and labels) indexed between $1$ and $N$ or between $1$ and $2N$ ? $\endgroup$ – Hugo Manet Feb 21 at 17:11
  • $\begingroup$ My samples are indexed between 1 and 2N. Regarding (2), this amounts to saying that the model must memorise the labels Y_i. $\endgroup$ – Aidan Rocke Feb 21 at 17:22
  • $\begingroup$ What is your question, specifically? $\endgroup$ – D.W. Feb 22 at 0:41

I think this is a similar approach to Shnor's Martingale characterisation of algorithmic randomness, I have sent you an email with more info, but it is a potential nice non-overfitting test and also alternative characterisation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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