Imitation as Learning: On the Complexity Equivalence of Generative and Discriminative Models

In machine learning theory, discriminative models and generative models are often viewed as two distinct technical routes: the former focuses on distinguishing positive from negative labels, while the latter attempts to imitate the data distribution. But a new study reveals that from a computational complexity perspective, these two types of tasks are actually equivalent. This conclusion not only challenges traditional understanding of the relationship between the two model types, but also provides a new perspective on the power of multiaccuracy oracles.

Discriminative vs. Generative: Two Seemingly Different Tasks

Given a class of machine learning models and samples from a data distribution with binary labels, we can define two computational tasks. The first is the discriminative task, i.e., training a discriminative model whose ability to distinguish positive from negative labels is comparable to the best member of the model class—this is called agnostic learning. The second is the generative task, i.e., training a generative model whose output is hard to distinguish from real data for all members of the model class—this is called multiaccuracy.

Intuitively, the discriminative task requires the model to "find differences," while the generative task requires the model to "eliminate differences," and the two seem to point in opposite directions. Prior work has shown that the regularity lemma from complexity theory can yield an efficient oracle reduction that reduces the indistinguishability task (multiaccuracy) to the distinguishing task (agnostic learning), in a style similar to boosting algorithms. That is, if agnostic learning can be solved, then multiaccuracy can be solved.

Agnostic learning is a core concept in computational learning theory. Unlike PAC learning, it does not assume that data can be perfectly labeled by a target concept; instead, it allows for noise, and the goal is to find a hypothesis whose error rate is comparable to that of the best member of the hypothesis class (within at most a constant factor). This is closer to reality than traditional PAC learning, because real data often contain noise or label inconsistencies. Agnostic learning is generally considered computationally hard; even for simple hypothesis classes (such as halfspaces), no efficient algorithm is known under general distributions.

Multiaccuracy is a fairness/fidelity notion for generative models, requiring that generated samples have a prediction distribution that is hard to distinguish from the real data distribution under all members of the model class (such as all linear classifiers). Formally, for any hypothesis in the hypothesis class, the difference between the expected loss on generated samples and the expected loss on real data does not exceed a threshold. This is stronger than simple moment matching, because it requires the generator to capture the conditional distributional characteristics of the data under a rich hypothesis class. A multiaccuracy oracle is therefore an abstract computational device capable of generating samples that satisfy the multiaccuracy condition.

Reverse Reduction: From Imitation to Discrimination

The main contribution of this work is proving that the reduction in the opposite direction also holds: there exists an efficient oracle reduction that reduces agnostic learning to multiaccuracy. This means that if you have an oracle capable of training a multiaccuracy generative model, you can also use it to solve the agnostic learning problem. The two tasks are therefore equivalent in complexity.

The key to this conclusion lies in the power of adaptive queries. Prior work has shown that post-processing a single multiaccuracy predictor is not even sufficient to achieve a weak form of learning. But the new study shows that if one is allowed to query the multiaccuracy oracle adaptively, the situation is completely different: the oracle can not only achieve agnostic learning, but also, through a similar efficient direct construction, achieve a range of learning objectives that appear to demand more.

Technical Core: Connection to Online Learning

At the technical level, the researchers established a connection between the offline problem and the no-regret learning version in the online setting. Using this connection, they can use follow-the-leader type algorithms to modify the label distribution and aggregate the predictions of the multiaccuracy oracle. This cross-domain connection is the key to proving the validity of the reduction.

The significance of this result is that it shows the multiaccuracy oracle to be an exceptionally powerful primitive. In computational learning theory, the power of a primitive often determines which learning tasks are computationally feasible. The multiaccuracy oracle can not only accomplish the task by which it is defined, but also "leverage" additional capabilities through adaptive queries, which provides new ideas for designing learning algorithms.

No-regret learning is a framework in online learning in which the decision-maker observes the loss after choosing a strategy each round, and the goal is to make the cumulative loss grow sublinearly relative to the cumulative loss of the best fixed strategy in hindsight (i.e., the regret). Follow-the-leader is one classic algorithm in this framework, choosing each round the strategy with the smallest average loss so far. The connection between this online algorithm and the offline learning problem is that by treating label distribution modification as an online decision process, no-regret guarantees can be used to ensure the performance of the aggregated predictions, thereby constructing the reduction.

Impact on Learning Theory

From a theoretical perspective, this equivalence deepens our understanding of the relationship between discriminative learning and generative learning. In the past, generative models and discriminative models were often discussed in different application scenarios, whereas this study unifies them from a complexity perspective. It suggests that, under certain conditions, the ability to imitate the data distribution and the ability to distinguish data labels are computationally equivalent.

Of course, this conclusion is established within the framework of oracle reductions, and the efficiency of practical algorithms still depends on the implementation cost of the oracle. But as a theoretical result, it points the way for future research: exploring the potential of multiaccuracy oracles in other learning tasks, and the role of adaptive queries therein. For researchers interested in the theoretical foundations of machine learning, this work provides a starting point worth exploring in depth.

One-line Summary

A new study proves that discriminative agnostic learning and generative multiaccuracy are equivalent in computational complexity.

Paragraph Summary

This article introduces a machine learning theory study proving that the agnostic learning task in discriminative models and the multiaccuracy task in generative models are equivalent in computational complexity. It was previously known that the indistinguishability task can be reduced to the distinguishing task, and this new work achieves the reverse reduction through adaptive queries to a multiaccuracy oracle, thereby unifying the two types of tasks. The technical core lies in connecting the offline problem with online no-regret learning, using follow-the-leader algorithms to modify the label distribution and aggregate predictions. The result shows that the multiaccuracy oracle is an exceptionally powerful primitive capable of achieving a variety of learning objectives, and provides a new perspective on understanding the relationship between generative and discriminative models.