acceptodds
Under review as a conference paper at ICLR 2027

Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

Abstract

Why large language models trained via log-loss minimization over massive and diverse datasets exhibit broad capabilities and generalizable skills is not yet fully understood. Grau-Moya et al. (ICML 2024) offer a conceptual explanation through the lens of meta-learning: if sequence-generating environments are drawn from a prior , minimizing population log-loss recovers the corresponding Bayesian mixture predictor . In the idealized limit in which is a universal prior, the optimal predictor corresponds to Solomonoff universal induction. Practical machine learning algorithms, however, generally produce only approximately optimal predictors. This raises a natural question: Does the prediction performance remain robust under approximation? In this paper, we first provide a tight bound on the worst-case effect of approximation on prediction error. We show any predictor satisfying retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor has error in an environment , we establish a tight bound on the excess error of relative to . Thus, approximation can substantially degrade performance in environments assigned small prior probability. In sharp contrast, when environments are averaged according to prior , we prove that the excess prediction error is in fact only . Furthermore, we establish a distribution-shift theorem for dominated shifts from a training prior to a test prior , interpolating our average-case and worst-case guarantees. Finally, we extend our robustness analysis to a finite-sampling setting relevant to learning universal predictors with neural networks and Transformers, where could be unbounded. Our theory extends the classical theory of Bayesian and Solomonoff Induction to approximate predictors and characterizes a broad spectrum of prediction behavior. It helps explain the sharp gap between strong empirical benchmark performance and poor worst-case performance in rare environments, while providing quantitative justification for targeted sampling and synthetic data generation designed to protect important but underrepresented task families.

Primary area:
learning theory
Keywords:
Solomonoff induction, Universal prediction, Meta-learning, Robustness to approximation, Distribution shift

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_rCHXOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies whether the prediction guarantees of ideal Bayesian predictors remain robust under approximation. Using Bayesian sequential prediction and Solomonoff induction as theoretical frameworks, it derives guarantees for approximate predictors.

Critical strengths

This paper goes beyond the idealized assumption of exact Bayesian prediction by explicitly accounting for approximation error. Section 5 also presents a seemingly interesting result, showing that the expected squared prediction error can remain controlled even when expected KL divergence is infinite.

Critical weaknesses

Overall, the authors position this paper as a theoretical work, yet it falls far below the expected bar for such a contribution. I could not identify a new analytical framework, interesting findings, or general and substantive theorems. The assumptions are classical and clearly unsuitable for modeling LLMs, while the conclusions are largely incremental, can be found even in many classical machine learning textbooks, and are clearly not unique to LLMs. Even I am not an expert in machine learning thoery, I am quite confident that the paper should be rejected.

The presentation is also far below the expected bar. I cannot determine what the authors intend to convey from the abstract, and the introduction further adds to the confusion through uninformative, ambiguous, and excessively verbose language.

The discussion also lacks conceptual precision. For example, semi-supervised learning, PAC learning, and reinforcement learning are presented in parallel as comparable “classical learning frameworks.” PAC learning is a theoretical framework, whereas semi-supervised learning and reinforcement learning refer to different learning paradigms or settings.

Although the paper is motivated by LLMs, its analysis is based on a Bayesian framework that assumes the learned model is close to the Bayesian optimum. This framework does not appear suitable for characterizing overparameterized models, and I seldom see such a Bayesian assumption used in serious LLM-related theoretical work. It is also uncommon to model complex LLM tasks using universal Turing machines.

I interpret Theorem 1 as showing that, even though the overall error is small, the error on a particular task can be large. I believe that general nonasymptotic theory, such as concentration inequalities, has already established this phenomenon in statistics. The extension of Hutter’s original theory is also incremental and relies on an additional Bayesian assumption that is itself questionable.

Theorem 2 also does not seem to provide a substantive new result, since the Solomonoff prior is defined to assign smaller prior probabilities to more complex environments. This prior was not proposed by the authors and should instead be viewed as an assumption. I am also concerned about whether it is an appropriate assumption for LLMs.

I also did not find any particularly novel findings in Theorems 3–6. The existence of corner cases, lower average-case error, and the impact of distribution shifts have been widely discussed in classical machine learning. I cannot identify any adjustment specifically made for LLMs or any findings that are unique to LLMs. I further examined Section 5 and likewise found no particularly interesting results.

