In standard machine learning, we want to minimize a model's discrete 0-1 classification loss—the percentage of incorrect predictions. Because the 0-1 loss is discontinuous and NP-hard to optimize directly, we traditionally swap it for a smooth, convex surrogate loss like cross-entropy or hinge loss. In benign settings, this swap is justified by the concepts of calibration and consistency: minimizing the surrogate mathematically guarantees that we are also minimizing the true 0-1 error.
However, when an adversary can perturb the inputs, this foundational bridge collapses. As Pranjal Awasthi et al. note in On the Existence of The Adversarial Bayes Classifier, while an absolute best theoretical classifier (the adversarial Bayes optimal classifier) exists, the surrogate losses used in practical adversarial training often fail to align with it. This misalignment means that minimizing a popular training loss does not necessarily translate to minimizing true adversarial risk.
The Geometry of Failure: Why Convexity Invites Attacks
Why do standard convex surrogates fail under adversarial attack? The answer lies in how convexity treats the decision boundary.
Convex margin losses are designed to be smooth and forgiving. They do not heavily penalize predictions that sit close to the decision boundary, provided they are on the correct side. In clean classification, this creates a smooth optimization landscape that is easy for gradient descent to navigate. But in an adversarial setting, this smoothness becomes a fatal vulnerability.
Han Bao et al. demonstrated in Calibrated Surrogate Losses for Adversarially Robust Classification that standard convex surrogates are fundamentally uncalibrated with respect to the adversarially robust 0-1 loss. Convexity inherently encourages models to be "indecisive" or "fence-sit" near the decision boundary. Because an attacker only needs a tiny perturbation to push an input across the boundary, any model that tolerates low-margin, indecisive predictions is easily exploited.
To formalize this, Natalie Frank et al. in The Adversarial Consistency of Surrogate Risks for Binary Classification and Laurent Meunier et al. in Towards Consistency in Adversarial Classification proved a striking impossibility result: no convex surrogate loss can be adversarially consistent in binary classification.
The authors reduced this global problem to a simple pointwise condition: a surrogate loss is adversarially consistent if and only if the loss value exactly at the decision boundary is strictly greater than the average loss of making a confident positive or negative prediction. Convex functions, by definition, violate this condition. They cannot create the sharp penalty required to deter the model from sitting near the boundary, making them fundamentally incapable of guaranteeing adversarial robustness.
Clean Setting (Convex Surrogate) Adversarial Setting (Requires Non-Convexity)
Loss Loss
| | /\ <- Sharp penalty at
| \ | / \ the decision boundary
| \ | / \
________|___\________ Decision Boundary _______|___/______\___ Decision Boundary
Uncertainty Tolerated Fence-Sitting Heavily Penalized
The Robustness Gap in Practice
This theoretical misalignment explains a long-standing frustration in adversarial machine learning: the gap between minimizing training objectives and achieving true robustness.
Popular adversarial training frameworks (such as PGD or TRADES) rely on minimizing the worst-case loss within a defined perturbation radius. However, Pranjal Awasthi et al. showed in H-Consistency Bounds for Surrogate Loss Minimizers that these objectives lack consistency guarantees when restricted to realistic hypothesis sets (like neural networks). Without these guarantees, an optimizer can find a global minimum of the surrogate loss that still leaves the decision boundary highly vulnerable.
This failure cascades into more complex safety settings:
- Learning to Defer: When a model is allowed to hand off difficult decisions to a human expert, standard convex surrogates fail. VRUND SHAH et al. showed in Towards Calibrated Losses for Adversarial Robust Reject Option Classification that convexity prevents the model from making the sharp transitions required to move cleanly between a confident prediction and a rejection state near the boundary under attack.
- Flawed Attack Evaluations: The misalignment affects attackers as well. Alexander Robey et al. pointed out in Adversarial Training Should Be Cast as a Non-Zero-Sum Game that maximizing a smooth surrogate like cross-entropy often causes an attacker to merely reduce a model's prediction confidence rather than finding a true, label-flipping perturbation.
Restoring Consistency via Non-Convex Surrogates
If convexity is the root cause of adversarial inconsistency, the solution requires abandoning it in favor of non-convex alternatives that strictly penalize boundary indecision. Several mathematical frameworks have emerged to restore this alignment.
Ramp and Margin Losses
One way to bypass the limitations of convexity is to use bounded, non-convex functions. Pranjal Awasthi et al. demonstrated in Calibration and Consistency of Adversarial Surrogate Losses that specific non-convex surrogates—such as the $\rho$-margin ramp loss—can achieve adversarial consistency under "realizable" conditions (where the model architecture is expressive enough to achieve zero adversarial error on the dataset).
Shifted Odd Losses
To handle noisy datasets where classes overlap, Laurent Meunier et al. proposed a new category of non-convex functions called "shifted odd losses" in Towards Consistency in Adversarial Classification. These functions satisfy the necessary pointwise boundary conditions to guarantee adversarial calibration without requiring perfect data separability.
Principled Smooth Surrogates
To bridge the gap between theoretical consistency and optimization tractability, researchers have designed smooth, non-convex surrogates that remain easy to optimize via gradient descent. Pranjal Awasthi et al. introduced the Principled Smooth Adversarial Loss (PSAL) in Theoretically Grounded Loss Functions and Algorithms for Adversarial Robustness, providing formal consistency guarantees. Similarly, Anqi Mao and Mehryar Mohri developed a smooth adversarial "comp-sum" loss in Cross-Entropy Loss Functions: Theoretical Analysis and Applications that provides tight, non-asymptotic consistency bounds, ensuring that minimizing the surrogate directly minimizes the true adversarial 0-1 error.
Crucially, this does not mean convex losses are entirely useless in practice. In a single-author work, Natalie Frank proved in Adversarial Surrogate Risk Bounds for Binary Classification that while convex losses are not universally consistent, they can still provide reliable quantitative risk bounds when applied to realistic, continuous data distributions. This explains why convex surrogates, despite their theoretical flaws in worst-case scenarios, still show empirical utility in everyday robust optimization tasks.
Key Foundational Work
Does Distributionally Robust Supervised Learning Give Robust Classifiers? (2018) — contributed 2 concept elements to this direction.