Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

Abstract: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 $\nu$ are drawn from a prior $w_{\nu}$, minimizing population log-loss recovers the corresponding Bayesian mixture predictor $\xi=\sum_\nu w_\nu\nu$. 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 \emph{approximately} optimal predictors. This raises a natural question: \emph{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 $\rho$ satisfying $D_{KL}(\xi \|\rho)\leq \eta$ retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor $\xi$ has error $O(\log(1/w_\mu))$ in an environment $\mu$, we establish a tight $\Theta(\eta/w_\mu)$ bound on the excess error of $\rho$ relative to $\xi$. 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(\eta)$. 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}(\xi\|\rho)$ could be unbounded. [For the full abstract, see the paper.]

Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2610.29289 [cs.LG]

(or arXiv:2610.29289v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.29289 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.