Two ways of defining successful machine learning have equivalent statistical and computational complexity under specified oracle assumptions, according to Agnostic Learning by Imitating, an arXiv preprint dated November 3, 2026. Sílvia Casacuberta and colleagues present a theoretical reduction connecting agnostic learning and multiaccuracy. Peer review has not been verified.
Agnostic learning seeks a predictor whose expected absolute error is within a tolerance ε of the best function in a chosen comparison class C, without assuming that class contains a perfect predictor. Multiaccuracy instead requires prediction errors to have absolute correlation at most ε with every function in C. Its generative interpretation involves producing synthetic binary labels for existing features that appear consistent with real labels to the restricted observers represented by C.
The study uses mathematical constructions rather than experiments. It assumes independent labeled examples, binary labels and a fixed, known feature distribution, while allowing arbitrary conditional label distributions. An oracle is a subroutine assumed to solve a specified task with the required guarantees; the reduction explains how access to one such solver can support another task.
The main theorem gives an agnostic learner with excess expected absolute error at most ε using O(ε^-5) calls to a multiaccuracy oracle with tolerance Ω(ε²). The previously known reverse reduction uses O(ε^-2) calls to an agnostic-learning oracle with tolerance Ω(ε). Together, these establish equivalence with polynomial overhead for every feature distribution and model class C. These asymptotic call bounds are not measured training times.
The new direction depends on adaptive queries: later requests depend on earlier predictions. The construction modifies label distributions while preserving the feature distribution, builds conditional multiaccuracy guarantees and combines predictions using ideas from online no-regret learning. This matters because earlier work showed that merely post-processing a single multiaccurate predictor can fail to outperform random guessing.
The authors also report extensions to swap multicalibration and swap omniprediction, stronger guarantees concerning calibration and performance across loss functions. They state that the reduction works in the statistical-query framework, allowing corresponding lower bounds for agnostic learning to carry over to multiaccuracy.
The result does not supply an efficient multiaccuracy oracle for every model class or establish practical speed, benchmark gains or real-world reliability. Its synthetic-label setting does not establish general-purpose data generation. The supplied passage reports no empirical evaluation and ends during the algorithm overview, with rendering artifacts; complete proofs, detailed sample and runtime bounds, and formal extension theorems were unavailable for assessment.
Cover illustration generated with AI; conceptual, not research evidence.