Computable universal learning
Dariusz Kalociński, Tomasz Steifer
Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al.~(STOC´21). In this model, there is no 'true' hypothesis fixed in advance; instead, an Adversary---playing the role of Nature---can change their mind for as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve finite number of mistakes while using a strategy that can be implemented as a computer program. We show that universal learning does not imply computable universal learning, even if the class of hypotheses is presented in computable way. We then study the agnostic variant of computable universal learning and provide an exact characterization of classes learnable in this sense. We also consider a variant of proper universal learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.