In standard machine learning, we rarely optimize for what we actually care about. We want to minimize the 0/1 loss (the percentage of misclassifications), but because that function is discrete and flat, we use "surrogates" like cross-entropy or hinge loss that are easy to optimize with gradients. In classical settings, this works beautifully: as we minimize the surrogate, we are guaranteed to minimize the 0/1 loss. This property is known as statistical consistency.
However, in adversarial machine learning—where an attacker can perturb an input $x$ within a radius $\epsilon$—this bridge between the surrogate and the target often collapses. Recent theoretical work has revealed that the convex loss functions we rely on are fundamentally ill-suited for adversarial robustness, leading to a search for new "adversarially consistent" objectives.
The Adversarial Bayes Classifier
To understand why surrogates fail, we first need to know what the "perfect" robust model looks like. In standard learning, this is the Bayes Classifier. In the robust setting, Pranjal Awasthi, Natalie Frank, and Mehryar Mohri proved the existence of the Adversarial Bayes Classifier.
This optimal classifier has a unique geometric property: it must be "locally constant." If a point is assigned a label, every point within its $\epsilon$-neighborhood must also be assigned that same label. If the classifier shifts its decision even slightly within that radius, an adversary can exploit that "indecision" to flip the prediction.
Why Convexity Fails Robustness
The central conflict in adversarial training is that convexity encourages indecision. Standard convex surrogates, like the hinge loss used in SVMs, do not heavily penalize points that are close to the decision boundary; they allow for a "margin" of uncertainty.
Han Bao and Natalie Frank have shown that these losses are often uncalibrated for adversarial risk. In The Adversarial Consistency of Surrogate Risks for Binary Classification, the authors identify a specific mathematical trap: "midpoint convexity." If a loss function is convex, the cost of being "half-right" on two different points is often lower than the cost of being "all-right" on one and "all-wrong" on the other. In an adversarial setting, this allows an attacker to push inputs into these low-penalty "uncertainty zones," flipping the label with minimal effort.
Furthermore, Natalie Frank proved that for a convex surrogate to be consistent, the Adversarial Bayes Classifier must be unique for that data distribution (Adversarial Consistency and the Uniqueness of the Adversarial Bayes Classifier). If there are multiple ways to draw an "optimal" robust boundary, a convex solver might pick one that is statistically valid but practically vulnerable.
H-Consistency and Finite Capacity
Traditional consistency theory assumes we have "infinite" model capacity (the ability to represent any function). In reality, we work with restricted hypothesis sets $\mathcal{H}$, like linear models or neural networks.
Yutao Zhong, Anqi Mao, and Pranjal Awasthi introduced H-Consistency Bounds to address this. They found that for many common surrogates, the error bounds in adversarial settings are "vacuous"—meaning the math provides no guarantee that minimizing the surrogate will actually reduce the adversarial 0/1 error for a specific architecture. This explains why adversarial training can feel unstable: the optimizer is successfully reducing the surrogate loss, but because the loss isn't calibrated to the hypothesis set, the actual robustness isn't improving.
Designing Consistent Robust Losses
If standard convex losses fail, what should we use instead? The research points toward non-convex surrogates that more aggressively penalize proximity to the decision boundary.
- The $\rho$-margin ramp loss: Unlike the hinge loss, which grows linearly, the ramp loss "flattens out," forcing the model to focus on points that are actually within the danger zone of the adversary. Awasthi et al. showed this loss can achieve calibration and consistency where convex losses cannot.
- Smooth Adversarial Comp-Sum Losses: Anqi Mao and Mehryar Mohri developed ADV-COMP-SUM, which uses a smooth upper bound of the margin loss. This provides a tractable objective for gradient descent while maintaining a rigorous theoretical link to the true adversarial 0/1 loss.
- Adaptive Bandwidth Surrogates: For non-parametric settings, Elvis Dohmatob demonstrated that using a non-convex smoothed surrogate with an adaptive bandwidth allows robust estimators to reach the same optimal convergence rates as standard, non-robust models.
By shifting from "convenient" convex surrogates to "consistent" robust surrogates, the field is moving away from heuristic "cat-and-mouse" defenses toward models with provable, predictable resilience.