The authors suggest replaying pretraining data during fine-tuning to mitigate forgetting. First, much of the pretraining data may be of low quality, so it is unclear why such information should be preserved. Could replaying the pretraining data make fine-tuning ineffective? Second, the connection between this suggestion and the main claim of the paper is unclear. This further raises questions about the feasibility of the Bayesian assumption adopted in the analysis.

Questions for authors

Please see the Critical Weaknesses above

4 comments

Thank you for your feedback. We recognize that the original presentation may not have communicated the motivation and significance of our results clearly enough. We have substantially revised the paper to clarify the connection to LLMs and the central theoretical message.


1. Motivation: Why is Bayesian prediction relevant to LLMs?

The standard recipe of LLM pretraining is quite simple: just minimizing next-token log loss over massive and diverse datasets. A natural theoretical question is to understand how such a simple pretraining paradigm can produce a general-purpose reasoning engine.

Following the meta-learning framework of Grau-Moya et al. (ICML 2024), consider training sequences generated by first sampling an environment/task ν\nu from a prior ww, and then sampling a sequence from ν\nu. Exactly minimizing population log loss recovers the Bayesian mixture predictor

$ \xi=\sum_\nu w_\nu\nu. $

This predictor performs Bayesian adaptation through its in-context learning. With a universal prior, it provides the idealized framework of Solomonoff induction.

Rather, limited model capacity, imperfect optimization, and finite training data motivate our central question: To what extent do the prediction guarantees of the ideal Bayesian predictor carry over to practical learned predictors?


2. Main findings: A sharp contrast between worst-case and average-case prediction.

Our results reveal two fundamentally different behaviors:

  • Environment-wise fragility, even with unlimited data. An arbitrarily small population approximation gap η\eta can substantially weaken the ideal O(log⁡(1/wμ))O(\log(1/w_\mu)) guarantee. Specifically, we establish a tight bound of order Θ(log⁡(1/wμ)+η/wμ)\Theta(\log(1/w_\mu)+\eta/w_\mu). Note that the excess error η/wμ\eta/w_{\mu} is exponentially larger than O(log⁡(1/wμ))O(\log(1/w_\mu)).
  • Average-case robustness, even with limited data. In contrast, we show that the prior-averaged excess error is at most O(η)O(\eta). Importantly, as the Bayesian predictor is the optimal average-case predictor among all possible predictors (Proposition 1), this excess O(η)O(\eta) is measured relative to the best possible predictor over all predictors. Our new Theorem 7 extends this guarantee to finite training data, which admits a similar bound, with an additional mild finite-sample term.

We further quantify robustness under distribution shift, showing how prediction guarantees depend on the coverage of the test distribution under the training prior.


3. Significance.

These results provide a quantitative explanation, within the Bayesian meta-learning framework, of how small aggregate prediction error can coexist with severe failures on rare tasks.

Our goal is not to claim that practical LLMs implement Solomonoff induction, but to establish which guarantees of ideal Bayesian prediction survive approximation and finite-data learning. We have reorganized the paper to make this distinction and its implications clearer.

Thank you for the response. After reading it and the revised paper, my concerns remain, and I am inclined to keep my original rating.

First, the response has deepened my concern about why LLMs are discussed at all. The authors now state that their goal is not to claim that practical LLMs implement Solomonoff induction. However, the revised paper still frames itself around LLMs throughout: the abstract opens with LLMs, the introduction is motivated by LLM pretraining, and the implications are drawn for LLM fine-tuning and training-data design. The results themselves are general statements about approximate Bayesian sequential prediction, and I still cannot identify any assumption, analysis, or finding that is specific to LLMs. My concern that this Bayesian framework is unsuitable for overparameterized models is also not addressed.

Second, many of my questions are left unanswered. These include (numbering as in the original submission) whether the phenomenon in Theorem 1 is already established by general nonasymptotic theory, why the extension of Hutter's theory is more than incremental, why Theorem 2 is a substantive result rather than a consequence of the assumed prior, what is novel in the remaining theorems, and the questions on replaying pretraining data during fine-tuning.

Instead of answering these points, the response mainly restates the motivation and the main results. I therefore do not consider it a reasonable rebuttal.

Thank you for your further feedback. We acknowledge that our previous response focused too much on summarizing the results rather than directly addressing your specific concerns. We apologize for this and respond to your questions point by point below.

Q1: Connections to LLMs

A1: This paper studies the LLM pretraining paradigm, rather than specific LLM neural architectures.

