CS Paper Radar

Machine Learning Beyond Statistical Consistency for Hybrid AI

Jinsook Kim, Jinho Kang

cs.LG cs.AIcs.LOstat.ML ·submitted 2026-11-01 13:54 UTC · v1
theory

Abstract

We propose a new definition of machine learning, according to which a machine learns a function when it computes the function successfully, that is, when the value it returns for each input has a proper derivation in a formal system. We extend Gödel's Representability Theorem, which equates computation with derivation, to empirical targets in two ways: the theorem is extended to the computable reals, and the data are admitted into the system as empirical definitions that record what has been observed. We prove that a machine learns a true probability if and only if two conditions are met. The Truth Condition is that its estimate converges to the true probability, which is statistical consistency. The Assurance Condition is that the machine properly derives its own convergence inside the system. Learning thus lies beyond statistical consistency, for it requires a derivation of the convergence from the record. A global assumption about the data, such as the i.i.d. assumption, does not supply such a derivation, because it leads only to a circular one, as we show for PAC learning. On the other hand, the two conditions are met for the probability of a sentence over a finite ideal corpus. A real machine can approximate a true probability only if an ideal machine can learn it precisely, that is, only in a domain that meets the two conditions. Modern AI works in such a domain, and we offer this as a clue to its success. Modern AI is hybrid as well, in two senses: First, it performs two kinds of tasks, namely probabilistic ones such as predicting the next word and deductive ones such as proving and coding. Second, it combines two parts of different kinds, a statistical proposer and a deductive verifier, for proving and coding. Our framework explains both senses of hybridity in one formal system.

Closest papers

Nearest neighbours by meaning across the whole index.

Agnostic Learning by Imitating

cs.LG cs.CCcs.DS ·2026-11-03 ·Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold, Konstantinos Stavropoulos +1 more
theory similarity 0.58
Abstract

Given a class of machine learning models and sample access to a data distribution with binary labels, which computational task is harder: training a discriminative model that distinguishes positive and negative labels as well as the best member of the class, or training a generative model whose outputs are indistinguishable from real data by all members of the class? We prove that these two fundamental tasks in computational learning theory are not just closely related, but actually equivalent to each other in complexity. One direction of this equivalence was previously known. Indeed, the powerful regularity lemma in complexity theory gives an efficient oracle reduction from the indistinguishability task (a.k.a. multiaccuracy) to the distinguishing task (a.k.a. agnostic learning) in the style of boosting algorithms. Our main contribution is an efficient oracle reduction in the other direction. Taking this idea further, we show that a multiaccuracy oracle is a remarkably powerful primitive, achieving not just agnostic learning but also a wide range of seemingly more demanding learning objectives via similarly efficient and direct constructions. Our results crucially use the power of making adaptive queries to the oracle, and stand in stark contrast to prior work, which showed that post-processing a single multiaccurate predictor is insufficient for even weak forms of learning. On a technical level, we draw a connection between our (offline) problem and a version of no-regret learning in the online setting, which allows us to use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle.

0.16

VALG: An Agentic System for ML Theory Research

cs.AI cs.LGmath.OCstat.ML ·2026-08-13 ·Dechen Zhang, Xuan Tang, Xinxiang Yin, Xingwu Chen, Jian Qian +1 more
theorycode/data similarity 0.58
Abstract

Machine learning theory studies learning procedures through mathematical setups in which the data model, training protocol, oracle access, loss, metric, and randomness define the phenomenon that a theorem is meant to explain. Solving an open problem therefore requires the problem formulation, theorem target, and proof mechanism to be developed in concert. Researchers formulate hypotheses, test them through preliminary theoretical or empirical analysis, and refine both assumptions and proofs. We investigate whether this process can be organized as an autonomous agentic workflow for ML theory research. We develop VALG, an agentic system that combines multi-level Verification, Adaptive formulation of Learning-theory problems, and Graph-structured proof development. Within each source-relative theorem branch, VALG maintains a fixed mathematical specification, checks the theorem-level composition of a typed proof-dependency graph, and constructs and reviews local proofs in dependency order. When a proof attempt fails, VALG identifies whether the obstruction lies in a derivation, the proof structure, or the theorem formulation and routes the next attempt accordingly. Formulation-level obstructions initiate an explicitly related variant or relaxation, preserving the mathematical relation between the resulting theorem and the source problem. We evaluate VALG on nine subproblems from five COLT 2026 open problems. Two runs produce internally finalized theorem candidates that match the scope of their source briefs; the remaining seven yield restricted-method results, special cases, or conditional theorems. These case studies show how VALG keeps source-scope matches, relaxations, conditional results, and blocked attempts mathematically distinct. VALG is open source at https://github.com/DechenZhang/VALG-ML-Theory-Agent.

0.60

Aligning Information Theory and Formal Verification: A Lean Formalization of Rate-Distortion Theory

cs.IT ·2026-10-14 ·Fubin Yan, Ruxuan Dong, Ruoxuan Shi, Duolei Wang, Kenneth W. Shum
code/data similarity 0.58
Abstract · Lean formalization and verification scripts: https://github.com/fubinyan/rate_distortion_lean4

Large language models have recently demonstrated an ability to generate substantial mathematical proofs and formalizations, including machine-checked arguments for major open problems and classical theorems. These developments highlight a growing workflow in which AI systems search for proofs while proof assistants certify their correctness. Within information theory, however, formalized libraries remain limited, and existing formalized theorems focus almost exclusively on Shannon's foundational lossless theorems. This paper presents the first Lean formalization of core components of rate-distortion theory, a central framework for lossy compression and modern machine-learning analysis. We identify the alignment challenges that arise when translating information-theoretic definitions, such as distortion measures, typicality and achievability, into a proof-assistant setting, and we develop a reusable library of definitions and lemmas faithful to textbook conventions. Our formalization provides a foundation for future AI-assisted proofs in information theory and enables subsequent mechanized developments to build on a coherent, verified infrastructure rather than generating long proofs from scratch.

