When Is Inductive Inference Possible?
Authors: Zhou Lu
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Inductive Inference
Online Learning
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We prove a sufficient and necessary condition for inductive inference: the hypothesis class H is a countable union of online learnable classes.

Abstract: 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 $\tilde{O}(\sqrt{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.
Our main technical tool is a novel non-uniform online learning framework, which may be of independent interest.

When Is Inductive Inference Possible?
Zhou Lu
Princeton University pooul@princetoo.com edu
Abstract
Can a physicist make only finite number of errors in the eternal quest to un- cover 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 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, exemplified by Solomonoff induction for learning Turing machines. In this paper, we provide a tight characterization of inductive inference by establishing 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 online learnable classes, potentially with uncountable size, matter the ob- servations are adaptively chosen or iid sampled. Morcover, the same condition is also sufficient and necessary in the agnostic setting, where any hypothesis class meeting this criterion enjoys Ō D(VT) regret bound for any time step T, while others require an arbitrarily slow rate of regret. Our main technical tool is a novel non-unine non-uniform online learning framework, which may be of independent interest.
Introduction
How does one move from observations scientific laws? The question of induction, one of the oldest and most basic problems in philosophy, dates back to the 4th century BCE when Aristotle recognized deduction and induction the cornersoons of human reasoning. Unlike deduction. where conclusions are drawn logically from premises, induction extrapolates general principles from empirical observations without such certainty.
The justification of induction has historically been contentious. David Hume, in his 'Problem of Induction', argued that extrapolations based past experiences cannot reliably predict the unexperienced. Despite such skepticism, induction remains essential for advancing from specific instances general theories, deriving first principles upon which rigorous deductive reasoning built, as Aristotle put it in 'Nicomachean Ethics':
"Induction is the starting-pon which knowledge even of the universal presupposes, while syllogism proceeds from the universals."
This highlights induction's 's crucial role in human reasoning and scientific discovery. Yet, the enduring question remains: how do we model induction, and what guarantees can it offer?
Inductive inference Gold [ 1967) as the most representative mathematical abstraction of induction, provides rigorous framework for modeling induction. In inductive inference, learner aims to deduce the ground-truth hypothesis h² from hypothesis class H based on an infinite observation sequence {2t). At each round t, the learner makes binary prediction ye based on previous
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

information after observing 2,, then the true outcome ht (zt) is revealed and the learner makes an error if yt * h" (zz). For example, the hypothesis class H. can represent different physical models, and the observations are the data collected by a physicist, who refines theories based on new evidence.
The question of inductive inference is whether the learner can make finite number of errors depending on Λ in such infinite process. Unfortunately, despite its critical importance to philosophy, theories for inductive inference are notably sparse. All existing theoretical results, including the famous Solomonoff induction Solomonoff [1964a] for learning Turing machines, provide only a sufficient condition on the size of the hypothesis class: inductive inference is possible, if [ S No. i.e. the size of the hypothesis class H. is at most countable.
Clearly | I No is not necessary condition. Consider H. = [felf(()) = L E R), , it has an uncountable size but can be easily learnt with at most one error: the learner keeps predicting y/+ = 0 until error is made, then h" can be identified. In this work, provide sufficient and necessary condition for inductive inference, via a novel link to online learning theory. Our main result the following (as a consequence of Theorems II]:
Theorem 1. Inductive inference is possible, if and only if Une where each Hn is an online learnable class (a hypothesis class with finite Littlestone dimension).
As an extension, we further demonstrate that the condition H. being countable union of online learnable classes is also sufficient and necessary for the agnostic setting, where the ground-truth ht may not lie in H. For the weaker criterion of consistency where the error bound additionally depends the observation sequence, derive necessary condition which conjecture to be tight. Algorithms from previous works, examples, and technical proof's are relegated to the appendix.
1.1 Our Approach
Due to the shared spirit of sequential decision decision-making -akinn between classic online learning theory Little stone [988 and inductive inference Solomonoff] [1964a]. seek to cast the problem of inductive and agnostic
inference within the online learning paradigm, which can handle uncountable-sin hypothesis classes. The challenge is that traditional online learning theory itself does not fully capture the nuances of inductive inference, for its focus on an adaptive adversary and worst-case uniform error bounds.
To bridge the gap between inductive inference and online learning, we propose a new framework termed non-uniform online learning to bypass these differences. Different from classic online learning, this setting considers an oblivious choice of the ground-truth hypothesis (Nature can't change her mind on the choice of h²) and non-uniform guarantees (error bound can vary for different h*) It can be seen as a natural generalization of the non-uninn non-uniform PAC learning notion Benedek and Itai] [1888] to the online setting. The comparison between the protocols of classic and non-uniform online learning is made below.
Classic online learning
Non-uniform online learning (inductive inference)
1: Given domain X' and hypothesis class H
1: Given domain X' and hypothesis class
2:
2: Nature selects ground-truth h- E H.
3: for =1=,, 1,....,, 0c do
3: for f. -== 1,..., ac do
4:
Nature presents observation 2, to Learner
4: Nature presents observation to Learner
5: Learner predicts yr
5: Learner predicts y/:
6: Nature selects a consistent he E H
6:
7: Nature reveals the true label (xy
7: Nature reveals the true label h (xx))
8: end for
8: end for
9: Goal: uniform error bound
9: Goal: error bound can depend on ht*
In the realizable setting, non-uniform online learning is indeed equivalent to inductive inference.
containing previous results as special cases. We show that Learner can achieve a finite error bound dependent on h², if and only if H is a countable union of hypothesis classes with finite Littlestone dimensions. Furthermore, for the weaker criterion of consistency which only requires a (non- hypothesis-wise) finite error bound, we obtain necessary condition that conjecture to be tight.

---

In the agnostic setting, when H. is expressed as UnEN+ Hn where each Hr has finite Littlestone dimension da, we propose an algorithm with an O( regret bound for any time step T when h" lies in Hn. In addition, the sharpness of such characterization is demonstrated by trichotomy of regret's dependency T" through the two complementary facts: (I) long H can't It be written in this form, it requires arbitrarily slow rates (2) any non-trivial H requires 2 (()T) regret.
1.2 Related Works
Inductive inference and learning The pioneer works of Solomonoff Solomonofi 1964a b 1978 established a rigorous theoretical framework for inductive inference. Via a Bayesian approach, Solomonoff's method of prediction assigns larger prior weights to hypotheses with shorter descrip- tion lengths, providing finite-error guarantees based on the prior weight of the ground truth. The principle of Occam's Razor that simplicity leads to better learning guarantees, as the cornerstone of
Solomonoff's 's theory. plays a vital role in the evolution of statistical learning [Blumer et al. [1987]
1989]. Mitchhel] [197].. Von Luxburg and Schölkopf [2011). Harmaan and Kulkarmi [2012]. Shalev- Shwartz and Bev-David [204]]. VC dimension Vapnik and Chervonenkis' [2015]. the fundamental concept in PAC learning, is widely regarded as measure of simplicity in learning theory [Sterkenburg and Grünwald [2021). Sterkenburg 2023). Besides theoretical investigations, there is also growing
interest in the empirical inductive inference capabilities of large language models Wang et al. [2023]
Qiu et al. 2023 Honovich et al. [2022]. Gendron et al. 2023 Grau-Moya et al. [2024].
Online learning Littlestone's seminal work Littlestone
1988 on online learnability in the realiz-
able case introduced the Littlestone dimension, a combinatorial measure precisely characterizing the number of errors. This concept was extended to the learning with expert advice setting, where the weighted majority algorithm Littlestone and Warmuth [1994] achieves an Ö(v regret. Since then, online learning has expanded into diverse scenarios, including the bandit setting Auer et al.) [1995), the agnostic setting Ben- Den-David et al. [2009]. the changing comparator setting Herbster and Warmuth
1998.. and the convex optimization area Zinkevich [2003), Kalai and Vempala [005 Hazan et al.
2007
Duchi al. [001]
Hazan et al. 2016
Non-uniform learning Though less explored, the non-uniform learning framework [enedek (Benedek and
Itai [1988) which allows hypothesis-dependeer generalization bounds, is crucial for our study. For a comprehensive introduction on non-uniform learning see Shalev-Shward and Ben-David [2014).
Closely related our work in non-uniform learning are Wu and Santhanam [202]] and Bousquet et al.
[202T]. The work of Wu and Santhanam [202 considered the setting they named EAS (eventually almost surely), which demands finite error bounds with probability 1, when the data stream is iid samples from some known distribution. The work of Bousquet et al.) [2021] considers how fast the generalization error decreases as the size of training data increases, based on new combinatorial structure called the VCL. tree. In addition to inductive bias on the hypothesis class, there is extensive research on universal consistency under stochastic process assumptions on observations Stone 1977). Antos and Lugosi| [1996]. Hanneke et al. 22200. [Hanneke [021] Blanchard et al. [2022]. Blanchard 2002]. These works on universal learning typically utilize a k-nearest neighbor type algorithm for the constructive proof, which doesn't 't fully align with practical scenarios of human reasoning and scientific discovery.
2 Setup
Given an infinite domain X' and the set of all 0/1 loss functions on X: S = =* we consider a non-empty subset H S as the hypothesis class. Both X' and H are known Learner and Nature in advance. In inductive inference, Nature iteratively presents Learner with 2; E X' and asks Learner to predict ÿ. (0, 1), then reveals the the true label ye E {0.1) to Learner, while Learner aims to make as few errors as possible by inferring H.
Formally, consider learning algorithm A of Learner, any function of historical observations (thus the learning algorithm is adaptive). In particular, a deterministic learning algorithm is any function with the following domain and codomain
UnEn (T%21 (X x (0, (0,1)) x x) (0,
A randomized learning algorithm is similarly defined by setting the codomain [0, 1].
3

---

Throughout this paper, we will work with the following general sequential game between Learner and Nature. Before the game begins. Learner fixes a learning algorithm A. time step N some is presented by Nature to Learner, and Learner predicts
dt A (2, x y.) x {2+)).
Then Nature reveals the true label yt and Learner makes an error je: + yt. We write x 1I { and the set of all possible x as X. For simplicity, we assume the continuum hypothesis. i.c. 2 N1.
In the following, we discuss different ways of Nature choosing (Ia, Vt) and the criteria of learning, corresponding to different notions of learnability.
2.1 Classic Online Learning
In the classic online learning setting, there is no restriction on Nature's choice of 2t, and the only restriction on Ye is the existence of a hypothesis h E H. consistent with history: vi t, hf (2,) y/- Classic online learnability is characterized by a combinatorial quantity of the hypothesis class H. called the Littlestone dimension Ld)m(H).
Definition 2 (Littlestone dimension). We call a sequence of data points æ1,". 222--1 X'
shattered tree of depth d, when for all labeling (y);". .ya) (0, 1]d there exists h H such that for all t E [d] we have that h(aa)) = yr. where
[-1
4 2 +
Σ
32 2,22-113 1-j
The Littlestone dimension Ldim(H) of a hypothesis class H is the maximal integer M such that there exist a shattered tree of depth M. When no finite M exists, we write Ldim(H) = co. We call any hypothesis class with finite Ldim Littlestone class.
It's clear from the definition of Littlestone dimension, that no algorithm can have a mistake bound strictly smaller than Ldim (H). Moreover, there is deterministic learning algorithm SOA 3 which is guaranteed to make at most Ldim (H) errors.
Lemma 3 (Online learnability Littlestone 1988)) When Ldim(H) < co, no learning algorithm makes errors strictly fewer than (H). addition, Algorithm 3 makes most Ldim (H) errors.
2.2 Inductive Inference as Non-uniform Online Learning
Nature's ability of selecting a changing h adaptively contradicts the principles of inductive inference that the ground-truth should be consistent. To set the stage for inductive inference, the first change we make to classic online learning is requiring Nature to fix a ground-trun truth hypothesis h" in advance and sets y/- ht (xx) thereforth. The main criterion we consider in this paper is then hypothesis-wise error bounds depending on h", besides the dependence on H.
The reason for mainly considering hypothesis- wise guarantees is twofold: (1) it follows the con- ventions of inductive inference literature (2) uniform guarantee is too strong for the problem of induction, while consistency guarantee is weak in that it's fully posterior and thereby less informative. Throughout this paper, all discussions are made under the above setting, unless otherwise specified (clasiic/onsisteney)) Denote the number of errors made by a learning algorithm A when Nature chooses and presents x to Learner as
err e (h,
2
10 - h(2z)l E OU
we define non-uniform online learnability:
Definition 4 (Non-uniform online learnability). We say hypothesis class H. is non-uniform online learnable, if there exists a deterministic learning algorithm A, such that
3m H N+, Wh H. Vz E X, err, I m(h).
In the definition above, Nature is allowed to adaptively choose x (for deterministic Learner, adaptive and oblivious adversaries are equivalent). A stronger yet common assumption is each drawn independently from some unknown μ fixed by Nature in advance. Let be equipped with some fixed separable o-algebra, define non-uniform stochastic online learnability as below.

---

Definition 5 (Non-uniform stochastic online learnability). We say hypothesis class H. is non- uniform stochastic online learnable, there exists a deterministic learning algorithm A, such that
3m H N Vh H. Vu, Pa-yy (ert x) S m(()) =
Equivalence to inductive inference the non- unn-uniform online learnability notions introduced above are indeed equivalent to the problem of inductive inference, with different rules of observations { Previous results on inductive inference can be written as special cases under our framework with countable-Sie sized hypothesis class H. The most important example is learning computable functions, previously settled by Solomonoff induction, see also Li et al. [2008]. our language, it concerns non-uniform online learning problem with H. being set of (binary) computable functions, which has a countable size. particular, H can be the set of possible infinite sequences generated by Turing machines, with X' = N+ and T2- L.
2.3 Agnostic Non-uniform Online Learning
So far we have assumed Nature must choose such that the whole data sequence is consistent with some h H. However, it's rather strong assumption that the ground-trute h² is already included in the hypothesis class in consideration. This motivates the study on the more realistic agnostic learning setting: Nature can select arbitrary ze; y/ in an oblivious way, where the sequence of re. yt is not necessarily realizable by some hypothesis h E H.
It's known that for the agnostic online learning setting, even hypothesis class H with finite Ldim (H) can make (V (TLLdimim)) errors in expectation for time horizon 7 Ben-David al. [2009]. making the finite error criterion less interesting. As a result, we will consider sub-linear dependence on T in the error bound. Agnostic non-uniform online learnability is defined as below.
Definition 6 (Agnostic non-uniform online learnability). We say hypothesis class H is agnostic non-uniform online learnable with rate r(T), if there exists a learning algorithm A, such that
3m H N+, Vr X, X, E {0, Vh E E
E
mmh)r(TT)
3 Non-uniform Guarantees in the Realizable Setting
In this section we study non-uniform (stochastic) online learnability in the realizable setting. We provide a complete characterization by showing the learnability of H is equivalent H being countable union of Littlestone classes. This result generalizes previous inductive inference methods such as [Solomonoff] [1964a] which provide only sufficient condition H. being countable for this setting. Our analysis begins with the basic uniform case.
Definition 7 (Uniform online learnability). We say hypothesis class H. is uniform online learnable, there exists deterministic learning algorithm A, such that
3m E N+ Vh H.Yz, err (h, S m.
The next lemma shows uniform online learnability is equivalent classic online learnability.
Lemma 8. H is uniform online learnable and only if H is classic online learnable. In addition, Ldim(H) (H) is a tight error bound.
We are ready to state our main results in the realizable setting. The proof is mainly based on the structural risk minimization (SRM) technique Vapnik and Chervonenkis 1974). Wu and Santhanam (202T) which our algorithm goes over each H., one by one. Intuitively, since each H., is uniform online learnable, we can safely exclude the whole class when a certain amount of errors are made by SOA.
Theorem H is non-uniform online learnable if and only if H can be written as a countable union of hypothesis classes with finite Littlestone dimension.
5

---

Algorithm Non-uniform Online Learner
1: Input: hypothesis class H. UneN+ Hr with d, Ldim(H,,) oo, Vn E N
2: Initialize a SOA algorithm An for each Hn, and error bounds é1, 02, all equal to 0.
3: for E N+ do
4: Observe Zt--
5: Compute Je argmin, fer + n].
6: Predicts OL as A,,,
7: Observe the true label Vr-
8: For each n. E N+, update en - en. + 1 if the prediction of An is not yt-
9: end for
Proof. We discuss the two directions respectively. If: Suppose H. can be written as a countable union of hypothesis classes Hi, with finite Littlestone dimension d,, Ldim(H,) We describe learning algorithm A (Algorithm]) D which non-uniform online learns H.
Let A., be the SOA algorithm which classic online learns H., with most d,, errors. By Lemma g An also uniform online learns Hr with at most dn errors. Denote e(t, n) as the the number of errors that An, would make if it were employed in the first t steps, let
argmin, , (e(l,n) n),
the algorithm A predicts as AJ, time t.
Assume the ground-truth hypothesis It lies in Ha. then As makes at most da errors which is finite. We have that e(t, + < de + k for any L. Therefore, J. dk k for any I, meaning H will only invoke algorithms within AI. Ad, +-- Furthermore, once an A, makes more than da + & errors, will not be chosen by A anymore, thus A makes most (d& + k)² errors, and this upper bound only depends on h² and is independent of the choice of æ.
Only if': Suppose H is non-uniform online learnable, we would like show it can be written countable union of uniform online learnable hypothesis classes
For any h. denote d(h) as the maximal number of errors made as admitted by the non-uniform online learaaility,, which is guaranteed be a finite number. We denote
Hn = (h: d(hh= = nt).
Since d(h) is a finite number for every h, we have that H = UneN Now we only need to prove each Hr uniform online learnable. By applying the same algorithm A which non-uniform online learns H. on Hn, we have that the number of errors made for any / E Hy is bounded by thus Ho uniform online learnable with uniform error bound n.
As corollary, Example 22 (rational thresholds) shows the existence of class non-uniform online learnable but not online learnable, demonstrating a separation between the two notions.
Corollary 10. Uniform online learnability Ç non-uniform online learnability.
Our second result shows that non-uniform online learnability is in fact equivalent non-uniform stochastic online learnability.
Theorem 11. H is non-uniform stochastic online learnable < it's non-uniform online learnable.
Proof. We only need discuss the only if direction, since the other direction is immediate from the definitions. It's equivalent to showing the following two are incompatible: (1) H is non-uniform stochastic online Icarnable; (2) H not non-uniform online learnable.
Suppose (1) and (2) both hold, we would like to derive a contradiction. (1) implies that there exists learning algorithm A such that for any h H. there a constant n(h),, for any μ, the number of emrors made is bounded by n(h) with probability 1.
However, (2) implies for the same algorithm A, there exists h H. such that for any n, there is sequence (m) E X that the number of errors is at least by some finite time t.. Now, pick

---

== (1) we define an arbitrary discrete probability measure i over with full support. For example, we can define
pl ((
2 Vi
There is positive possibility that in the first ((n(h)+1) steps, the sequence is identical x, which incurs rhh)) n(h) errors, contradicting (1). In particular, the probability is lower bounded by
2 2 2- (((+)) 2 (m(w+))) >0.
The two theorems together imply that for both the strongest (adaptive) and weakest (stochastic) Nature's ss choice on z, the characterization for learnability the same, therein applies to any other setting in between such stochastic process Hanneke proness/Hannkke [2021] or dynamically changing environment Wu et al. [023]. As a result, Theorem[aan Theorem together imply our main result inductive inference, now that all natural choices of observation sequences share the same characterization: H is a countable union of Littlestone classes.
Non-uniform Guarantees in the Agnostic Setting
The realizable assumption implies belief that the law of nature already lies in set of hypotheses known to Learner. This however doesn't match the practical scenarios of scientific progress where theories are usually proven not perfectly correct along with the development of science.
As result, the more realistic way to consider the agnostic setting, in which pose no constraint on how Nature presents yt. with Learner's s objective to be performing as good as the best hypothesis h" from the whole class. We obtain the following regret bound showing that any countable union of Littlestone classes is also learnable in this setting.
Theorem 12. When H = UnEnt H. is a countable union of hypothesis classes with finite Littlestone dimension dns then it's s agnostic non uni-unfform learnable at rate ÖVTT), with expected regret
T
Σ
1 Bet
Σ
[ = =Ō =Oggnn-ooog)
for any x, T and E Hn. Under Ô we hide logarithmic dependences except for n.
Algorithm 2 Agnostic Non-uniform Online Learner
1: Input: a hypothesis class H = UneN+ Hi with d, = Ldim < oo, Vn E N+
2: For each Hn, initialize a Hierarchical FPL instance An, with experts being the set of Algorithm instances with L S. d, and learning rate n) = Ve. The complexity of an instance with it = is
1 (d,, + 2) log j.
3: Initialize a complexity kn = 2(log n + 1) for each expert An.
4: for E N+ do
1 5: Choose learning rate Vi
6: Sample a random vector q ~ exp. i.e. P(q: = =)= for x 0 and all i E N+
7: Output prediction Ú, of expert An which minimizes
An In
1/.
8: Observe the true label Vt-
9:
end for
Furthermore, we show Theorem indeed provides a tight characterization by the following result, that any hypothesis class which can I be written countable union of Littlestone classes requires
7

---

arbitrarily slow rates, with a different spirit than the typical Q (T) lower bound in Ben-David et al. 2009).
Proposition 13. For any hypothesis class H. if it can't be written as a countable union of Littlestone classes, then it's not agnostic non-uniform online learnable al rale Ti- for any > 0.
On the other hand, it's well-known an S2( ((VT) lower bound is inevitable, even for the simplest case with two hypothesis classes differing on only one point.
Proposition 14. As long [H] > 1, then for any Learner's algorithm and T e N+ the expected regret at time T is at least ((( ))
As result, we reach the following trichotomy that provides a complete characterization of agnostic non-uniform online learnability, including degenerate, typical, and arbitrarily slow rates, which can be seen as an online agnostic analogue to the universal learning trichotomy of Bousquet et al. [2021]
Theorem 15. There are only three possible rates of agnostic non con-uniform online learning:
H is learnable at rate 0 - H|| 1.
H is learnable at rate 6(vT)
+ H. is countable union of Littlstoone classes.
H requires arbitrarily slow rates
b H isn't II countable union of Littlestone classes.
5 Non-uniformity Versus Consistency in the Realizable Setting
In addition to hypothesis-wise wise guarantees, we can also consider the weaker notion of consistency, which needs no uniformity over x for a fixed h and only requires the number of errors to be finite.
We will restrict our attention to the realizable setting only, since non non-hypothesis-iii guarantees are ill-defined in the agnostic setting.
Definition 16 (Consistency). A hypothesis class H. is consistent, if there a deterministic algorithm A, such that A .) co for any x)) chosen by Nature.
In the classic online learning setting, it was proven by Bousquet et al. 2021 that a hypothesis class H is consistent, if and only if H has an infinite-depth shatter tree. Example 21 (integer thresholds) is consistent but not online learnable, showing that uniformity * consistency in the classic online learning setting.
To characterize consistency in our setting where Nature must fix h² beforehand, we introduce the following definition on the size of an infinite (binary) tree, such that besides the set of nodes V, each edge is marked with some number E {0, 1} where left edges are 0 and right edges are 1.
Definition 17 (Size of infinite tree). Given hypothesis class H. for any infinite tree, a countable branch 6 = (V1, 21, 02 22,.... where ut+1 is the z--ch of vt, is called realizable if there is some e H. consistent on The size of this tree is
(blb is realizable)| c NU UN,
In addition, we say the tree is full-size if all branches realizable.
Example 22 (rational thresholds) has an infinite-depth shatter tree yet no Ni-size trees. Example 23 (real thresholds), however, has full-size tree. Clearly, when H has full-size tree, it's not consistent, since any deterministic Learner must make no correct predictions on one of the branches. We obtain a stronger necessary condition for consistency by the following result.
Theorem 18. If a hypothesis class H. is consistent in the non non-uniform (stochastic) online learning setting, it doesn't 't have any &i-size tree in which tree nodes belong to X.
Proof. Suppose for contradiction that there exists -i-size tree T while H. is consistent the same time. For each E B, let ha E H be some hypothesis consistent with b. Consider a set S = Usc of Nature's strategies, where by 8s Nature fixes hn beforehand and shows the branch to Learnr.
Now, since H is consistent, there is some Learner's 's algorithm A such that makes m, < oc errors when Nature plays for any b E B. Denote Bm {b/ms m.. we have that B Bm.
8

---

On the one hand, any countable union of countable sets is still countable, while on the other hand, [B] N,, therefore there must exists some m < oo such that |Bm-1 N1
Consider a new hypothesis set H" = (h E H/h E Bm-). Since it's a subset of H. A is also consistent on H" In particular, the tree T is still Nı-size. Central to our proof is the claim that for any Ni-size tree, there exists a node of the tree, such that both induced sub-trees of its children are -issize.
Suppose for contradiction the claim is false, denote the root as N1. we can recursively define an infinite sequence N2, .a...... such that for any 2, N, is the child of Ni-1 and N,'s brother's induced sub-tree (denoted as Ti) is at most Nizsize Now the set of realizable branches countable: besides the single branch defined by the infinite sequence, any other branch falls in one sub-tree Te. and there are only countably many such Nn-size sub-trees Tr. This contradicts the fact that the tree is Ni-size and proves the claim.
By repeatedly using the claim, we can find m² levels of nodes of the tree T
((11)), ((2,1), ((2,2))"11 +2,1)) (mm +2,2 21))
where m(,)) is the ancestor of ((141.2)-1) ((2+122/)) and each ((,))) induces an Ni-size sub-tree. Notice that any node ((i,)) need not to be ë-depth node in the tree T, and ((i.)) may be multi- generation grandfather of P(i+1.2j-1)- (())))
Now, by construction 7 shatters the m² + 2 levels of nodes, therefore any deterministic algorithm including A will make least m² errors on one of the finite branches (if we see the levels of nodes as a tree). This however contradicts the definition of B,,, which completes the proof.
((L1)
V(2.2)
(2.11)
Figure 1: An example of ((.)). Here the red paths denote realizable branches.
In addition, when is known to Learner in the non-uniform stochastic online learning setting, we strengthen result of Wu and Santhanam [202T] in which they name consistency as EAS.
Definition 19 (EAS online learnability). class H. is eas-online learnable w.r.t distribution μ4, there exists learning algorithm A such that for all h E H and μ
IP ((err x) < oo) 1.
They proved that H is eas-online learnable if and only (Theorem 7 in Wu and Santhanam (2021), where 7L' is said to be effective cover if for any h E H. there exists E Ht such that (we say covered by 1/') p(((x)) + (x)))) O. We strengthen
has a countable effective cover w.r.t j
this result by showing that in the same setting of Wu and Santhanam 2021] non-uniformity- consistency.
Proposition 20. When μ is known to Learner, class H. is non-uniform stochastic online learnable and only if H has countable effective cover w.r.t p.
any æ. varying h" any x, fixed h" NA
unknown μ. fixed h*
known μ., fixed h"
non-uniform
Us, LS=
Uw, L.S
No effective cover
O
consistent
no DO tree C
no N1 size tree
?
No effective cover
Table 1: Summary of learnabilities in the non-uniform realizable setting. LS denotes any Littlestone class. Our results are marked in red. Necessary conditions are marked blue.

---

Discussion
Summary of Results We resolve long-standing philosophical question, the question of inductive inference, via a novel link to online learning theory. Different from previous results on inductive inference, which only provide sufficient condition that the hypothesis class has countable size, we provide sufficient and necessary condition: inductive inference is possible, if and only if the hypothesis class a countable union of online learnable classes. We hope this connection offers fresh perspective that could open new avenues for research in both fields.
From the technical side, develop novel framework called non-uniform online learning, where the ground-truth hypothesis is determined in advance and hypothesis-wet -isse eπror bounds are considered. In both realizable and agnostic settings, we prove that the hypothesis class H. being countable union of Littlestone classes is the sufficient and necessary condition for learnability. Our results provide sharp characterization of inductive inference beyond countable-sinn sized realizable hypotheses.
Philosophical Interpretations Our findings reveal an intrinsic trade-off between dn and in both the error bound of Theorem the regret bound of Theorem 12] depending on how we make the countable partition H. = UeEt H.,. A finer partition can decrease the Littlestone dimension d,, of the class H., that belongs to for every H. however, at the cost of creating more classes and increasing the dependence on Such trade-off shows connection to certain philosophical debates around falsifiability, such as "the mission classify truths, not certify them" Miller [2015].
Future Directions Identifying sufficient condition for consistency remains an unresolved chal- lenge. We conjecture that having no Ni-size tree is a tight characterization. Understanding inclusion relations between different learnabilities, as outlined in the table, is also an important problem. The current work prioritizes error bounds without delving into computational constraints. It's interest- ing to study non-uniform online learnability with computable learners for this theory's practical applicability, as in Agarwal et al. 2020). Sterkenburg 20022. Hasrati and Ben-David [2023].
10

