  Adversarial robustness is an increasingly critical property of classifiers in
applications. The design of robust algorithms relies on surrogate losses since
the optimization of the adversarial loss with most hypothesis sets is NP-hard.
But which surrogate losses should be used and when do they benefit from
theoretical guarantees? We present an extensive study of this question,
including a detailed analysis of the H-calibration and H-consistency of
adversarial surrogate losses. We show that, under some general assumptions,
convex loss functions, or the supremum-based convex losses often used in
applications, are not H-calibrated for important functions classes such as
generalized linear models or one-layer neural networks. We then give a
characterization of H-calibration and prove that some surrogate losses are
indeed H-calibrated for the adversarial loss, with these function classes.
Next, we show that H-calibration is not sufficient to guarantee consistency and
prove that, in the absence of any distributional assumption, no continuous
surrogate loss is consistent in the adversarial setting. This, in particular,
falsifies a claim made in a COLT 2020 publication. Next, we identify natural
conditions under which some surrogate losses that we describe in detail are
H-consistent for function classes such as generalized linear models and
one-layer neural networks. We also report a series of empirical results with
simulated data, which show that many H-calibrated surrogate losses are indeed
not H-consistent, and validate our theoretical assumptions.
