Agnostic learning and multiaccuracy proved equivalent: one multiaccuracy oracle, queried adaptively, reaches the best discriminator
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.