Definition
Binary Supervised Learning Algorithm ( PAC-learning)
A binary supervised learning algorithm in the PAC-learning framework is an algorithm
that, given an accuracy parameter and a failure probability , has access to a sampling oracle . Each query to
returns a labelled sample where
is drawn according to an unknown distribution and is a hidden target concept. The algorithm outputs a hypothesis . The algorithm
is a PAC learner if, with probability at least over the randomly drawn training sample , the hypothesis has misclassification probability at most , i.e.,