Agnostic Learning
A learning framework that does not assume the existence of a zero-error target concept. It requires finding an approximately optimal classifier whose error is close to that of the best classifier in the hypothesis class under any data distribution.
Timeline (last 90 days)
From a computational complexity perspective, the two types of tasks for discriminative models and generative models (agnostic learning and multi-accuracy) are equivalent.
The regularity lemma can yield an efficient oracle reduction that reduces the indistinguishable task (multi-accuracy) to the distinguishing task (agnostic learning).
Agnostic learning does not assume the data can be perfectly labeled by the target concept but instead allows noise, with the goal of finding a hypothesis whose error rate is comparable to (at most a constant factor worse than) that of the best member of the hypothesis class.
Agnostic learning is generally considered computationally hard, and even for simple hypothesis classes (such as halfspaces) there is no known efficient algorithm under general distributions.
All Facts (4)
From a computational complexity perspective, the two types of tasks for discriminative models and generative models (agnostic learning and multi-accuracy) are equivalent.
50%UnverifiedThe regularity lemma can yield an efficient oracle reduction that reduces the indistinguishable task (multi-accuracy) to the distinguishing task (agnostic learning).
50%UnverifiedAgnostic learning does not assume the data can be perfectly labeled by the target concept but instead allows noise, with the goal of finding a hypothesis whose error rate is comparable to (at most a constant factor worse than) that of the best member of the hypothesis class.
50%UnverifiedAgnostic learning is generally considered computationally hard, and even for simple hypothesis classes (such as halfspaces) there is no known efficient algorithm under general distributions.
50%