Following Grau-Moya et al. (ICML 2024), under idealized assumptions (sufficient model capacity, perfect optimization, and unlimited training data), pretraining (minimizing next-token log loss) recovers the Bayesian mixture predictor. In particular, if the training data are generated by a universal Turing machine with random input bits, then the idealized LLM pretraining paradigm yields a model that implements Solomonoff universal induction.

By "our goal is not to claim that practical LLMs implement Solomonoff induction," we mean that we do not claim that practical LLM training data can produce Solomonoff universal induction.

Our work studies the robustness of this idealized pretraining paradigm under imperfect learning conditions.

Q2: My concern that this Bayesian framework is unsuitable for overparameterized models is also not addressed.

A2: Bayesian framework does not impose any restriction on the number of model parameters. The fact that the Bayesian mixture minimizes population log loss over all predictors holds independently of the model architecture or parameter count.

Of course, overparameterization alone does not guarantee that minimizing empirical log loss yields a predictor close to the Bayesian optimum. This is precisely why we study approximation errors. Moreover, our new Theorem 7 explicitly accounts for representation error, optimization error, and finite-sample effects.

Q3 The presentation is also far below the expected bar. I cannot determine what the authors intend to convey from the abstract, and the introduction further adds to the confusion through uninformative, ambiguous, and excessively verbose language.

A3: We have substantially revised the abstract and the "Our Main Contributions" subsection. We hope the revised version is clearer. The two main messages are:

  • Even with unlimited training data, compared with perfection optimization, an arbitrarily small approximation gap can substantially weaken the task-wise prediction performance.
  • In contrast, average-case prediction performance remains robust under approximation, even with limited training data.

Q4: The discussion also lacks conceptual precision. For example, semi-supervised learning, PAC learning, and reinforcement learning are presented in parallel as comparable “classical learning frameworks.” PAC learning is a theoretical framework, whereas semi-supervised learning and reinforcement learning refer to different learning paradigms or settings.

A4: Revised as suggested.

Q5: Although the paper is motivated by LLMs, its analysis is based on a Bayesian framework that assumes the learned model is close to the Bayesian optimum.

A5: We do not assume that the approximation gap η\eta is small. Instead, we treat it as a variable and study how prediction performance depends on η\eta.

We acknowledge that assuming finite DKL(ξ∣ρ)D_{\mathrm{KL}}(\xi|\rho) can be restrictive for predictors learned from finite data. Therefore, we have added a new finite-data analysis (Section 4.3), which establishes an average-case guarantee without requiring the finite KL assumption.

Q6: I seldom see such a Bayesian assumption used in serious LLM-related theoretical work.

A6: There is an established line of theoretical research studying LLM in-context learning through Bayesian inference. See "Genewein et al. Algorithmic compression via pretrained neural networks. Entropy 2026" for a survey. They demonstrated that Bayesian prediction is a suitable theoretical framework for studying LLM pretraining and in-context learning.

Q7: It is also uncommon to model complex LLM tasks using universal Turing machines.

A7: Universal Turing machines are used here as idealized data generators, rather than as literal models of how real-world LLM training data are generated. By the Church–Turing thesis, they can represent any computable sequence-generating process.

In particular, Grau-Moya et al. (ICML 2024) explicitly studied meta-training neural networks, including Transformers, using UTM-generated data, and analyzed their convergence toward Solomonoff prediction under idealized assumptions.

Q8: I interpret Theorem 1 as showing that, even though the overall error is small, the error on a particular task can be large. I believe that general nonasymptotic theory, such as concentration inequalities, has already established this phenomenon in statistics.

A8: We are not aware of a classical concentration inequality that directly Theorem 1 (in the original version).

Q9: The extension of Hutter’s original theory is also incremental and relies on an additional Bayesian assumption that is itself questionable.

A9: We have substantially revised this part of the paper. Our main finding is that even with unlimited training data, an arbitrarily small approximation gap can substantially degrade the environment-wise prediction guarantee.

Theorem 1 (Theorem 3 in the revised paper) is not our main contribution; rather, it serves to establish the tightness of our analysis by providing a matching upper bound.

Q10: Theorem 2 also does not seem to provide a substantive new result, since the Solomonoff prior is defined to assign smaller prior probabilities to more complex environments. This prior was not proposed by the authors and should instead be viewed as an assumption. I am also concerned about whether it is an appropriate assumption for LLMs.

Q10: We agree that the Solomonoff prior is classical and is not our contribution.

