Equivalence of training generative and discriminative models in complexity
Agnostic Learning by Imitating
Machine LearningComputational ComplexityData Structures and Algorithms
Summary
This paper studies two common tasks in machine learning: teaching a system to tell apart positive and negative examples, and teaching a system to create examples that look real. The authors show that these two tasks are essentially equally hard in terms of computational effort. They build on previous work that linked these tasks in one direction and complete the link in the other direction. Their findings also show that having a tool that can tell when a model is accurate in many ways is very powerful for different learning goals, especially when used with interactive queries.
What this means in practice
- •For machine learning engineers: Design training algorithms that switch efficiently between generative and discriminative objectives using oracle-based query methods.
- •For online system designers: Develop adaptive algorithms that aggregate predictions and update label distributions leveraging no-regret learning principles.
A theory result. No direct application yet.
Authors
Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold, Konstantinos Stavropoulos, Pranay Tankala
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.