When can a learning function be realized as a computer program?
The paper Computable Universal Online Learning by Dariusz Kalociński (IPI PAN) and Tomasz Steifer (IPPT PAN) has been accepted for presentation at NeurIPS 2025, one of the world’s leading conferences on machine learning and artificial intelligence.
The authors address a fundamental question in learning theory: when can a learning function be realized as a computer program? Their study concerns the mathematical model known as universal online learning, in which the learner is required to make only finitely many mistakes on each realizable data sequence, without any uniform bound on the number of mistakes across all such sequences.
Although both universal learning and computable learning have been studied extensively in the past, the authors show that their combination is far from straightforward. In particular, they prove that there exist relatively simple hypothesis classes that are theoretically learnable, yet cannot be learned by any function realizable by a computer program. This result reveals a gap between theoretical learnability and actual algorithmic implementability.
The analysis also provides full characterizations in both the agnostic setting—where data sequences need not come from the target class—as well as in the proper-learning setting, where the learner must always output a hypothesis from the class under consideration. The results uncover important connections between the learnability of hypothesis classes and their topological structure, offering new insights into the limits of when learning functions can be formally realized by algorithms.
The research was carried out as part of the project entitled: "Computable structure theory, and philosophy of mathematical structuralism" financed by the National Science Centre (NCN), project no 2023/49/B/HS1/03930.