In machine learning, two fundamental goals are: training a model to classify data as accurately as the best in a given set of models, and training a model to generate labels that look real to all those models. These goals seem different, and it was unclear which is computationally harder.
The authors prove they are equivalent in complexity. They provide an efficient algorithm that uses a multiaccuracy oracle (which checks if generated labels are indistinguishable) to achieve agnostic learning (optimal classification). This complements the known reduction in the opposite direction, establishing full equivalence.
This unifies two important learning paradigms, showing that progress on one directly benefits the other. It also reveals that ensuring indistinguishability is a powerful primitive that can accomplish a wide range of learning tasks.