---

References
Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, and Ruth Urner. On learnability wih computable learners. In Algorithmic Learning Theory, pages 48-60. PMLR, 2020.
András Antos and Gâbor Lugosi. Strong minimax lower bounds for learning. In Proceedings of the ninth annual conference on Computational learning theory, pages 303-309, 1996.
Peter Auer, Nicolo
Yoav Freund, and Robert E Schapire. Gambling rigged casino: The adversarial multi- armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages 322-331. IEEE, 1995.
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, volume page 1, 2009.
Gyora M Benedek and Alon Itai. Nonuniform learnability. In Automata, Languages and Programming: 15th International Colloquium Tampere, Finland, July 11-15, 1988 Proceedings 15, pages 82-92. Springer, 1988.
Moise Blanchard. Universal online learning: An optimistically universal learning rule. In Conference on Learning Theory, pages 1077-1125. PMLR, 2022.
Moise Blanchard, Romain Cosson, and Steve Hanneke. Universal online learning with unbounded losses: Memory is all you need. In International Conference on Algorithmic Learning Theory, pages 107-127. PMLR, 2022.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Occam's 's razor. Information processing letters, 2776):37 1987.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the chhrin-chervvnenkis dimension. Journal of the ACM (JACM), 36(4):929-96) 965,,,,,,,, 1989.
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Ychudayoff. A theory of universal learning. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532-541, 2021.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Gaël Gendron, Qiming Bao, Michael Witbrock, and Gillian Dobbie. Large language models are not abstract reasoners. arXiv preprint arXiv:2305. 2023.
E Mark Gold. Language identification in the limit. Information and control, 10(5):447-474, 1967.
Jordi Grau-Moya, Tim Genewein, Marcus Hutter, Laurent Orseau, Grégoire Delétang, Elliot Catt, Anian Ruoss, Li Kevin Wenliang, Christopher Mattern, Matthew Aitchison, universal predictors. arXiv preprint arXiv:2401.1445 2024.
Learning
Steve Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes. The Journal of Machine Learning Research, 22(1):5751-5866 2021.
Steve Hanneke, Aryeh Kontorovich, Sivan Sabato, and Roi Weiss. Universal bayes consistency in metric spaces. In 2020 Information Theory and Applications Workshop (ITA), pages 1-33. IEEE, 2020.
Gilbert Harman and Sanjeev Kulkarni. Reliable reasoning: Induction and statistical learning theory. MIT press, 2012.
Niki Hasrati and Shai Ben-David. On computable online learning. In International Conference on Algorithmic Learning Theory, pages 707-725. PMLR, 2023.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69: 169-192, 2007.
Flad Hazan et Introduction to online convex optimization. Foundations and Trends Optimiza- tion, 2(3-4):157-33 2016.