Q11: I also did not find any particularly novel findings in Theorems 3–6. The existence of corner cases, lower average-case error, and the impact of distribution shifts have been widely discussed in classical machine learning. I cannot identify any adjustment specifically made for LLMs or any findings that are unique to LLMs.

A11: We agree that average-case analysis and distribution shift are classical topics in machine learning. However, our contributions are the quantitative guarantees for LLM pretraining paradigm, rather than the introduction of these concepts.

As clarified earlier, our analysis concerns the LLM pretraining paradigm, rather than specific LLM architectures.

Q12: I further examined Section 5 and likewise found no particularly interesting results.

A12: We have substantially strengthened the finite-data analysis (now Section 4.3, Theorem 7), establishing guarantees for predictors learned by approximately minimizing regularized empirical log loss. Please see our response to Reviewer 1, "New Finite-Data Result (Section 4.3, Theorem 7)," for details.

Q13: The authors suggest replaying pretraining data during fine-tuning to mitigate forgetting. First, much of the pretraining data may be of low quality, so it is unclear why such information should be preserved. Could replaying the pretraining data make fine-tuning ineffective? Second, the connection between this suggestion and the main claim of the paper is unclear. This further raises questions about the feasibility of the Bayesian assumption adopted in the analysis.

A13: Our fine-tuning discussion is a population-level analysis showing how replaying pretraining data can preserve average prediction performance on the original task distribution.

We agree that replaying low-quality data may not be desirable and that excessive replay could weaken adaptation to target tasks. In fact, we explicitly characterized the trade-off between target-task performance and original-task performance through the mixing parameter λ\lambda.

We acknowledge that practical fine-tuning is more complicated, particularly when considering computational efficiency, data quality, and data efficiency. Our result provides a theoretical explanation rather than an unconditional recommendation to replay pretraining data.

Finally, regarding the soundness concerns raised in your original review, we would appreciate it if you could identify any specific theorem or proof step that you believe is incorrect. We would be happy to address such concerns directly.

Reviewer_wuPxOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how approximating an ideal Bayesian sequence predictor affects prediction accuracy. It establishes a sharp contrast between potentially large errors on rare tasks and small average excess error, together with distribution-shift and fixed-horizon finite-data guarantees.

Critical strengths
  • The central question is precise and relevant to theoretical accounts of meta-learning and in-context learning.
  • The matching universal lower bound in Theorem 3 appears to be the strongest technical contribution.
  • The paper provides detailed proofs and useful distinctions between different prediction-error criteria.
Critical weaknesses
  • Limited applicability to learned predictors: The infinite-horizon universal results assume finite KL divergence from the universal mixture, which computable predictors cannot satisfy. The authors should foreground the distinction between these abstract results and attainable finite-horizon guarantees.
  • Potentially prohibitive finite-data constants: The bounds depend on the minimum probability of an entire length-(n) sequence. Their exponential remainder can therefore hide severe horizon dependence and does not establish a practically informative learning rate.
  • Contribution and interpretation need sharpening: Several upper bounds follow from standard loss decompositions and domination arguments. The paper should emphasize its genuinely new results, distinguish total task-wise error from additive excess error, and moderate its implications for practical LLM training.

The topic is within ICLR’s scope; my reservations concern the significance and practical interpretation of the theoretical contribution.

Questions for authors
  1. How should the infinite-horizon approximation assumption be interpreted for predictors that are computable and require finite data?
  2. Can the finite-data constants be made explicit in the main statement?
  3. Are there any important conclusions about computationally bounded learning?
2 comments

Thank you for your constructive feedback. We have substantially revised the paper, particularly to address your concerns about the KL assumption, the finite-data bound, and the applicability of our results to computable predictors.


1. Improved finite-data guarantee (Section 4.3, Theorem 7).

We agree that the previous finite-data bound had potentially prohibitive constants. We have replaced this analysis with a new MDL-inspired result.

Specifically, for predictors ρ^m\hat{\rho}_m approximately minimizing a regularized empirical log loss, trained on mm independent sequences of length nn, we prove

