One World Seminar on Mathematics of Machine Learning

Abstract: Classical statistical theory is insufficient to explain the successes of general-purpose AI models, because it depends on handcrafted inductive biases that it cannot justify. No Free Lunch (NFL) theorems force any learner that beats chance on some environments to underperform on others. We might hope that past experience informs which environments to expect, but NFL applies equally to meta-learning. Thus, any method that makes meaningful predictions necessarily begins with an inductive bias external to the data. Choosing to bias toward short programs yields Solomonoff induction (SI), whose performance is competitive against all computable learners – albeit up to “constants” that become large when comparing against specialized methods that exploit background information. We therefore relativize SI to an information vantage point, biasing toward short programs with access to all preexisting information. This reframes the inductive bias: instead of seeking some absolute notion of simplicity, we favor accessibility with respect to our vantage point. An algorithm can only outpredict the relativized SI to the extent that its code contains additional information about the data, and no algorithm can generate such information. While SI is incomputable and hence not a practical algorithm, it provides a formal optimum for inference in the limit of infinite compute, and there is evidence to suggest that frontier AI systems roughly approximate it. Thus, the only known answer to meta-NFL is rooted in algorithmic information theory, which we should expect to play a fundamental role in explaining the generalization behavior of modern (and future) AI systems. Reference: https://djsutherland.ml/papers/nfl-ait.pdf

Abstract: The Solomonoff distribution M assigns an a priori probability to a finite binary

string z by summing over all programs whose output begins with z, a program of

length ℓ weighted by 2−ℓ: the likely strings are those with many short explanations.

This is apparently a purely discrete notion of complexity. However, Riemann sums

are also countable. We show that the sum defining M contains, suitably reorganised,

Riemann sums approximating the Bayesian evidence of any computable statistical

model — singular integrals whose asymptotics are governed by Singular Learning

Theory and, through it, by invariants of algebraic geometry. Concretely, for every

computable Bayesian model we construct a single monotone Turing machine whose

induced semimeasure agrees with the evidence Zn up to a uniform multiplicative

constant. For a computable Bayesian model satisfying in addition the hypotheses of

Watanabe’s free energy asymptotics, it follows that data Xn = X1···Xn drawn i.i.d.

from the true distribution satisfies −log M(Xn) ≤ nLn(w0) + λlog n−(m−1) log log n+ OP(1),

where Ln is the empirical loss, w0 an optimal parameter, λ the learning coefficient,

and m its multiplicity. The learning coefficient, a geometric measure of model

simplicity, thereby appears within the Solomonoff distribution as the coefficient of

log n in an upper bound on code length.