Solomonoff Induction and Singular Integrals

This paper explores the deep connection between two distinct frameworks for measuring model simplicity: Solomonoff induction, which uses Kolmogorov complexity to assign a priori probabilities to data, and Singular Learning Theory (SLT), which uses the geometry of parameter spaces to analyze the asymptotic behavior of Bayesian evidence. The authors seek to bridge these worlds by showing how the learning coefficient—a geometric measure of model complexity—emerges naturally within the Solomonoff distribution.

The authors construct a specific monotone Turing machine that acts as a universal sampler for any computable Bayesian model. By reorganizing the sum defining the Solomonoff distribution, they show that it contains Riemann sums that approximate the Bayesian evidence integral of these models. They prove that for any computable Bayesian model, there exists a fixed machine whose induced semimeasure agrees with the model's evidence up to a constant factor. This allows them to apply Watanabe’s free-energy asymptotics to derive an upper bound on the code length of data generated by such models.

The study establishes that the Solomonoff distribution provides a universal upper bound on the code length of data, where the coefficient of the log n term is precisely the learning coefficient of the underlying model. This confirms that the learning coefficient, which measures the effective complexity of a singular model, is a fundamental component of the Solomonoff prior. The authors show that the additive constant in this bound depends only on the description of the model, not on the sample size or the data itself, effectively unifying algorithmic information theory with the geometric study of statistical learning.

This work provides a formal bridge between the discrete, program-based view of intelligence (Solomonoff induction) and the continuous, geometry-based view of learning (SLT). By showing that the learning coefficient appears as a coefficient in the Solomonoff distribution, the authors provide a rigorous foundation for why simple models are preferred in both algorithmic and statistical contexts. This insight is crucial for understanding the behavior of complex models, such as neural networks, where singular learning theory is increasingly used to explain generalization and phase transitions.