EDmSn(ξ,ρ^m)≤4(ηrep+ηopt+nmlog⁡1πρ⋆).\mathbb{E}_{D_m}S_n(\xi,\hat{\rho}_m)\leq 4(\eta_{\mathrm{rep}}+\eta_{\mathrm{opt}}+\frac{n}{m}\log\frac{1}{\pi_{\rho^{\star}}}).

  • LHS: Sn(ξ,ρ^m)S_n(\xi,\hat{\rho}_m) equals the difference between Eμ∼wSn(μ,ρ^m)\mathbb{E}_{\mu\sim w}S_n(\mu,\hat{\rho}_m) and Eμ∼wSn(μ,ξ)\mathbb{E}_{\mu\sim w}S_n(\mu,\xi).

  • RHS: The bound separates representation error, optimization error, and an explicit finite-sample term of order nmlog⁡1πρ⋆\frac{n}{m}\log\frac{1}{\pi_{\rho^\star}}. Here, ρ⋆\rho^{\star} attains the smallest representation gap within the model class and πρ⋆\pi_{\rho^{\star}} is its prior weight. In particular, if the model class is expressive enough to contain ξ\xi, the finite-sample term reduces to (n/m)log⁡(1/πξ)(n/m) \log(1/\pi_\xi).

  • The basic idea is inspired by the MDL theory: we view the training samples as the first m blocks of an infinite i.i.d. sequence of length-n blocks drawn from ξ\xi, with an independent test sequence forming the next block. The MDL-inspired training objective then defines a blockwise sequential predictor: it selects ρ^m\hat{ρ}_m after observing the first mm blocks and keeps this model fixed while predicting the next block. Its expected cumulative squared prediction error within that block is exactly EDmSn(ξ,ρ^m)\mathbb{E}_{D_m}S_n(\xi,\hat{\rho}_m).


2. An explicit computable construction.

To clarify that worst-case fragility is not an artifact of the uncomputability of universal induction, we establish the same inverse-prior amplification for a finite class of efficicently computable environments (New Theorem 2).

Specifically, consider M\mathcal{M} consisting of 2n2^n deterministic environments μy=δy0∞\mu_y=\delta_{y0^\infty}, each with prior weight 2−n2^{-n}, where y∈0,1ny\in\\{0,1\\}^n. Let ξ\xi be the mixture of M\mathcal{M}. For every environment μy\mu_y and η>0\eta>0, there is a efficiently computable predictor ρ\rho satisfying

DKL(ξ∣ρ)≤η,S(μy,ρ)=n2+⌊η2n⌋2.D_{\mathrm{KL}}(\xi|\rho)\le\eta,\qquad S(\mu_y,\rho)=\frac n2+\frac{\lfloor\eta2^n\rfloor}{2}.

Thus, a small population approximation gap can produce an exponentially amplified error on a rare environment, even when both the environment class and the approximate predictor are efficiently computable.


3. Reorganized presentation.

We have reorganized the paper to emphasize the paper's central message: Environment-wise guarantees can be fragile even with infinite training data, whereas average-case prediction remains robust with limited training data.


4. The Bayesian mixture is the optimal average-case predictor (Proposition 1).

We would like to mention that: the average-case decompostion

Eμ∼wSn(μ,ρ)=Eμ∼wSn(μ,ξ)+Sn(ξ,ρ).\mathbb{E}_{\mu\sim w}S_n(\mu,\rho)=\mathbb{E}_{\mu\sim w}S_n(\mu,\xi)+S_n(\xi,\rho).

implies that ξ\xi minimizes the prior-averaged prediction error over all possible predictors. Our average-case guarantees therefore measure excess error relative to the best possible predictor, rather than merely a chosen reference model.

Thank you for the clarification and for reorganizing the paper. This will be considered for the final rating.

Reviewer_2Lr8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors study robustness to approximation in sequential prediction. The primarily aim to answer the question of if an approximation of the optimal Bayesian predictor retains the guarantees from previous work. The answer this question for worst-case and average-case regimes as well as cases where there is a distributional shift. They primarily consider cumulative squared prediction error but also connect to cumulative hellinger and KL errors. In the worst-case regime, they show that for any approximate predictor ρ\rho for which the KL divergence with respect to the optimal Bayesian predictor ζ\zeta is finite and upper bounded by some η\eta, the error that the approximate predictor incurs relative to the optimal is O(η/wμ)O(\eta/w_{\mu}) (Theorem 1). The authors then show that this is tight via a lower bound (Theorem 3). In the average-case regime (Theorem 4), the authors show that this additive error can be improve to O(η)O(\eta).