---

Mark Herbster and Manfred K Warmuth. Tracking the best expert. Machine learning, 32:151-178, 1998.
Or Honovich, Uri Shaham, Samuel Bowman, and Omer Levy. Instruction induction: From few examples natural language task descriptions. arXiv preprint arXiv:2205. 2022.
Marcus Hutter, Jan Poland, et al. Adaptive online prediction by following the perturbed leader. 2005.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-37,, 2005.
Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008.
Nick Littlestone. Learning quickly when irrelevant attributes abound: new linear-threshold algorithm. Machine learning, 2:285-318, 1988.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-261, 1994.
David Miller. Critical rationalism: restatement and defence. Open court, 2015.
Tom M Mitchell. Machine learning. 1997.
Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang. Yoon Kim, Yejin Choi, Nouha Dziri, al. Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis refinement. arXiv preprint arXiv:2310.08559 2023.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Ray Solomonoff. Complexity-bard based induction systems: comparisons and convergence theorems. IEEE transactions on Information Theory, 24(4):422 432, 1978.
Ray J Solomonoff. A formal theory of inductive inference, part i. Information and control, 7(1):1-22, 1964a.
Ray J Solomonoff. A formal theory of inductive inference. part ii Information and control, 7(2): 224-254, 1964b.
Tom F Sterkenburg. On characterizations of learnability with computable learners. In Conference on Learning Theory, pages 3365-3379. PMLR, 2022.
Tom F Sterkenburg. Statistical learning theory and occam's 's razor: The argument from empirical risk minimization. 2023.
Tom Sterkenburg and Peter D Grünwald. The no-free-lunch theorems of supervised learning. Synthese, 199(3-4)99999-1000 -0000 2021.
Charles Stone. Consistent nonparametric regression. The annals statistics, pages 595-620, 1977.
Vladimir Vapnik and Alexey Chervonenkis. Theory pattern recognition, 1974.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. In Measures of complexity: festschrifi for alexey chervonenkis, pages 11-30. Springer, 2015.
Ulrike Von Luxburg and Bernhard Schölkopf. Statistical learning theory: Models, concepts, and results. In Handbook of the History of Logic, volume 10, pages 651-706. Elsevier, 201
Ruocheng Wang. Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D Goodman. Hypothesis search: Inductive reasoning with language models. arXiv preprint arXiv:2309.0m 05660 2023.
12

