Abstract
We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor $M$ from the true distribution $\mu$ by the algorithmic complexity of $\mu$. Here we assume we are at a time $t > 1$ and have already observed $x = x_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of algorithmic complexity of $\mu$ given $x$, plus the complexity of the randomness deficiency of $x$. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.
Introduction
In the realm of algorithmic information theory, Ray Solomonoff’s universal induction stands as a theoretical gold standard for sequence prediction. Solomonoff proved that a universal predictor $M$—which aggregates all possible computable explanations for a dataset—will eventually converge to the true distribution $\mu$ of any sequence. His landmark result showed that the total cumulative error is bounded by the algorithmic complexity of the environment, $K(\mu)$.
However, Solomonoff’s bound is a "day zero" estimate. It provides a global limit on error from the start of the sequence but offers little insight into expected future performance after a significant amount of data has already been observed. Intuitively, as we observe more data, we should "learn" the underlying distribution, and our future error bounds should shrink. This paper by Chernov and Hutter addresses this gap by providing tighter, posterior bounds on future prediction errors.
The Problem with Standard Conditional Complexity
To quantify what is left to learn after observing a prefix $x$, one might naturally turn to conditional Kolmogorov complexity, $K(\mu|x)$. In theory, this measures the information required to describe $\mu$ given that $x$ is already known.
However, standard conditional complexity behaves poorly in the context of growing sequences. Because the length of the data $\ell(x)$ can itself be used to encode information, $K(\mu|x)$ is not monotonic; it can actually increase as more data is observed. This "length problem" makes standard complexity an unreliable metric for quantifying the remaining uncertainty in a learning process. If the complexity of the environment can spike simply because we observed more bits, it fails to capture the intuitive notion of progressive learning.
Methods and Definitions
The authors propose a more robust framework for posterior bounds using two primary innovations:
1. Monotone Conditional Complexity ($K_*$)
To resolve the non-monotonicity of standard complexity, the authors introduce $K_*(\mu|x*)$. Unlike standard measures, this version is specifically designed for sequence prediction. It requires that if a program generates a distribution $\mu$ given a prefix $x$, it must remain consistent and generate that same $\mu$ for any possible future extension of $x$. This ensures that $K_*(\mu|x*)$ can only stay the same or decrease as the observed sequence $x$ is prolonged, effectively modeling the reduction of uncertainty over time.
2. Randomness Deficiency ($d_\mu$)
Even with a perfect model, a predictor can be "unlucky" if the observed data $x$ is highly atypical for the distribution $\mu$. The authors use the concept of randomness deficiency, $d_\mu(x)$, to quantify this atypicality. A high deficiency suggests that the observed prefix $x$ is not representative of $\mu$, which naturally increases the difficulty of future prediction.
Key Results
The paper establishes two major bounds for future loss (the difference between the universal predictor $M$ and the true distribution $\mu$ for all future bits):
- The Length-Dependent Bound (Theorem 1): As a baseline, the authors prove that future loss is bounded by $K(\mu|x) + K(\ell(x))$. While this confirms that learning reduces the bound, the inclusion of the $K(\ell(x))$ term means the bound still grows logarithmically with time, a vestige of the limitations of standard complexity.
- The Monotone Bound (Theorem 7): This is the paper's central contribution. Using the new monotone complexity, the future loss is bounded by: $$K_*(\mu|x*) + K(\lceil d_\mu(x) \rceil)$$ This bound is significantly more elegant. It suggests that future error depends only on the remaining information hidden in the environment ($K_*$) and how "weird" the past data was ($d_\mu$), removing the artificial dependence on the length of the sequence.
Significance and Applications
These results are particularly impactful for deterministic sequences. For a sequence like the digits of $\pi$, once the predictor has seen enough data to identify the underlying algorithm, $K_*$ drops toward zero. The authors demonstrate that their new bound is much tighter than Solomonoff’s original bound in these cases, proving that the universal predictor "solves" deterministic rules much faster than previously thought.
While the universal predictor $M$ and Kolmogorov complexity $K$ are incomputable, they serve as the theoretical limit for all prediction and compression algorithms. This work provides the mathematical foundation for understanding how any inductive learner—even a practical one—should ideally behave as it accumulates experience.
Future Work
The authors suggest that these monotone bounds could be extended to broader Bayesian model classes and online classification problems. In such scenarios, the predictor receives specific "features" or "covariates" before making a prediction, and extending the $K_*$ framework to these contexts could provide tighter bounds for modern machine learning tasks.
Summary updated