Turing-Universal Learners with Optimal Scaling Laws

Preetum Nakkiran

Introduction

In the pursuit of artificial general intelligence, the machine learning community has become increasingly focused on "scaling laws"—the empirical observation that model performance improves predictably as a function of data, compute, and parameters. Researchers dedicate significant effort to engineering specific architectures, such as Transformers or ResNets, to optimize these scaling rates for particular domains. However, a fundamental theoretical tension persists: the "No-Free-Lunch" (NFL) theorems suggest that no single algorithm can be optimal across all possible data distributions.

This paper challenges the practical interpretation of NFL theorems by demonstrating the existence of a "universal learner." The author proves that a single, explicit algorithm can match the best possible asymptotic scaling rate for any computable distribution, effectively "solving" the problem of optimal algorithm design from a purely theoretical, asymptotic perspective.

The Turing-Universal Learner ($A^*_T$)

The proposed algorithm, $A^*_T$, is a meta-learner rooted in algorithmic information theory and a variation of Levin’s universal search. Rather than relying on a fixed architectural bias, $A^*_T$ systematically explores the space of all possible computable learning algorithms.

For a dataset of size $n$, the algorithm proceeds through four primary stages:

  1. Enumeration: It generates the first $\log n$ Turing Machines (TMs) in lexicographic order. This set represents all "short" computable learning algorithms, including any architecture a human might reasonably design.
  2. Training: Each of these TMs is executed on 99% of the available data for a specified time duration $T(n)$.
  3. Validation: The remaining 1% of the data serves as a holdout set to evaluate the empirical performance of each TM's resulting predictor.
  4. Selection: The algorithm outputs the predictor that achieved the lowest error on the holdout set.

A more flexible variant, $A^+$, is also described. This version eliminates the fixed time bound by running all possible TMs in parallel and updating its best prediction as more compute becomes available over time.

Theoretical Guarantees

The core contribution of the paper is a mathematical guarantee on the learning curve $G^*(n)$ of the Universal Learner. The author proves that if there exists any algorithm $A$ that runs in time $T(n)$ and achieves a learning curve $G(n)$ for a distribution $\mathcal{D}$, then the Universal Learner $A^*$ satisfies:

$$G^*(n) \leq G(0.99n) + O\left(\sqrt{\frac{\log \log n}{n}}\right)$$

This result implies that $A^*$ matches the best possible rate (e.g., a power-law $n^{-\alpha}$) for any distribution, incurring only a polylogarithmic slowdown in runtime. If an optimal learner exists for a task, the Universal Learner will eventually perform just as well.

Resolving the No-Free-Lunch Paradox

The paper resolves the apparent contradiction with No-Free-Lunch theorems through a "quantifier shift." Traditional NFL theorems state that for every algorithm, there exists a distribution on which it performs poorly ($\forall A, \exists \mathcal{D}$). In contrast, this work demonstrates that there exists a single algorithm that eventually performs optimally for every distribution ($\exists A^*, \forall \mathcal{D}$). By focusing on the limit as $n \to \infty$ and restricting the competition to computable algorithms, the "Free Lunch" becomes theoretically possible.

Discussion: The Asymptotic Trap

While the existence of $A^*_T$ is a significant theoretical milestone, the author emphasizes that the algorithm is strictly a theoretical construct and is not intended for practical use. The "transient phase"—the amount of data $n$ required before the universal learner begins to outperform specialized algorithms—is astronomically large. For $A^*_T$ to "discover" a complex modern architecture like a Transformer, $n$ might need to exceed the number of atoms in the observable universe.

This serves as a cautionary tale for the field. It suggests that "optimal asymptotic scaling" is a surprisingly weak criterion for evaluating learning algorithms. If a brute-force search can satisfy the definition of an "optimal learner," then the metric fails to capture the inductive biases that make modern deep learning successful in the finite-data regime.

Conclusion

The existence of a Turing-Universal Learner proves that, asymptotically, the search for the "best" learning algorithm is over. However, this revelation shifts the burden of research from asymptotic optimality to the study of algorithmic progress in finite-sample regimes. The challenge for future work is to develop metrics that explain why specific architectures like ResNets or Transformers are efficient in practice, whereas a universal search—despite its theoretical optimality—remains useless for real-world applications.

Summary updated

Abstract

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(n^2)$), 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.
BibTeX
@misc{nakkiran2021turing,
  author = {Preetum Nakkiran},
  title = {{Turing-Universal Learners with Optimal Scaling Laws}},
  year = {2021},
  eprint = {2111.05321},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.05321},
}
Figure