# Turing-Universal Learners with Optimal Scaling Laws

arXiv: https://arxiv.org/abs/2111.05321 · HTML: https://mlsanity.com/paper/2111.05321/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 9 Nov 2021.

## Builds on (most cited first, 12 of 12)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Deep Learning Scaling is Predictable, Empirically](https://mlsanity.com/paper/1712.00409/) (2017)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [A Constructive Prediction of the Generalization Error Across Scales](https://mlsanity.com/paper/1909.12673/) (2019)
- [Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2002.02561/) (2020)
- [Learning Curve Theory](https://mlsanity.com/paper/2102.04074/) (2021)
- [The Shape of Learning Curves: a Review](https://mlsanity.com/paper/2103.10948/) (2021)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm](https://mlsanity.com/paper/1905.10843/) (2019)

## Built on by (most cited first, 4 of 4)

- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Understanding Visual Feature Reliance through the Lens of Complexity](https://mlsanity.com/paper/2407.06076/) (2024)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

For a given distribution, learning algorithm, and performance metric, the rate of convergence (or data-scaling law) is the asymptotic behavior of the algorithm's test performance as a function of number of train samples. Many learning methods in both theory and practice have power-law rates, i.e. performance scales as n-α for some α > 0. Moreover, both theoreticians and practitioners are concerned with improving the rates of their learning algorithms under settings of interest. We observe the existence of a "universal learner", which achieves the best possible distribution-dependent asymptotic rate among all learning algorithms within a specified runtime (e.g. O(n2)), while incurring only polylogarithmic slowdown over this runtime. This algorithm is uniform, and does not depend on the distribution, and yet achieves best-possible rates for all distributions. The construction itself is a simple extension of Levin's universal search (Levin, 1973). And much like universal search, the universal learner is not at all practical, and is primarily of theoretical and philosophical interest.