Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

Why large language models trained via log-loss minimization over massive and diverse datasets exhibit broad capabilities and generalizable skills is not yet fully understood. Grau-Moya et al. (ICML 2024) offer a conceptual explanation through the lens of meta-learning: if sequence-generating environments ν are drawn from a prior w ν, minimizing population log-loss recovers the corresponding Bayesian mixture predictor ξ= sum νw νν. In the idealized limit in which w is a universal prior, the optimal predictor corresponds to Solomonoff universal induction. Practical machine learning algorithms, however, generally produce only approximately optimal predictors. This raises a natural question: Does the prediction performance remain robust under approximation? In this paper, we first provide a tight bound on the worst-case effect of approximation on prediction error. We show any predictor ρ satisfying D KL(ξ|ρ) at most η retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor ξ has error O((1/w μ)) in an environment μ, we establish a tight Θ(η/w μ) bound on the excess error of ρ relative to ξ. Thus, approximation can substantially degrade performance in environments assigned small prior probability. In sharp contrast, when environments are averaged according to prior w, we prove that the excess prediction error is only O(η). Furthermore, we establish a distribution-shift theorem for dominated shifts from a training prior w to a test prior w', interpolating our average-case and worst-case guarantees. Finally, we extend our robustness analysis to a finite-sampling setting relevant to learning universal predictors with neural networks and Transformers, where D KL(ξ|ρ) could be unbounded. [For the full abstract, see the paper.]