0.43

Solomonoff Induction with Reflective Oracles

cs.CC ·2026-11-10 ·Damini Kusum
similarity 0.57
Abstract

We study predictive properties of a reflective variant of Solomonoff induction formulated using reflective oracles (Fallenstein et al. 2015, Wyeth et al. 2025). We show that the resulting optimal predictor succeeds against computable predictive strategies that specify only part of the data-generating process. The argument relies on the fact that hypotheses computable from the predictor's own conditional probabilities remain within the reflective hypothesis class. In particular, the predictor learns incomplete models specified by computable interval restrictions on next-bit probabilities. We also establish weighted forms of unbiasedness and calibration. Finally, we discuss whether an optimal predictor's conditional probabilities suffice to compute every hypothesis in the reflective class.

0.16

Language Is an Insufficient Substrate for Quantitative Reasoning, and Consequential Domains Need Large Quantitative Models

cs.AI cs.LG ·2026-09-10 ·Reuben Vandeventer, David Imrem, David J. Wild
position similarity 0.57
Abstract

The prevailing assumption in applied machine learning is that progress on consequential quantitative decisions such as pricing risk, allocating capital, triaging patients, or containing a network intrusion will follow from progress in large language models (LLMs). A language model is trained on a representation of the world that was produced by human description; description is a lossy encoding of the quantitative record, and the loss is irreversible: no downstream model, at any scale, can recover from a description what the description did not encode. We formalize this as a property of the representation on which a model is trained rather than of the model capacity, and we identify three further properties that consequential settings demand of a model and that a language substrate cannot supply by construction: reproducibility, lineage from every output back to the source records that produced. it, and calibrated uncertainty. We argue that these properties define a distinct model class, which we call the Large Quantitative Model (LQM).

0.22

A Unifying Perspective on Probabilities as Model Predictions

cs.CY stat.MLcs.LGmath.ST ·2026-09-09 ·Benedikt Höltgen
position similarity 0.56
Abstract

Although probabilistic statements are ubiquitous, foundational disagreements persist about their understanding, as exemplified by debates between Bayesians and frequentists; moreover, it is unclear when and why acting on them actually leads to desirable outcomes. Here, we argue that every probability is the output of a \emph{prediction method}, that is, it depends on both a particular way of constructing abstractions and a way of transforming them into predictions. Through this, we provide a unifying perspective on supposedly different kinds of probabilities and show that even supposedly objective ones are model-dependent. We demonstrate that when a finite calibration criterion is met, one can anticipate the distribution of utilities for a given policy and inform successful decision-making on finite sets of events. Based on the notion of prediction methods, inductive arguments, and the probability calculus, we explain the feasibility of the calibration criterion in many settings. Overall, we develop a coherent perspective on probabilities and their use, connecting key intuitions behind other interpretations along the way.

0.24

Why machines will still not rule the world

cs.AI ·2026-10-08 ·Jobst Landgrebe, Barry Smith
position similarity 0.56
Abstract

In our book Why machines will never rule the world [13, 14] we argue that arti- ficial general intelligence is mathematically impossible. This is because the human beings and the processes which exhibit intelligence are complex systems whose be- haviour cannot be captured by the kinds of models that we can generate with or without computers. Proponents of contemporary machine intelligence respond with two lines of argument: a theoretical one, grounded in the universal approximation theorems for neural networks and the Church-Turing-Deutsch principle; and an em- pirical one, grounded in rapidly rising scores on standardized benchmarks. In this communication we examine and reject both responses. First, we show serious issues in the physicalist counter-argument based on the Church-Turing-Deutsch principle. Second, we review recent evidence to the effect that prominent benchmarks are compromised by training-data contamination, flawed test construction, and strate- gic optimization. Our central argument remains: That models required to perform cognitive behaviour in open-ended, thermodynamically complex and non-ergodic environments are not and will not become achievable.

0.24

The Structure Gap: When More Data Cannot Replace Structured Reasoning

cs.LG cs.AI ·2026-10-27 ·Kheer Sagar Patel, Mojtaba Soltanalian
theory similarity 0.56
Abstract · 13 pages, 6 figures, 2 tables. Includes supplementary material and reproducibility code/data

A persistent belief in modern AI is that sufficiently large learners trained on sufficiently much data can make explicit domain knowledge optional. This paper examines a limitation of that belief. We define structure-encoded problems: tasks whose input-output map is determined, or sharply constrained, by known structure such as a solver, symmetry group, graph, physical law, measurement operator, grammar, combinatorial search space, or optimization objective. For such tasks, the central question is not expressivity--a dense neural network may contain the desired map--but finite-data identification, extrapolation, and certification. We introduce the structure gap: the finite-resource gap between a method that receives the governing structure and a learner that receives only examples. The strongest useful form of the claim is asymptotic rather than absolute: structure-agnostic learning may approach a structured solver as coverage grows, but every finite dataset can leave residual uncertainty that the structure resolves by construction. We prove this exactly for a Gaussian inverse problem: the known-operator Wiener solver attains Bayes risk, while the dense empirical learner in the correct linear class has persistent expected excess risk. We also prove a cell-coverage lower bound and an unobserved-orbit non-identifiability result. Controlled experiments in known-operator inversion, sparse recovery, and graph reachability with size extrapolation instantiate the mechanisms. When validated structure is available, it can constrain the hypothesis space before learning begins, leaving learning to address components the structure does not specify.

0.36