  Most work in the area of learning theory has focused on designing effective
Probably Approximately Correct (PAC) learners. Recently, other models of
learning such as transductive error have seen more scrutiny. We move toward
showing that these problems are equivalent by reducing agnostic learning with a
PAC guarantee to agnostic learning with a transductive guarantee by adding a
small number of samples to the dataset. We first rederive the result of
Aden-Ali et al. arXiv:2304.09167 reducing PAC learning to transductive learning
in the realizable setting using simpler techniques and at more generality as
background for our main positive result. Our agnostic transductive to PAC
conversion technique extends the aforementioned argument to the agnostic case,
showing that an agnostic transductive learner can be efficiently converted to
an agnostic PAC learner. Finally, we characterize the performance of the
agnostic one inclusion graph algorithm of Asilis et al. arXiv:2309.13692 for
binary classification, and show that plugging it into our reduction leads to an
agnostic PAC learner that is essentially optimal. Our results imply that
transductive and PAC learning are essentially equivalent for supervised
learning with pseudometric losses in the realizable setting, and for binary
classification in the agnostic setting. We conjecture this is true more
generally for the agnostic setting.
