“Turing-Universal Learners With Optimal Scaling Laws”, Preetum Nakkiran2021-11-09 (AI scaling; similar)⁠:

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 (eg. 𝒪(n²)), while incurring only poly-logarithmic 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 (Levin1973).

And much like universal search, the universal learner is not at all practical, and is primarily of theoretical and philosophical interest.

Similar Links: