Newest papers

Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors

Qian Li, Shang‐Hua Teng · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.29289 · cited by 0 works (OpenAlex) · open-access PDF

Chinese

Grau-Moya et al. (ICML 2024)提供了一个概念化的解释,通过Meta-learning的镜头:如果序列生成环境 $ν$是从先前 $w_n$的环境中抽取的,那么从先前 $w_n$的环境中抽取的能力和可概括的技能还没有得到充分理解。 Grau-Moya et al. (ICML 2024)提供了一个概念化的解释:如果序列生成环境 $ν$是从先前 $w_n$的环境中抽取的,那么从先前 $w_n$的环境中抽取的能力和可概括的能力,那么从先前的Bayesian混合物预测器 $x=\sum_n_n$的预测器才会得到回收。 在理想化的界限中, $w$是普遍预测

Machine translation (Meta M2M100); the English original follows.

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 $w_ν$, minimizing population log-loss recovers the corresponding Bayesian mixture predictor $ξ=\sum_νw_νν$. In the idealized limit in which $w$ is a universal prior, the optimal predictor corresponds to Solomonoff universal induction. Practical machine learning algorithms, however, generally produce only \emph{approximately} optimal predictors. This raises a natural question: \emph{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 $D_{KL}(ξ\|ρ)\leq η$ retains bounded cumulative-expected-squared prediction error. However, while the Bayesian mixture predictor $ξ$ has error $O(\log(1/w_μ))$ in an environment $μ$, we establish a tight $Θ(η/w_μ)$ 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 $w$, we prove that the excess prediction error is only $O(η)$. Furthermore, we establish a distribution-shift theorem for dominated shifts from a training prior $w$ to a test prior $w'$, 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 $D_{KL}(ξ\|ρ)$ could be unbounded. [For the full abstract, see the paper.]

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Bounded function, Robustness (evolution), Bayesian probability, Computer science, Artificial intelligence, Machine learning

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange