When Is Inductive Inference Possible?

Thank you for your valuable feedback! We will address your concerns here.

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).

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.

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.

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.

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)$.

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$.

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).

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.

We 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!

Thank you for your valuable feedback! We will address your concern here.

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.

For 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.

Some 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.

Thank you for your valuable feedback! We will address your concerns here.

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.

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.

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.

If our explanation on the equivalence still feels unclear to you, we are happy to hear from your further suggestions and revise our writing correspondingly.

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.

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.

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.

If 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!