---

Changlong Wu and Narayana Santhanam. Non-uniform consistency of online learning with random sampling. In Algorithmic Learning Theory, pages 1265-1285. PMLR, 2021.
Changlong Wu, Ananth Grama, and Wojciech Szpankowski. Online learning dynamically changing environments. arXiv preprint arXiv:2302.00103, 2023.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-9368 2003.
13

---

A Algorithms from Previous Work
Algorithm 3 Standard Optimal Algorithm (SOA)
1: Input: a hypothesis class H.
2: Initialize the active hypothesis set V1 H.
3: for E N+ do
4: Observe Zt-
5: For y E {0, let Vi" = (h: h(x))) = v,h. V.).
6: Predict It = argmax, a )d))(V
7: Observe the true label Vt-
8: Update V2+1 V if yt + dt. Otherwise set Vo+1 Vz.
9: end for
Algorithm 4 Expert(i1, . ,i))
1: Input: hypothesis class H., indices i1 < ... < it.
2: Initialize the active hypothesis set V1 H.
3: for E N+ do
4: Observe Zt--
5: For E {0, let V = {h h(x)) y. h Vi).
6: Predict Jt = argmax, argmax,Ldim(V2 Ldim(V
7: Observe the true label l/+
8: Update V4+1 = V/ if yt + in and (",,"., (r.). Otherwise set V2+1 V..
9: end for
Algorithm 5 Follow the Perturber Leader (FPL)
Input: a countable class of experts E1, E2,....
2: Initialize complexity k; for each expert E, such that EiENt e-hi < 1.
3: for / E N+ do
4: Choose learning rate 7/--
5: Sample random vector ~ exp, i.c. P(q. A) - for A 2 0 and all e N
6: Output prediction de of expert E, which minimizes
[E,(),))))))) + hi Q
7: Observe the true label ye-
8: end for
B Examples
Example 21. Consider X' N+ and let H be the of all threshold functions
H {h: h(x) 1,22), n N).
The Littlestone dimension Ldim errors, by keeping predicting 0 until the first mistake. It's clear H is consistent but not uniformly classic online learnable.
However, there is simple learning algorithm with finite
Example 22. Consider X' = [0, 1). and the class of all rational thresholds
H = {h: f((x) = 1[z20] c Q}.
This hypothesis class has infinite Littlestone dimension, thereby not uniformly online learnable. However, We have the countable decomposition H = 1 where each He is singleton H. [[[22)) Thus it's 's non-uniformly online learnable.
14

---

Example 23, Consider X' = [0, 1]. and the class of all real thresholds
H = (h (xx) = 1 | C E R)-
This hypothesis class is not even EAS online learnable under the uniform distribution Wu and Santhanam [02T]. thus not consistent.
In the language of Definition 17 has a full-size infinite shatter tree. The naive way of setting the tree nodes as (2. 4 8
doesn't t give full-size tree, because the limit of some converging
branch can be one of the seen nodes. For example, consider branch with (g 3 5 9
I g I6 ..),, the limit requires the only possible consistent hypothesis to be h(x) [=2 which contradicts the
first round error h(2)) 0.
Instead, shrink the window size each round to prevent the convergence to any node seen. For example, we can half the window size then take the middle point to construct the tree which is a full-size infinite tree
1 3
3
5
11
13
2 4' 4'
16
16
16
16 64
C Omitted Proofs
We include here the omitted proofs from the main-text, which either straightforward standard in literature.
C.1 Proof of Lemma
Proof. The first claim is proven by the existence of shatter tree with depth Ldim(H). Let d Ldim(H) and set Fe to be T;, as in the definition, then Nature chooses yt = -9. Learner makes mistakes. The existence of consistent hypotheses is guaranteed by the definition of shatter tree.
For the second claim, it suffices to prove that whenever SOA makes an error, the Littlestone dimension of the active hypothesis set strictly decreases. Assume for the contrary that Ldim (V,n)) Ldim but y/ * ÿt. The definition of ýe implies Ldim VV,) Ldim(V?)) obtain a shatter tree with depth Ldim V.) + for V,, which is a contradiction.
(V) In this case, we
C.2 Proof of Lemma
Proof. We only need to discuss the only if direction, since it's clear from the definition any online learnable problem is automatically uniform online learnable. The claim is reduced to showing uniform online learnability implies online learnability.
Suppose H is uniform online learnable, then there is a learning algorithm A and finite number d, such that for any h H and choice of x E X by Nature, A makes most emrrr..
We claim that applying the same algorithm A to the online setting, where Nature is even allowed to adaptively choose consistent hū, will also make at most errors.
We prove by contradiction. Suppose for some and some time step the algorithm makes the (d + 1)th error at time T, while the Nature chooses h at this time step. Notice that hy is consistent with the whole history of data. The algorithm will also make d + errors at time T, when Nature fixes hip in advance and uses the same since it incurs exactly the same history of data. However, this contradicts our assumption on uniform online learnability.
C.3 Proof of Theorem
Proof. In agnostic online learning, Ben-David et al. [2009] attains an O O(VTLdim) regret bound for Littlestone classes, which however requires 7 to be known in advance. To get rid of such dependence, we use the FPL algorithm Hutter et al. (2055) for the learning with experts problem with countably many experts and unknown T. particular, we use Algorithm (a subroutine for learning Littlestone class with known Ldim and T') as the experts for the Hierarchical FPL Algorithm from HHutter al. [2005), to obtain a regret bound for any Littlestone class in the agnostic setting, without knowing T. Having such algorithms for each of H., in hand, we then build another hierarchy by
15

---

using these algorithm experts under a meta FPL Algorithm 5 to finally obtain a non-uniform regret bound for every hypothesis H. We begin with lemmas on the guarantees of these algorithms.
(2009). Let be any sequence chosen by Nature, for any N we denote (I1. ... (2T, VT) as the first rounds of x, y. Let H be hypothesis class with Ldim < Then there exists some L S Ldim (H) and some sequence S i1
Lemma 24 (Error Bound of Expert(i1, ...) (Algorithm 4) Ben-David et al.
ib S T, such that Expert(ii,""
makes at most
L Σ (N(m))a
emrors on (01.)))."" .. (rr, yr) for any h E M.
Lemma 25 (Regret Bound of FPL (Algorithm 5
Hutter al. 2005)), Let q J/ and k; satisfying EiENt e I 1, for any y and T E N+ the regret wir.t any expert Eg is bounded by
T
T
E
Mis #ud
[E,(,)) S (k: + 2)VT.
t=1
Lemma 26 (Regret Bound of Hierarchical FPL (Theorem 9 in Hutter et al. 2005 Let kg satisfying EieNi e- & 1, for any x, and T E N+, there is an algorithm (Hierarchical FPL.) such that the regret any expert Fy bounded by
T Σ
log k;
E
22 + + ([E(E)))))))
Ö(VK.T)
Now we explain the details of how we aggregate the algorithms. Fix any Hr with Ldim Ldim(H,)) dn. we first extend the result of (Ben-David et al. (209 to infinite horizon.
By Lemma 24 for any T E N+, there is an Expert(i), ... ,rr)) with v, < T attaining the claimed error bound. Counting the number of experts with i I T, we find there are at most T', such experts. In addition, the number of experts with éz T is also bounded by Td..
We specify a way of assigning complexities k; Hierarchical FPL. For each expert with iz j. assign a complexity + (dn + 2) log To see why it's valid choice, notice
Σ EN
e -1-d +2) log
Σ EEN
S. 0.83.
2t
tEN
By Lemma 26
immediately gives an expected regret bound of
Ō ((vd,T)
on the Hierarchical FPL instance against Algorithm instances. Now, choose ky =2(log n + 1) for the meta FPI algorithm, verify
Ee-he
kn
1 21+ Σ
nENt
nEN+
As result, by Lemma 25 for any h E Hn, the regret compared with it up to time T' is bounded by
o(Vd,T)+ +2logn + 4)vT = =
-0TT=0((va))) ((Vd, logn)
C.4 Proof of Lemma 24
The proof is simplified rephrase of Lemma 12 in et al. 22099]
16

