Complexity-Theoretic Universal Inductive Inference

Solomonoff’s theory of universal inductive inference (Inf. Control., 1964) provides a framework for predicting a future observation from past ones generated by an arbitrary randomized Turing machine. The theory is founded on the notion of resource-unbounded Kolmogorov complexity, and thus Solomonoff’s approach cannot be realized as a finite-step algorithm. In this paper, we develop a complexity-theoretic counterpart of Solomonoff’s theory. We construct a polynomial-time universal inductive inference algorithm that extrapolates a sequence of symbols generated by any unknown t-time randomized Turing machine in time polynomial in t, assuming that time-bounded Kolmogorov complexity can be computed in average polynomial time. Previously, it was not even known whether distributional learning for all polynomial-size circuits—an i.i.d. analogue of inductive inference—is feasible if NP is easy on average. Moreover, without any unproven assumption, we characterize a distribution of sequences for which there exists an efficient inductive inference algorithm by the notion of prequential compression. We also construct an optimal efficient inductive inference algorithm that performs as well as any other efficient algorithms. Our universal inductive inference algorithm relies on (1) a new algorithmic proof of a chain rule for time-bounded algorithmic information, and (2) an online algorithm that boosts the “confidence” of our inductive inference algorithm.