The Adversarial Inconsistency of Convex Surrogate Losses

131 concepts52 papers1 proposal

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:

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.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 63 papers
  2. Version 1 · 2026-10-04 · 106 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_adversarial_surrogate_inconsistency_38d58196,
  title = {adversarial surrogate inconsistency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-surrogate-inconsistency/rdr_38d58196b29346efa68541209af77228},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_adversarial_surrogate_inconsistency_38d58196_v2,
  title = {adversarial surrogate inconsistency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-surrogate-inconsistency/rdr_38d58196b29346efa68541209af77228/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake