Turing-Universal Learners with Optimal Scaling Laws

Preetum Nakkiran

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},
}

Loading related content...

Figure