In the case where there is a distribution shift, the authors find that if the test prior is dominated by the training prior up to a factor CC, then the average excess error is O(\log C + C\eta). They instantiate this theorem for several examples. Finally, the authors examine learning from finitely many training sequences. At a fixed sequence length, it shows that KL divergence can be infinite in expectation when a learned predictor assigns zero probability to an unseen event that has positive mass under μ\mu, while squared prediction error still admits a meaningful expected bound. Its finite-sample term decays exponentially in sample size for fixed problem parameters, although the constants can deteriorate substantially with sequence length and rare-event probabilities.

Critical strengths
  1. The paper is very well written and structured. I enjoyed reading it and appreciate the effort the authors put into motivating and contextualizing the results.
  2. The technical results appear correct, and the proofs are well structured. I went through the proofs but did not examine every detail.
  3. Theorems 3 and 5 are particularly nice results. The former establishes a tight lower bound in the worst-case regime and the latter provides a guarantee when there is a distribution shift.
Critical weaknesses
  1. My primary concern with the paper is the validity of the finite KL divergence assumption. This seems like a very strong requirement, and I am not sure of any practical settings for which it holds. The finite horizon results are still relevant, but the remaining theorems may not be very useful in practice if this assumption is required. I think this limits the usefulness of the paper, but I would be happy to discuss this with the authors.
  2. I think it would have been nice to have some empirical validation of the results, although this isn't required for a theoretical work.
Questions for authors
  1. What are some practical regimes in which the finite KL divergence across an infinite horizon actually holds? In regimes where this doesn't holds, can the results still apply?
1 comment

Thank you for your thoughtful review and for recognizing the strengths of our theoretical results. We have substantially revised the paper to address your main concern about finite data.


1. New Finite-Data Result (Section 4.3, Theorem 7).

We agree that the KL assumption is restrictive. Importantly, our revised paper establishes a new finite-data guarantee that does not require this assumption.

Specifically, for predictors ρ^m\hat{\rho}_m approximately minimizing a regularized empirical log loss, trained on mm independent sequences of length nn, we prove

EDmSn(ξ,ρ^m)≤4(ηrep+ηopt+nmlog⁡1πρ⋆).\mathbb{E}_{D_m}S_n(\xi,\hat{\rho}_m)\leq 4(\eta_{\mathrm{rep}}+\eta_{\mathrm{opt}}+\frac{n}{m}\log\frac{1}{\pi_{\rho^{\star}}}).

  • LHS: Sn(ξ,ρ^m)S_n(\xi,\hat{\rho}_m) equals the difference between Eμ∼wSn(μ,ρ^m)\mathbb{E}_{\mu\sim w}S_n(\mu,\hat{\rho}_m) and Eμ∼wSn(μ,ξ)\mathbb{E}_{\mu\sim w}S_n(\mu,\xi).

  • RHS: The bound separates representation error, optimization error, and an explicit finite-sample term of order nmlog⁡1πρ⋆\frac{n}{m}\log\frac{1}{\pi_{\rho^\star}}. Here, ρ⋆\rho^\star attains the smallest representation gap within the model class and πρ⋆\pi_{\rho^\star} is its prior weight. In particular, if the model class is expressive enough to contain ξ\xi, the finite-sample term reduces to (n/m)log⁡(1/πξ)(n/m) \log(1/\pi_\xi).

  • The basic idea is inspired by the MDL theory: we view the training samples as the first m blocks of an infinite i.i.d. sequence of length-n blocks drawn from ξ\xi, with an independent test sequence forming the next block. The MDL-inspired training objective then defines a blockwise sequential predictor: it selects ρ^m\hat{ρ}_m after observing the first mm blocks and keeps this model fixed while predicting the next block. Its expected cumulative squared prediction error within that block is exactly EDmSn(ξ,ρ^m)\mathbb{E}_{D_m}S_n(\xi,\hat{\rho}_m).


2. The Bayesian mixture is the optimal average-case predictor (Proposition 1).

The average-case decomposition

Eμ∼wSn(μ,ρ)=Eμ∼wSn(μ,ξ)+Sn(ξ,ρ).\mathbb{E}_{\mu\sim w}S_n(\mu,\rho)=\mathbb{E}_{\mu\sim w}S_n(\mu,\xi)+S_n(\xi,\rho).

implies that ξ\xi minimizes the prior-averaged prediction error over all possible predictors. Our average-case guarantees therefore measure excess error relative to the best possible predictor, rather than merely a chosen reference model.


3. Reorganized presentation.

We have reorganized the paper to emphasize the paper's central message: Environment-wise guarantees can be fragile even with infinite training data, whereas average-case prediction remains robust with limited training data.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.