  In many learning theory problems, a central role is played by a hypothesis
class: we might assume that the data is labeled according to a hypothesis in
the class (usually referred to as the realizable setting), or we might evaluate
the learned model by comparing it with the best hypothesis in the class (the
agnostic setting).
  Taking a step beyond these classic setups that involve only a single
hypothesis class, we introduce comparative learning as a combination of the
realizable and agnostic settings in PAC learning: given two binary hypothesis
classes $S$ and $B$, we assume that the data is labeled according to a
hypothesis in the source class $S$ and require the learned model to achieve an
accuracy comparable to the best hypothesis in the benchmark class $B$. Even
when both $S$ and $B$ have infinite VC dimensions, comparative learning can
still have a small sample complexity. We show that the sample complexity of
comparative learning is characterized by the mutual VC dimension
$\mathsf{VC}(S,B)$ which we define to be the maximum size of a subset shattered
by both $S$ and $B$. We also show a similar result in the online setting, where
we give a regret characterization in terms of the mutual Littlestone dimension
$\mathsf{Ldim}(S,B)$. These results also hold for partial hypotheses.
  We additionally show that the insights necessary to characterize the sample
complexity of comparative learning can be applied to characterize the sample
complexity of realizable multiaccuracy and multicalibration using the mutual
fat-shattering dimension, an analogue of the mutual VC dimension for
real-valued hypotheses. This not only solves an open problem proposed by Hu,
Peale, Reingold (2022), but also leads to independently interesting results
extending classic ones about regression, boosting, and covering number to our
two-hypothesis-class setting.
