2023/11/30 by Lu Zhou, Zhou Lu, Lu, Zhou · 1 voice · 1 citation
Computer Science · Decision Sciences · Mathematics · #Active learning (machine learning) #Advanced Bandit Algorithms Research #Algorithmic learning theory #Artificial intelligence #Cardinality (data modeling) #Class (philosophy) #Computability, Logic, AI Algorithms #Computer science #Conjecture #Consistency (knowledge bases) #Countable set #Discrete mathematics #Inductive reasoning #Inference #Learnability #Machine Learning and Algorithms #Machine learning #Mathematical economics #Mathematics #Perspective (graphical) #Probably approximately correct learning #Regret #Theoretical computer science #cs.LG
paper · pdf · doi:10.48550/arxiv.2312.00170
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/11/30 · openalex created_date 2023/12/05 · openalex updated_date 2026/07/28
Can a physicist make only a finite number of errors in the eternal quest to uncover the law of nature? This millennium-old philosophical problem, known as inductive inference, lies at the heart of epistemology. Despite its significance to understanding human reasoning, a rigorous justification of inductive inference has remained elusive. At a high level, inductive inference asks whether one can make at most finite errors amidst an infinite sequence of observations, when deducing the correct hypothesis from a given hypothesis class. Historically, the only theoretical guarantee has been that if the hypothesis class is countable, inductive inference is possible, as exemplified by Solomonoff induction for learning Turing machines. In this paper, we provide a tight characterization of inductive inference by establishing a novel link to online learning theory. As our main result, we prove that inductive inference is possible if and only if the hypothesis class is a countable union of online learnable classes, potentially with an uncountable size, no matter the observations are adaptively chosen or iid sampled. Moreover, the same condition is also sufficient and necessary in the agnostic setting, where any hypothesis class meeting this criterion enjoys an O(√(T)) regret bound for any time step T, while others require an arbitrarily slow rate of regret. Our main technical tool is a novel non-uniform online learning framework, which may be of independent interest.