---

Proof. Fix any h E H. we denote j1. "1. Jk be the time steps that h doesn't er. It's equivalent to prove that there exists an Expert(i), ir.) such that makes most Ldim errors on Ji,'. Jkk-
Notice that the sequence (I)) Vin) V....... (m Vj. ) is realizable on H. running SOA on this sequence will incur at most Ldim(H) errors. Choose any sub-sequence & ".. tu of ji, .jk with L s Ldim (H). which contains all time steps that SOA makes errors on. The Expert(t1, .tt) makes the same predictions as SOA on ji, ... .Jk. thereby it makes at most Ldim(H) errors on J1. iJk. concluding the proof.
C.5 Proof of Proposition 13
Suppose is agnostic non-uniform online learnable at rate T for some 6 > 0. Define
h' argmin
as the best hypothesis in hindsight, the definition of agnostic non-uniform online learnability directly implies that for any x, yy, T. the expected regert is bounded by
T
E
Σ 11 6=1
S mmmm)h") m(h")T''
We have the partition H = UnE++ Hn. where H. E H: m(h) S n).. Since H can't be written as a countable union of Littlestone classes, one of Hi is a Littlestoee class. Suppose it's Hm, then Learner's 's expected regret on Hm is (uniformly) bounded by mT
However, since it's not Littlestone class, it has infinite Littlestone dimension. In particular, it has arbitrary depth shatter trees. Fix any shatter tree with depth To [(2m)² + 1, the first integer such that mTToe chooses a sequence among them and presents it to Learner, then Learner has expected loss Ia since every prediction is merely random coin flip. On the other hand, since the tree is shattered, the best hypothesis in hindsight must have loss O, thus Learner has expected regret at least Za. We conclude that it's impossible for Learner to have expected regret at most mT))- every sequence since Ta leading to the desired contradiction.
Consider the 2 sequences of xr y defined by this tree. If Nature randomly
2
2
mTj-
C.6 Proof of Proposition 14
Without loss of generality we can consider the simple problem where X {0} and H. (h) 0, (0) = 1}. Nature always selects I; = 0 and generates by iid coin flips, i.c. y1 0 with probability 2.2 Clearly, the expected number of errors made by Learner at any time T is z.
T
On the other hand, define 2, 2y 1 and S Σi= 24- We have that Vi +
B[2 1, E 2 E[ E[ = 0. As result, E[5?] = T and E(S*] 3T have that
E 2 Bi2e1
1) 37 By the Paley Zygmund inequality,
S2 2 4
3
P
>
16
Notice the distribution of S is symmetric, we get
VT
3
P
S
>
2
32
As a result, with probability at least of errors made by hy is at most we conclude that
32 there are VT more than 0 in {y1, ). and the number
Notice implies that minkeR ΣT (p)))) S VT
3VT
E
1
(e
min NeH
Σ
(
64
As result, H. can't be Iearnt with rate ol VT).
17

---

C.7 Proof of Proposition 20
Proof. We only need discuss the direction, since non-uniform stochastic online learnability implies EAS online learnability.
Suppose H. has countable effective cover H.' We claim that with probability 1 the drawing of there exists h E H'' such that
h² h*xx)) h (m:), bt N
To see this, we fix the h' w.r.t h" as in the definition of effective cover, then P Pa- (x) * (x))) 0. Since any countable union of zero-measure set still has zero measure, we conclude the proof of the claim.
Since Ht' is countable, we list its elements as h4, M/..". ... We partition H. into Unen Hy, such that Hn is the set of h covered by hr
Conditioned on the event 1 consider the simple algorithm that outputs the prediction of h which has the smallest index n among all consistent hypotheses in H'. When It" & Hm. Iim is consistent with all 2t, then clearly this algorithm makes at most errors, which is hypothesis-wii bound as desired. In addition, this happens with probability 1.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: make sure all the claims are accurate.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: we discuss the limitations and future directions for improvement the Discus- sion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification: we provide the full set of assumptions for all theoretical results. We provide complete (and correct) proof for all theoretical results, among which the simpler ones are left to the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guuddeeeeedouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
21

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
we carefully follow the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: there is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "Iv1gfSPbjQ", "reviewer": "Reviewer_y4NC", "summary": "This paper studies the non-uniform online learning problem, where error bounds can depend on the hypothesis rather than being uniform across hypotheses. In particular, the paper derives theoretical results on (i) conditions for non-uniform online learnability; (ii) regret bounds when the true hypothesis lies outside of the hypothesis class; and (iii) necessary condition for consistency, where error bounds can additionally depend on the data sequence.", "questions": "- Do the authors have an example of a hypothesis class which is a countable union of Littlestone classes but not countable? Examples 21 and 22 are both countable so don’t illustrate the value of the new result.\n\n- Similarly, for the consistency definition, what is an example of a class that is not non-uniform learnable but consistent?", "limitations": "I do not have sufficient expertise in this area to assess the limitations of the theoretical work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper comprehensively studies the non-uniform online learning problem. The theoretical results seem sound, drawing upon existing uniform learnability results. I would be interested in the opinion of a learning theory expert on the significance of the results.", "weaknesses": "Given that a major claimed contribution of the work is the conceptual link between inductive inference and non-uniform online learning, I would have expected a more formal description of the equivalence (e.g. side-by-side mathematical definitions, with references), and a more detailed contextualization of the existing works in both areas and how they are subsumed by the proposed framework. For example, what are the ‘different rules of observations’? It seems to me that the informal statement of inductive inference (finite number of errors given hypothesis) is naturally formulated as Definition 4.\n\nIn terms of presentation, I feel that some examples of hypothesis classes and learning problems in the main paper would be helpful in making the motivation of the paper more accessible; along the lines of the Examples in the Appendix but perhaps more diverse. See Qns below for some specifics", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We will address your concerns here.\n\n**Significance of the results**: we briefly summarize our contributions here (1) we give a sufficient and necessary condition for inductive inference, a fundamental problem in philosophy, while previous works only provided sufficient conditions (2) to solve this problem, we introduce a new framework called non-uniform online learning, which is closely connected to other learnability notions and can be of independent interest. We hope this addresses your concern on the significance of our results, and we are happy to answer further questions if any.\n\n**More explanation on equivalence**: the equivalence is discussed in lines 140-147. Since our framework is a strictly more general form than previously considered inductive inference by removing constraints on $\\mathcal{H}$ and $x_t$, we believe it's unnecessary to have another side-by-side mathematical definitions (as opposed to line 67). We give a representative example of how the problem of learning computable functions is subsumed by our framework in lines 143-147. \n\n**Different rules of observations**: it refers to different Nature's choices of observations $x_t$. Here Definition 4 formulates the adversarial case while Definition 5 handles the stochastic case. By Theorem 9 and Theorem 11, we prove that the two cases share the same sufficient and necessary condition, which implies this condition is also sufficient and necessary for any \"rule of observation\" between the adversarial and stochastic cases. This corresponds to \"different rules of observations\" in line 141. \n\nIf our explanation on the equivalence still feels unclear to you, we are happy to hear from your further suggestions and revise our writing correspondingly.\n\n**More examples**: we put the examples in the appendix due to space limit, we will add some key examples back to the main paper for readability as you suggested. Below we answer your questions.\n\n**A countable union of Littlestone classes but not countable**: we give a stronger example which is a Littlestone class with an uncountable size. Consider the set of indicator functions on $[0,1]$, i.e. $\\{f_c| f_c(x)=1_{x=c}, c\\in [0,1]\\}$. The size of this hypothesis class is uncountable because $[0,1]$ has the same cardinality as $\\mathbb{R}$. This class itself has Littlestone dimension 1. A naive algorithm that makes at most one error on this class is the following: always predict $y_t=0$ until making the first error on some $x_t=c$, then the ground-truth $h^*$ is identified as $f_c$ and we predict w.r.t. $f_c$ afterwards.\n\n**Not non-uniform learnable but consistent**: this is left as an open question, as shown in Table 1. Currently we only know non-uniform learnablity is a subset of consistency and we obtained a new necessary condition for consistency (Theorem 18). It's unclear whether consistency can be separated from non-uniform learnablity or not.\n\nIf our response has addressed your concerns, please consider reevaluate our paper. If you have further questions, please let us know. Thank you again for your valuable time and insights!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y2b8iO0y0c", "reviewer": "Reviewer_4vEY", "summary": "This paper establishes a novel link between inductive inference and online learning theory. It introduces a novel non-uniform online learning framework and proves a very interesting result on hypothesis class characterization: the authors show inductive inference is possible if and only if the hypothesis class is a countable union of online learnable classes, irrespective on the observations' distribution.", "questions": "(See above)", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I found this paper is a thorough, beautifully written piece of work that guides the readers intuitively on the series of theoretical results. The necessary and sufficient characterization on hypothesis class when inductive inference is possible is philosophically interesting and would be an interesting addition to the field. The authors presents a wholistic analysis and contextualizing the current work with past literature: through comparison with classic online learning setting, to analysis on agnostic setting and comparison with non-uniformity with consistency. I find this paper would be a valuable addition to the research community.", "weaknesses": "The main weakness of this paper is the unclear practical implications of the paper's main result (Theorem 1) on downstream tasks. For example, given one can characterize the hypothesis class as a countable union of online learnable classes - what would it mean to the general machine learning community, e.g., can it offer guidance towards algorithm designs? Could the authors elaborate more on how the potential practical impact of their work?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We will address your concern here.\n\n**Practical implications**: this work is devoted to a conceptual link between philosophy and learning theory, therefore practical implication is not the primary objective and is beyond the scope of the current work. We believe the new conceptual finding itself is valuable because understanding inductive reasoning is a fundamental problem.\n\nFor concrete practical applications, our algorithm has the potential to be made more practical by designing approximate algorithms (as we briefly mentioned in future directions). The original form of Solomonoff induction is also known to be intractbale, but later works built approximate versions of Solomonoff induction. \n\nSome recent works study the practical use of inductive inference in large language models (for example, \"Learning Universal Predictors\" by Grau-Moya et al 2024), and we believe our algorithms can be useful in practice by a similar approach, for understanding if large language models implicitly learn such Bayesian algorithms during inference. We leave these as future research directions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hDMeaWJ1P7", "reviewer": "Reviewer_Cxri", "summary": "The authors *characterize* possible inductive inference by connecting it to online learning.\nI find their work extremely interesting!", "questions": "Page 1:\nCan you please say a few words about the connection of inductive inference to computational complexity and theory of computation?\nI have a feeling that some of the papers of Shuichi Hirahara and Mikito Nanashima should be cited.\n\nPage 2:\nCan you please elaborate on the comparison of two pseudocode segments?\n\nPage 3:\nLine 111:\nNotation in math display is confusing :)\n\nPage 4:\nLine 124:\nPlease avoid contractions.\n\nI do not understand Lines 140 -- 147.\n\nPage 5:\nCan you please elaborate on Lines 179 -- 181?\n\nPage 6:\nWhy do you choose $x = x^{n(h) + 1}$?\n\nPage 7:\nCan you please elaborate on your notion of Regret?\n\nPage 8:\nI am confused by Lines 268 -- 269.\n\nPage 9:\nI like the philosophical interpretations!\n\nPlease elaborate on future work.\nHow is your work connected to computational complexity and computational learning theory?", "limitations": "None.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The choice of topic is excellent, delivery is strong.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We will address your concerns here.\n\n**Connection to computational complexity (page 1)**: good point! Inductive inference (especially Solomonoff's method) is not only linked to learning theory but also to the theory of computation. We will add some discussion on this connection (e.g. the paper \"Learning in Pessiland via Inductive Inference\" by the authors you mentioned).\n\n**Comparison between pseudocodes (page 2)**: we list them side by side for a straightforward comparison. Only lines 2,6,9 are different. Here lines 2,6 correspond to the difference in protocols: classic online learning allows a changing ground-truth (line 6), while inductive inference requires the ground-truth to be fixed in advance (line 2). Line 9 corresponds to the difference in criteria: classic online learning requires uniform error bounds, while inductive inference allows the bounds to depend on the ground-truth. We will add a caption to briefly explain the differences.\n\n**Lines 140-147 (page 4)**: this paragraph conveys two messages (1) our framework considers general $\\mathcal{H}$, while previous work on inductive inference only considers $\\mathcal{H}$ with a countable size (2) our framework incorporates different setting on how Nature chooses $x_t$ (adversarial or stochastic), while most previous work only considers a certain rule of nature's choice on $x_t$. By these two, we reach the conclusion that our framework is a general framework of inductive inference, subsuming the previously considered settings. As an example, we cast the problem of learning computable functions under our framework. If you have further questions, please let us know.\n\n**Lines 179-181 (page 5)**: once $A_n$ makes more than $d_k+k$ errors at some time step $t_0$, then for any $t> t_0$, $e(t,n)\\ge d_k+k$, and $e(t,n)+n> d_k+k$ since $n\\ge 1$. By the definition of how we pick the index $J_t$ (line 5 in Algorithm 1), index $k$ will always be strictly better than index $n$ for any $t> t_0$ because $e(t,k)+k\\le  d_k+k$, then our algorithm will never pick $J_t=n$ after $t_0$. Combining it with the fact that only indexes no larger than $d_k+k$ can be possibly invoked, we make at most $(d_k+k)^2$ errors.\n\n**Choice of $x^{n(h)+1}$ (page 6)**: $n(h)+1$ is the smallest number $n$ that guarantees a contradiction, for which we want $n>n(h)$.\n\n**Notion of regret (page 7)**: the regret notion in Theorem 12 is from Definition 6. It's a natural extension of the regret notion in agnostic online learning to the non-uniform setting: we require a uniform dependence on $T$ ($r(T)$ is the same across different $h$), while the overhead $m(h)$ can vary with different $h$.\n\n**Lines 268-269 (page 8)**: Figure 1 can serve as an intuitive explanation. Roughly speaking, we use the claim from lines 261-262 multiple times, to find a sub-tree which is a binary tree with depth $m^*+2$, each node being the root of an $\\aleph_1$-size tree. In Figure 1, $v_{(1,1)}$ is the ancestor of the sub-tree, with $v_{(2,1)}$ and $v_{(2,2)}$ being its children (though $v_{(2,1)}$ is not its child in the original tree).\n\n**Future work (page 9)**: as we briefly mentioned, our learning algorithms are inevitably intractable, and we leave a computationally tractable approximate algorithm for future work.\n\nWe hope our response has addressed your concerns. If you have further questions, please let us know. Thank you again for your valuable time and insights!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper gives a full characterization of when inductive inference is possible, in both realizable and agnostic settings, strengthening past sufficient conditions with an elegant necessary and sufficient condition. The achievable algorithms, however, are inherently intractable. The technical contributions toward building this theory are novel and the paper is presented very methodically (albeit not for the uninitiated in learning theory, with many concepts assumed known, e.g., the SOA algorithm.) Reviewers appreciated the work and requested a few clarifications that ought to be part of the revision of the paper.
Decision: Accept (spotlight)