Agnostic Learning by Imitating: Proving Equivalence Between Discriminative and Generative Learning

Paper Overview

• Field: Machine Learning / Computational Learning Theory
• Authors: Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold, Konstantinos Stavropoulos, Pranay Tankala
• Published: 2026-11-03
• arXiv: 2611.05346

Summary

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? The authors 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: 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. The paper's main contribution is an efficient oracle reduction in the other direction.

Key Contributions

• Equivalence result: Agnostic learning and multiaccuracy-based indistinguishability are computationally equivalent tasks.
• Multiaccuracy as a powerful primitive: A multiaccuracy oracle achieves not just agnostic learning but also a wide range of seemingly more demanding learning objectives via similarly efficient and direct constructions.
• Adaptive queries matter: The results crucially use the power of making adaptive queries to the oracle, standing in stark contrast to prior work showing that post-processing a single multiaccurate predictor is insufficient for even weak forms of learning.

Technical Approach

On a technical level, the authors connect the (offline) problem to a version of no-regret learning in the online setting. This allows them to use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle.

Original 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.

*Auto-collected on 2026-11-05.*