Agnostic learning and multiaccuracy proved equivalent: one multiaccuracy oracle, queried adaptively, reaches the best discriminator
Synopsis
For a fixed feature distribution and an arbitrary model class, agnostic learning (training a discriminator that matches the best member of the class) and multiaccuracy (training a generator whose labels no observer in the class can distinguish from real ones) are proved equivalent in statistical and computational complexity. Only the direction from agnostic learning to multiaccuracy was known; the converse was blocked because a single multiaccurate predictor can fail to beat random guessing even after calibration. The new reduction repeatedly queries a multiaccuracy oracle, splits by prediction level sets and averages the iterates, yielding a predictor that is both multiaccurate and calibrated and thus performs agnostic learning.
Interpretation
Agnostic learning and multiaccuracy are proved equivalent in complexity, not merely closely related. Previously only the direction from agnostic learning to multiaccuracy was known, via the regularity lemma of complexity theory, which reduces agnostic learning to multiaccuracy in the style of boosting algorithms. The equivalence states that for every feature distribution and model class, an efficient algorithm for either task can be transformed into one for the other by an oracle reduction with polynomial overhead.
The converse reduction works by repeatedly querying the multiaccuracy oracle and combining its answers across rounds. A single multiaccurate predictor is insufficient even for weak agnostic learning under any post-processing, because multiaccurate but anti-calibrated predictors exist whose true label stays nearly uniform given the prediction. Each round changes the label distribution while keeping the feature marginal fixed, conditions multiaccuracy on level sets of the prediction, and finally takes a weighted average of the iterates; the reduction can also be implemented in the statistical query framework.
Perspective
The result covers a fixed and known feature marginal, binary labels and an arbitrary given model class, and is stated as an oracle reduction with polynomial overhead; the reduction can also be implemented in the statistical query framework, so statistical query lower bounds for agnostic learning apply to multiaccurate prediction as well.
The lower bounds concern the number of calls to a conditional multiaccuracy oracle rather than to the underlying multiaccuracy oracle, which is left as a direction for future work; some hard instances are specific to the particular reduction algorithm while others are not.